5 ms·

First practical SHA-256 collision for 31 steps. fse2024

179 points by devStorms 3y ago

tptacek 3y ago
This is a good time to re-read JP Aumasson's "Too Much Crypto" post: https://eprint.iacr.org/2019/1492.pdf 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 3y ago
  I noticed blake3 uses 7 doublerounds, i.e. 14 chacha rounds. Is it intended due to increased communication or another bug?
layer8 3y ago
“Steps” means “rounds” here. For the general advances see the table under https://en.wikipedia.org/wiki/SHA-2#Cryptanalysis_and_validation 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.
renonce 3y ago
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?
jl6 3y ago
I assume “steps” here means rounds? For reference, standard SHA-256 is 64 rounds.
- deleted 3y ago
  [deleted]
- slau 3y ago
  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.
- H8crilA 3y ago
  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.
  - panzi 3y ago
    I wonder, given the current rate of development when will there be the first collision in the hashes of the Linux kernel git repository. Wait, did git finish the switch to SHA-256 or is it still using SHA-1. Googling... all I can find suggests that everyone is still using it with SHA-1 and SHA-256 repos aren't compatible with SHA-1 repos (whatever that means exactly).
    - CuriousCosmic 3y ago
      So tldr is "it's in progress". You can use SHA-256 in production. And you can convert SHA-1 repos into SHA-256 repos. However: - SHA-1 repos are not compatible with SHA-256 repos so you can't mix and match the trees (i.e. a SHA-256 fork couldn't upstream their commits to a SHA-1 repo). - The conversion path from SHA-1 to SHA-256 will break all GPG signatures on the repo. - There may be breaking changes to the SHA-256 repository implementation in the future however those changes will be guaranteed to come with an upgrade path for any users of the existing SHA-256 implementation. So it's viable as an option but it's by no means "blessed" like the existing SHA-1 impl is.
popol12 3y ago
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.
- Karliss 3y ago
  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)).
  - rowbin 3y ago
    But your are going backwards though. You have a sha-256 value and want to find an input with the same result. But this input again has to be a sha-256 result and you need to find an input for that as well, right? This would only work if you have the intermediate sha-256 value, that produces the final sha-256 or you can find a collision that itself is a sha-256 value.
    - glandium 3y ago
      Going backwards, as you say, is called a pre-image attack. That's different from a collision attack, which is generating two inputs with the same hash. Pre-image attacks are MUCH more difficult. How much more? well, MD-5 is considered broken, and yet, there isn't one for it.
      - H8crilA 3y ago
        Pre-image is approximately "twice as difficult" as a collision. A generic attack on, say, a 256 bit long hash function takes 2^128 time to find a collision, but 2^256 time to find a preimage. And like you say, this also shows up in practice: both MD-5 and SHA-1 are completely broken when it comes to collision resistance, but both are (probably) still OK for preimage resistance. I would still not recommend either of them for anything.
lifthrasiir 3y ago
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 https://bsky.app/profile/retr0.id/post/3konobbmf6o2a [1] https://eprint.iacr.org/2024/349.pdf https://eprint.iacr.org/2024/349.pdf
- wongarsu 3y ago
  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.
  - egberts1 3y ago
    Better off with SHAKE256: none of that "oops, I went with easier SHA3-224", plus SHAKE256 is faster.
0x073 3y ago
Good that git still use sha1 ;)
- deleted 3y ago
  [deleted]
- hot_gril 3y ago
  Good old MDA4. Nothing beats that.
- hn_p4ttern 3y ago
  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.
  - chasil 3y ago
    Doesn't it also have to be the same size in bytes?
    - deleted 3y ago
      [deleted]
  - dist-epoch 3y ago
    Due to the way hashing works, any change is equivalent to any other one for the purpose of finding a collision. So you can just alter the formatting to a different convention, alter spacing, add a comment, reorder equivalent lines. So you can insert a comment and continue altering it until you get a match by varying the line breaking, switching words with synonyms.
  - keybored 3y ago
    I believe there is one more step. You have to somehow get the collision into the repository. Because if you have <hash> in your own repo and pull something from another repo with the same <hash>, the remote changes will not overwrite your blob for <hash> (it will stay the same). Or at least that’s what I seem to remember from something that Torvalds wrote.

