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 downloadablesfurther technical data (in ascii format)CA certificate |
(Beautiful Collision, 2004) |
What a beautiful collision
(Bic Runga, 2002)
Things that go bump in the night With such beautiful precision Fate could create you and I Here it comes a beautiful collision
(David Crowder Band, 2005)
Is happening now There seems no end to where you begin and where I end now You and I, collide |

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. |

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`

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.

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.

Here is the updated "full" version of the paper, including the details of the colliding certificates.