Collision Attacks on SHA-256 up to 37 Steps with Improved Trail Search

As a NIST-standardized hash function, SHA-256 has been extensively analyzed in the context of collision attacks. Although Mendel et al. introduced the first 31-step collision attack at EUROCRYPT 2013, the number of attacked steps has not been increased for more than a decade. After a thorough review of existing attacks, we identify that progressing beyond 31 steps necessitates new local collisions in the message expansion. To date, such local collisions have been manually constructed, which is both time-consuming and technically challenging. Besides, even the latest automated models for searching signed differential trails fail to accurately account for the bit conditions imposed by Boolean functions, potentially overlooking high-quality trails. In this paper, we enhance the existing framework by overcoming these two limitations. Firstly, an automated tool that can efficiently identify high-quality local collisions is given following the main idea of EUROCRYPT 2013. Secondly, two new models of Boolean functions that can accurately capture bit conditions are introduced. Leveraging these improvements, we finally reach the first 37-step collision attack on SHA-256, extending the number of attacked steps by six, and this is the first such advancement in 12 years.