7 ms·

The severity between the preimage attacks depends on context. For Git, for example, a first-preimage attack won't buy you anything, but a second-preimage could

The severity between the preimage attacks depends on context. For Git, for example, a first-preimage attack won't buy you anything, but a second-preimage could be potentially devastating depending on how lucky you get. If Mallory wanted to make it look like you signed a document you didn't, second-preimage would be devestating. And with the demonstration of two PDFs sharing the same hash, this is a pretty severe one: many PGP signatures, for example, still use SHA-1. But even so, you could take some signature from any point in the past.

gliptic 10y ago
If you can do a first-preimage attack, you can do a second-preimage attack. Just hash the document you have. Therefore a first-preimage attack is strictly more severe.
- mikegerwitz 10y ago
  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]
- xamuel 10y ago
  mikegerwitz is technically right. As an illuminating example, consider a hash-algorithm in which there's at least one hash that occurs precisely once. Then a 2nd-preimage attack is formally impossible no matter how much computational power you have (assuming by "second" you meant "distinct second"). But a 1st-preimage attack is formally possible.
  - lisper 10y ago
    One of the requirements for a hash to be cryptographically secure is that all possible values are equally likely. So yes, it is possible (in fact trivial) to construct a hash of the sort you describe, but such a hash would not be cryptographically secure to begin with.
    - Dylan16807 10y ago
      It's easier to use and to reason about a uniform hash, but you can design a secure system with a non-uniform hash. I'd be willing to bet that an altered version of SHA3-256 that replaces four bits in the middle with length%16 is better for most purposes than SHA256, despite being non-uniform.
  - tlb 10y ago
    A 'good' hash function (exhibiting uniformity) that converts arbitrary-sized documents to finite-sized hashes should not have any hashes that occur precisely once. This can occur with ill-conceived hash functions, for example if it bundles the length of the document with the hash, so there would be only 256 distinct hashes with length=1.
  - gliptic 10y ago
    For that to be the case, in real hash functions, it would require you to be constrained to a certain number of possible preimages, not too many more than the number of possible hashes, so that it's likely that H^-1(H(x)) = x but there can still be a distinct y such that H(y) = H(x). So I concede that this could be the case under very specific circumstances, but I doubt it makes much difference in the real world.
- ddlatham 10y ago
  Not if the second-preimage attack is properly defined to find a second distinct document with the same hash as the first.
  - eridius 10y ago
    If you can do a first-preimage attack, then just keep doing it until you get a distinct document. I'm not sure what sort of first-preimage attack you have in mind that is only capable of producing a single preimage for any hash.
    - ddlatham 10y ago
      Since the parent was claiming that first-preimage attacks were strictly more severe, which seems to be a theoretical claim for all possible first-preimage attacks, I was pointing out that doesn't necessarily hold. First-preimage attacks are not guaranteed a priori to be able to produce multiple distinct documents for a given hash.
      - eridius 10y ago
        I think the argument here is twofold: 1) If you have some first-preimage attack against a hash, that attack can probably be "continued" such that it produces multiple preimages. 2) Even if your attack can only ever produce one preimage, since there's an infinite number of documents that can produce the same hash, it's vanishingly unlikely that your attack will produce the exact preimage that you already have (note: this is assuming a cryptographically secure hash, where all outputs are equally likely). Therefore, even if you can only get one preimage, it's still almost certainly a second preimage.
petertodd 10y ago
Git's workflow makes first-preimage attacks dangerous, because a mallicious third-party may submit a pull-req to your repo that contains files for which they've pre-generated a collision: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-February/013600.html https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017... Git is vulnerable to SHA1 collisions in standard development workflows.

gliptic 10y ago

If you can do a first-preimage attack, you can do a second-preimage attack. Just hash the document you have. Therefore a first-preimage attack is strictly more severe.

mikegerwitz 10y ago
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]
xamuel 10y ago
mikegerwitz is technically right. As an illuminating example, consider a hash-algorithm in which there's at least one hash that occurs precisely once. Then a 2nd-preimage attack is formally impossible no matter how much computational power you have (assuming by "second" you meant "distinct second"). But a 1st-preimage attack is formally possible.
- lisper 10y ago
  One of the requirements for a hash to be cryptographically secure is that all possible values are equally likely. So yes, it is possible (in fact trivial) to construct a hash of the sort you describe, but such a hash would not be cryptographically secure to begin with.
  - Dylan16807 10y ago
    It's easier to use and to reason about a uniform hash, but you can design a secure system with a non-uniform hash. I'd be willing to bet that an altered version of SHA3-256 that replaces four bits in the middle with length%16 is better for most purposes than SHA256, despite being non-uniform.
- tlb 10y ago
  A 'good' hash function (exhibiting uniformity) that converts arbitrary-sized documents to finite-sized hashes should not have any hashes that occur precisely once. This can occur with ill-conceived hash functions, for example if it bundles the length of the document with the hash, so there would be only 256 distinct hashes with length=1.
- gliptic 10y ago
  For that to be the case, in real hash functions, it would require you to be constrained to a certain number of possible preimages, not too many more than the number of possible hashes, so that it's likely that H^-1(H(x)) = x but there can still be a distinct y such that H(y) = H(x). So I concede that this could be the case under very specific circumstances, but I doubt it makes much difference in the real world.
ddlatham 10y ago
Not if the second-preimage attack is properly defined to find a second distinct document with the same hash as the first.
- eridius 10y ago
  If you can do a first-preimage attack, then just keep doing it until you get a distinct document. I'm not sure what sort of first-preimage attack you have in mind that is only capable of producing a single preimage for any hash.
  - ddlatham 10y ago
    Since the parent was claiming that first-preimage attacks were strictly more severe, which seems to be a theoretical claim for all possible first-preimage attacks, I was pointing out that doesn't necessarily hold. First-preimage attacks are not guaranteed a priori to be able to produce multiple distinct documents for a given hash.
    - eridius 10y ago
      I think the argument here is twofold: 1) If you have some first-preimage attack against a hash, that attack can probably be "continued" such that it produces multiple preimages. 2) Even if your attack can only ever produce one preimage, since there's an infinite number of documents that can produce the same hash, it's vanishingly unlikely that your attack will produce the exact preimage that you already have (note: this is assuming a cryptographically secure hash, where all outputs are equally likely). Therefore, even if you can only get one preimage, it's still almost certainly a second preimage.

petertodd 10y ago

Git's workflow makes first-preimage attacks dangerous, because a mallicious third-party may submit a pull-req to your repo that contains files for which they've pre-generated a collision: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-February/013600.html https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017... Git is vulnerable to SHA1 collisions in standard development workflows.