The First Practical Collision for 31-Step SHA-256

SHA-256 is a hash function standardized by NIST and has been widely deployed in real-world applications, e.g., Bitcoin. Recently, an improved collision attack on 31-step SHA-256 was proposed by Li-Liu-Wang at EUROCRYPT 2024, whose time and memory complexity are 2^49.8 and 2⁴⁸, respectively. Such a result indicates that we are close to a practical collision attack on 31-step SHA-256, and that the current bottleneck is the memory complexity. To overcome such an obstacle, we develop a novel memory-efficient attack in this paper, which allows us to find the first practical colliding message pair for 31-step SHA-256 in only 1.2 h with 64 threads and negligible memory. This technique is general and Li-Liu-Wang’s collision attack on 31-step SHA-512 can also be significantly improved, i.e., the time and memory complexity can be improved by a factor of 2^20.9 and 2^42.1, respectively. Although we have set a new record in the practical collision attack on SHA-256, which improves the previous best practical attack published at EUROCRYPT 2013 by 3 steps, the attack is still far from threatening the security of SHA-256 since it has 64 steps in total. On the other hand, our new attack shows that nearly half of full SHA-256 can be practically cracked now, and it should be viewed as a major progress in the cryptanalysis of SHA-256 since 2013.