View source for HAVAL

From The ECRYPT Hash Function Website

← HAVAL

You do not have permission to edit this page, for the following reason:

---

You can view and copy the source of this page.

== Specification == * digest size: 128,160,192,224,256 bits * max. message length: < 2⁶⁴ bits * compression function: 1024-bit message block, 3/4/5 passes with 256-bit chaining variable * Specification: http://labs.calyptix.com/haval.php <bibtex> @inproceedings{asiacryptZhengPS92, author = {Yuliang Zheng and Josef Pieprzyk and Jennifer Seberry}, title = {HAVAL - A One-Way Hashing Algorithm with Variable Length of Output}, pages = {83-104}, editor = {Jennifer Seberry and Yuliang Zheng}, booktitle = {ASIACRYPT}, publisher = {Springer}, series = {LNCS}, volume = {718}, year = {1993}, isbn = {3-540-57220-1}, url = {http://dx.doi.org/10.1007/3-540-57220-1}, abstract = {A one-way hashing algorithm is a deterministic algorithm that compresses an arbitrary long message into a value of specified length. The output value represents the fingerprint or digest of the message. A cryptographically useful property of a one-way hashing algorithm is that it is infeasible to find two distinct messages that have the same fingerprint. This paper proposes a one-way hashing algorithm called HAVAL. HAVAL compresses a message of arbitrary length into a fingerprint of 128, 160, 192, 224 or 256 bits. In addition, HAVAL has a parameter that controls the number of passes a message block (of 1024 bits) is processed. A message block can be processed in 3, 4 or 5 passes. By combining output length with pass, we can provide fifteen (15) choices for practical applications where different levels of security are required. The algorithm is very efficient and particularly suited for 32-bit computers which predominate the current workstation market. Experiments show that HAVAL is 60% faster than MD5 when 3 passes are required, 15% faster than MD5 when 4 passes are required, and as fast as MD5 when full 5 passes are required. It is conjectured that finding two collision messages requires the order of 2^{n/2} operations, where n is the number of bits in a fingerprint.}, } </bibtex> == Cryptanalysis == === Best Known Results === ---- === Generic Attacks === * [[GenericAttacksMerkleDamgaard| Generic Attacks on the Merkle-Damgaard Construction ]] ---- === Collision Attacks === <bibtex> @inproceedings{iciscYuW07, author = {Hongbo Yu and Xiaoyun Wang}, title = {Multi-collision Attack on the Compression Functions of MD4 and 3-Pass HAVAL}, booktitle = {ICISC}, year = {2007}, pages = {206-226}, url = {http://dx.doi.org/10.1007/978-3-540-76788-6_17}, editor = {Kil-Hyun Nam and Gwangsoo Rhee}, publisher = {Springer}, series = {LNCS}, volume = {4817}, isbn = {978-3-540-76787-9}, abstract = {In this paper, we present a new type of multi-collision attack on the compression functions of both MD4 and 3-Pass HAVAL. Different from Joux’s multi-collision attack, our method focuses on the multi-collision of the compression function. For MD4, we utilize two different feasible collision differential paths to find a 4-collision with about 221 MD4 computations. For 3-Pass HAVAL, we can find a 4-collision with complexity about 2^{30} and a 8-near-collision with complexity 2^9.}, } </bibtex> <bibtex> @inproceedings{fseYuWYP06, author = {Hongbo Yu and Xiaoyun Wang and Aaram Yun and Sangwoo Park}, title = {Cryptanalysis of the Full HAVAL with 4 and 5 Passes}, pages = {89-110}, booktitle = {FSE}, publisher = {Springer}, series = {LNCS}, volume = {4047}, year = {2006}, isbn = {3-540-36597-4}, url = {http://dx.doi.org/10.1007/11799313_7}, abstract = {HAVAL is a cryptographic hash function with variable digest size proposed by Zheng, Pieprzyk and Seberry in 1992. It has three variants, 3-, 4-, and 5-pass HAVAL. Previous results on HAVAL suggested only practical collision attacks for 3-pass HAVAL. In this paper, we present collision attacks for 4 and 5 pass HAVAL. For 4-pass HAVAL, we describe two practical attacks for finding 2-block collisions, one with 2⁴³ computations and the other with 2³⁶ computations. In addition, we show that collisions for 5-pass HAVAL can be found with about 2¹²³ computations, which is the first attack more efficient than the birthday attack. Keywords: Hash function, collision, differential path, message modification. } } </bibtex> <bibtex> @inproceedings{asiacryptRompayBPV03, author = {Bart Van Rompay and Alex Biryukov and Bart Preneel and Joos Vandewalle}, title = {Cryptanalysis of 3-Pass HAVAL}, pages = {228-245}, url = {http://springerlink.metapress.com/openurl.asp?genre=article{\&}issn=0302-9743{\&}volume=2894{\&}spage=228}, editor = {Chi-Sung Laih}, booktitle = {ASIACRYPT}, publisher = {Springer}, series = {LNCS}, volume = {2894}, year = {2003}, isbn = {3-540-20592-6}, abstract = {HAVAL is a cryptographic hash function proposed in 1992 by Zheng, Pieprzyk and Seberry. Its has a structure that is quite similar to other well-known hash functions such as MD4 and MD5. The specification of HAVAL includes a security parameter: the number of passes (that is, the number of times that a particular word of the message is used in the computation) can be chosen equal to 3, 4 or 5. In this paper we describe a practical attack that finds collisions for the 3-pass version of HAVAL. This means that it is possible to generate pairs of messages hashing to the same value. The computational complexity of the attack corresponds to about $2^29$ computations of the compression function of 3-pass HAVAL; the required amount of memory is negligible.}, } </bibtex> ---- === Second Preimage Attacks === <bibtex> @inproceedings{fseLeeCKSH08, author = {Eunjin Lee and Donghoon Chang and Jongsung Kim and Jaechul Sung and Seokhie Hong}, title = {Second Preimage Attack on 3-Pass HAVAL and Partial Key-Recovery Attacks on HMAC/NMAC-3-Pass HAVAL}, booktitle = {FSE}, year = {2008}, pages = {189-206}, abstract = {In 1992, Zheng, Pieprzyk and Seberry proposed a one-way hashing algorithm called HAVAL, which compresses a message of arbitrary length into a digest of 128, 160, 192, 224 or 256 bits. It operates in so called passes where each pass contains 32 steps. The number of passes can be chosen equal to 3, 4 or 5. In this paper, we devise a new differential path of 3-pass HAVAL with probability 2^-114, which allows us to design a second preimage attack on 3-pass HAVAL and partial key recovery attacks on HMAC/NMAC-3-pass HAVAL. Our partial key-recovery attack works with 2^122 oracle queries, 5·2^32 memory bytes and 2^96 3-pass HAVAL computations. }, url = {http://dx.doi.org/10.1007/978-3-540-71039-4_12}, editor = {Kaisa Nyberg}, publisher = {Springer}, series = {LNCS}, volume = {5086}, isbn = {978-3-540-71038-7}, } </bibtex> ---- === Preimage Attacks === ---- === Others ===

Return to HAVAL.