GoKawiilSometime around 2010, sophisticated malware known as Flame hijacked the mechanism that Microsoft used to distribute updates to millions of Windows computers around the world. The malware—reportedly jointly developed by the US and Israel—pushed a malicious update throughout an infected network belonging to the Iranian government.
The lynchpin of the “collision” attack was an exploit of MD5, a cryptographic hash function Microsoft was using to authenticate digital certificates. By minting a cryptographically perfect digital signature based on MD5, the attackers forged a certificate that authenticated their malicious update server. Had the attack been used more broadly, it would have had catastrophic consequences worldwide.
Getting uncomfortably close to the danger zone
The event, which came to light in 2012, now serves as a cautionary tale for cryptography engineers as they contemplate the downfall of two crucial cryptography algorithms used everywhere. Since 2004, MD5 has been known to be vulnerable to “collisions,” a fatal flaw that allows adversaries to generate two distinct inputs that produce identical outputs.
Within four years, two other pieces of research further demonstrated the weakness of MD5. The latter used 200 Sony Playstations running for three days to generate a rogue TLS certificate. Despite the fatal flaw being well known, a small part of Microsoft’s sprawling infrastructure still used the hash function.
Determined to keep a similar scenario from playing out again, organizations everywhere are rolling out new algorithms to replace RSA and elliptic curves. For more than three decades, the two public-key algorithms have been known to be vulnerable to Shor’s algorithm, a series of equations that allow a quantum computer of sufficient strength to solve the mathematical problems underpinning these two algorithms in polynomial time, a dramatic speed-up from the exponential time required by classical computers.