[api]

There’s a strong argument against back doors of this type in ECC.

To back door the NIST curves would require that the NSA knows a secret attack against ECC and used brute force search to find seed hashes to generate the curves to be vulnerable. It would have to be a secret attack since nobody else has found it.

Thing is… if this is true it means there is a secret attack against some elliptic curves.

Using 1990s technology they couldn’t have brute forced all that many curves, meaning some non-trivial percentage of curves must be vulnerable.

How do we know curve25519 isn’t vulnerable to this secret attack? We don’t.

The ultimate conclusion is that if NIST curves are backdoored using secret math we shouldn’t use ECC at all, at least unless NSA discloses the math. But they couldn’t do that without blowing up the Internet since so much uses the NIST curves. It would be an argument to phase out all ECC.

[mike_hearn]

The argument for a back door goes like this:

1. The NSA is one of the world's only institutions that has any use for the otherwise irrelevant specialism of designing asymmetrically backdoored cryptography algorithms. They also have (or had) lots of maths PhDs writing internal papers. It's reasonable to assume they know things about kleptography that others don't, as it's not a well funded sub-field of cryptography outside the signals intelligence world. So if there was an attack they'd discovered it wouldn't be surprising if others didn't find it.

2. A good protection against kleptographic attacks is to use "nothing up my sleeve numbers", where the constants that go into an algorithm are derived from some well known source that isn't suspicious.

3. The NIST curves know about this sort of risk and attempt to use NUMS numbers. The constants are derived from the output of SHA1, which at the time was considered secure.

4. But the input to SHA1 is a giant random-looking number, not something obvious and above suspicion. Thus the setup fails to provide the assurance it was supposed to create because the NSA could have searched for a weak curve (if there was such a thing to begin with).

The argument that curve25519 wouldn't be susceptible is simply that curve25519 uses NUMS numbers properly, and so there's no wiggle room where djb or anyone else could have done a secret scan to find curves with certain properties.

As may be clear, how strong you think the above argument / problem is, will depend entirely on your intuition about how well explored kleptography is by non-secret research. Unfortunately as people generally don't publish negative results that's very hard to judge.

[tptacek]

From memory, so I'm probably wrong, but: I thought the bona fides for Curve25519's design was that it demonstrated clear engineering reasons for all its choices, and Bernstein's issue with other curves was that NUMS constants (like pi, e, etc) were manipulable in the sense that you could take permutations of them --- the (silly) B4D455 paper.

[schoen]

NSA did make a mysterious announcement a few years ago that people should not use ECC and should go back to older public-key methods. Of course, due to their fundamental conflict of interest and reluctance to share their rationale, very few organizations that didn't have to follow that guidance apparently did so.

[zahllos]

This is a bit misinformed.

NSA required the use of "Suite B Cryptography" for commercial vendors of government systems, which in its latest revision meant ECC. However, vendors were (and are) slow to adopt ECC from the previously used RSA. If you want public evidence of how slow such transitions can be, check any other commercial crypto like certificate authorities and see which trust chains are entirely elliptic curve. Mostly people are stuck on RSA, even though elliptic curves broadly offer better speed and smaller keys/signatures for the same or better levels of security. There's also still plenty of deployed DES and SHA-1, even though the former is inadvisable and the latter inexcusable. In fact, from what I read in the response to the NSA proposing to drop SHA-3 in favour of SHA-2 in the new PQ standards, vendors were a bit frustrated at the change because of the short timescale involved in the migration. I interpret the demanding schedule for adoption of PQC as a deliberate choice by NSA - a somewhat passive aggressive response to vendors to tell them to get their acts together, based on their experience of trying to roll out ECC.

What NSA said is "if you haven't migrated to elliptic curve cryptography, you should now wait for post quantum and then start on that". You can read that message here: https://web.archive.org/web/20151123081120/https://www.nsa.g... and here is the exact quote:

> For those partners and vendors that have not yet made the transition to Suite B elliptic curve algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum resistant algorithm transition.

I don't think there's much mystery here - basically it amounts to a bunch of procurement rules and guidelines.

[schoen]

I wasn't aware of this interpretation. Thanks.

[api]

If they won’t share the rationale then we are back to speculating.

They are now pushing PQ crypto because they think, probably reasonably, that we are one or two breakthroughs from a scalable quantum computer.

[cheschire]

“Post quantum”, for anyone else confused by this seemingly obscure acronym.