An Attack For Hash Function HAVAL-160 With 4 Passes

Hash functions play a very important role in information security. It compresses any arbitrary bit-length message m into a fixed-length hash value h(m). Hash functions are in public, and their management processes don't keep secret. The security of hash function depend on it's one-way property. The output of hash function is independent of input. Hash function can be directly used to data integrity, and be the security guarantee for many cryptosystems and protocols such as signature, group signature, message authentication code, e-cash, bit commitment, coin-flipping, e-voting etc.Recently the standard hash functions are popular and favorable. It have two families: MDx family (MD4, MD5,HAVAL, RIPEMD,RIPEMD-160) and SHA family(SHA-0, SHA-1, SHA-256,384, 512 ). These hashing algorithms reveal the main design method and technology of the hash functions.The cryptoanalysis for hash functions has made much progress. Hans Dobbertin gave an attack for the full MD4 in 1996, which can find a collision with the probability of 2'22. The latest attack on MD4 is a more efficient attack described by Kasselman in 1997. As for MD5, B.den Boer and A.Bosselaersobber found a kind of pseudo-collisions for MD5 which composed of the same message with two groups of different initial values. In Eurocrypto'96, Dobbertin presented one collision of MD5 which is made up of two different messages under another initial value. in Crypto'2004 conference Xiaoyun. Wang present a new powerful attack on MD5 which raise a stir. B.V.Rompay gave an attack for 3-pass HAVAL in 2003, which computational complexity of the attack corresponds to about 229 computations.But Xiaoyun.Wang make use of bit-trace method to search a collison line in 2004, to modify the messages, to gain sufficient conditions, which allows us to find collisionsefficiently. For SHA family, Xiaoyun.Wang has made much progress for SHA-1,she found a differential attack for SHA-1 with the probability of 2~69 in 2005,HAVAL was presented by Y. L. Zheng etc at Auscrypto'92. It can be processed in 3,4 or 5 passes, and produces 128, 160, 192, or 224-bit fingerprint.We make use of Xiaoyun.Wang' technology to break the HAVAL-160 with 4 passes. We can found a differential attack for HAVAL-160 with the probability of 2"40. The result is much better than 2'80, which is the result of birthday attack.