CryptoDB
The First Practical Collision for 31-Step SHA-256
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | ASIACRYPT 2024 |
| Abstract: | 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^{48}, 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 hours 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. |
BibTeX
@inproceedings{asiacrypt-2024-34565,
title={The First Practical Collision for 31-Step SHA-256},
publisher={Springer-Verlag},
author={Yingxin Li and Fukang Liu and Gaoli Wang and Xiaoyang Dong and Siwei Sun},
year=2024
}