8
$\begingroup$

Background: there is a theory going around that claims that P256 was backdoored by the NSA. The theory goes is that the NSA found a weakness that applies to a nontrivial fraction of elliptic curves (perhaps one in a thousand, perhaps one in a trillion). So, what the NSA supposedly did is use a published procedure to generate elliptic curves, and cycled through thousands/trillions of seeds, generating the curves for those seeds, until they found such a weak curve. They then convinced people to use it.

Now, critical to this theory is that the curve P256 was originally generated by the NSA; is this true?

Now, the earliest reference I could find to the curve parameters now known as P256 is in this early draft of X9.62, dated 1998. This draft presents (in annex A.3.3.2) a way of selecting an $a, b$ pair based on the seed and prime $p$. That procedure doesn't yield a unique $a, b$ pair unless one of them was preselected (in the case of P256, they selected $a = p-3$, and that gives a unique $b$ value).

The draft latter gives some examples of using the above procedure for generating curves; in annex J.5.3, it gives an example of a 256 bit prime elliptic curve; those curve parameters are P256.

One way of viewing annex J.5.3 is as a test vector for the curve generation procedure, and was never specifically intended for wide scale use; the authors may very well have expected people to use the procedure with their own seeds. I would also note that random looking inputs are common for test vectors.

Now, this is speculation based on what I see in the text. My question: does anyone know anything more about the background (and what was happening internally in X9)? I know that NIST has been active in X9 in the past; I don't know if they were active back in 1998...

$\endgroup$
6
  • 1
    $\begingroup$ Someone tried a FOIA request and got nothing, appealed and got nothing; see the thread here muckrock.com/foi/united-states-of-america-10/… and the final letter here cdn.muckrock.com/foia_files/2020/02/14/… $\endgroup$
    – yoyo
    Sep 19, 2023 at 23:26
  • $\begingroup$ While I can appreciate it from some angles, from a purely mathematical perspective, I never understood why, out of all the primes and all the curves and all the points on those curves, only a handful of parameters ever get used. $\endgroup$
    – yoyo
    Sep 19, 2023 at 23:33
  • 1
    $\begingroup$ P256 already is in the X9.62 working draft of 1997-11-17. $\endgroup$
    – fgrieu
    Sep 20, 2023 at 5:21
  • 2
    $\begingroup$ Found this from Bernstein. Mentions Jerry Solinas, who is mentioned in this paper as working for the NSA from a quick search. $\endgroup$ Sep 20, 2023 at 6:36
  • 2
    $\begingroup$ Bernstein repeatedly mentions Jerry Solinas as the person who chose the NIST curves. This comment from a user on Hacker News also says the NSA/Jerry Solinas worked with Certicom engineers for choosing the curves. This Certicom document for X9.62 credits Jerry Solinas for contributions during development of the ECDSA standards. $\endgroup$ Sep 20, 2023 at 18:02

1 Answer 1

3
$\begingroup$

Jerry Solinas, an NSA employee, definitely provided the seeds. This has been confirmed by one of the authors of the ANSI X9.62 ECDSA standard (Alfred Menezes), who is also an author of a paper called 'A Riddle Wrapped in an Enigma' related to this topic:

Jerry Solinas did provide the seeds to me sometime in Fall 1997. At the time, I was the primary author of the ANSI X9.62 ECDSA standard, and Jerry was attending the standards meetings as an NSA representative. I don't know if Jerry selected the seeds himself, but in any case he was the person who contributed the seeds to the ANSI standards committee. (Jerry is the "NSA representative" mentioned on page 8 of my article with Neal Koblitz.)

It has also been corroborated by other people. Furthermore, Jerry Solinas is credited in the Acknowledgements of a Certicom paper on ECDSA:

The authors would like to thank the members of the ANSI X9F1 and IEEE P1363 working groups, and, in particular, Jerry Solinas, for their many comments and contributions during the development of the ECDSA standards.

Now, this is where it gets interesting. Jerry supposedly chose an English phrase/sentence (e.g. "Jerry deserves a raise.") and hashed it with SHA-1 to produce the seeds. However, he forgot the sentence, possibly due to his machine being replaced/upgraded. After controversy erupted, he tried 'every phrase that he could think of that was similar to this' without success. A story that has again been corroborated.

There's actually a \$12,288 bounty offered by Filippo Valsorda for (password) cracking the seeds. Half the bounty (\$6,144) goes to the first person to find at least one, and the other half goes to the person (or the same person) to find all five. I will try to update this answer if anything comes of this (remind me if I don't).

Unfortunately, it's not a simple task because this is all we know:

  1. SHA-1 should have been used.
  2. The sentence probably mentions Jerry (Solinas).
  3. Someone else (e.g. a colleague) may be mentioned.
  4. There's likely a counter since not every hash is suitable.
  5. Instead of a counter, it could be the hash was hashed repeatedly (SHA-1(SHA-1(phrase))) or incremented (IP2BS(BS2IP(hash) + 1)).

The P-192 and P-256 seeds were in ANSI X9.62, whereas the others were new to FIPS 186-2, meaning potential differences. There's also no clue to whether there's a full stop, where the counter is, how the counter is encoded, etc.

Of course, this assumes Jerry/the source of the story was telling the truth. It's theoretically possible this story is fiction (a cover story) and leading people on a wild-goose chase. Whilst we don't know the details, it feels like sloppy behaviour from the NSA. Just because it sounds believable/relatable doesn't guarantee it's true. Jerry could have been told to spread this story, with the other people sharing it not having witnessed Jerry generating the seeds. For all we know, Jerry didn't even generate the seeds. Perhaps we'll never know.

However, even if you argue this is a cover story, there are various arguments against malicious seeds. Summarised from 'A Riddle Wrapped in an Enigma':

  1. The class of weak curves must be extremely large to obtain a weak curve with the seeded-hash method, making it detectable by researchers. Even if you reduce the class size (still likely detectable), an infeasible amount of computation for 1997 ($2^{86}$ for P-256) had to be performed. No such weaknesses in the NIST curves has ever been found after over 20 years.
  2. The NSA would have deliberately selected weak elliptic curves for US government usage (unclassified/classified), meaning they would have had to have been confident that nobody else would discover the weakness in the future whilst they're still in use.
  3. The NIST curves were generated by the Information Assurance Directorate (IAD) under Brian Snow and Mike Jacobs in the 1990s, who were the defensive arm of the NSA and pushed for security during that period. Furthermore, most of the Snowden revelations, including the backdoored Dual_EC_DRBG, concern much later events. We shouldn't project what we know about the NSA post-2001 back to the 1990s.

The authors concluded:

there is no plausible reason to mistrust the NIST curves

But they mentioned two reasons why other curves may be preferable:

  1. Public perception = the NIST curves are backdoored. You avoid controversy/get brownie points by using something else.
  2. Other curves have some advantages, although there have been improvements with the NIST curves, they're standardised/popular, and there are other problems with different types of curves.

In sum, you can argue either way about whether to use the NIST curves. The consensus among cryptographers seems to be that they're safe, but there are other popular, newer curves now.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.