Colliding X.509 Certificates

News (December 30, 2008)

News (October 23, 2006)

Colliding X.509 Certificates for Different Identities

Colliding X.509 Certificates based on MD5-collisions

We announce a pair of valid X.509 certificates, based on the MD5 hash-function,
that have identical signatures.

colliding certificate number 1
colliding certificate number 2

We provide a detailed description of the construction method (in pdf format).
This short paper is also available from the Cryptology ePrint Archive, as report 2005/067.
This description is also incorporated in an appendix in the "full" version of the paper
"On the possibility of constructing meaningful hash collisions for public keys",
by Arjen Lenstra and Benne de Weger.

Additional downloadables

further technical data (in ascii format)
CA certificate

www.beautifulcollision.com (we have no relation to this band, we just like the picture)

(Beautiful Collision, 2004)

What a beautiful collision
Things that go bump in the night
With such beautiful precision
Fate could create you and I
(Bic Runga, 2002)

Here it comes a beautiful collision
Is happening now
There seems no end to where you begin and where I end now
You and I, collide
(David Crowder Band, 2005)

Visualising the collision

Collision		No Collision
	To the left you see a visual representation of the collision of the certificates. For each 512 bit block of input from one of the two certificates, the MD5 compression function is called once. Inside this compression function an inner loop is performed 64 times, updating an internal state. Each time when for each of the two certificates one inner loop in the compression function has been completed, and also when one entire compression function has completed, the difference in the internal states for the two certificates is represented as one horizontal line of pixels in the picture. A black pixel stands for identical bits, a white pixel for different bits. What should have happened is a bit pattern that, from the point on where the certificates differ, rapidly starts looking random, and stays random. To the right we give an example of this, showing the effect of an arbitrary input difference of only one bit. The randomness is only per horizontal line. Consecutive lines have a lot of dependencies, which explains the 4-fold almost horizontal translation patterns that you might observe, in both left and right pictures.

Verification with OpenSSL

As we described in the paper, if you want to verify yourself our claims on the above certificates, you can use tools like Peter Gutmann's dumpasn1 and certificate viewers like Microsoft's. We forgot to mention OpenSSL, which of course is also very useful (Eric: thanks for reminding us). Here is a recipe.

To get a human-readable view of the contents of the certificates:
   openssl x509 -in MD5Collision.certificate1.cer -inform DER -text
   openssl x509 -in MD5Collision.certificate2.cer -inform DER -text

To verify the signature on the two certificates against the CA certificate, first convert the certificates to PEM-format ("openssl verify" does not work with the DER format):
   openssl x509 -in MD5Collision.certificate1.cer -inform DER -out MD5Collision.certificate1.pem
   openssl x509 -in MD5Collision.certificate2.cer -inform DER -out MD5Collision.certificate2.pem
   openssl x509 -in MD5CollisionCA.cer -inform DER -out MD5CollisionCA.pem
and then do the verification:
   openssl verify -CAfile MD5CollisionCA.pem MD5Collision.certificate1.pem
   openssl verify -CAfile MD5CollisionCA.pem MD5Collision.certificate2.pem

Colliding X.509 Certificates based on SHA1-collisions

We would like to announce a pair of valid X.509 certificates, based on the SHA1 hash-function, that have identical signatures. However we are not yet able to do so. The reason is that generating collisions for the SHA1 hash-function still takes a prohibitively large amount of time.
However, as soon as somebody is able to produce in practice collisions for the SHA1 compression function with prescribed IV, we can easily come up with colliding certificates based on that.

Authors

Arjen Lenstra (EPFL Lausanne, Lucent Bell Labs and Technische Universiteit Eindhoven)
Xiaoyun Wang (Shandong University, Jinan, China)
Benne de Weger (Technische Universiteit Eindhoven)

Benne will act as corresponding author. E-mail: b@m@m@d@weger.tue@nl (sorry, I accidentally interchanged ats and dots).

March 1, 2005. Latest update: March 17, 2006.

Background paper

The idea for the construction of the colliding certificates came up when Arjen Lenstra and Benne de Weger were writing the paper "On the possibility of constructing meaningful hash collisions for public keys". This paper has been presented at ACISP 2005 (download the paper (210 KB) and the presentation (111 KB)).
Here is the updated "full" version of the paper, including the details of the colliding certificates.