Sometime 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.

The event, whichcame to lightin 2012, now serves as a cautionary tale for cryptography engineers as they contemplate the downfall of two crucial cryptography algorithms used everywhere. Since2004, 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,twoother pieces ofresearchfurther 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 toShor’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.

Earlier this month, both Google and Cloudflarebumped uptheir internal deadline for PQC (post-quantum cryptography) readiness to 2029, an acceleration of roughly five years. The moves were largely prompted by two pieces of research showing that CRQC (cryptographically relevant quantum computing/computer) may arrive sooner than previously estimated.

While there’s little known evidence that a CRQC will emerge in the next four years, the revised deadlines set a good example for peers such as Amazon and Microsoft, whose timelines are two to six years longer. They also largely align with US government goals; the Defense Department is requiring all national security systems to use quantum-safe algorithms by December 31, 2031, and the National Institute of Standards and Technology is calling for the deprecation of vulnerable algorithms by 2035. While many expertsstrongly doubtCRQC will arrive by 2029, others say an industry-wide acceleration is necessary given the stakes and the difficulty of the work required to be ready.

“You have to remember that transitioning the Internet to post-quantum, especially for digital signatures, is a massive undertaking,” Dan Boneh, a computer scientist and cryptographer at Stanford University, said in an interview. “It would be amazing if the entire Internet can get it all done by 2029. By setting a 2029 goal, they are giving themselves some slack in case they fail to meet that deadline. If they target 2035 and miss by two to three years, we are getting uncomfortably close to the danger zone.”

Brian LaMacchia, a cryptography engineer who oversaw Microsoft’s post-quantum transition from 2015 to 2022 and now works at Farcaster Consulting Group, agreed.

PQC readiness “is mostly actuarial/risk management—even if the chance of building a CRQC by, say, 2030 is very low (say 5 percent), the downside risk is huge,” he explained. “Combine that with very long transition engineering times, and you should have started already.”

Source: Drudge Report