Research On Related Technologies Of Collision Attack On MD4 And MD5

As an important tool of modern information security theory, Hash functions play an important role when ensure the reliability of the information interactive process. However, along with the breakthrough of MD5 and the introdution of semantic chosen-prefix collisions for MD5, the security analysis and research of Hash functions become the focus.In recent years, as the widely used Hash function, MD5 becomes "famous" because of the introdution and applications of the algorithm of chosen-prefix collision and Flame. The security of MD5 is questioned. But, due to some practical factors, MD5 still plays a role in the information security system. MD4 is the design basis of most Hash functions such as MD5 and SHA-1. The analysis of it gives some guide to the study of follow-up Hash functions. This paper focuses on analyzing the related technologies and algorithms of collision attack on MD4 and MD5, and obtain the following results:1、The automatic algorithm to construct differential path in MD4 in [17] is improved. By studying the theory of MD4 and the automatic algorithm to construct differential path, the factors which affect the weight of differential path results from the algorithm is analysed. Finally, the particularity of the difference in the 32 th bit is fully considered to control unnecessary carry expansions of signed differences more effectively in the process of cancelation search. And the new differential path is constructed. Compared with the path in [17], the weight is reduced by 6 and the number of sufficient conditions is reduced by 14.2、According to the unbalanced distribution of the complexity of chosen-prefix collisions under the practical requirement, a improved algorithm of chosen-prefix collisions for MD5 is designed. Firstly, combined with Non-Adjacent Form(NAF), the probability related to the complexity of birthday search is deduced under certain conditions. And the derivation process is verified by comparing the deduced value with the analog value given in [37]. Then the relation between the balance parameter and the complexity of birthday search is established. Secondly, to solve the problem that the computational complexity is almost entirely determined by the birthday search when the algorithm of chosen-prefix collisions is applied to fake X.509 certificate, the improved algorithm is designed combining with the above results about the balance parameter,which improves the form of birthday collision by introducing new message block differences. Under the practical requirement for parameter, the complexity of the improved algorithm can be reduced by one bit on average.3、The algorithm of detecting continuous near-collision blocks on Hash functions is given. By the analysis of collision attack detection on Hash functions which is the first example of counter-cryptanalysis introduced by Stevens, the algorithm of detecting continuous near-collision blocks is obtained by expanding of the existing algorithm of last near-collision block detection. And the detection of certificate which is used in flame is implemented successfully. Within 0.06 seconds, 4 continuous near-collision blocks is obtained,and all of the corresponding differential paths are given for the first time. Finally, preliminary comparisons between the forging of certificate in flame and the algorithm of chosen-prefix collisions are made based on the collision information we get.