Perhaps an obvious analogy, but it made me laugh nonetheless:

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.

Bruce Schneier reports on his blog that SHA-1 has been broken as described in a paper by Chinese researchers Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu. Federal Information Processing Standard 180 (FIPS-180) describes SHA-1 in the following way:

Explanation: This Standard specifies a Secure Hash Algorithm, SHA-1, for computing a condensed representation of a message or a data file. When a message of any length

The SHA-1 is called secure because it is computationally infeasible to find a message which corresponds to a given message digest, or to find two different messages which produce the same message digest. Any change to a message in transit will, with very high probability, result in a different message digest, and the signature will fail to verify. SHA-1 is a technical revision of SHA (FIPS 180). A circular left shift operation has been added to the specifications in section 7, line b, page 9 of FIPS 180 and its equivalent in section 8, line c, page 10 of FIPS 180. This revision improves the security provided by this standard. The SHA-1 is based on principles similar to those used by Professor Ronald L. Rivest of MIT when designing the MD4 message digest algorithm (“The MD4 Message Digest Algorithm,” Advances in Cryptology – CRYPTO ’90 Proceedings, Springer-Verlag, 1991, pp. 303-311), and is closely modelled after that algorithm.

The general conclusion of this paper is that collisions can be found after 2^69 hash operations, instead of the brute force 2^80. A collision is where two given messages are found to produce the same result. This effectively means that 2^11 fewer operations are required to produce a collision. Computationally, this means that if it took a week to compute 2^69 hash operations before a collision, it would have taken 2048 weeks to compute 2^80 hash operations before, which is about 39 years. That’s a pretty significant reduction in the amount of time necessary to break a hash. Now it still takes a long time to compute a hash and 2^69 of them is a huge amount, but as Moore’s law continues to give us faster processors, a 2^11 reduction in operations is very, very important. It effectively renders SHA-1 useless for the long-term, and maybe even for the short term.