179 points by devStorms 3y ago

This is a good time to re-read JP Aumasson's "Too Much Crypto" post: https://eprint.iacr.org/2019/1492.pdf 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 3y ago
I noticed blake3 uses 7 doublerounds, i.e. 14 chacha rounds. Is it intended due to increased communication or another bug?

layer8 3y ago

“Steps” means “rounds” here. For the general advances see the table under https://en.wikipedia.org/wiki/SHA-2#Cryptanalysis_and_validation 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.

renonce 3y ago

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?

jl6 3y ago

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

deleted 3y ago
[deleted]
slau 3y ago
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.
H8crilA 3y ago
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.
- panzi 3y ago
  I wonder, given the current rate of development when will there be the first collision in the hashes of the Linux kernel git repository. Wait, did git finish the switch to SHA-256 or is it still using SHA-1. Googling... all I can find suggests that everyone is still using it with SHA-1 and SHA-256 repos aren't compatible with SHA-1 repos (whatever that means exactly).
  - CuriousCosmic 3y ago
    So tldr is "it's in progress". You can use SHA-256 in production. And you can convert SHA-1 repos into SHA-256 repos. However: - SHA-1 repos are not compatible with SHA-256 repos so you can't mix and match the trees (i.e. a SHA-256 fork couldn't upstream their commits to a SHA-1 repo). - The conversion path from SHA-1 to SHA-256 will break all GPG signatures on the repo. - There may be breaking changes to the SHA-256 repository implementation in the future however those changes will be guaranteed to come with an upgrade path for any users of the existing SHA-256 implementation. So it's viable as an option but it's by no means "blessed" like the existing SHA-1 impl is.

popol12 3y ago

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.

Karliss 3y ago
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)).
- rowbin 3y ago
  But your are going backwards though. You have a sha-256 value and want to find an input with the same result. But this input again has to be a sha-256 result and you need to find an input for that as well, right? This would only work if you have the intermediate sha-256 value, that produces the final sha-256 or you can find a collision that itself is a sha-256 value.
  - glandium 3y ago
    Going backwards, as you say, is called a pre-image attack. That's different from a collision attack, which is generating two inputs with the same hash. Pre-image attacks are MUCH more difficult. How much more? well, MD-5 is considered broken, and yet, there isn't one for it.
    - H8crilA 3y ago
      Pre-image is approximately "twice as difficult" as a collision. A generic attack on, say, a 256 bit long hash function takes 2^128 time to find a collision, but 2^256 time to find a preimage. And like you say, this also shows up in practice: both MD-5 and SHA-1 are completely broken when it comes to collision resistance, but both are (probably) still OK for preimage resistance. I would still not recommend either of them for anything.

lifthrasiir 3y ago

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 https://bsky.app/profile/retr0.id/post/3konobbmf6o2a [1] https://eprint.iacr.org/2024/349.pdf https://eprint.iacr.org/2024/349.pdf

wongarsu 3y ago
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.
- egberts1 3y ago
  Better off with SHAKE256: none of that "oops, I went with easier SHA3-224", plus SHAKE256 is faster.

0x073 3y ago

Good that git still use sha1 ;)

deleted 3y ago
[deleted]
hot_gril 3y ago
Good old MDA4. Nothing beats that.
hn_p4ttern 3y ago
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.
- chasil 3y ago
  Doesn't it also have to be the same size in bytes?
  - deleted 3y ago
    [deleted]
- dist-epoch 3y ago
  Due to the way hashing works, any change is equivalent to any other one for the purpose of finding a collision. So you can just alter the formatting to a different convention, alter spacing, add a comment, reorder equivalent lines. So you can insert a comment and continue altering it until you get a match by varying the line breaking, switching words with synonyms.
- keybored 3y ago
  I believe there is one more step. You have to somehow get the collision into the repository. Because if you have <hash> in your own repo and pull something from another repo with the same <hash>, the remote changes will not overwrite your blob for <hash> (it will stay the same). Or at least that’s what I seem to remember from something that Torvalds wrote.