3 ms·

>However, given an existing file and hence its hash, it is not possible, as far as anyone knows, to generate a second file with that same hash. Interesting...I

by jtaft 8y ago

>However, given an existing file and hence its hash, it is not possible, as far as anyone knows, to generate a second file with that same hash. Interesting...I thought google did exactly this in 2017. Although, they controlled the PDF prefix. https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html https://security.googleblog.com/2017/02/announcing-first-sha...

geofft 8y ago
Yeah, this is the difference between a collision and a preimage attack. A collision is, given a hash function, come up with two documents with the same hash, but you can control both documents. A preimage attack is, given a hash function and one document (or one hash), find another document with the same hash. That's much harder - you don't have the ability to force the algorithm's internal state into something convenient. A preimage attack is what you worry about if you think the person giving you the signature might be untrustworthy, e.g., they're currently promising one thing but they might swap it out with something else later. A collision attack is what you worry about even if you don't think the person giving you the signature is untrustworthy and you're expecting someone else to swap out the document before it gets to you. So there are a good handful of scenarios where you don't care about preimage attacks but you do care about collisions - e.g., if Microsoft is signing Windows Update files, presumably they don't need to conduct a preimage attack to send you a malicious update, they can just directly sign a malicious update. But you don't want other people sending you malicious updates that appear to be signed by Microsoft.
- jtaft 8y ago
  Thanks for the clarification. I thought Columbia's definition of a pre-image attack was incorrect, due to the vagueness of the verbiage "existing file". Ie, I considered the chosen document created by google as an "existing file".
- hcs 8y ago
  Is your second paragraph reversed? It seems like a collision is where you'd worry about someone having prepared two documents that they could swap.
  - geofft 8y ago
    Yes, you're right, sorry, I completely swapped the two terms in that entire paragraph.
- Moodles 8y ago
  > A preimage attack is what you worry about if you think the person giving you the signature might be untrustworthy, e.g., they're currently promising one thing but they might swap it out with something else later. A collision attack is what you worry about even if you don't think the person giving you the signature is untrustworthy and you're expecting someone else to swap out the document before it gets to you You mean vice versa right? Untrustworthy person: could make a collision before giving you the input and mess you around. Trustworthy person doesn't do that (because they are trustworthy). But someone might find a second pre-image attack and do it later on
  - geofft 8y ago
    Yes, sorry. Please swap "preimage attack" and "collision" in that entire paragraph: I meant to say there were cases where you don't care about a collision (as demonstrated for SHA-1) but you do care about a preimage (not yet demonstrated, but certainly a risk).
tialaramex 8y ago
Nope, as it says right at the top, that's just a Collision. In metaphor terms, that CWI Amsterdam + Google announcement is about them making two documents that are different but which you can't tell apart (using SHA1). They could fool you into thinking you had one when it was really the other. But, for a Bad Guy this is only useful under very specific circumstances. If a shady guy offers you what seems to be... his own self-published novel "Interdimensional Hat Monkeys 4" you don't care whether it's the real thing or a "fake", who cares? Whereas Second Pre-Image lets you find a convincing forgery for any document at all. Now the shady guy offers you a suitcase full of what appear to be genuine $20 bills. It really matters if those are fake! A suitcase full of real ones are worth a lot of money, whereas a suitcase of fakes is a recipe for jail time. Online, the main application of Collision is obtain bogus certificates. You make two documents A and B, A is an ordinary seeming true statement which you can get certified, while B is something outrageous nobody would certify, but you have chosen them to have the same SHA1. If the Certificate signatures use SHA1, you can get a CA to sign document A, then just attach that signature to document B. So that's why SHA1 was not allowed for new certificates since 2016. Old ones don't matter because bad guys can't travel back in time and make old documents to try this trick on them. We did have some other counter-measures, to make this trick impractical for real bad guys in the Web PKI. Most important was, we required the CA to choose random serial numbers (that's why the "serial number" on your certificate is just random and doesn't gradually increase in newer certificates) and this means a bad guy applying for a certificate can't guess what the serial number will be in advance, which makes it harder to come up with the pair of documents.
- comex 8y ago
  To further clarify: > You make two documents A and B, A is an ordinary seeming true statement which you can get certified, while B is something outrageous nobody would certify, This does imply that the attacker only has limited choice with respect to A and B. They can’t just be random bytes: A has to be not only a syntactically valid X.509 certificate, but one that a legitimate CA will generate (based on the attacker’s inputs in a Certificate Signing Request) and sign, while B has to be a syntactically valid certificate which is useful to the attacker to have a signature for. However, in practice, collision attacks tend to let the attacker arbitrarily pick parts of both messages, while other parts are chosen by the algorithm and do look like a large amount of random binary gunk. In this case, most of the fields of an X.509 certificate are not adequately controllable and/or not large enough to stick the gunk into, but there’s one exception: the public key field, which just happens to be a large blob of binary data that’s chosen by the attacker and expected to look random. So that’s what was used, in the famous proof-of-concept MD5 certificate forgery from 2006 that resulted in the random serial number requirement being added. More details: https://blog.cloudflare.com/why-its-harder-to-forge-a-sha-1-certificate-than-it-is-to-find-a-sha-1-collision/ https://blog.cloudflare.com/why-its-harder-to-forge-a-sha-1-...

