I just finished reading Colliding X.509 Certificates by Arjen Lenstra, Xiaoyun Wang, and Benne de Weger and I now have chills running up my spine. If I understand the paper correctly, the researchers generated two RSA moduli that could be swapped but still produce the same MD5, which means that the contents of a certificate signed by a trusted third party could be replaced using the same signature. 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 Trusted Third Party (TTP) and replace the key with another that wasn’t actually signed by the TTP. In essence this means that the TTP signature does not guarantee that the certificate holder actually has the private key to go along with the key that was originally signed. This also means that certificates signed using MD5 are not to be trusted.