Weakened Algorithm Threatens Trust Online

How an outdated algorithm put secure Internet transactions at risk.

Most people know to look for a padlock icon in the corner of their browsers when banking or conducting other sensitive transactions online. In part, this means that the site has a certificate that has been verified by a higher authority to confirm its identity. Recently, however, a team of security researchers found that a critical security system can be undermined by taking advantage of the outdated algorithms that some companies used to create these certificates. A loose-knit group of security researchers from the United States and Europe presented details of the attack at the 25th Annual Chaos Communication Congress in Berlin at the end of December.

Necessary firepower: Security researchers undermined the certificate system that secures sensitive online transactions. To perform the necessary calculations, the researchers used a cheap cluster of 200 PlayStation 3 machines. The multiple cores of the PlayStation 3 are particularly suited to performing the kinds of calculations needed for the attack, the researchers say. Credit: Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger. The cluster was sponsored by EPFL DIT and by a matching equipment grant from the Swiss National Science Foundation.

The padlock is part of the key online security protocol called SSL (Secure Socket Layer), and it appears as an assurance that a transaction is safe from eavesdropping, tampering, or forgery. A hacker can easily create a banking website that looks like the real thing, but it's much harder to forge the digital certificate that accompanies the site. This is because SSL uses a clever trick to create each certificate: two mathematically linked keys, one of which is kept secret while the other is published openly on the Internet.

A select group of trusted higher powers--known as certificate authorities--can verify the identity of a website. An authority does this by checking that the site is genuine before combining its private key with the website's public key to create the certificate. A main part of the procedure also involves applying what's known as a hash function to generate a unique signature for the certificate. Anyone who visits that site can verify that this certificate is genuine by checking the signature and referring back to the certificate authority's public key.

All this happens behind the scenes, and popular browsers such as Internet Explorer and Firefox have built-in trust for certain certificate authorities, explains Paul Kocher, president and chief scientist of the security company Cryptography Research, who was involved in creating the latest version of SSL. Any certificate that can be traced back to one of those authorities is automatically trusted by the browser. "The entire browser trust model relies on all of the certificate authorities acting well," Kocher notes.

Story continues below

However, some certificate authorities still use a hash function called MD5 to produce certificate signatures. Most authorities have abandoned MD5 because researchers have shown it to be vulnerable to what is called a collision: under certain circumstances, it's possible to produce two certificates that will generate exactly the same digital signature.

A hash function's value disappears if it's easy to produce two certificates with exactly the same fingerprint, explains Marc Stevens, a PhD student in the cryptology and information security group at the Centrum Wiskunde & Informatica, in the Netherlands, whose work on MD5 was crucial to the research. Stevens has been producing collisions using MD5 for several years, enlisting the computing power of 200 PlayStation 3 consoles. The architecture of these machines' microprocessors is well-suited to the kinds of calculations needed for his work. Stevens says that it would take about 8,000 PCs to equal the power that the PlayStations provide. Using the hardware, the team was able to perform the calculations needed for the attack in the space of a weekend.