RIPEMD-160 and SHA-256 are two hash functions used to generate the bitcoin address. In particular, RIPEMD-160 is an ISO/IEC standard and SHA-256 has been widely used in the world. Due to their complex designs, the progress to find (semi-free-start) collisions for the two hash functions is slow. Recently at EUROCRYPT 2023, Liu et al. presented the first collision attack on 36 steps of RIPEMD-160 and the first MILP-based method to find collision-generating signed differential characteristics. We continue this line of research and implement the MILP-based method with a SAT/SMT-based method. Furthermore, we observe that the collision attack on RIPEMD-160 can be improved to 40 steps with different message differences. We have practically found a colliding message pair for 40-step RIPEMD-160 in 16 hours with 115 threads. Moreover, we also report the first semi-free-start (SFS) colliding message pair for 39-step SHA-256, which can be found in about 3 hours with 120 threads. These results update the best (SFS) collision attacks on RIPEMD-160 and SHA-256. Especially, we have made some progress on SHA-256 since the last update on (SFS) collision attacks on it at EUROCRYPT 2013, where the first practical SFS collision attack on 38-step SHA-256 was found.
Does this mean that it’s now practical to attack Sha256? I’m sure all the GitHub people will be really sad cuz they have to change to sha 512
No. We’re a few steps closer to it being broken, but still far away.
First of all, it’s a semi-free-start collision. I don’t know what semi means here (I’d have to read the paper), but a free-start collision is where the attacker gets to control the initial state of the hash function, which gives them a significant advantage over the normal situation, where they don’t.
Secondly, their attack applies to “39-step” SHA-256, which I assume means 39 rounds. Real SHA-256 uses 64 rounds. I don’t know precisely how the attack difficulty scales up with the number of rounds, but I’m guessing it’s roughly exponential.