First practical SHA-256 collision for 31 steps. fse2024

[lifthrasiir]

It took me a lot of head scratching to exactly understand what this means, so for your information: this is not a full attack and you are safe (for now). If you need a concrete proof:

    import hashlib
    m0 = bytes.fromhex('''
        c32aef52 512294ba 9db5ed8c 8c8c88ed b2de2765 63a2d14e ec7619cc 93b21182
        e5050f50 f0839b60 7b1ee176 aaa06d68 c462343c 67898962 9558f495 04281f2c
    ''')
    m1 = bytes.fromhex('''
        5d0f5ae6 05e98311 8fa3c73a 9af8c49d a2bf31f7 de547b67 5baecee3 da0d8c94
        e4c19564 f682d45c f7c57698 f871f9b5 f14469b7 fc28eb0c 2d76db75 043fe071
    ''')
    m1p = bytes.fromhex('''
        5d0f5ae6 05e98311 8fa3c73a 9af8c49d a2bf31f7 de548b61 5b8e46f2 8a1dd69a
        bcc08464 f6825458 f7c57698 f871f9b5 f14469b7 fc28eb0c 2d76db75 043fe071
    ''')
    print(hashlib.sha256(m0 + m1).hexdigest())
    # 2627577ac401cf44d837cf8471cac13ad7d8385bd00e4daf59fd3c3c646eaaae
    print(hashlib.sha256(m0 + m1p).hexdigest())
    # c945222bf0868a2218d5683c69b2b6c4720093e40c46d1197262d991e4d483b6

As far as I can understand, this is same as [1] and the first practical semi-free-start collision of 31 out of 64 rounds of SHA-256, at the complexity of 2^49.8. "Step" here equates to "round", which is not always the case and I was much confused. (RIPEMD-160 for example has 5 rounds and 16 steps per each round.) There are other theoretical cryptanalyses with more rounds of SHA-256, but this one is fairly practical and the group has explicitly demonstrated. But it is still far from the full collision attack or more like MD5 suffered back in 2009.

(By the way I couldn't exactly reproduce the claimed result even with a 31-round version of SHA-256. Maybe they simply ran a step function 31 times without any initial rounds? I don't know.)

EDIT: @Retr0id has reproduced this result: https://bsky.app/profile/retr0.id/post/3konobbmf6o2a

[1] https://eprint.iacr.org/2024/349.pdf

[wongarsu]

There was a practical collision attack on 28 rounds in 2016. Only 3 rounds of progress in 8 years is a pretty good sign for sha256.

For new code it might be better to use blake2b, blake3 or sha3, but at the same time I don't think there is any rush to migrate existing systems away from sha256.

[layer8]

“Steps” means “rounds” here. For the general advances see the table under https://en.wikipedia.org/wiki/SHA-2#Cryptanalysis_and_valida... .

In 2016 there was a practical collision attack for 28 rounds. At that rate of progress, a practical collision attack for all 64 rounds would be reached in around 90 years from now.

[tptacek]

This is a good time to re-read JP Aumasson's "Too Much Crypto" post:

https://eprint.iacr.org/2019/1492.pdf

The comparison is probably broken in a variety of ways, but the Keccak team proposed KangarooTwelve, a 12- (1/2 as many) round Keccak variant, after a practical attack on 6-round Keccak was published.

[GoblinSlayer]

I noticed blake3 uses 7 doublerounds, i.e. 14 chacha rounds. Is it intended due to increased communication or another bug?

[jl6]

I assume “steps” here means rounds? For reference, standard SHA-256 is 64 rounds.

[H8crilA]

SHA-2, including SHA-256, is constructed using a Davies–Meyer compression function. That compression function starts with a block cipher - so an object like AES, but with wider keys and wider block size. For SHA-2 this block cipher is called SHACAL-2.

Now what we're seeing here is an attack on SHA-2 assuming a very, very significant degradation in SHACAL-2, where we run far fewer rounds than assumed in the standard. This is your typical cryptoanalytical result, interesting, but it is very very far from showing that "SHA-2 is broken".

As a side note I once estimated that the Bitcoin network is likely to produce a collision in SHA-256 sometime in 2050s, assuming the current rate of growth of the hash throughput. Of course that's a big assumption, and also nobody will notice the collision, as nobody is saving all those past hashes :)

Another side note - if you're interested in learning about hash functions then I recommend looking into SHA-3. Not because it's newer and shinier, but because I think it is actually the easiest to understand. It has a very clever design.

[slau]

Yes, the follow-up post (hidden by default) reads:

> Don’t panic, folks. This is very good work, especially given the low memory complexity of this attack. But there are 33 steps left. Your bitcoins are safe.

[popol12]

Bitcoin is using double sha256, just in case someone is wondering.

Though I wonder if double sha256 makes it twice harder to break or if it's better or lower than that.

[nabla9]

Frank @jedisct1

>Wouldn’t help in that case. Collision resistance of a composition degrades to the one of the weakest function (it’s even slightly worse). Double SHA2 only protects against length extension attacks. https://twitter.com/jedisct1/status/1772911384356868586

[Karliss]

I don't think double sha256 makes any difference with regards to collisions. If there is a collision after single sha256 they will still collide after second layer of hashing sha256(x)=sha256(y) => sha256(sha256(x))=sha256(sha256(y)).

[renonce]

I understand the definitions of such crypto algorithms but have no idea about differential cryptanalysis. Can someone explain how attacks like this are constructed, and why it took 8 years to advance cryptanalysis by 3 rounds? What insight was needed that took 8 years to discover and formulate as a practical attack?

[0x073]

Good that git still use sha1 ;)

[hn_p4ttern]

Is it used to sign a commit, right ? Which are the probabilities to have a collision that:

a) is still code

b) is still code AND is code similar to a previous commit

c) is still code AND is code similar to a previous commit AND is valid

d) is still code AND is code similar to a previous commit AND is valid AND makes sense for something

OR at least

a) is still code

b) is still code AND is valid

d) is still code AND is valid AND makes sense for something

Let me know.

[hot_gril]

Good old MDA4. Nothing beats that.