Cryptography Developments: Elliptic Curves, Part 2

Last week I started telling you about an recent interesting paper, “A Riddle Wrapped in an Enigma” by two highly respected cryptographers, Neal Koblitz and Alfred Menezes.

I gave you the background last week: the NSA’s long interest in ECC (or Elliptic Curve Cryptography), some reports of NSA back doors inserted into standardized algorithms, and the startling announcement from the NSA this past August that organizations that haven’t yet converted from RSA to ECC shouldn’t bother. We need post-quantum cryptography, also called quantum-resistant.

Learning Tree’s System and Network Security Introduction course explains the need for various cryptographic technologies, and the advantages of asymmetric algorithms like ECC. But we don’t usually get into speculation and conspiracy theories. Let’s see what Koblitz and Menezes came up with as possible explanations of the NSA’s announcement.

Does the NSA have a general-purpose quantum computer?

Based on the Snowden revelations, no.

Work to build a “cryptologically useful quantum computer” is funded by a small fraction of the NSA’s budget. A Washington Post article concludes “the documents provided by Snowden suggest that the NSA is no closer to success than others in the scientific community.” If NSA or someone else was close to building one, this would be much more heavily funded.

Can the NSA break ECC?

No, they conclude.

NSA advocacy for ECC dates from a period when their Information Assurance Directorate, the defensive arm, pushed for strong security. It wasn’t until 9/11 and the Patriot Act that influence shifted to Signals Intelligence (or SIGINT), the offensive side. At any time, if NSA knows how to break ECC, the weakness is likely to be discovered by others before long.

Are the NIST curves weak?

This is unlikely for a combination of technical and historical reasons.

Their explanation is the most mathematical section of the paper. The math-free summary is that given the methods of curve generation and selection, a back door would require the existence of a large and strikingly unusual class of curves, the very thing that ECC researchers have been looking for at least since the mid 1990s. It would also mean that the NSA had been deliberately recommending weak protection for Top Secret material for twenty years.

ECC has been researched at least since the mid 1980s. In 2000, NIST published FIPS-186-2, defining 15 elliptic curves providing varying security levels.

Mind you, it’s time to move to a new family of curves for other reasons, as described here. But it’s not as if the NIST curves are likely to have back doors.

What about side-channel attacks?

For example, modifying firmware to steal information when cryptography isn’t protecting it. That’s certainly a problem, but it’s one to be solved with physical isolation and tamper-proof devices, not by the mathematics bypassed by side-channel attacks.

Was the NSA careless, embarrassed, or in a panic when they made the announcement?

This is the most amusingly wild-eyed theory. Maybe after the Dual EC_DRBG scandal the NSA felt that any further guidance about ECC would be assumed to be further promotion of back doors, so they needed a clean start with fresh ideas from academia on post-quantum cryptography. That would mean ignoring all underlying start-of-the-art technical knowledge, meaning that it was a crazy response done because they’re even more crazy than we suspect.

It’s good that it was included in the interest of completeness, but no. A policy statement is the result of a long period of discussions and drafts.

Besides, the original August announcement has already been quietly modified a number of times. The changes were relatively minor clarifications of wording or expanded detail, not “Never mind, the intern responsible for that nonsense has been sacked.”

Does the NSA know about flaws in proposed post-quantum systems?

The theory here is that NSA hopes the world recklessly rushes into something NSA can break more easily than RSA or ECC. Again, as with the speculation that NSA can break ECC, this doesn’t make sense. The U.S. has no monopoly on math skill.

Was the announcement intended for government agencies with higher security requirements?

No, it was a very public statement that will influence private industry. If anything, this might suggest that RSA is weaker than we know and NSA wants to give industry an excuse not to move to ECC.

Has the NSA made advances in classical cryptanalysis of ECC?

Or at least suspect that one is likely to be found soon?

This may be the most interesting theory, although really no more provable than any of the others. ECC security is based on the difficulty of the elliptic curve discrete logarithm problem. Maybe NSA feels that analytical advances are here or at least eminent.

Or maybe it’s just caution…

It’s the least exciting of the possibilities, but I think the best explanation is that this is simply an abundance of caution. NSA doesn’t have a quantum computer, they don’t know exactly when one will be developed, but it might be soon so let’s get ready.

Type to search

Do you mean "" ?

Sorry, no results were found for your query.

Please check your spelling and try your search again.