Paper 2006/161

Cryptanalysis of 4-Pass HAVAL

Zhangyi Wang, Huanguo Zhang, Zhongping Qin, and Qingshu Meng

Abstract

HAVAL is a cryptographic hash function proposed by Zheng et al. Rompay et al and Wang et al found collisions of full 3-Pass HAVAL. In this paper, we study the security of 4-Pass HAVAL. We find collisions of full versions of 4-Pass HAVAL. The attack is similar to the two-block attack of MD5 proposed by Wang et al. The computational complexity of the attack is about 2^30-2^32 for the first block and 2^27-2^29 for the second block. We use this attack to find 256bit collisions of 4-Pass HAVAL in 3-4 hour on a common PC.

Note: An attack on 4 and 5 passes of Haval was presented at FSE 2006 (FSE 2006 : "Cryptanalysis of the Full HAVAL with 4 and 5 Passes" by H.Yu, X.Wang, A.Yun, and S.Park) , which provides a stronger attack on HAVAL than this paper. We were ill-informed about the result already obtained on FSE2006 as well as the specific method of this research when independently carrying on our research. In fact until now we still can't retrieve the corresponding abstract or the full text document from the FSE2006 homepage and the LNCS database of Springer Press. Though acknowledging that the publication of the result on FSE2006 is prior to ours and the specific attack result is also superior to ours, we are still willing to share our method in this paper with everyone on eprint. My email address: wzy@whu.edu.cn