On December 30, 2008, seven researchers from the Netherlands, Switzerland and the United States told a hacker conference in Berlin that they could fake the padlock in a web browser. They had built a forged certificate authority, a credential that lets its holder vouch for any website on the internet, and every common browser would accept it as genuine.
As a precaution, they had deliberately made their own copy expire in 2004, so the demonstration only worked on a computer with its clock set back. The method itself had no such limit.
The heavy computing was done by a cluster of about 200 PlayStation 3 consoles in a Swiss university lab. The certificates the team had to buy along the way cost $657.
The padlock rests on a fingerprint
When you open a site over HTTPS, your browser checks a certificate that says the site is who it claims to be. That certificate is signed by a certificate authority (CA), a company that browsers have agreed to trust.
A CA does not sign the whole certificate. It signs a short fingerprint of it, called a hash. If two different certificates produce the same hash, a signature on one is also a valid signature on the other.
In 2008, some CAs still made those fingerprints with MD5, an algorithm Ron Rivest published in April 1992. Researchers in China showed in 2004 that two different files could share an MD5 hash. By 2007, three of the seven had refined the technique so that an attacker could choose how both files began.
Most CAs had moved on, but not all. The team collected 30,000 certificates from CAs trusted by Firefox and found about 9,000 signed with MD5. Of those, 97 percent came from one brand: RapidSSL, owned by VeriSign.
Why PlayStations
The attack combined an improved mathematical method with a very large computational search, and the PS3 was well suited to the search. It could run Linux, and its Cell processor was built to do the same arithmetic on many numbers at once. That is the same reason the US Air Force wired more than 1,700 of them into a supercomputer two years later.
The team used the “PlayStation Lab” at EPFL in Lausanne, a cluster of about 200 consoles run by cryptographer Arjen Lenstra, one of the seven. Each attempt took about 18 hours on the PS3s, followed by 3 to 10 hours of finishing work on a single quad-core PC.
In their talk, the researchers put the cluster’s output at roughly 8,000 ordinary desktop processor cores, or about $20,000 of rented time on Amazon’s cloud.
A six-second window
A collision only helps if the attacker knows in advance exactly what the CA will write into the certificate. Two fields were out of the team’s hands: the serial number and the moment the certificate became valid.
RapidSSL made both predictable. Its system was fully automated, its serial numbers went up by one each time, and it issued each certificate exactly six seconds after the customer clicked the final button.
So the team picked a serial number and a second a few days ahead and computed a colliding pair to match. Then they bought certificates of their own to push the counter to just below the target, and clicked at the chosen moment. Each certificate cost $45, but free reissues brought the effective price down to $2.25 a request.
The first three weekends failed, thrown off by timing problems and by other customers buying certificates at the wrong moment. The fourth worked. RapidSSL issued an ordinary website certificate, serial number 643015, valid from November 3, 2008. Because the two specially built certificates had the same MD5 hash, the team could copy RapidSSL’s genuine signature onto their rogue one. That rogue certificate carried the authority to sign certificates for any other website.
A forged certificate does not send anyone to a fake site by itself. An attacker would still need to intercept or redirect the victim’s connection, for example on an insecure wireless network or by tampering with DNS.
A hack built not to be used
The researchers did not want a working skeleton key in circulation. They backdated their forged certificate so it was only valid from July 31 to September 2, 2004, which meant any browser with a correct clock would reject it as expired. They also kept its private key to themselves.
Anyone who wanted to try the live demo in Berlin had to set their computer’s clock back to August 2004 first.
The response was fast. VeriSign switched new RapidSSL certificates to the newer SHA-1 algorithm at 11 a.m. Pacific time the same day, and offered to replace older MD5 certificates for free. Microsoft’s advisory, published the same day, said it knew of no active attacks, noted that most public CAs had already dropped MD5, and told the rest to stop signing new certificates with it. By January 2, another CA on the team’s list, TC TrustCenter, said it had started replacing its MD5 certificates.
The speed is the telling part. MD5 had been publicly broken for four years, and a replacement had been available the whole time. RapidSSL changed its issuing process within hours once there was a practical attack nobody could wave away. The other holdouts still had their own transitions to finish.
What came next
The 2008 attack was a proof of concept. Four years later, the real thing turned up. The Flame espionage malware, discovered in May 2012, used an MD5 collision to forge a Microsoft certificate and pass itself off as a Windows update. Marc Stevens, one of the seven, analyzed it and found a variant of the attack that had never been published.
SHA-1, the replacement, did not last either. The team had warned in 2008 that it showed similar weaknesses on paper. On February 23, 2017, Stevens and colleagues at CWI Amsterdam and Google announced the first SHA-1 collision. By then Chrome had already started marking sites with SHA-1 certificates as insecure.
Both times, a weakness that had existed only in research papers became a working attack years after the first warnings. In 2008, it took years of cryptographic research, a university’s existing cluster of game consoles and $657 in certificate purchases.