Re: MD5 collision in X509 certificates
Anne & Lynn Wheeler <[EMAIL PROTECTED]> writes:
>the purpose of a certificate is analogous to the old letters of credit in the
>sailing ship days it supposedly establishes the bonifides of the
>individual in an offline, non-connected world where the relying party has no
>other recourse regarding trust/integrity of the individual that they are
>dealing with.
I ran into an interesting example of the conflict between PKI's almost
completely offline design vs.the almost completely online world recently.
Someone showed me a full-page diagram of their PKI/certificate management
process containing several dozen boxes, a maze of connecting arrows, labels,
references to pages and pages of further explanation, etc etc etc. After
reverse-engineering the process displayed in the diagram over a period of
about quarter of an hour, I simplified the whole thing by drawing a single
line from the top left ("I have someone's public key") to the bottom right
("Ask an online service who it belongs to and whether it's OK to use"),
completely bypassing the morass of PKI in the middle. (This is a bit like the
financial industry use of PKI that Lynn mentioned a while back in which you
throw away everything but the public key and check that directly, because all
the PKI does is get in the way).
At that point the conversation went something like this:
"Why not do it that way then, since that's the end effect anyway?".
"We can't do that. $LARGE_ORGANISATION have spent millions of dollars
setting up their PKI, and they won't allow something that sidesteps it".
"So the only reason the PKI is there is because not having it there would be
an admission of its uselessness?"
"Uhh, yeah".
This leads to the following PKI business model:
1. Spend millions of dollars setting up a PKI.
2. Everyone is forced to use it because not to do so would be a waste of the
setup costs.
3. Profit!
Peter.
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: MD5 collision in X509 certificates
On 3/5/05, [EMAIL PROTECTED] (Anne & Lynn Wheeler) wrote: >The implication is that if i can substitute a public key in some >certificate that attests to represent some other party then it may >be some form of identity theft (fraudulent messages can be created that >otherwise appear to have originated from you ... and validate with the >substituted public key). The other might be elevation of privileges >adding characteristics to a certificate that were otherwise not provided. The real concern, and there is no evidence that it is easy, is that if a certificate is signed using a MD5 hash, and another certificate, with a different (RSA) public key, can be substituted, maintaining the signature, then it will be probable that the new public key will be the product of many primes, and (relatively) easy to factor. If this were possible, it would lead to identity theft. While this scenario is not, as far as I know, easy, it seems to me that it is time to abandon MD5 in signatures. The issues with SHA1 are worrisome, but not yet, IMHO, fatal. However, it would be prudent to plan on moving beyond SHA1 in the near future. All IMHO. Cheers - Bill - Bill Frantz| The first thing you need when | Periwinkle (408)356-8506 | using a perimeter defense is a | 16345 Englewood Ave www.pwpconsult.com | perimeter. | Los Gatos, CA 95032 - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: MD5 collision in X509 certificates
On Sat, Mar 05, 2005 at 09:23:11AM -0700, Anne & Lynn Wheeler wrote: > Victor Duchovni wrote: > >What is the significance of this? It seems I can get a certificate for > >two public keys (chosen, not given) while only proving posession of the > >first. Is there anything else? In what sense is the second public key > >useful to the attacker? > > the purpose of a certificate is analogous to the old letters of credit > in the sailing ship days it supposedly establishes the bonifides of > the individual in an offline, non-connected world where the relying > party has no other recourse regarding trust/integrity of the individual > that they are dealing with. > > [...] I've read very similar posts a few times before, and agree with them all wholeheartedly! My question is however about this specific exposure. This collision is between two keys generated together by the attacker, not someone else's given key and another generated by the attacker. Yes, this allows one to obtain a certificate for a public key whose private key did not sign the CSR, but what does this mean in practice? It appears that neither public key can be used to impersonate anyone else... -- /"\ ASCII RIBBON NOTICE: If received in error, \ / CAMPAIGN Victor Duchovni please destroy and notify X AGAINST IT Security, sender. Sender does not waive / \ HTML MAILMorgan Stanley confidentiality or privilege, and use is prohibited. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: MD5 collision in X509 certificates
Victor Duchovni wrote: What is the significance of this? It seems I can get a certificate for two public keys (chosen, not given) while only proving posession of the first. Is there anything else? In what sense is the second public key useful to the attacker? so three kinds of attacks on certificate contents ... the previously two mentioned * identity theft * privilege escalation the other is possibly by the relying party against the key owner. in the early '90s identity certificates were all the rage. some problems were at the time the certification took place ... it might not be possible for the certification authority to determine all possible kinds of identity information that a relying party (at any point in the future) might require ... so there was a trend to overloading an identity certificate with all possible types of identity information on the off chance that something might be useful to some relying party in the future. this led to increasing realization that such collection of identity information might represent various kinds of privacy violation and you saw some retrenching to relying-party-only certificates in the mid-90s ... misc. relying-party-only certificates only containing an account number to be used in online/real-time transaction (note however, in online/real-time relying-party-only scenario it is also trivial to show that certificates are redundant and superfluous) http://www.garlic.com/~lynn/subpubkey.html#rpo the other thing in the 90s was trying to project a value proposition for certificates. there was a lot of FUD and confusion generated about the value of certificates to the point that it was frequently obscured that it was even necessary to have security and safety around the protection and use of the private key ... and/or that any form of 3-factor authentication was even involved in the access and use of the private key. To this day, you have people writing about using a digital certificate to create a digital signature. So another value representation for digital certificates was that of non-repudiation. basically if the non-repudiation flag in a digital certificate was checked/marked ... then the relying party could assume non-repudiation on the part of the originating party. Again this is a scenario trying to represent the value of a digital certificate in place of the safety and security around the access and use of the private key. So the story given to merchants in the merchant/consumer market place was that the existed circumstances were that in any dispute the burden of proof is on the merchant but the proposal was that if a merchant could produce any certificate (for the originator's public key) that had the non-repudiation flag marked/checked, then the burden of proof (in a dispute) whould shift from the merchant to the consumer. So if that effort had been succesful ... then it would be in the interest of merchants to be able to produce a consumer digital certificate that included the non-repudiation flag (regardless of whether that certificate had been used in the original transaction or not since by definition all burden of proof then is shifted to the consumer). some of this is discussed in various postings regarding finread ... where the EU attempted to dictate some minimum hardware environment that would provide some level of assurance around the access and use of the private key (which helps diffuse the confusion around whether the digital signature value proposition relies solely in the existance of a digital certificate or whether there is some value in controlling the access and use of private keys and it possibly isn't the case that digital signatures are generated by digital certificates): http://www.garlic.com/~lynn/subpubkey.html#finread other past postings on 3-factor authentication http://www.garlic.com/~lynn/subpubkey.html#3factor - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: MD5 collision in X509 certificates
Victor Duchovni wrote: What is the significance of this? It seems I can get a certificate for two public keys (chosen, not given) while only proving posession of the first. Is there anything else? In what sense is the second public key useful to the attacker? the purpose of a certificate is analogous to the old letters of credit in the sailing ship days it supposedly establishes the bonifides of the individual in an offline, non-connected world where the relying party has no other recourse regarding trust/integrity of the individual that they are dealing with. in the PKI/certificate world ... the relying party receives some sort of digitally encrypted/signed information and validates it using the public key presented in the attached certificate. a correctly validation then implies some kind of 3-factor authentication (although the PKI/certificate paradigm tends to totally gloss over this characteristic, instead attempting to focus the communities attention on the value of the certification as opposed to focusing the attention on any possibility/value/trust that some part of 3-factor authentication might have occured). In any case, if the public key (from some source, possibly a certificate) is able to validate the transmission, then the relying party assumes that some portion of 3-factor authentication occured in the access and use of the corresponding private key ... possibly * something you have (private key exclusively in a hardware token) * something you know (hardware token won't work appropriately w/o PIN) * something you are (hardware token requires some biometric) in any case, given that the relying party accepts the validation by the public key as representing some implied 3-factor authentication involved in access and use of the corresponding private key ... then the relying party may be faced with just who the implied authentication corresponds to. In the typical, long time accepted business process ... the relying party will have prior relationship with the entity being authenticated and it will be explicit and/or implicit in the communication itself. In the more modern world, in the situations where the relying party has no prior relationship with the authenticated entity ... they will have access to online and/or real-time information to establish that fact. However, certificates were targeted at the offline email world ... where the email was created, digitally signed (presumably after some form of 3-factor authentication occuring to establish access/use of the private key), and the email, digital signature, and certificate packaged up and sent off to some party that there had been no previous communciation (might be considered spam in this day and age). After some number of intermediary store-and-forwards stops, the package arrives at the post office of the relying party. the relying party eventually calls their post office, exchanges emails and hangs up. At this point the relying party is presented with a digital signed message with whom that they had no prior communciation. The attached certificate provides the public key for validating the digital signature and the rest of the certificate contents is supposedly to attest to some characteristic of the email sending party (that the relying party has no other way of validating). The implication is that if i can substitute a public key in some certificate that attests to represent some other party then it may be some form of identity theft (fraudulent messages can be created that otherwise appear to have originated from you ... and validate with the substituted public key). The other might be elevation of privileges adding characteristics to a certificate that were otherwise not provided. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: MD5 collision in X509 certificates
On Wed, Mar 02, 2005 at 12:35:50PM +, Ben Laurie wrote: > Cute. I expect we'll see more of this kind of thing. > > http://eprint.iacr.org/2005/067 > > Executive summary: calculate chaining values (called IV in the paper) of > first part of the CERT, find a colliding block for those chaining > values, generate an RSA key that has the collision as the first part of > its public key, profit. > What is the significance of this? It seems I can get a certificate for two public keys (chosen, not given) while only proving posession of the first. Is there anything else? In what sense is the second public key useful to the attacker? -- /"\ ASCII RIBBON NOTICE: If received in error, \ / CAMPAIGN Victor Duchovni please destroy and notify X AGAINST IT Security, sender. Sender does not waive / \ HTML MAILMorgan Stanley confidentiality or privilege, and use is prohibited. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: MD5 collision in X509 certificates
Ben Laurie wrote: > Dan Kaminsky wrote: > >> The x.509 cert collision is a necessary consequence of the earlier >> discussed prime/not-prime collision. Take the previous concept, make >> both prime, and surround with the frame of an x.509 cert, and you get >> the new paper. > > > Actually, not - an RSA public key is not prime. Generating colliding > public keys takes quite a bit more work. *laughs* Yes, I suppose it would be difficult for pq to be prime now wouldn't it :) So they've basically solved: md5(pq) == md5(p'q') For integer values of p, q, p' and q'. You are right, this is much more work. --Dan - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: MD5 collision in X509 certificates
Dan Kaminsky wrote: The x.509 cert collision is a necessary consequence of the earlier discussed prime/not-prime collision. Take the previous concept, make both prime, and surround with the frame of an x.509 cert, and you get the new paper. Actually, not - an RSA public key is not prime. Generating colliding public keys takes quite a bit more work. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ "There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit." - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: MD5 collision in X509 certificates
Ben, Semantic gap, and I do apologize if I didn't make this clear. Wang adapts to any initial state, so you can create arbitrary content to prepend your collision set with, adapt to its output, and then append whatever you like. The temporal ordering is indeed important though; you can't create the doppelganger set before you know what's prepended to it. The fact that we can have arbitrary content adapted to allows for a critical expansion of the applied risks (i.e. we wouldn't be seeing colliding certs w/o it). I don't think it's fair to say my attacks -- in some vague, general sense -- are "wrong", given what was at best a small difference in interpretation. The x.509 cert collision is a necessary consequence of the earlier discussed prime/not-prime collision. Take the previous concept, make both prime, and surround with the frame of an x.509 cert, and you get the new paper. Still nice to see...Rescorla specifically thought it wasn't possible. I look forward to actually having the code to work on this myself. --Dan Ben Laurie wrote: > Cute. I expect we'll see more of this kind of thing. > > http://eprint.iacr.org/2005/067 > > Executive summary: calculate chaining values (called IV in the paper) > of first part of the CERT, find a colliding block for those chaining > values, generate an RSA key that has the collision as the first part > of its public key, profit. > > BTW, reading this made me notice that Dan Kaminsky's attacks are wrong > in detail, if not in essence. Because the output of the MD5 block > function depends on the chaining values from previous blocks, it is > not the case that you can prepend arbitrary material to your colliding > block, as he claims. However, you can (according to the paper above) > generate collisions with any IV, so if you know what the prepended > material is, then Kaminsky's attack will still work. > > Cheers, > > Ben. > - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
MD5 collision in X509 certificates
Cute. I expect we'll see more of this kind of thing. http://eprint.iacr.org/2005/067 Executive summary: calculate chaining values (called IV in the paper) of first part of the CERT, find a colliding block for those chaining values, generate an RSA key that has the collision as the first part of its public key, profit. BTW, reading this made me notice that Dan Kaminsky's attacks are wrong in detail, if not in essence. Because the output of the MD5 block function depends on the chaining values from previous blocks, it is not the case that you can prepend arbitrary material to your colliding block, as he claims. However, you can (according to the paper above) generate collisions with any IV, so if you know what the prepended material is, then Kaminsky's attack will still work. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ "There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit." - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
