Research Of Preimage Attacks On Hash Function

As an important tool in cryptography,hash functions have been widely used in digital signatures, message authentication, data integrity and so on. The security analysis of hash functions is a dominant and active topic in cryptography. Recently appeared preimage attacks on hash function algorithms play a very important role in this realm. Compared with the collision attack,the preimage attack is more difficult to achieve. However, the preimage attack has a fatal effect on hash functions.In this thesis, the methods of preimage attacks on MD-4, MD-5 and SHA-0 which were proposed on the international conference for the past two years are analyzed. Then the improved schemes are proposed. The main work in this thesis includes:(1) The absorption properties of boolean functions, reversibility of compression functions, specificity of message expansion on MD-4, the meet-in-middle attacks and random graph theory are researched and summarized deeply.(2) Leurent's method is improved by our methods. The space complexity of the attack is reduced from 231 to 216 by the first scheme. The time complexity of the attack is reduced from 2102 to 298 by the second scheme.(3) The difficulties that the Leurent's method applies to MD-5 are further analyzed. After comparision of preimage attacks between ones to the reduced steps MD-5 and full MD-5, the idea source of Yu Sasaki's preimage attack on full MD-5 is analyzed. Another feasible initial structure is experimented.(4) Two preimage attacks for reduced SHA-0 are analyzed. One is the 50 steps of SHA-0 propsed by Cannière, and the other is the 52 steps of SHA-0 propsed by K.Aoki. Message modification techniques are tried to apply for choosing the state variables. At the same time, the balance complexity between the calculation and transformation of partial pseudo-preimage is explored.