Colliding X.509 Certificates for Different Identities

 Technische Universiteit Eindhoven
 
Latest News (Dec. 30, 2008) Jointly with Alex Sotirov, Jake Appelbaum, David Molnar and Dag Arne Osvik we have extended thois work into a realistic attack: Creating a rogue CA certificate.
 
News (Feb. 12, 2008) This work has had some influence on the catalogue of algorithms suitable for the German Signature Law (Signaturgesetz). This catalogue (a.o.) prescribes the conditions and time frames for hash algorithms to be used in legally protected digital signatures in Germany. One of the changes introduced in the 2008 version of the catalog is the new condition that SHA-1 may be used for so-called "qualified certificates" until 2010 only when there is at least 20 bits of entropy in the certificate serial number. This remarkable change was introduced to thwart exactly the type of certificates that we present here for the MD5 hashfunction.

Links:
Bekanntmachung zur elektronischen Signatur nach dem Signaturgesetz und der Signaturverordnung (Übersicht über geeignete Algorithmen) (website)
2008 version
2007 version

We are grateful to prof. Werner Schindler of the BSI for pointing us to this document, and for his confirmation that the reason for this recent change in the catalog is indeed the appearance of our colliding certificate construction.
   
News (Nov. 30, 2007) See the chosen-prefix collision website.
Note that the wording has changed, from target collision to chosen-prefix collision.
 
Announcement
Colliding X.509 Certificates
for Different Identities		 We announce a pair of X.509 certificates with the following properties:
colliding
The to-be-signed parts of the certificates form a collision for the MD5 hash function. This means that their signatures are identical. These signatures have been generated by a Certification Authority that uses MD5.
different identities
One certificate has "Arjen K. Lenstra" as Common Name, the other one has "Marc Stevens" instead. They also have different O-fields (for Organization) and serial numbers. These values were chosen before the collision construction started.
This aspect is the main difference with our Colliding X.509 Certificates construction of last year, where we had colliding certificates but with identical owner names.
valid
Both certificates are constructed according to the standards (X.509 certificate profile (RFC 3280), correct ASN.1 and DER encoding).
[[Actually, this is strictly speaking not true: we made a small mistake in the DER encoding, but common certificate processing software seems not to notice this.]]
unsuspicious
Each certificate by itself looks unsuspicious. This is because the random looking bitstrings that are needed to make the collision happen are 'hidden' inside the public key moduli, which usually are random looking anyway. As a result the RSA public keys are different for the two certificates.
secure RSA keys
Each modulus is a product of two different prime numbers, and is (to the best of our knowledge) just as hard to factor as any other proper RSA modulus of the same size. By calling these moduli secure we do not in the first place refer here to the key size of 8192 bits. This unusually large key size was needed to be able to hide the collision. We would have liked to have a normal key size of, say, 2048 bits, but our methods currently are not able to reach this.
   
Chosen-prefix Collisions These certificates are just an example of a more general construction. For any targeted pair of distinct messages m1 and m2 we can effectively construct appendages b1 and b2 such that MD5(m1||b1) equals MD5(m2||b2). We call this a chosen-prefix collision. Said differently, we can cause an MD5 collision for any pair of distinct IHVs.

The construction of the colliding certificates is based on a chosen-prefix collision for MD5, constructed for this purpose by Marc Stevens in the HashClash project.
See the chosen-prefix collision website.
   
Verification of the certificates Some suggestions to scrutinize our certificates yourself:
Peter Gutmann's dumpasn1
Gives a human-readable view of the contents, there's a GUI version too.
Microsoft Certificate Viewer
This can be accessed from the Windows Explorer by doubleclicking on a certificate file with extension .cer, or in Internet Explorer via Toole -> Internet Options -> Content -> Certificates. Certificates can be imported here, when the CA certificate is placed in the "Trusted Root CA" store. Then checking of the signatures is done automatically upon opening any certificate in the Certificate Viewer. This viewer shows all fields of the certificate in human readable form, with the unfortunate exception of the signature.
OpenSSL
Here's a recipe to verify the certificates with OpenSSL.
   
Verification of the collision Verification of the collision itself can be done on a Windows system by e.g. Jem Berkes' md5sums.exe
(on unix, use the md5 command).
Here's a recipe to verify the collision with md5sums.
   
Links See the HashClash project webpage for related stuff.
The previous Colliding X.509 Certificates construction.
The new application: Creating a rogue CA certificate.
An interesting site on Meaningful Collisions (for SHA-1), about work similar to our method of choisen-prefix collision construction, but focusing on SHA-1.
   
Authors
  ___
 / _ \
| / | |
| \_|/
 \____
 Marc Stevens, presently at CWI, Amsterdam, The Netherlands
Arjen K. Lenstra, EPFL, Lausanne, Switzerland
Benne de Weger, TU/e, Eindhoven, The Netherlands

Please send all correspondence to Benne de Weger.
   
Publication Date October 23, 2006
   
Latest Modification January 1, 2009
   
Vanity counter

The certificates

Here are the certificates (downloadable):

colliding certificate number 1 (on the name of "Arjen K. Lenstra")
colliding certificate number 2 (on the name of "Marc Stevens")

Here is the CA certificate with which the colliding certificates can be validated:

CA certificate (on the name of "Hash Collision CA")



Announcement paper

Detailed Announcement paper (v1.1) in pdf-format.
This announcement is published as Cryptology ePrint Archive Report 2006/360.
The paper describes the way we constructed the certificates, and has some thoughts on applications of chosen-prefix collisions in general, and attack scenarios based on our certificate construction in particular.
Version 1.1 contains an appendix on differential path construction, and some other minor changes.

Final paper

Our paper has been accepted at EuroCrypt 2007, and thus will be published in the EuroCrypt 2007 Proceedings.
It has been thoroughly rewritten, with many more details about the method of finding chosen-prefix collisions, but with less details about the certificates.
Here is the final paper (v2.0) in pdf-format.

Technical Details

Technical Details sheet in pdf-format,
with details on the construction of the certificates and the RSA moduli.
Also the private keys are in there, to enable validation of our claim that the RSA moduli really are secure.


The collision

Here is the collision: a pair of different files (downloadable) having identical MD5 hash:
(the files are binary (not human readable), and contain the 'to-be-signed' parts of the certificates):

the first file: collision1.bin
the second file: collision2.bin

We also have a file (human readable) showing the bit differences between the two collision files:

bit difference file