Hacker News Reader

>> Because MD5 is a relatively weak algorithm, it is possible to create deliberate hash "collisions". That is, take some data and manipulate it until it has the same MD5 as a different piece of data.

> First sentence is true. Second sentence is false - that's called a preimage attack. MD5 is broken for collisions, not preimage or second preimage.

>> It is somewhat cheap and easy to produce a file with a specific SHA-1 hash.

> No, that's called a second preimage attack. SHA-1 is broken for collision, not preimage or second preimage

To use an analogy people might be familiar with, it's like the birthday paradox; you can find two people with the same birthday without looking too hard, but it's a lot more work to start with one person's birthday and then try to find someone else with that exact birthday. Right now, we can fairly easily find pairs of MD5/SHA1 hashes that are the same, but it's not currently feasible to start with one input to the hash function and then find some different input that produces the exact same hash.

And the OP's citations even make this clear.

From the MD5 citation:

> Q: Is it possible to make a file get an arbitrary MD2/MD4/MD5/MD6/SHA1/SHA2/SHA3, or the same hash as another file?

> A: No.

From the SHA-1 citation:

> "Finding a practical collision attack breaks the hash function badly of course, but the actual damage that can be done with such a collision is somewhat limited as the attacker will have little to no control on the actual data that collides," Thomas Peyrin, one of the researchers told ZDNet via email over the weekend.

> > Because MD5 is a relatively weak algorithm, it is possible to create deliberate hash "collisions". That is, take some data and manipulate it until it has the same MD5 as a different piece of data. > > First sentence is true. Second sentence is false - that's called a preimage attack. MD5 is broken for collisions, not preimage or second preimage. > > > It is somewhat cheap and easy to produce a file with a specific SHA-1 hash. > > No, that's called a second preimage attack. SHA-1 is broken for collision, not preimage or second preimage.

I think that's backwards. Producing a file with a specific SHA-1 hash is a preimage attack while producing a file with the same hash as another file is a second preimage attack.

Not that it matters for SHA-1 where both aren't broken yet.

You're right, thanks. I went ahead and fixed my post.

This isn't fair to the OP.

> > That is, take some data and manipulate it until it has the same MD5 as a different piece of data.

> Second sentence is false - that's called a preimage attack.

It's actually rather poorly specified description of either, tbh. I don't think this is a charitable read of the sentence.

Formally, a second preimage game has one party (the adversary to your algorithm) generate some data and and a second party (your algorithm) generate some other different data, with a hash that matches that of the unmodified data chosen by the first party.

A collision attack lets your algorithm choose both pieces of data, and the adversary simply verifies the hashes match.

Most collision attacks, going back to Wang's original attack on md5, generate a random string and manipulate it until certain preconditions hold and hope that its pair's hash matches, and otherwise try again until one matches. (Where pair is defined as some inversion under the constraint system -- usually the same block with certain bits flipped).

But that description sounds awfully like the original vague description. :-)

Edit to add: the OP is misinformed about preimage attacks being easy, outside of specific scenarios like rainbow tables and the like. For the general case of arbitrary hashes it is hard.

In general, is it harder to do preimage attacks or second preimage attacks?

In general, preimage would be harder than second preimage because you have less information(just the hash of message0) whereas for second preimage you know the message and the hash(because you can obviously compute the latter from the former).

What about cases where the hash output isn't properly distributed across all possible outputs. Could some specific hash outputs be easier to find preimages for, and therefore have weaker preimage resistance? The idea here being that if you take some arbitrary message it's unlikely to produce one of these weaker hashes, but by simply selecting a weak hash directly you can find a message for it.

Or is this just too contrived and no function ends up working this way in practice?

I think in these attacks are usually talked about in terms of an arbitrary, not specially selected, message / hash.

When wikipedia says "Given a hash value h, it should be difficult to find ....", "h" there is any arbitrary hash.

For example, I can tell you the md5 preimage for 5f4dcc3b5aa765d61d8327deb882cf99. Google can tell you that one. That doesn't mean there's a real preimage attack for md5 since given any arbitrary h, I cannot tell you what hashes to it.

> The idea here being that if you take some arbitrary message it's unlikely to produce one of these weaker hashes, but by simply selecting a weak hash directly you can find a message for it.

You don't get to select the weak hash, like "5f4dcc3b5aa765d61d8327deb882cf99" in this case, to prove you have a preimage attack.

What's the threshold for this though? If you choose the hash and I have to produce the preimage, that scenario means you could always pick a "strong" hash, but if e.g. 50% of hashes are "weak" hashes, then a completely randomly selected hash would have a 50% chance of being "weak" and therefore attackable. If I can break 50% of randomly-selected hashes, does that count? Or would it have to be more like producing a preimage for hashes generated by randomly-selected inputs (and therefore the "weak" hashes in this scenario would be unlikely to be produced).

Well, theoretically, I'm sure it's possible to construct it that way, but I think your intuition that this doesn't happen in practice is correct.

I don't have any justification for that though other than it would seem like a strange thing in an algorithm designed to be resistant to these things for the output distribution to be skewed like that.

Edit:

Thinking about it some more, if some inputs give weaker(to preimage attack) hashes, then for those specific inputs, second preimage could only possibly be slower by the extra time needed to compute the hash and do the preimage attack. Which is generally insignificant next to the time it takes to do the preimage attack.

I suspect second preimage attacks are easier because with the given message0, you can see the internal state of the hash function on message0 while you tweak your message1. Whereas in preimage attacks, you are only given the final hash.

Yeah - I would imagine with some hash functions it doesn't make much difference whether you have access to message0, or just the hash of message0. Whereas with other hash functions it might make a lot of difference.

It's never going to be better to only have the hash vs having the message itself though.