Hashes are used to create a digital "fingerprint" that is supposed to uniquely identify a given document and can easily be calculated to verify that the document hasn't been modified in transit. But the flaw in the MD5 algorithm makes it possible to create two different documents that have the same numerical hash value.
That, the researchers said, explains how someone could create a digital certificate for a phishing site that has the same fingerprint as the certificate for a genuine Web site. They added, though, that they don't expect to see any actual attacks using the flaw that they exploited — a point that Microsoft Corp. seconded in a security advisory in which it downplayed the threat to Internet users.
Using their farm of Playstation 3 machines, the researchers built a rogue certificate authority that could issue bogus certificates. The Playstation's Cell processor is popular with code breakers because it is particularly good at performing cryptographic functions.
The researchers planned to present their findings today at the Chaos Communication Congress, a hacker conference being held in Berlin. Even before their talk took place, it already was the subject of speculation within the Internet security community.
The team that did the research work included independent researchers Jacob Appelbaum and Alexander Sotirov, as well as computer scientists from the Centrum Wiskunde & Informatica, the Ecole Polytechnique Federale de Lausanne, the Eindhoven University of Technology and the University of California, Berkeley.
Although the researchers believe that a real-world attack using their techniques is unlikely, they say their work shows that the MD5 algorithm should no longer be used by the certificate authority companies that issue digital certificates. "It's a wake-up call for anyone still using MD5," said David Molnar, a Berkeley graduate student who worked on the project.
In addition to VeriSign, TC TrustCenter AG, EMC Corp.'s RSA unit and Thawte Inc. use MD5 to generate their digital certificates, according to the researchers. They said that VeriSign also uses the algorithm on a certificate service offered through its Japanese Web site, in addition to RapidSSL.com.
Exploiting the MD5 bug to carry out an attack would be hard, because cybercrooks would first have to trick a victim into visiting the malicious Web site that hosts a fake digital certificate. That could be done, however, by using what's called a man-in-the-middle attack. Last August, for example, security researcher Dan Kaminsky showed how a major flaw in the Internet's Domain Name System could be used to launch such attacks.
And with this latest research, it's now potentially easier to attack Web sites that are secured using Secure Sockets Layer (SSL) encryption, which relies on trustworthy digital certificates. "You can use Kaminsky's DNS bug combined with this to get virtually undetectable phishing," Molnar said.
"This isn't a pie-in-the-sky talk about what may happen or what someone might be able to do, this is a demonstration of what they actually did with the results to prove it," HD Moore, director of security research at BreakingPoint Systems Inc., wrote in a blog post about the researchers' findings.
Cryptographers have been gradually chipping away at the security of MD5 since 2004, when a team lead by Shandong University's Wang Xiaoyun demonstrated flaws in the algorithm.
Given the state of research into MD5, certificate authorities should have upgraded to more secure algorithms such as SHA-1 "years ago," said Bruce Schneier, a noted cryptography expert and chief security technology officer at BT PLC.
RapidSSL.com will stop issuing MD5-based digital certificates by the end of January and is looking for ways to encourage its customers to move to new certificates after that, said Tim Callan, VeriSign's vice president of product marketing. But first, Callan added, VeriSign wants to get a good look at the new research.
Molnar and his team have communicated their findings to VeriSign indirectly, via Microsoft, but they have yet to speak directly to VeriSign, out of fear that it might take legal action to quash their talk. In the past, companies sometimes have obtained court orders to prevent security researchers from talking at hacker conferences.
Callan said he wished that VeriSign had been given more information ahead of time. "I can't express how disappointed I am that bloggers and journalists are being briefed on this but we're not, considering that we're the people who have to actually respond," he said.
While Schneier said he was impressed by the math behind this latest research, he said that there are already far more important security problems on the Internet — weaknesses that expose large databases of sensitive information to attackers, for example.
"It doesn't matter if you get a fake MD5 certificate, because you never check your certs anyway," he said. "There are dozens of ways to fake that, and this is yet another."