5 ms·

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,

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

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