First practical SHA-256 collision for 31 steps. fse2024
1–10 of 68 posts
Re: First practical SHA-256 collision for 31 steps. fse2024
#2I assume “steps” here means rounds? For reference, standard SHA-256 is 64 rounds.
Re: First practical SHA-256 collision for 31 steps. fse2024
#3I assume “steps” here means rounds? For reference, standard SHA-256 is 64 rounds.
[deleted]
Re: First practical SHA-256 collision for 31 steps. fse2024
#4I assume “steps” here means rounds? For reference, standard SHA-256 is 64 rounds.
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.
Re: First practical SHA-256 collision for 31 steps. fse2024
#5Bitcoin 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.
Re: First practical SHA-256 collision for 31 steps. fse2024
#6It 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
(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
Re: First practical SHA-256 collision for 31 steps. fse2024
#7Bitcoin 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.
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)).
Re: First practical SHA-256 collision for 31 steps. fse2024
#8Bitcoin 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.
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)).
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.
Re: First practical SHA-256 collision for 31 steps. fse2024
#9I assume “steps” here means rounds? For reference, standard SHA-256 is 64 rounds.
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.
Re: First practical SHA-256 collision for 31 steps. fse2024
#10Earlier quoted context omitted.
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)).
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.
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.