Cryptanalysis Of The Reduced HASH Functions SHA-256 And SHA-512

Hash functions play a very important role in modern cryptography.They are also called hash codes,hash results,message digests or digital fingerprints. They compress an input of arbitrary length to a result with a fixed length.Hash functions can be used to data integrity and be guarantee the security of many cryptosystems and protocols.Hash functions are frequently used in digital signature schemes to compress large messages for processing by publickey cryptosystems such as RSA.There are several advantages to using hash functions for digital schemes:breaking the mathematical structure of some digital schemes;improving the implement speed of digital schemes;ignoring the message corresponding to signature;separating the signature and encryption.In addition to the two basic properties-compression and ease of computationcryptographic hash functions need to satisfy the following three security properties:(1)Preimage resistance:for any pre-specified output y,it is computationally infeasible to find an input x such that h(x)= y.(2)Second-preimage resistance:for any input x,it is computationally infeasible to find another input x' such that h(x)= h(x').(3)Collision resistance:it is computationally infeasible to find any two distinct inputs x,x' with the same output,i.e.,h(x)= h(x').Currently,the standard hash functions are consist of two families:MDx family(MD4[24],MD5[25],HAVAL[37],RIPEMD[26],RIPEMD-128[10],RIPEMD-160[10]) and SHA family(SHi-0[16],SHA-1[17],SHA-256[18],SHA-384[18], SHA-512[18]).They have the same design philosophy and have a similar structure.Differential cryptanalysis[2]introduced by Biham and Shamir in 1990,is one of the most powerful chosen plaintext attacks in symmetric-key cryptography (i.e.,in block ciphers,stream ciphers,hash functions and MAC algorithms). The attack is a method which analyzes the effect of particular differences in plaintext pairs on the differences of resultant ciphertext pairs.These differences can be used to assign probabilities to the possible keys and to locate the most probable key.Xiaoyun Wang etc.used the conception of differences that was different from the conventional differential analysis to attack MD4,MD5, RIPEMD,HAVAL,SHA-0,SHA-1[30,31,34,36].In 2006,Florian Mendel etc.[21]gave a differential path of 18-step SHA-256. But they gave an false example of an 18-step collie;ion for SHA-256.In 2008,Ivica Nikolic etc.[22]found full collision for 21-step reduced SHA-256, semi-free start collision,i.e.collision for a different initial value,for 23-step reduced SHA-256,and semi-free start near collision for 25-step reduced SHA-256.In this thesis,we provide new attacks on step-reduced SHA-256 and SHA-512. The main contributions of this thesis include two parts.One is to derive the sufficient conditions that guarantee the feasibility of the 18-step SHA-256 differential path.Another is the cryptanalysis of 18-step SHA-512 for the first time.We give the real collisions for 18-step SHA-256 and SHA-512 with complexity 2¹⁴.