## Cryptology ePrint Archive: Report 2007/079

How To Find Many Collisions of 3-Pass HAVAL

Kazuhiro Suzuki and Kaoru Kurosawa

Abstract: The hash function HAVAL is an Australian extension of well known Merkle-Damg\r{a}rd hash functions such as MD4 and MD5. It has three variants, $3$-, $4$- and $5$-pass HAVAL. On $3$-pass HAVAL, the best known attack finds a collision pair with $2^{7}$ computations of the compression function. To find $k$ collision pairs, it requires $2^{7}k$ computations. In this paper, we present a better collision attack on $3$-pass HAVAL, which can find $k$ collision pairs with only $2k+33$ computations. Further, our message differential is different from the previous ones. (It is important to find collisions for different message differentials.)

Category / Keywords: