An Attack On The Last Three Passes Of 4-Pass HAVAL-128

With the great development of computer technology, human society is stepping into the era of electronics in recent years. The tendency for using information and network technology is inevitable. Electronic payments and the E-commerce are becoming necessary for development of our society. This also makes digital signature develop very quickly. Security is the most important factor for the design of digital signature. Now, the one-way HASH functions are widely used in the field of information security such as digital signature, information distinguishing etc. The one-way HASH functions are becoming one of the central techniques in modern cryptology. This article has done something with the analysis of HASH function.About the analysis of HASH functions, lots of work has been done in the latest year. Xiaoyun Wang, from Shandong University of China, declared her successful attacks to MD5, MD4, RIPEMD, HAVAL on Crypto'04 in the summer of last year. These results are world-shaking. MD5 is one standard encryption algorithm of one-way HASH function. Another one is SHA-1. On 7th, 2, 2005, NIST declared that SHA-1 is secure and that there is no enough reason to doubt that it won't be attacked successfully recently. Just a week later, professor Wang declared to the world that she had attacked SHA-1 successfully. Today, almost all HASH functions have been attacked successfully by her.In 1992, Yuliang Zheng. Josef Pieprzyk and Jennifer Seberry invented HAVALalgorithm. It is another HASH function after MD4 and MD5 algorithm. This algorithm has many merits such as high efficiency and being used variously according to the user's need. Its security level was considered rather high at that time. HAVAL algorithm is widely used in the field of information technology.According to the techniques of its design, we can think HAVAL algorithm belongs to MDx HASH functions. Designers used some special non-linear functions to seven variable parameters in HAVAL algorithm. HAVAL is a typical HASH function, so the analysis to HAVAL is very important to cryptology. The best result of the analysis to HAVAL is given by Professor Xiaoyun Wang in the article "An Attack On HASH Function HAVAL-128" in which she drew a good conclusion: there is a method to attack HAVAL-128. There is an attack to find one collision of HAVAL-128 with the running time of 210 HAVAL algorithms. Inspired by her achievement this idea, I have attacked the last three passes of 4-pass HAVAL-128 algorithm successfully in this article.Firstly, the properties of the pass-function of 4-pass HAVAL algorithm are given in the article. These properties will be used detailedly in the analysis to HAVAL algorithm. In each pass, there is a pass function f,(x6,x5,x4,x3,x2,x1,x0) ,(i = 1,2,3,4). Before being input to f1(x6,x5,x4,x3,x2,x1,x0), the seven variables in it must be executed the permutations:φ1(x6,.x5,x4,x3,x2,x1,x0)(i = 1,2,3,4). So wecombine the two steps and consider f1 (φ1 (x6, x5, x4, x3, x2, x1, x0)) (i = 1,2,3,4) as newpass-functions. Then the properties given in my article are not about f1(x6,x5,x4,x3,x2,x1,x0), but f1(φ1(x6,x5,x4,x3,x2,x1,x0)) (i = 1,2,3,4 ). Forexample: in property 1, we can see:(?) x1x6 +x5 =0.Secondly, in this article I attack the last three passes of the 4-pass HAVAL-128 successfully and draw the following conclusion:Conclusion: There exists a method about the attack to the last three passes of the 4-pass HAVAL-128 successfully. There is an attack for finding one collision of thelast three passes of the 4-pass HAVAL-128 with the running time of 29~210HAVAL algorithms. If techniques such as messages modification are adopted, the result can be improved surely.The process of attacking can be divided to four steps:Step 1: Define the differential of two messagesm = (m0,m1,...,m31) and m' =(m'0,m'1,...,m'31)As △m = m' -m = (△m0,△m1,△m2,...,△m31).Here △m1= m1 - m'1 (i = 0,1,2,... ,31).Step 2: Find a partial collision in the fourth pass of HAVAL-128. For example: from the step 103 to the step 111, assuming △m28 = 210, △m19 = -231 , △m1 = 0(i = 23,26,6,30,18,25 ), we can easily find a collision by controlling other changes inthese eight steps by adding some conditions. These conditions come from the properties of the pass functions.Step 3: Similar to Step 2, we can find a partial collision in the second and third pass of HAVAL-128 and deduce all the conditions for controlling changes from△m28 = 210, △m19 = -231. This collision occurs between step 38 and step 68.Step 4: According to specific conditions in the third and fourth pass, the possibility of the collision can be deduced out, then the important conclusion in this article has been drawn.In the last part of my article, the techniques which include the simple modification and the advanced modification are mentioned. With adopting these techniques , the method of this article will be more effective and the result will be better.