Quantum computing, once elliptic curve crypto was viewed as a savior. Now its future looks doomed.
In August, National Security Agency officials advised US agencies and businesses to prepare for a not-too-distant time when the cryptography protecting virtually all sensitive government and business communications is rendered obsolete by quantum computing. The advisory recommended backing away from plans to deploy elliptic curve cryptography, a form of public key cryptography that the NSA spent the previous 20 years promoting as more secure than the older RSA cryptosystem.
Almost immediately, the dramatic about-face generated questions and anxiety. Why would the NSA abruptly abandon a series of ECC specifications it had championed for so long? Why were officials issuing the advice now when a working quantum computer was 10 to 50 years away, and why would they back away from ECC before recommending a suite of quantum-resistant alternatives? The fact that the NSA was continuing to endorse use of RSA, which is also vulnerable to quantum computing, led some observers to speculate there was a secret motivation that had nothing to do with quantum computing.
On Tuesday, researchers Neal Koblitz and Alfred J. Menezes published a paper titled A Riddle Wrapped in an Enigma that compiles some of the competing theories behind the August advisory. The researchers stressed that that their paper isn’t academic and at times relies on unsourced facts and opinions. And sure enough, some of the theories sound almost conspiratorial. Still, the paper does a good job of evaluating the strengths and weaknesses of the NSA’s highly unexpected abandonment of ECC in a post quantum crypto (PQC) world.
“The PQC announcement suggests that NSA has no interest in this topic because it now views ECC as only a stopgap solution,” the researchers wrote. “This caught many people by surprise, since it is widely believed that ECC will continue to be used extensively for at least another decade or two.”
The researchers remain skeptical that quantum computing is the real reason for backing away from ECC. Documents leaked by former NSA subcontractor Edward Snowden have so far given no indication of any advances in the field that pose an imminent threat to any form of public key crypto. The budget for quantum-based research is modest by NSA standards, an indication that neither the US nor any other country is on the brink of a breakthrough, they said.
The theory that has generated the most attention among readers is that NSA researchers are now aware of breakthroughs that are unrelated to quantum computing that threaten ECC but not RSA. Matt Green, a Johns Hopkins University professor specializing in cryptography, notes the advance might involve classical cryptanalysis of what’s known as the elliptic curve discrete logarithm problem (ECDLP). To date, the mathematical problem is believed to be so hard to solve that properly implemented ECC can’t be broken without requiring millions or even billions of years. But there’s no proof this assumption is correct. If NSA researchers stumbled on a new way to tackle the problem efficiently, it would torpedo the entire suite of crypto schemes banks, government subcontractors, and others have been using at the strong urging of the federal government.
“If the NSA’s mathematicians began to make even modest, but sustained advances in the state of the art for solving the ECDLP, it would put the entire field at risk,” Green wrote in a blog post. “Beginning with the smallest of the standard curves, P-256, which would now provided less than the required 128-bit security.”
P-256 refers to a curve set in a 256-bit field. Because of the exponential number of operations required to solve ECDLP provides the equivalent of 128 bits of security, the minimum threshold mandates for encrypting classified material. A little-noticed provision in the NSA’s August communication, Green noted, was the announcement that P-256 was being retired.
While not everyone agrees with the theories, the paper makes a compelling argument that NSA researchers are aware of new information they have yet to disclose that’s causing them to lose confidence in cryptography they were among the first to champion in the late 1990s and have continued to support ever since. More recently, ECC has been embraced as the alternative to the frailer RSA cryptosystem. The NSA’s announcement is causing some researchers to question that assumption. Hanging in the balance is the security of just countless industrialized governments, banks, and websites everywhere.
