Cryptanalysis Of SM3Cryptographic Hash Algorithm

Hash functions paly an important role in cryptography, it is widely used in digital signature, message authentication, integrity check, etc. They are supposed to satisfy collision resistance, preimage resistance and second preimage resistance. In2005, the analysis of MD5and SHA-1[1,2] show that the security of widely used hash functions, i.e. MD5and SHA-1, are suspected. As a consequence, a new hash standard competition organized by National Institute of Standards and Technology (NIST) was started in2007. Recently, NIST announced Keccak was the new hash standard.SM3cryptographic hash algorithm[3], a new Chinese cryptographic hash standard, designed by Xiaoyun Wang et al., was announced by the Office of State Commercial Cryptography Administration of China in2010. It is based on the Merkle-Damgard design and uses message block of length512bits and outputs hash value of length256bits. The design of SM3cryptographic hash algorithm resembles the design of SHA-2but includes additional fortifying features such as feeding two message-derived words into each step, as opposed to only one in the case of SHA-2. As far as we know, few attacks were published on (step-reduced) SM3cryptographic hash algorithm. The previous work on analysis of the SM3that we are aware of has been presented by Zou et al.[4] at ICISC2011. In that paper, the first preimage attack on step-reduced SM3was provided. In particular, the authors presented attacks on SM3reduced to30steps from the7-th step with time complexity224930-step operations and28steps from the1-st step with time complexity2241.528-step operations.With the development of cryptographic analysis technology, not only the three classical security requirements (preimage resistance, second preimage resistance and collision resistance) are considered, researchers look at more security properties of hash functions, such as non-randomness, pseudo-preimage attack(free-start preimage attack), near-collisions, etc.In this thesis, we analyze the characteristics of SM3cryptographic hash algorithm, and research the security of SM3cryptographic hash algorithm by applying the following two attack methods:1. We study the pseudo-preimage attack on28-step SM3cryptographic hash algorithm. Combined with the method of converting meet-in-the-middle preimage attack into pseudo-collision attack[46], we obtain a pseudo-collision attack on28-step SM3cryptographic hash algorithm with time complexity2112.5and momory complexity231. Our result shows that the28-step SM3cryptographic hash algorithm is not immune to pseudo-collision attack.2. The non-randomness property of SM3cryptographic hash algorithm has been researched. Using the boomerang technique and the message modification technique, we obtain the32-step,33-step,34-step and35-step boomerang distinguishers on SM3cryptographic hash algorithm. Furthermore, we propose the32-step boomerang attack on SM3cryptographic hash algorithm with complexity214.4, the33-step boomerang attack on SM3cryptographic hash algorithm with complexity232.4, the34-step boomerang attack on SM3cryptographic hash algorithm with complexity253.1and the35-step boomerang attack on SM3cryptographic hash algorithm with complexity2117.1.