4 ms·

> 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

by nayuki 4y ago

> 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 preimage attack. SHA-1 is broken for collision, not preimage or second preimage. ---- Please see this section for the 3 core properties of a cryptographic hash function: https://en.wikipedia.org/wiki/Cryptographic_hash_function#Properties https://en.wikipedia.org/wiki/Cryptographic_hash_function#Pr... . They appear similar but are very different. In a collision attack, you are allowed to manipulate both message0 and message1 as much as you like until hash(message0) = hash(message1). Because the attacker has so much choice, this is the hardest attack to defend against, and this is how almost every hash function has failed. In a second preimage attack, you are given a target message0 (which you cannot change), and you can manipulate message1 as much as you want until hash(message1) = hash(message0). This would be like making a new SSL certificate with the same hash as another publicly available certificate belonging to someone else that you cannot modify. In a preimage attack, you are given a target hash value h (which was generated from some secret message0 that is not known to you), and you can manipulate message1 as much as you want until hash(message1) = h. This would be like reversing a password hash back to a password.

lilyball 4y ago
In general, is it harder to do preimage attacks or second preimage attacks?
- nayuki 4y ago
  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.
  - p1necone 4y ago
    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.
- mtlmtlmtlmtl 4y ago
  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).
  - lilyball 4y ago
    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?
    - mtlmtlmtlmtl 4y ago
      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.
    - TheDong 4y ago
      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.
saghm 4y ago
>> 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.
zauguin 4y ago
> > 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.
- nayuki 4y ago
  You're right, thanks. I went ahead and fixed my post.
anamexis 4y ago
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.
cipherboy 4y ago
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.

by nayuki 4y ago

lilyball 4y ago

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

nayuki 4y ago
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.
- p1necone 4y ago
  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.
mtlmtlmtlmtl 4y ago
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).
- lilyball 4y ago
  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?
  - mtlmtlmtlmtl 4y ago
    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.
  - TheDong 4y ago
    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.

saghm 4y ago

>> 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.

zauguin 4y ago

> > 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.

nayuki 4y ago
You're right, thanks. I went ahead and fixed my post.

anamexis 4y ago

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.

cipherboy 4y ago

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.