MD5 considered harmful NOW.

Yesterday, a significant attack against MD5-hashed X509 certificates was announced.

http://www.win.tue.nl/hashclash/rogue-ca/

It exploits existing known weaknesses of MD5 to certain collision attacks to create bogus X509 certificates. The researchers were even able to create bogus X509 CA certs, thus breaking the chain of trust for X509 certificates.

X509 certificates are used for establishing trust and authentication in SSL communication, as well as many types of encrypted email, VPN authentication, 802.1x authentication, etc. With the new attack, someone can create fake certificates that look perfectly valid to the party attempting to verify that they're talking to someone they trust. Certification Authorities (CAs) are trusted third-parties who verify that an entity is who they say they are, and issue certificates for entities to use, saying "This server that you're talking to, named server-x belongs to this entity-y, signed CA-z".

Every hash algorithm has collisions. When you're boiling down an arbitrary amount of data into a short, fixed length signature, it's going to happen eventually that some other chunk of data will end up with the same signature. The problem is when someone learns how to make a piece of data collide with another piece of data on purpose. Especially if they can make their own fake X509 certificate look like it was signed by a trusted authority, when in reality, it wasn't.

So this attack is doubly bad... an attacker using this method can not only create fake certificates, they can create fake CA certificates which can then be used to sign other fake certificates, and look just like a trusted CA.

How bad is this? Well, it's not as immediately bad as it seems. First, the attack took quite a bit of hardware and time. 200 PS3s and a high-end multi-CPU PC took about 24 hours for each successful attempt. Clearly, this is a lot of CPU time. However, it's not infeasible to do it with a distributed search spread across a few hundred collaborating PCs (such as a botnet or a zombie army) or a similarly constructed cluster.

Secondly, it doesn't allow anyone to actively attack you just yet. It allows them to masquerade as someone you trust, though. A phishing attempt with a valid but fake Wamu.com SSL cert would certainly appear more trustworthy.

The short term fix for you and me is to be yet again more careful of what we click on. The long term fix is for CAs to stop issuing MD5 certs, stop using MD5 internally, etc. Heck, they could even make the effort of revoking their MD5 CA certs and re-issuing with SHA1 or better. Buyers of certs from CAs (and folks who self-sign their own) must stop using MD5.

Now, there's known weaknesses in SHA1, too. It's weak enough that the NIST will no longer permit it for government use in 2010. It's still several orders of magnitude stronger than MD5, though. Better to be safe, though, and require SHA256 or SHA512.