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)
(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)
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.
openssl x509 -in MD5Collision.certificate1.cer -inform DER -text
openssl x509 -in MD5Collision.certificate2.cer -inform DER -text
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
openssl verify -CAfile MD5CollisionCA.pem MD5Collision.certificate1.pem
openssl verify -CAfile MD5CollisionCA.pem MD5Collision.certificate2.pem