How To Find Many Collisions of 3-Pass HAVAL

Abstract. The hash function HAVAL is an Australian extension of well known Merkle-Damg˚ard 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.) Key words: hash function, HAVAL, collision, differential attack