5 ms·
This point seems to be getting re-hashed (no pun intended) a lot, so here's a quick summary: there are three kinds of attacks on cryptographic hashes: collision
by lisper 10y ago
This point seems to be getting re-hashed (no pun intended) a lot, so here's a quick summary: there are three kinds of attacks on cryptographic hashes: collision attacks, second-preimage attacks, and first-preimage attacks.
Collision attack: find two documents with the same hash. That's what was done here.
Second-preimage attack: given a document, find a second document with the same hash.
First-preimage attack: given an arbitrary hash, find a document with that hash.
These are in order of increasing severity. A collision attack is the least severe, but it's still very serious. You can't use a collision to compromise existing certificates, but you can use them to compromise future certificates because you can get a signature on one document that is also valid for a different document. Collision attacks are also stepping stones to pre-image attacks.
UPDATE: some people are raising the possibility of hashes where some values have 1 or 0 preimages, which makes second and first preimage attacks formally impossible. Yes, such hashes are possible (in fact trivial) to construct, but they are not cryptographically secure. One of the requirements for a cryptographically secure hash is that all possible hash values are (more or less) equally likely.
- mikegerwitz 10y agoThe 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 agoIf 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 agoGetting 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 agoBut if you have a first preimage atack, you could then use it on the hash to get (presumably) another document...
- mikegerwitz 10y agoA 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 agoYou 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.
- petertodd 10y agoGit'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.
- tripzilch 10y ago> This point seems to be getting re-hashed (no pun intended) why not??
- deleted 10y ago[deleted]
- yuhong 10y agoAlso the difference between identical and chosen prefix attacks too (this attack is identical prefix).
- bo1024 10y ago> UPDATE: some people are raising the possibility of hashes where some values have 1 or 0 preimages, which makes second and first preimage attacks formally impossible. Yes, such hashes are possible (in fact trivial) to construct, but they are not cryptographically secure. One of the requirements for a cryptographically secure hash is that all possible hash values are (more or less) equally likely. True, but the main issue with these proposals is that we want hash functions that are much shorter than the original thing being hashed. For instance, we want every string of length one million bits to get hashed down to some string of length 4096. So those 2^4096 short hash strings can't mostly have 1 or 0 pre-images, in fact on average they have to have gazillions of pre-images each.
- andreyf 10y ago> in fact on average they have to have gazillions of pre-images each pretty sure "on average" they have at least a few gazillion orders of magnitude more than a few gazillion pre-images each ;)
- xapata 10y agoYou're saying the average of infinities is a gazillion gazillion? For any hashcode, there are an infinite number of documents that would result in that hashcode.
- andreyf 10y agoNah, way bigger than that. I'm saying 10 times as big as a few gazillion at least a few gazillion times! (key words are "at least")