>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
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.
There is a pre-image attack for MD5, it's just not considered good enough to be practical. Quoting Wikipedia:
> In April 2009, an attack against MD5 was published that breaks MD5's preimage resistance. This attack is only theoretical, with a computational complexity of 2123.4 for full preimage.
Yes, but that's very little improvement over the generic 2^128 attack - trying random messages until one happens to match the target hash. The attack quoted by Wikipedia achieves only 4.6 bits of speedup (note that it's 2^123.4, not 2134.4 :) ). There are attacks of this sort against many cryptographic primitives, including AES, where you can gain just a few bits over the generic / brute force attacks.
Now, I find a collision string SS (of length 128 bits, like an MD5 hash), where MD5(SS) == Y
Then I find a collision string SSS (this time, length doesn't matter), where MD5(SSS) == SS
Then we have MD5(MD5(SSS)) == Y, which was only twice harder than finding a single MD5 collision.
Could someone explain what is wrong with my reasoning ?
Edit: Oh okay, got it, when we say "MD5 is broken, it's possible to do a collision attack", what we mean is that we can easily find 2 strings S1 and S2 where MD5(S1) == MD5(S2)
But S1 and S2 and found randomly, we don't have a way to find a string S3 where MD5(S3) == Y for any Y value (that is what we call a pre-image attack, not a collision attack)
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.
Where on earth did you get this idea from? What is a "generic attack"? How could you turn a collision somehow into a pre-image attack? How is many orders of magnitude "twice" ?
You can find this in any introduction to cryptography textbook/course. "Generic attack" is a common term for "just use brute force" [1]. It's called "generic" because it works regardless of the implementation of the primitive. For pre-image resistance the generic attack just hashes messages until it finds the right image, for collision resistance you can get a quadratic speedup via the so called birthday problem / birthday attack [1][2], where you keep hashing messages and storing the hashes until any two of the messages happen to hash to the same value.
>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