Preimage Attacks On Step-Reduced HAS-160,RIPEMD-160 And SM3

The hash function is one of the fundamental primitives in modern cryptogra-phy.They are used to compress messages of arbitrary length to fixed length hash values and used for numerous security protocols,such as digital signature,data integrity and message authentication.Hash functions should satisfy three main security properties:collision resistance,preimage resistance and second preimage resistance.With the breakthroughs in the collision attacks on a series of standard hash functions,preimage attack also has drawn a great amount of attention from many researchers.The meet-in-the-middle attack is one of the basic tools used in preimage attacks.It is improved by splice-and-cut technique,partial matching technique,biclique technique,initial structure technique and so on.However,the complexities of preimage attacks based on the meet-in-the-middle attack are very close to brute-force search.Owing to the existence of message expansion,preimage attacks are very difficult to achieve full steps.For these reasons.there are two directions of preimage attacks.One aims to attack more steps,the other is to reduce the complexities.This thesis analyses the security of HAS-160,RIPEMD-160 and SM3.They are based on the Merkle-Damgrd design,use message block of length 512 bit-s.The hash values are 160 bits,160 bits and 256 bits respectively.Firstly,a 71-step pseudo-preimage attack and a 71-step preimage attack on HAS-160 are proposed.Secondly,preimage attacks on 31-step,32-step,33-step,34-step and 35-step RIPEMD-160 are presented.Thirdly,a 29-step and a 30-step preimage attacks are proposed.All of the attacks are the best on each hash standard in terms of number of steps.· Pseudo-preimage and preimage attacks on HAS-160HAS-160 is the Korean hash standard which was developed by Korean gov-ernment in 2000 and widely used in Korea.The structure of HAS-160 resembles the structure of SHA-1.Hong et al.proposed the best preimage attacks on step-reduced HAS-160.The results consist of a 67-step preimage attack starting from the first step and a 68-step one starting from the thirteenth step.This thesis focuses on increasing the steps of preimage attacks.6-step bicliques are constructed.Combined with the differential meet-in-the-middle attack,a pseudo-preimage attack on 71-step HAS-160 with complexity 2158.12 is proposed.This attack is starting from the first step and increases the best pseudo-preimage at-tack by 4 steps.However,this work does not satisfy the message padding owing to the linear spaces use the message padding bits.By carefully splitting the com-pression function and fixing the linear spaces into 4 message words,linear spaces are independent of message padding bits and the dimensions increase from 3 to 5.The probabilities of differential characteristics are improved.Benefits from the above,a preimage attack starting from the seventh step with complexity 2158.97 is proposed.This improves the preimage attack starting from the intermediate step by 3 steps.As far as we know,this is the best preimage attack on step-reduced HAS-160 in terms of number of steps.· Preimage attacks on RIPEMD-160RIPEMD-160 was proposed by Dobbertin,Bossselaers and Preneel in 1996.It is the strengthened version of RIPEMD and standardized in ISO/IEC 10118-3.Its compression function uses a double-branch structure.This makes the imple-mentation of splice-and-cut too difficult.There is no preimage attack on step-reduced RIPEMD-160 which is starting from the first step.The best preimage attack starting from the intermediate step is a 31-step one which was proposed by Ohtahara et al.To increase the attack steps,the initial value is located in bicliques and the matching point is fixed in the output of right branch.By ex-haustive searching the position of linear spaces,the lower constant bits in initial values are obtained and 3.5-step bicliques are constructed.Using the differential meet-in-the-middle attack,preimage attacks on 31-step,32-step,33-step and 34-step RIPEMD-160 are proposed and the complexities are 2157.97,2157.75,2158.80 and 2158.91 respectively.This work gives the first preimage attacks starting from the first step.Furthermore,by setting linear spaces in one message word,a preimage attack on 35-step RIPEMD-160 with complexity 2159.38 is proposed.This attack is starting from the second step and improves the preimage attack starting from the intermediate step by 4 steps.As far as we know,they are the best preimage attacks on step-reduced RIPEMD-160 in terms of number of steps.· Preimage attacks on SM3SM3 is the Chinese hash standard which was designed by Xiaoyu Wang et al.Its structure resembles the design of SHA-2.SM3 introduces some additional fortifying features to achieve greater security,such as feeding two message-derived words into each step.Because of the first 16 steps using a linear boolean function,it is difficult,to apply preimage attacks starting from the first step.This thesis focuses on the preimage attack starting from the first step.The best preimage attack on step-reduced SM3 is a 29-step one which was proposed by Wang et al.An improved preimage attack on 29-step SM3 is presented by using indirect partial matching technique and bit-carry guessing.It decreases the complexity of the 29-step pseudo-preimage attack by a factor of 26 and improves the complexity of the 29-step preimage attack by a factor of 23.Furthermore,a preimage attack on 30-step SM3 with complexity 2255.2 is proposed.This work increases the preimage attack starting from the first step by 1 step.As far as we know,this is the best preimage attack on step-reduced SM3 starting from the first step.