Meet-in-the-Middle Preimage Attacks On Hash Functions

Cryptographic hash functions, known as hash functions, are one of threecryptographic primitives （others are encryption algorithm and signature algo-rithm）. Cryptographic hash functions play important role in modern commu-nications, finance, and security computation, etc. The classical and importantsecurity properties of hash functions are collision resistance, second preimage re-sistance, and preimage resistance. The second preimage resistance and preimageresistance of six hash functions: MD4, Extended MD4,3-pass HAVAL, SM3,DHA-256and SShash, are analyzed in the thesis.MD4is a hash function designed by Ronald L. Rivest and published atCRYPTO1990. The design philosophy of many important hash functions, suchas MD5, SHA-1and SHA-2, root in MD4. Moreover, MD4is still used in somecontext. We present the formula for computing complexity for the meet-in-the-middle attack on MD4, and propose the multi-neutral-word partial-fixing tech-nique, and also design the algorithm for computing complexity automatically,such that we give an improved preimage attack on one-block MD4with the timecomplexity295MD4compression function operations, as compared to the2107complexity of the previous attack by Aoki et al.（SAC2008） with the new tech-niques. Extended MD4is the256-bit version of MD4. We also use the similartechniques to improve the pseudo-preimage and preimage attacks on ExtendedMD4with2^25.2and2^12.6improvement factor, as compared to previous attacksby Sasaki et al.（ACISP2009）, respectively. The attacks are the best preim-age attacks on MD4and Extended MD4. The preimage attacks on one-blockhash functions are particularly interesting, as the attackers do not use the char-acteristics of the merkle-damg ard construction and they attack the compression functions directly.HAVAL is a hash function proposed by Yuliang Zheng et al. at AUSCRYPT1992, including3-,4-and5-pass versions. We use a nice mix techniques to im-prove pseudo-preimage and preimage attacks on3-Pass HAVAL at the complexityof2¹⁷²and2^209.6, respectively, as compared to the previous best known results:2¹⁹²and2²²⁵by Sasaki et al.（ASIACRYPT2008）.SM3was published by China State Cryptography Administration in Dec.2010. SM3is a dedicated hash function with output length of256bits and64steps of operations. We present a preimage attack on30-step SM3, which is thefirst result that analyzes preimage resistance of SM3.DHA-256（Double Hash Algorithm） was designed by Jesang Lee et al. andproposed at the Cryptographic Hash Workshop hosted by NIST in November2005. DHA-256is a dedicated hash function with output length of256bits and64steps of operations. We show a preimage attack on35-step DHA-256. Wealso show one-block preimage attack on27-step DHA-256. To the best of ourknowledge, this is the first result that analyzes preimage resistance of DHA-256.SShash is a hash family proposed by Somitra Kumar Sanadhya et al. inASIACCS2009, including SShash-256（64steps） and SShash-512（80steps）. Weshow pseudo-preimage and preimage attacks on28-step SShash. As far as weknow, this is the first result that investigates the security of the SShash hashfamily.The preimage attacks can be trivially turned into the corresponding secondpreimage attacks in the thesis, as they can deal with the operations about themessage, such as the message padding rule and appending the length of theoriginal message.