12
$\begingroup$

I am surely not an expert on the field, but I heard some people say that NIST P-256 somehow has backdoors. I don't know about the seriousness of this claim; maybe it's just a conspiracy theory.

If there is some truth to the hearsay, why is NIST P-256 still implemented? Almost everyone I asked said it's a bad idea to use P-256. If this is true:

  1. Why is it still in GPG (as of 2017)?
  2. Does it have any use (expect legacy and compatibility)?
  3. Is it really broken to the point to be unsafe to be used, in a professional environment?
$\endgroup$
2

2 Answers 2

24
$\begingroup$

Because P-256 is the most used elliptic curve and there are no certain reasons to believe it's insecure. It's the first standardized curve at the 128 bit security level (which is very popular).

The rumors about its backdoor came from 3 factors:

  • The Snowden's revelations included a generic claim of the NSA trying to backdoor NIST standardized crypto
  • DualEC DRBG being a NIST standard actually backdoored by the NSA
  • Daniel J. Bernstein trying to push for his own curve25519

But there is no backdoor connection between DuelEC DRBG and NIST Curves and we have no idea about how to backdoor an elliptic curve. Bernstein and Lange built a site claiming P-256 is not safe. But it actually boils down to the fact that NIST curves, generated in the 90s, lack some of the fancy features of more modern elliptic curves, as the fancy techniques were not known at the time.

To address your questions directly:

  1. For compatibility reasons, since it's the most used elliptic curve.
  2. Yes of course, e.g. TLS.
  3. No, we believe it's secure.
$\endgroup$
6
  • 17
    $\begingroup$ I think this answer is being a bit unfair with DJB: NIST P-256 uses the notorious unexplained seed c49d3608 86e70493 6a6678e1 139d26b7 819f7e90, which is why many cryptographers are suspicious about this curve. $\endgroup$
    – br1
    Commented Apr 3, 2018 at 18:04
  • 2
    $\begingroup$ @br1 I admit to have a strong opinion on the ridigity topic. I also don't believe there is a single cryptographer(let's define it, in this context, as a person who has at least one peer reviewed paper slightly related to ECC) who genuinely believes NIST curves are backdoored. $\endgroup$
    – Ruggero
    Commented Apr 4, 2018 at 10:03
  • 6
    $\begingroup$ There are several academic cryptographers who published interesting works on this topic, search for keywords such as: Brainpool, NUMS, Million Dollar Curve. I don't know if they believe that some standard curves are backdoored, but at least they seem very cautious about using unexplained parameters, which is why some alternatives are proposed. $\endgroup$
    – br1
    Commented Apr 6, 2018 at 1:04
  • 3
    $\begingroup$ @Ruggero There are, however, reputable cryptographers who do find it suspicious. I don't think anyone thinks it's backdoored for sure, but the risk is there (after all, a breakthrough in ECC cryptanalysis could find a large enough class of weak curves that some could be found through passing the seed through SHA-1 by brute force). $\endgroup$
    – forest
    Commented May 28, 2018 at 2:01
  • 9
    $\begingroup$ I think yall misunderstand what Bernstein & Lange are saying with SafeCurves. The main issue with P-256 is that it's hard to get everyone to implement it correctly without having bugs that leak secret information. They did a good talk—search "SchmooCon 2014 SafeCurves" on YouTube, if you jump to about 32 minutes in, Tanja illustrates the difference between Edwards curves (eg. 25519) vs Weierstrass curves (P-256). Regarding the unexplained seed, they're not saying they think P-256 is actually backdoored, but that it could be, and there's no built-in way to convince anyone that it isn't. $\endgroup$
    – dlitz
    Commented Feb 21, 2019 at 14:53
7
$\begingroup$

Daniel J. Bernstein's Safe Curves page has most of the info you want. To summarize:

1) Because it is approved for use by the US government, and they require the use of approved curves when interacting with them. Other agencies have similar requirements.

2) Outside of such contracts, no.

3) Possibly not, but there are curves which are safer and more efficient. Thus, if you don't have to use it you shouldn't. It isn't broken, but it is brittle: there are several very subtle errors that can be made when implementing it which will cause a break.

$\endgroup$
3
  • $\begingroup$ "there are curves which are safer and more efficient", could you provide some? $\endgroup$
    – auxten
    Commented Oct 15, 2018 at 2:38
  • 1
    $\begingroup$ The link to the safe curves page lists most of them. Those with a green check as "safe" are the ones you want. $\endgroup$ Commented Oct 16, 2018 at 15:25
  • 1
    $\begingroup$ I knew this safe curves page and also did some benchmark here: github.com/CovenantSQL/CovenantSQL/blob/develop/crypto/… . Maybe ed25519 or other curves are safer(?) but according to my bench result, P256 is the fastest curve. gist.github.com/auxten/7f612c197200ced21a04bbee507b3635 $\endgroup$
    – auxten
    Commented Oct 17, 2018 at 8:46

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.