Hashing Over Tiny Details

By Brian Krebs
washingtonpost.com Staff Writer
Tuesday, December 30, 2008; 11:01 AM

Building on research from 2004 and 2007, an international team of mathematicians and cryptographers sought to exploit vulnerabilities within RapidSSL, to duplicate the cryptographic signature the company uses to certify secure socket layer (SSL) certificates.

These certificates are used by banking and e-commerce sites to assure users that they are making transactions at a safe and secure site.

The cryptographic strength of each certificate, however, is determined by the complexity of the "hash" or mathematical algorithm used to generate it. A hash algorithm converts digital data, such as a block of text or a computer file, into a fixed string of numbers, to disguise the original file. The resulting hash can be used to uniquely identify a set of data, much like a fingerprint uniquely identifies a human.

A good hash function will produce a completely different result if the original file is changed even slightly. Web browsers can use this key feature of hashes to spot a fake SSL certificate by comparing its hash value to an index of known, authentic values for that certificate: If the two values do not match, the browser warns the user that someone in the middle may be trying to present a counterfeit certificate in an effort to intercept data transmitted between the Web site and the visitor.

Still, researchers have shown that with some older hashing algorithms, it is possible to force different chunks of data to produce the same hash value, a condition akin to having two very different keys that open the same lock. This condition, known as a "hash collision," is supposed to be relatively rare. For example, a 128-bit hash scheme known as "MD5" can have 3.4 x 10 to the 38th power possible values, which can produce some 340,282,366,920,938,463,463,374,607,431,768,211,456 possible hashes.

In 2004, however, a team of Chinese researchers proved it was possible to force collisions for MD5 hashes. In 2006, mathematicians and cryptographers from Germany, the Netherlands and Switzerland significantly expanded on that work by successfully producing two digital certificates that had different identities but identical cryptographic signatures. That research was published in May 2007.

Earlier this year, that same European team was joined by researchers at University of California, Berkeley and other U.S. based experts, who wanted to find a collision that would allow them to create a rogue certificate authority that was implicitly trusted by all Web browsers. For their experiment, the researchers targeted RapidSSL, a large SSL provider that uses MD5 signatures to secure its digital certificates.

In order to find a hash collision that would mimic the signature embedded in all RapidSSL-signed certificates, the researchers needed some serious computing power. They ultimately chose to network together some 200 Playstation 3 gaming consoles, a veritable supercomputing cluster that equaled the combined number-crunching power of more than 8,000 modern desktop PCs.

According to researcher Jacob Appelbaum, it took the team and the network of PlayStations just 16 hours to find enough hash collisions with RapidSSL's public certificate to generate the output needed to successfully forge the company's digital signature.

The researchers claim that even a highly skilled researcher and programmer who has been working in this area before might spend more than a month trying to duplicate their efforts. But Gene Spafford, a professor of computer science at Purdue University, worries what such knowledge might mean in the hands of organized cyber criminals who control massive botnets ¿ collections of hacked personal computers typically used for blasting out spam.

"The researchers say they're only going to describe their work in general terms, but these botnet gangs have potentially hundreds of thousands of computers at their disposal, and quite a few talented programmers," Spafford said. "Assuming these guys have the know-how and realize the potential gains here, it might only be a couple of weeks before they have something up and runing on the botnets trying to break CA keys this way. If they do, they're not going to do anything as thoughtful as setting the key's expiration date in the past: It's just going to start showing up in the wild."

© 2008 The Washington Post Company