Articles

Improved Preimage Attack on 3-Pass HAVAL

Expand
  • (Department of Computer Science and Engineering,
    Shanghai Jiaotong University, Shanghai 200240, China)    

Received date: 2011-06-14

  Online published: 2012-01-12

Abstract

 HAVAL is a hash function proposed by
 Zheng et al. in 1992, including 3-, 4- and 5-pass versions.
We improve pseudo-preimage and preimage attacks on 3-pass HAVAL at
the complexity of 2^  172   and 2^  209.6  , respectively, as
compared to the previous best known results: 2^  192   and 2^  225 
by Sasaki et al. in 2008. We extend the skip interval for
partial-patching and apply the initial structure technique to find
the better message chunks, and combine the
indirect-partial-matching, partial-fixing and multi-neutral-word
partial-fixing techniques to improve the attacks based on the
meet-in-the-middle method. These are the best pseudo-preimage and
preimage attacks on 3-pass HAVAL.

Cite this article

ZHONG Jin-min (钟锦敏), LAI Xue-jia (来学嘉), DUAN Ming (段 明) . Improved Preimage Attack on 3-Pass HAVAL[J]. Journal of Shanghai Jiaotong University(Science), 2011 , 16(6) : 713 -721 . DOI: 10.1007/s12204-011-1215-3

References

1  Wang X Y, Lai X J, Feng D G, et al. Cryptanalysis of the hash

functions MD4 and RIPEMD [C]//  Advances in Cryptology,

EUROCRYPT 2005, LNCS 3494. Berlin: Springer-Verlag, 2005: 1-18.

    2  Wang X Y, Yu H B. How to break MD5 and other hash functions

[C]//  Advances in Cryptology, EUROCRYPT 2005, LNCS

3494. Berlin: Springer-Verlag, 2005: 19-35.

    3  Wang X Y, Yu H B, Yin Y Q L. Efficient collision search

attacks on SHA-0 [C]//  Advances in Cryptology, CRYPTO 2005,

LNCS 3621. Berlin: Springer-Verlag, 2005: 1-16.

    4  Wang X Y, Yin Y Q, Yu H B.   Finding collisions in the full

SHA-1 [C]//  Advances in Cryptology, CRYPTO 2005, LNCS 3621.

Berlin: Springer-Verlag, 2005: 17-36.

    5  Zheng Y L, Pieprzyk J, Seberry J.   HAVAL---A one-way hashing

algorithm with variable length of output [C]//  Advances in

Cryptology, ASIACRYPT 1992, LNCS 718. Berlin: Springer-Verlag,

1993: 83-104.

    6  Wang X Y, Feng D G, Yu X Y.   An attack on hash function

HAVAL-128 [J].  Science in China Series F: Information

Sciences, 2005, 48  (5): 545-556.

    7  Van ROMPAY B, Biryukov A, Preneel B,   et al. Cryptanalysis of

3-pass HAVAL [C]//  Advances in Cryptology, ASIACRYPT 2003, LNCS

2894. Berlin: Springer-Verlag, 2003: 228-245.

    8  Yu H B, Wang X Y, Yun A, et al. Cryptanalysis of the full

HAVAL with 4 and 5 passes [C]//  Fast Software Encryption 2006,

LNCS 4047. Berlin: Springer-Verlag, 2006: 89-110.

    9  Suzuki K, Kurosawa K.   How to find many collisions of 3-pass

haval [C]//  Second International Workshop on Security, IWSEC

2007, LNCS 4752. Berlin: Springer-Verlag, 2007: 428-443.

    10  Yu H B, Wang X Y.   Multi-collision attack on the compression

functions of MD4 and 3-pass HAVAL [C]//  Information Security

and Cryptology, ICISC 2007, LNCS 4817. Berlin: Springer-Verlag,

2007: 206-226.

    11  Lee E, Chang D, Kim J,   et al. Second preimage attack on 3-pass

HAVAL and partial key-recovery attacks on HMAC/NMAC-3-pass HAVAL

[C]//  Fast Software Encryption 2008, LNCS 5086. Berlin:

Springer-Verlag, 2008: 189-206.

    12  Yu H B, Wang G L, Zhang G Y, et al. The second preimage attack

on MD4 [C]//  Cryptology and Network Security (CANS) 2005, LNCS

3810. Berlin: Springer-Verlag, 2005: 1-12.

    13  Wang G L, Wang S H.   Second preimage attack on 5-pass HAVAL and

partial key-recovery attack on HMAC/NMAC-5-pass HAVAL [C]//

Progress in Cryptology, AFRICACRYPT 2009, LNCS 5580. Berlin:

Springer-Verlag, 2009: 1-13.

    14  Aoki K, Guo J, Matusiewicz K, et al. Preimages for

step-reduced SHA-2 [C]//  Advances in Cryptology, ASIACRYPT

2009, LNCS 5912. Berlin: Springer-Verlag, 2009: 578-597.

    15  Sasaki Y, Aoki K.   Finding preimages in full MD5 faster than

exhaustive search [C]//  Advances in Cryptology, EUROCRYPT 2009,

LNCS 5479. Berlin: Springer-Verlag, 2009: 134-152.

    16  Leurent G.   MD4 is not one-way [C]//  Fast Software

Encryption 2008, LNCS 5086. Berlin: Springer-Verlag, 2008: 412-428.

    17  Sasaki Y.   Meet-in-the-middle attacks using output truncation

in 3-pass HAVAL [C]//  Information Security (ISC) 2009, LNCS

5735. Berlin: Springer-Verlag, 2009: 79-94.

    18  Aumasson J P, Meier W, Mendel F.   Preimage attacks on 3-pass

HAVAL and step-reduced MD5 [C]//  Selected Areas in Cryptography

2008, LNCS 5381. Berlin: Springer-Verlag, 2009: 120-135.

    19  Sasaki Y, Aoki K.   Preimage attacks on 3, 4, and 5-pass HAVAL

[C]//  Advances in Cryptology,  ASIACRYPT    2008,

LNCS 5350. Berlin: Springer-Verlag, 2008: 253-271.

    20  Isobe T, Shibutani K.   Preimage attacks on reduced tiger and

SHA-2 [C]//  Fast Software Encryption 2009, LNCS 5665. Berlin:

Springer-Verlag, 2009: 139-155.

    21  Aoki K, Sasaki Y.   Meet-in-the-middle preimage attacks against

reduced SHA-0 and SHA-1 [C]//  Advances in Cryptology, CRYPTO

2009, LNCS 5677. Berlin: Springer-Verlag, 2009: 70-89.

    22  Guo J, Ling S, Rechberger C,   et al. Advanced

meet-in-the-middle preimage attacks: First results on full tiger,

and improved results on MD4 and   SHA-2   [C]//  Advances in

Cryptology, ASIACRYPT 2010, LNCS 6477. Berlin: Springer-Verlag,

2010: 56-75.

    23  Zhong J M, Lai X J.   Improved preimage attack on one-block md4

[EB/OL]. (2011-07-01). http://eprint.iacr.org/2010/583.pdf.

    24  Aoki K, Sasaki Y.   Preimage attacks on one-block MD4, 63-step

MD5 and more [C]//  Selected Areas in Cryptography 2008, LNCS

5381. Berlin: Springer-Verlag, 2009: 103-119.

    25  Lai X J, Massey J L.   Hash functions based on block ciphers

[C]//  Advances in Cryptology, EUROCRYPT 1992, LNCS 658.

Berlin: Springer-Verlag, 1993: 55-70.
Options
Outlines

/