Paper 2026/1120

Pushing Collision Attacks on SHA-2 to 39 Steps

Abstract

The SHA-2 family is a U.S. federal standard and mainly includes SHA-256 and SHA-512. In particular, SHA-256 plays a central role in real-world applications and is widely regarded as one of the most important hash functions in use today. At CRYPTO 2026, Li et al. proposed collision attacks up to 37-step SHA-2, but they could not reach 38 steps due to the low-probability uncontrolled part in the corresponding differential characteristics. In this paper, we propose an improved search procedure to find high-quality differential characteristics for 38-step SHA-256 and SHA-512, respectively. Exploiting the special shape of the 38-step differential characteristics, the meet-in-the-middle method to fulfill the corresponding differential conditions is extremely memory-efficient. Consequently, we successfully achieve the first 38-step collision attack on both SHA-256 and SHA-512, whose time complexity is $2^{104.3}$ and $2^{125.4}$, respectively. The memory complexity of the 38-step collision attack is negligible. The methods are also applied to the 36-step and 37-step collision attacks on SHA-2 published at CRYPTO 2026, leading to a significant improvement in both time and memory complexity. In particular, the time complexity of the collision attack on 36-step SHA-256 is only $2^{57}$ and the memory complexity is negligible. We have verified this collision attack by providing the first colliding message pair for 36-step SHA-256. More remarkably, we apply the new method to 39 steps of SHA-2 and obtain the first effective collision attack on 39-step SHA-512, with a time complexity of $2^{178}$ and negligible memory complexity. However, the method does not yield an effective collision attack on 39-step SHA-256 due to the same issue arising from the low-probability uncontrolled part. Overall, this work further pushed the limit of memory-efficient collision attacks on round-reduced SHA-2 and significantly advances the state of the art.