Colliding X.509 Certificates for Different Identities
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.
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.
Announcement Colliding X.509 Certificates for Different Identities
We announce a pair of X.509 certificates with the following properties:
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.
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
X.509 Certificates construction of last year, where we had colliding
certificates but with identical owner names.
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.]]
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.
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:
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.
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.
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.
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):