The National Security Agency has long cuddled up to Elliptic Curve Cryptography, swaying standards bodies away from RSA crypto and toward ECC in the late 1990s, as well as recommending it as a strong enough solution for sensitive government agencies to use in guarding their biggest secrets.
In August, however, the NSA let it publicly slip, in relatively hushed tones, that it was divorcing itself from Suite B, a 20-year-old public crypto standard that relied on ECC and was certified for top secret data protection. The agency suggests concerns over advances in quantum computing as the reason for its about-face in support of Suite-B.
“Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, which has made it clear that elliptic curve cryptography is not the long term solution many once hoped it would be,” the NSA said in its Aug. 19 statement. “Thus, we have been obligated to update our strategy.”
Cryptographers, however, aren’t buying that reasoning.
In an admittedly not-so-academic paper, entitled “A Riddle Wrapped in an Enigma,” noted cryptographers Neal Koblitz and Alfred J. Menezes ponder possible explanations, none of which are as concrete as their resolve that post quantum computing advances aren’t the answer.
The Snowden documents, the clearest window into the NSA’s capabilities, show no supreme advances in this field, and the researchers point out that the portion of the agency’s budget devoted to this study ($80M) is meager. They put it at best that there’s a 50-50 chance of a practical quantum computer being available before 2030.
The paper refutes theories that the NSA can break ECC, or even post quantum computing. The PQC theory suggests that the NSA’s stiff-arm against ECC is rooted in a desire to hurry along the standardization of PQC and perhaps introduce some of the same weaknesses that plague Dual EC-DRBG, for example, opening the door for exploitation by the agency.
“If the NSA has some ideas on how to attack PQC, then it is likely that before long people outside the NSA would have similar ideas,” Koblitz and Menezes wrote. “In particular, the cryptographers of other nations (such as Russia and China) would soon be able to attack private and government users in the U.S., and part of the NSA’s mission is to prevent this.”
Complementary to its decision to move away from ECC was also the NSA’s deprecation of P-256, the smallest of the standard ECC curves. Koblitz and Menezes also shoot down thinking that the NSA believes RSA-3072, the RSA alternative to ECC 256 and ECC 384, is more resistant to advances in quantum computing. However, the cryptographers point out that once sufficient physics and engineering breakthroughs make it possible to crack P-256, it’s only a question of investing adequate resources in cracking RSA-3072.
So what’s up here?
Matthew Green, a cryptographer and Johns Hopkins University professor, speculates that the NSA isn’t worried about quantum computing, instead it could have made advances in cryptanalysis of the elliptic curve discrete logarithm problem (ECDLP).
“And panic is the result,” Green wrote in a blog post this week.
ECDLP is thought to be impractical and close to impossible to arrive at; the security of ECC rests on its shoulders. And as Green says in his post, the problem must be close to impossible to solve, otherwise, cryptosystems that rely upon it are useless. ECDLP is also much more efficient than RSA, which requires 3072 bits to achieve the same security ECDLP can in 256 bits.
“But while the ability to use (relatively) tiny elliptic curve points is wonderful for implementers, it leaves no room for error,” Green wrote. “If 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 also analyzes points made in the Koblitz and Menezes paper as to whether the NSA had backdoored NIST elliptic curves. Since it’s believed the NSA influenced NIST standards development in this arena—see Dual EC DRBG—the thinking is that the NSA has found a weak elliptic curve it could exploit and crack secure communication.
For this to be true, Green said, a “vast proportion” of curves would have to be weak in order to be compromised. If this is the case, this could also be a plausible reason for the agency to recommend and immediate abandon ship.
“The implication of such a large class of vulnerable curves is very bad for the field of ECC. It dwarfs every previous known weak curve class and would call into question the decision to use ECC at all,” Green wrote, adding that if Koblitz and Menezes are right, the answer would be to abandon ECC.
“In other words, Koblitz and Menezes are saying that if you accept the weak curve hypothesis into your heart, the solution is not to replace the NIST elliptic curves with anything at all, but rather, to leave the building as rapidly as possible and perhaps not shut the door on the way out. No joke,” Green wrote. “On the gripping hand, this sounds very much like the plan NSA is currently implementing. Perhaps we should be worried.”
