5 ms·

Getting the first-preimage of the document and hashing that same preimage just gives you back the original hash---it's like an identity function. It doesn't gi

Getting the first-preimage of the document and hashing that same preimage just gives you back the original hash---it's like an identity function. It doesn't give you a second document. Edit: I misinterpreted your message. I added "same" above to convey what I thought you were saying.

palunon 10y ago
But if you have a first preimage atack, you could then use it on the hash to get (presumably) another document...
- mikegerwitz 10y ago
  A first-preimage attack just means you have H(P), find preimage P (where H is SHA1). If you found preimage P and wanted another document that hashes into it (so, H(P) = H(P')), you'd have to perform a second-preimage attack and brute-force one. An "ideal" hash function is one where the only way to compute a second-preimage is through brute force. Due to the pidgeonhole principle, there will always be a second preimage---it's just whether it's computational feasible to compute it.
  - eridius 10y ago
    > Due to the pidgeonhole principle, there will always be a second preimage It's trivial to construct a hash function where this isn't true. However, it should be true for any cryptographically secure hash.
Gankro 10y ago
You seem to be mistaking or misreading something here. * Collision attack: find X and Y such that hash(X) = hash(Y) * Second-preimage: given X, find Y such that hash(X) = hash(Y) * First-preimage: given hash(X), find Y such that hash(X) = hash(Y) > If you have an encrypted message that you hashed/signed _before_ encrypting, and Eve wants to know what you said, first-preimage would be worse, and second-preimage wouldn't buy you anything. first-preimage doesn't do anything here. It gets you some text that matches the hash. It's overwhelmingly unlikely to be the original message, and if it's not the exact original message, it won't have any similarity to it. Unless you can enumerate all hash collisions for a value efficiently, which is a much a stronger claim, this isn't any better than brute-force guessing the text. > Getting the preimage of the document and hashing that preimage just gives you back the original hash---it's like an identity function. It doesn't give you a second document. The second-preimage attack supposes you have X, the first-preimage attack supposes you have hash(X). If "all" you have is a first-preimage attack, then it's trivial convert it into a second-preimage attack. You hash(X) and feed it into your attack.
- ddlatham 10y ago
  You're missing something in your definition of a second-preimage attack, which is that Y != X.
  - Gankro 10y ago
    Ah good point. It could be that the first-preimage attack gets you exactly X, in which case it fails to handle second-preimage. I would expect this to be incredibly unlikely (especially since they seem to generally involve generating some random garbage). I would also expect most first-preimage attacks have a way to "continue" to a third value, eventually.
  - shawabawa3 10y ago
    That's kind of implicit. If X = Y, it's not an attack, it's the primary purpose of hashing
- deleted 10y ago
  [deleted]

palunon 10y ago

But if you have a first preimage atack, you could then use it on the hash to get (presumably) another document...

mikegerwitz 10y ago
A first-preimage attack just means you have H(P), find preimage P (where H is SHA1). If you found preimage P and wanted another document that hashes into it (so, H(P) = H(P')), you'd have to perform a second-preimage attack and brute-force one. An "ideal" hash function is one where the only way to compute a second-preimage is through brute force. Due to the pidgeonhole principle, there will always be a second preimage---it's just whether it's computational feasible to compute it.
- eridius 10y ago
  > Due to the pidgeonhole principle, there will always be a second preimage It's trivial to construct a hash function where this isn't true. However, it should be true for any cryptographically secure hash.

Gankro 10y ago

You seem to be mistaking or misreading something here. * Collision attack: find X and Y such that hash(X) = hash(Y) * Second-preimage: given X, find Y such that hash(X) = hash(Y) * First-preimage: given hash(X), find Y such that hash(X) = hash(Y) > If you have an encrypted message that you hashed/signed _before_ encrypting, and Eve wants to know what you said, first-preimage would be worse, and second-preimage wouldn't buy you anything. first-preimage doesn't do anything here. It gets you some text that matches the hash. It's overwhelmingly unlikely to be the original message, and if it's not the exact original message, it won't have any similarity to it. Unless you can enumerate all hash collisions for a value efficiently, which is a much a stronger claim, this isn't any better than brute-force guessing the text. > Getting the preimage of the document and hashing that preimage just gives you back the original hash---it's like an identity function. It doesn't give you a second document. The second-preimage attack supposes you have X, the first-preimage attack supposes you have hash(X). If "all" you have is a first-preimage attack, then it's trivial convert it into a second-preimage attack. You hash(X) and feed it into your attack.

ddlatham 10y ago
You're missing something in your definition of a second-preimage attack, which is that Y != X.
- Gankro 10y ago
  Ah good point. It could be that the first-preimage attack gets you exactly X, in which case it fails to handle second-preimage. I would expect this to be incredibly unlikely (especially since they seem to generally involve generating some random garbage). I would also expect most first-preimage attacks have a way to "continue" to a third value, eventually.
- shawabawa3 10y ago
  That's kind of implicit. If X = Y, it's not an attack, it's the primary purpose of hashing
deleted 10y ago
[deleted]