by jtaft 8y ago

geofft 8y ago

Yeah, this is the difference between a collision and a preimage attack. A collision is, given a hash function, come up with two documents with the same hash, but you can control both documents. A preimage attack is, given a hash function and one document (or one hash), find another document with the same hash. That's much harder - you don't have the ability to force the algorithm's internal state into something convenient. A preimage attack is what you worry about if you think the person giving you the signature might be untrustworthy, e.g., they're currently promising one thing but they might swap it out with something else later. A collision attack is what you worry about even if you don't think the person giving you the signature is untrustworthy and you're expecting someone else to swap out the document before it gets to you. So there are a good handful of scenarios where you don't care about preimage attacks but you do care about collisions - e.g., if Microsoft is signing Windows Update files, presumably they don't need to conduct a preimage attack to send you a malicious update, they can just directly sign a malicious update. But you don't want other people sending you malicious updates that appear to be signed by Microsoft.

jtaft 8y ago
Thanks for the clarification. I thought Columbia's definition of a pre-image attack was incorrect, due to the vagueness of the verbiage "existing file". Ie, I considered the chosen document created by google as an "existing file".
hcs 8y ago
Is your second paragraph reversed? It seems like a collision is where you'd worry about someone having prepared two documents that they could swap.
- geofft 8y ago
  Yes, you're right, sorry, I completely swapped the two terms in that entire paragraph.
Moodles 8y ago
> A preimage attack is what you worry about if you think the person giving you the signature might be untrustworthy, e.g., they're currently promising one thing but they might swap it out with something else later. A collision attack is what you worry about even if you don't think the person giving you the signature is untrustworthy and you're expecting someone else to swap out the document before it gets to you You mean vice versa right? Untrustworthy person: could make a collision before giving you the input and mess you around. Trustworthy person doesn't do that (because they are trustworthy). But someone might find a second pre-image attack and do it later on
- geofft 8y ago
  Yes, sorry. Please swap "preimage attack" and "collision" in that entire paragraph: I meant to say there were cases where you don't care about a collision (as demonstrated for SHA-1) but you do care about a preimage (not yet demonstrated, but certainly a risk).

tialaramex 8y ago

Nope, as it says right at the top, that's just a Collision. In metaphor terms, that CWI Amsterdam + Google announcement is about them making two documents that are different but which you can't tell apart (using SHA1). They could fool you into thinking you had one when it was really the other. But, for a Bad Guy this is only useful under very specific circumstances. If a shady guy offers you what seems to be... his own self-published novel "Interdimensional Hat Monkeys 4" you don't care whether it's the real thing or a "fake", who cares? Whereas Second Pre-Image lets you find a convincing forgery for any document at all. Now the shady guy offers you a suitcase full of what appear to be genuine $20 bills. It really matters if those are fake! A suitcase full of real ones are worth a lot of money, whereas a suitcase of fakes is a recipe for jail time. Online, the main application of Collision is obtain bogus certificates. You make two documents A and B, A is an ordinary seeming true statement which you can get certified, while B is something outrageous nobody would certify, but you have chosen them to have the same SHA1. If the Certificate signatures use SHA1, you can get a CA to sign document A, then just attach that signature to document B. So that's why SHA1 was not allowed for new certificates since 2016. Old ones don't matter because bad guys can't travel back in time and make old documents to try this trick on them. We did have some other counter-measures, to make this trick impractical for real bad guys in the Web PKI. Most important was, we required the CA to choose random serial numbers (that's why the "serial number" on your certificate is just random and doesn't gradually increase in newer certificates) and this means a bad guy applying for a certificate can't guess what the serial number will be in advance, which makes it harder to come up with the pair of documents.

comex 8y ago
To further clarify: > You make two documents A and B, A is an ordinary seeming true statement which you can get certified, while B is something outrageous nobody would certify, This does imply that the attacker only has limited choice with respect to A and B. They can’t just be random bytes: A has to be not only a syntactically valid X.509 certificate, but one that a legitimate CA will generate (based on the attacker’s inputs in a Certificate Signing Request) and sign, while B has to be a syntactically valid certificate which is useful to the attacker to have a signature for. However, in practice, collision attacks tend to let the attacker arbitrarily pick parts of both messages, while other parts are chosen by the algorithm and do look like a large amount of random binary gunk. In this case, most of the fields of an X.509 certificate are not adequately controllable and/or not large enough to stick the gunk into, but there’s one exception: the public key field, which just happens to be a large blob of binary data that’s chosen by the attacker and expected to look random. So that’s what was used, in the famous proof-of-concept MD5 certificate forgery from 2006 that resulted in the random serial number requirement being added. More details: https://blog.cloudflare.com/why-its-harder-to-forge-a-sha-1-certificate-than-it-is-to-find-a-sha-1-collision/ https://blog.cloudflare.com/why-its-harder-to-forge-a-sha-1-...