3 ms·

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.
    - lilyball 4y ago
      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).

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.
  - lilyball 4y ago
    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).