MD5 Exploit Potentially Compromises SSL Security
SSL-based security using X509 certificates from certain CA's opens a vulnerability to sites masquerading under a forged X509 certificate, even in a "secure" connection. This was demonstrated recently at the Chaos Conference in Berlin by spoofing a real certificate.
"Making the theoretical possible is sometimes the only way you can affect change and secure the Internet." This is the conclusion of "MD5 Considered Harmful Today: Creating a rogue CA certificate", a talk given on December 29th 2008 at the 25th Chaos Communication Congress in Berlin. In this talk, the authors revealed how they have used a previously theoretical attack on the MD5 signature, first described in 2004, to construct forged certificates that can allow a "perfect man in the middle attack" on SSL secured web sites.
The attack works like this. SSL servers are authenticated by using an x.509 certificate issued by one of many "trusted signing authorities" or "CA's". The signing authority "signs" a certificate using one of several cryptographic algorithms to generate a hash. The algorithms are designed so that the probability of two different sets of data computing the same hash value -- a collision --is extremely small.
To make an attack, the attacker needs to buy several SSL certificates from CAs who sign certificates with the MD5 algorithm. Using information derived from these certificates, it's possible to construct an apparently valid, but forged, certificate with a valid signature from one of the purchased certificates, but with different contents, by adding a specially computed block of data to force a collision. Now the MD5 algorithm will falsely verify that the signature matches the new contents. In effect, it's like forging a letter by putting new contents onto a piece of paper that was legitimately signed.
Once the forged certificate is created, it can be used in a "man in the middle" attack; by using the certificate, a proxy can be set up that appears to be legitimate to both ends of an SSL connection; at that point, any confidential information can be captured and stored by the attacker.
The attack is computationally intensive, but recent advances and Moore's Law have made the computation of a colliding certificate feasible. In this case, the computation could be done for around $2000 in the Amazon EC2 cloud, or by a "home supercomputer" built from clustered PS3 game consoles.
This attack doesn't mean that all Internet or SSL security has been compromised, but it does mean vendors should move away from using the MD5 signing algorithm. The authors have identified and notified a number of signing authorities who still have active certificates with MD5 signatures.