« Too stupid to commit fraud | Main | Remote device fingerprinting with timestamps »

March 1, 2005

A pair of certificates with the same signature

Eu-Jin Goh pointed me to this paper by Lenstra, Wang, and de Weger, entitled "Colliding X.509 Certificates". Lenstra et al start with an MD5 collision and the first half of a certificate and generate a pair of RSA public keys that produce the same digest value. This produces a pair of certificates with the same signature. This isn't that surprising a result, since it's implicit in the fact that MD5 has collisions, but it's nicely written up and clearly explained.

From a security perspective, this isn't really so bad, for two reasons:

  1. The attacker doesn't actually control all of the first half of the certificate, so mounting the attack on a real CA is harder.
  2. The only thing that's different between these certificates is the public key. So, if we ignore point (1), an attacker would be able to get a certificate with a public key different from that he gave the CA. This isn't inherently that interesting, but an extension to have other differences besides the public key (e.g., the name) would be quite interesting, although you probably wouldn't be able to really control the name you got.
So, don't panic. The analysis I posted here is still pretty accurate.

You can find the colliding certificates and some more details here.

Posted by ekr at March 1, 2005 12:21 PM | Filed under:

Comments

As to your second point, that would be very interesting. Start the MD5 spoofing after the subject public key, but before the SubjectAltName. It would be difficult/impossible to get both a usable new subject name *and* proper ASN.1 structure, however.

Posted by: Paul Hoffman at March 1, 2005 5:10 PM

The paper mentions that the Wang et al technique for finding MD5 collisions will be published at Eurocrypt this year. Presumably that will be enough information to let us create desktop MD5-collision software, if the authors don't publish their own implementation. Then people can play games with trying to get some kind of semi-reasonable name collisions. Of course I don't imagine Verisign will give you a cert any more that uses an MD5 hash, so you can't create a useful cert collision. These authors made their own "CA" key to issue the certs.

Posted by: Hal Finney at March 2, 2005 2:26 PM