NSA security advisory sparks concern of cryptoapocalypse
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.