Preimage and pseudo-collision attacks on step-reduced SM3 hash function
SM3 [12] is the Chinese cryptographic hash standard which was announced in 2010 and designed by Wang et al. It is based on the Merkle-Damgard design and its compression function can be seen as a block cipher used in Davies-Meyer mode. It uses message block of length 512 bits and outputs hash value of length 256 bits. This letter studies the security of SM3 hash function against preimage attack and pseudo-collision attack by using the weakness of diffusion process and linear message expansion. We propose preimage attacks on 29-step and 30-step SM3, and pseudo-preimage attacks on 31-step and 32-step SM3 out of 64 steps. The complexities of these attacks are 2245 29-step operations, 2(251.1) 30-step operations, 2(245) 31-step operations and 2(251.1) 32-step operations, respectively. These (pseudo-)preimage attacks are all from the 1-st step of the reduced SM3. Furthermore, these (pseudo-)preimage attacks can be converted into pseudo-collision attacks on SM3 reduced to 29 steps, 30 steps, 31 steps and 32 steps with complexities of 2(122), 2(125.1), 2(122) and 2(125.1) respectively. As far as we know, the previously best known preimage attacks on SM3 cover 28 steps (from the 1-st step) and 30 steps (from the 7-th step). (c) 2013 Elsevier B.V. All rights reserved.
sm3 hash function preimage attack cryptography collision attack differential meet-in-the-middle