[FoRK] X.509 certificate collision via MD5 collisions

Jeffrey Kay jeff at k2.com
Wed Mar 2 10:23:37 PST 2005


In reading the paper for the third time, I realized that one of my 
assertions below is wrong.  This technique does not allow you to 
replace anything but the RSA modulus in the certificate, so you can't 
drop in a new distinguished name, expiration date, etc. because the MD5 
collision generation is based on the starting from an initialization 
vector (IV) produced by running MD5 across that content.  From there 
you can generate an MD5 collision and use that to create two RSA moduli 
that can be swapped without invalidating the digital signature.

This is still a significant problem because it means that the key pair 
may not be firmly associated with the content of the certificate, 
invalidating what a TTP (like Verisign or Thawte) does.  So the cert 
may be valid, but the key could be replace with another that was not 
originally signed into the cert.  If you got to the point where you 
could replace an existing key in a cert (which this technique does not 
propose), the entire digital signature trust model goes out the window. 
  Stealing someone's identity becomes trivial.

Of course, this is all based on MD5, which was already shown to have 
problems.  Presumably other hashes will eventually show problems like 
this also.

-- jeff

On Mar 2, 2005, at 11:02 AM, Jeffrey Kay wrote:

> This is a pretty interesting paper -- worth reading.
>
>> Colliding X.509 Certificates version 1.0
>> 1st March 2005
>> Arjen Lenstra, Xiaoyun Wang, and Benne de Weger
>>
>> http://eprint.iacr.org/2005/067
>>
>> We announce a method for the construction of pairs of valid X.509 
>> certificates in which the “to be signed” parts form a collision for 
>> the MD5 hash function. As a result the issuer signatures in the 
>> certificates will be the same when the issuer uses MD5 as its hash 
>> function.
>
> It seems that the approach was to generate two RSA moduli that could 
> be swapped but still produce the same MD5, hence the same signature.  
> Another interesting question is whether, given an arbitrary modulus, 
> another can be generated that produces the same MD5.  It almost seems 
> like the same problem to me, so I must be missing something here.  The 
> attack isn't on the public key itself since the factors necessary to 
> generate the private key are still computationally hard to obtain but 
> rather on the content of the certificate.  The key assumption is that 
> the certificate is signed by a third party signer, which supplies the 
> public key for verification.
>
> Even as posed, this is a pretty scary paper.  You could generate a 
> certificate with your legitimate content in it (distinguished name, 
> etc.), get that signed by a TTP and reuse that signature on another 
> certificate with content in it that masqueraded as someone else.  You 
> could also conceivable just recode parts of the certificate (such as 
> the length of issue) and be safe.  Since you generated the pair of 
> keys that causes this to happen, you could masquerade as anyone you 
> wanted as long as you got your initial certificate signed.
>
> Pretty interesting attack.  Computationally intense in some areas, but 
> definitely a viable attack particularly against downloadable browser 
> plug-ins.  It reminds me of when Verisign signed a fraudulent 
> Microsoft certificate;  this attack makes that much more possible.  
> This attack could end the usefulness of TTPs in many circumstances.
>
> -- jeff
>
> jeffrey kay
> weblog <k2.com> pgp key <www.k2.com/keys.htm> aim <jkayk2>
> share files with me -- get shinkuro -- <www.shinkuro.com>
>
> "first get your facts, then you can distort them at your leisure" -- 
> mark twain
> "if the person in the next lane at the stoplight rolls up the window 
> and locks the door, support their view of life by snarling at them" -- 
> a biker's guide to life
> "if A equals success, then the formula is A equals X plus Y plus Z. X 
> is work. Y is play. Z is keep your mouth shut." -- albert einstein
>
> _______________________________________________
> FoRK mailing list
> http://xent.com/mailman/listinfo/fork
>

jeffrey kay
weblog <k2.com> pgp key <www.k2.com/keys.htm> aim <jkayk2>
share files with me -- get shinkuro -- <www.shinkuro.com>

"first get your facts, then you can distort them at your leisure" -- 
mark twain
"if the person in the next lane at the stoplight rolls up the window 
and locks the door, support their view of life by snarling at them" -- 
a biker's guide to life
"if A equals success, then the formula is A equals X plus Y plus Z. X 
is work. Y is play. Z is keep your mouth shut." -- albert einstein



More information about the FoRK mailing list