Research On The Cryptanalysis Methods Of Hash Functions

The analysis on the hash functions is one of the focuses in the cryptography nowadays. MD5 is one of the important hash functions, so in this paper we will analyze on the collision attack algorithms on MD5 deeply and thereby present some methods to resist the collision attack on hash functions. For the collision attack algorithms, our contributions mainly include the following four parts:1. Using the necessary and sufficient condition which is to guarantee that the subtraction modulo 2ⁿ and left shift rotation can be commuted, we will prove that two sufficient conditions given by Liang Jie and Lai Xuejia are redundant. Then we will prove that two of the 16 redundant conditions proposed by Yuto Nakano et al. are not redundant actually. Additionally, we will show that there is a mistake in the collision attack algorithm presented by Liang Jie and Lai Xuejia for the second-block collision message because they didn't consider the dependence in the sufficient conditions, and correct the mistake. Finally, we obtain a new set of sufficient conditions and verify that it can always yield a MD5 collision according to a number of computer simulations.2. We will present a method to guarantee that a chaining value satisfies more than one sufficient condition. Moreover, we will point out that two sufficient conditions are no longer able to be modified by the multi-message modification method presented by Yu Sasaki et al. in the new set of sufficient conditions, and propose a new method to make one of them satisfied deterministically. Then we present new multi-message modification techniques on other three sufficient conditions. Finally, we will test our results by computer simulations and the average runtime for a MD5 collision is about three hours.3. By analyzing the properties of the nonlinear functions used in MD5 and the differences in term of XOR and subtraction modulo 2³², we prove that some sufficient conditions presented by Liang Jie and Lai Xuejia are also necessary to guarantee the differential path and give a set of necessary and sufficient conditions to guarantee the output differences of the last two steps. Then utilizing the set of necessary and sufficient conditions we present an improved collision attack algorithm on MD5. Finally, we analyze the average computational complexity of our attack algorithm which is 0.7187 times of that of the previous collision attack algorithms, and test the result by computer simulations.4. We deeply analyze the construction of the differential path, the set of sufficient conditions and the message modification techniques which are the key steps in the collision attacks on hash functions. Then according to the results we present some methods to resist the collision attack on hash functions.