Difference between revisions of "HAVAL"

From The ECRYPT Hash Function Website
 
(→‎Second Preimage Attacks)
 
(9 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
== Specification ==
 
== Specification ==
  
−
<!--
+
 
−
* digest size: 160 bits
+
* digest size: 128,160,192,224,256 bits
 
* max. message length: < 2<sup>64</sup> bits
 
* max. message length: < 2<sup>64</sup> bits
−
* compression function: 512-bit message block, 160-bit chaining variable
+
* compression function: 1024-bit message block, 3/4/5 passes with 256-bit chaining variable
−
* Specification:  
+
* 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 ==
 
== Cryptanalysis ==
Line 21: Line 37:
  
 
=== Collision Attacks ===
 
=== 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<sup>43</sup> computations
 +
and the other with 2<sup>36</sup> computations. In addition, we show that collisions for 5-pass HAVAL
 +
can be found with about 2<sup>123</sup> 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 ===
 
=== 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>
  
 
----
 
----

Latest revision as of 11:30, 10 November 2008

1 Specification

  • digest size: 128,160,192,224,256 bits
  • max. message length: < 264 bits
  • compression function: 1024-bit message block, 3/4/5 passes with 256-bit chaining variable
  • Specification: http://labs.calyptix.com/haval.php

Yuliang Zheng, Josef Pieprzyk, Jennifer Seberry - HAVAL - A One-Way Hashing Algorithm with Variable Length of Output

ASIACRYPT 718:83-104,1993
http://dx.doi.org/10.1007/3-540-57220-1
Bibtex
Author : Yuliang Zheng, Josef Pieprzyk, Jennifer Seberry
Title : HAVAL - A One-Way Hashing Algorithm with Variable Length of Output
In : ASIACRYPT -
Address :
Date : 1993

2 Cryptanalysis

2.1 Best Known Results

2.2 Generic Attacks

2.3 Collision Attacks

Hongbo Yu, Xiaoyun Wang - Multi-collision Attack on the Compression Functions of MD4 and 3-Pass HAVAL

ICISC 4817:206-226,2007
http://dx.doi.org/10.1007/978-3-540-76788-6_17
Bibtex
Author : Hongbo Yu, Xiaoyun Wang
Title : Multi-collision Attack on the Compression Functions of MD4 and 3-Pass HAVAL
In : ICISC -
Address :
Date : 2007

Hongbo Yu, Xiaoyun Wang, Aaram Yun, Sangwoo Park - Cryptanalysis of the Full HAVAL with 4 and 5 Passes

FSE 4047:89-110,2006
http://dx.doi.org/10.1007/11799313_7
Bibtex
Author : Hongbo Yu, Xiaoyun Wang, Aaram Yun, Sangwoo Park
Title : Cryptanalysis of the Full HAVAL with 4 and 5 Passes
In : FSE -
Address :
Date : 2006

Bart Van Rompay, Alex Biryukov, Bart Preneel, Joos Vandewalle - Cryptanalysis of 3-Pass HAVAL

ASIACRYPT 2894:228-245,2003
http://springerlink.metapress.com/openurl.asp?genre=article{\&}issn=0302-9743{\&}volume=2894{\&}spage=228
Bibtex
Author : Bart Van Rompay, Alex Biryukov, Bart Preneel, Joos Vandewalle
Title : Cryptanalysis of 3-Pass HAVAL
In : ASIACRYPT -
Address :
Date : 2003

2.4 Second Preimage Attacks

Eunjin Lee, Donghoon Chang, Jongsung Kim, Jaechul Sung, Seokhie Hong - Second Preimage Attack on 3-Pass HAVAL and Partial Key-Recovery Attacks on HMAC/NMAC-3-Pass HAVAL

FSE 5086:189-206,2008
http://dx.doi.org/10.1007/978-3-540-71039-4_12
Bibtex
Author : Eunjin Lee, Donghoon Chang, Jongsung Kim, Jaechul Sung, Seokhie Hong
Title : Second Preimage Attack on 3-Pass HAVAL and Partial Key-Recovery Attacks on HMAC/NMAC-3-Pass HAVAL
In : FSE -
Address :
Date : 2008

2.5 Preimage Attacks

2.6 Others

Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=HAVAL&oldid=2243"