1. 3

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.



  2. 2

    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

    1. 1

      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.