Hacker News Reader

Comment by glandium | Hacker News Reader

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.

View on HN

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.

Let's say I have a string S.

MD5(MD5(S)) = Y

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.

[1] https://crypto.stackexchange.com/questions/19194/is-there-an...

[2] https://en.wikipedia.org/wiki/Birthday_problem

I don't think that "look, raw brute force has this property" is at all useful in this context where you'd obviously actually compare a real attack not brute force. There's no reason to believe (and every reason not to) that the same property somehow applies.

That Stack Exchange answer also immediately set off alarm bells in my head because it pretends to be entirely generic, but the obvious thing to do with entirely generic cryptographic intuitions is apply them to the One Time Pad and check their answers work. This intuition doesn't work. Even if you could try all the possible keys you learn nothing, because of the hand-waving about "plausible" plaintext.

Birthday attach is a real attack and often useful in practice. "Just use brute force" is a huge oversimplification, but the SO link explains it in more detail.

One time pad is not a hash algorithm so obviously a generic attack on a collision function doesn't apply to it.

twice as difficult ? It doesn't match what you say after that

2²⁵⁶ = 2¹²⁸ * 2¹²⁸

So, isn't it rather 2¹²⁸ times more difficult ?

Security is typically measured in bits. But yes you're right, maybe I should have written "square as difficult" to be more clear :)

Reply on news.ycombinator.com