This is a pretty interesting paper -- worth reading.
Colliding X.509 Certificates version 1.0 1st March 2005 Arjen Lenstra, Xiaoyun Wang, and Benne de Weger
http://eprint.iacr.org/2005/067
We announce a method for the construction of pairs of valid X.509 certificates in which the ?to be signed? parts form a collision for the MD5 hash function. As a result the issuer signatures in the certificates will be the same when the issuer uses MD5 as its hash function.
It seems that the approach was to generate two RSA moduli that could be
swapped but still produce the same MD5, hence the same signature.
Another interesting question is whether, given an arbitrary modulus,
another can be generated that produces the same MD5. It almost seems
like the same problem to me, so I must be missing something here. The
attack isn't on the public key itself since the factors necessary to
generate the private key are still computationally hard to obtain but
rather on the content of the certificate. The key assumption is that
the certificate is signed by a third party signer, which supplies the
public key for verification.
Even as posed, this is a pretty scary paper. You could generate a
certificate with your legitimate content in it (distinguished name,
etc.), get that signed by a TTP and reuse that signature on another
certificate with content in it that masqueraded as someone else. You
could also conceivable just recode parts of the certificate (such as
the length of issue) and be safe. Since you generated the pair of keys
that causes this to happen, you could masquerade as anyone you wanted
as long as you got your initial certificate signed.
Pretty interesting attack. Computationally intense in some areas, but
definitely a viable attack particularly against downloadable browser
plug-ins. It reminds me of when Verisign signed a fraudulent Microsoft
certificate; this attack makes that much more possible. This attack
could end the usefulness of TTPs in many circumstances.
-- jeff
jeffrey kay
weblog