Researchers use MD5 collisions to create Rogue CA

December 31, 2008

With the help of about 200 Sony Playstation 3 consoles, an international team of security researchers have devised a way to undermine one of the algorithms used to protect secure Web sites - a capability that the researchers said could be used to launch nearly undetectable phishing attacks. To accomplish that, the researchers said that they had exploited a bug in the MD5 hashing algorithm used to create some of the digital certificates used by Web sites to prove they are what they claim to be. The researchers said that by taking advantage of known flaws in the algorithm, they were able to hack VeriSign Inc.'s certificate authority site and create fake digital certificates for any web site on the Internet.1

The attack is based on known weaknesses in the cryptographic hash function known as MD5. In 2004, researchers from China showed it was possible to generate the same MD5 fingerprint for two different messages using off-the-shelf computer hardware. Three years later, a separate group of researchers built off of those findings by showing how to have almost complete freedom in the choice of both messages.2

The latest findings take the known MD5 weaknesses a step further by showing how collisions allow for the creation of valid digital credentials used by certificate authorities. Once the researchers have generated the rogue certificate authority certificate, they can create SSL certificates for any site that will be accepted by just about any web-connecting device.2

The researchers began their proof-of-concept attack with more than 200 PlayStation 3 consoles running in a Linux cluster, which they used to generate millions of possible certificates. Once they found a pair that had a special collision in the MD5 hash, they requested a legitimate website certificate from one of the authorities that relies only on MD5 to generate signatures.2 The computing effort took a couple days, so a reasonably size botnet could probably do it faster.3

The vulnerability in the web's SSL system is made possible by a handful of certificate authorities who continue to rely solely on MD5 to sign certificates. Even though the number amounts to a tiny fraction of authorities, all web browsers continue to accept MD5 hashes. The researchers didn't identify the certificate authorities by name2, but most public certificate authority roots no longer use MD5 to sign certificates, and have upgraded to the more secure SHA-1 algorithm.4

If the researchers' results can be duplicated by a malicious agent, they could generate any number of certificates that would be trusted by browsers all around the world. This alone might be sufficient, though this attack could be coupled with a sophisticated DNS attack would make it really hard for anyone to realize that they've been suckered. Your browser would report that you're at; your browser would report that you were using HTTPS to protect the connection; and your browser would report that the SSL certificate being used for that HTTPS connection really did belong to

The researchers contemplate that it might take a month for a knowledgeable group to pull off a similar attack and longer for a group less knowledgeable. But where there is money to be made, like in phishing and forging, the criminals will follow, and they're well funded and can hire talented staff.6

The trust we place in PKI has always been on shaky ground. That it works is more a matter of luck than good engineering. This case simply highlights that even one component can bring the whole system to its knees.6

Bruce Schneier, a noted cryptography expert explains it best: "The CA system is broken, but it works because broken systems tend to be better for society, which needs fluidity in the face of complicated social constructs... Systems that are broken but work are very common in the real world: Front door locks are surprisingly pickable. Think of faxed signatures, for example. It's a ridiculous form of authentication, yet people trust these documents all the time for very important stuff."7

1. "Researchers hack VeriSign's SSL scheme for securing Web sites", Computerworld, December 30, 2008

2. "Boffins bust web authentication with game consoles", The Register, December 30, 2008

3. "MD5 SSL Summary", SANS Internet Storm Center, December 30, 2008

4. "Microsoft Security Advisory (961509)", Microsoft, December 30, 2008

5. "MD5 collision creates rogue Certificate Authority", CrunchGear, December 30, 2008

6. "Yes, Trust In The PKI Is Broken", InformationWeek, December 30, 2008

7. "One Weak Link to Rule Them All", The Washington Post, December 30, 2008