Paper 2024/349

New Records in Collision Attacks on SHA-2

Yingxin Li, East China Normal University
Fukang Liu, Tokyo Institute of Technology
Gaoli Wang, East China Normal University

The SHA-2 family including SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 and SHA512/256 is a U.S. federal standard pub- lished by NIST. Especially, there is no doubt that SHA-256 is one of the most important hash functions used in real-world applications. Due to its complex design compared with SHA-1, there is almost no progress in collision attacks on SHA-2 after ASIACRYPT 2015. In this work, we retake this challenge and aim to significantly improve collision attacks on the SHA-2 family. First, we observe from many existing attacks on SHA-2 that the current advanced tool to search for SHA-2 characteristics has reached the bottleneck. Specifically, longer differential characteristics could not be found, and this causes that the collision attack could not reach more steps. To address this issue, we adopt Liu et al.’s MILP-based method and implement it with SAT/SMT for SHA-2, where we also add more techniques to detect contradictions in SHA-2 characteristics. This answers an open problem left in Liu et al.’s paper to apply the technique to SHA-2. With this SAT/SMT-based tool, we search for SHA-2 charac- teristics by controlling its sparsity in a dedicated way. As a result, we successfully find the first practical semi-free-start (SFS) colliding message pair for 39-step SHA-256, improving the best 38-step SFS collision attack published at EUROCRYPT 2013. In addition, we also report the first practical free-start (FS) collision attack on 40-step SHA-224, while the previously best theoretic 40-step attack has time complexity 2110. More- over, for the first time, we can mount practical and theoretic collision attacks on 28-step and 31-step SHA-512, respectively, which improve the best collision attack only reaching 27 steps of SHA-512 at ASIACRYPT 2015. In a word, with new techniques to find SHA-2 characteristics, we have made some notable progress in the analysis of SHA-2 after the major achievements made at EUROCRYPT 2013 and ASIACRYPT 2015.

Available format(s)
Attacks and cryptanalysis
Publication info
A minor revision of an IACR publication in EUROCRYPT 2024
practical collision attackSHA-2SAT/SMT
Contact author(s)
liyx1140 @ 163 com
liufukangs @ gmail com
glwang @ sei ecnu edu cn
2024-02-27: approved
2024-02-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yingxin Li and Fukang Liu and Gaoli Wang},
      title = {New Records in Collision Attacks on SHA-2},
      howpublished = {Cryptology ePrint Archive, Paper 2024/349},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.