3
$\begingroup$

Here: http://safecurves.cr.yp.to/ , I read that the NIST P-256 elliptic-curve is not safe.

The article lists several aspects (off-curve point, side-channel, etc.) where implementing P256 can fail the security, how should we understand these?

I think this is valid for encrypting, but are these also valid for signing?

Improve this question
$\endgroup$
4
  • 8
    $\begingroup$ P256 is secure, it just lacks some nice-to-have features that make writing a fast and secure implementation easier. $\endgroup$
    – CodesInChaos
    Oct 13, 2017 at 7:11
  • $\begingroup$ Reading the article reminds me why we should not implement our own crypto but use libraries written by people who know what/how they are doing. $\endgroup$
    – gusto2
    Oct 13, 2017 at 7:33
  • 2
    $\begingroup$ Claiming NIST curves as insecure but some obscure never–heard–of curves as secure is IMHO complete bullshit. $\endgroup$
    – user27950
    Oct 13, 2017 at 15:02
  • $\begingroup$ As far as I know these attacks are for any use of the curve in crypto; i.e. it is not tied to any specific use case such as encryption / signing. $\endgroup$
    – Maarten Bodewes ♦
    Jun 14, 2018 at 11:47

2 Answers 2

Reset to default
2
$\begingroup$

Quoting CodesInChaos:

P256 is secure, it just lacks some nice-to-have features that make writing a fast and secure implementation easier.

Improve this answer
$\endgroup$
-1
$\begingroup$

The seed used in the pre-hash of the SHA1 function for P256 parameter generation (c49d3608 86e70493 6a6678e1 139d26b7 819f7e90) seems to never have been verified. If a large chunk of randomly generated curves are "weak", they could have just iterated random numbers to find this value. The seed was not some simple, small low-entropy constant < 10 or something*. https://credelius.com/credelius/?p=97

This post explains the standard selection process by which the curves were selected: https://dissect.crocs.fi.muni.cz/standards/nist and reference 7 links to this article saying Solinas (who was formerly at the NSA) suggested the NIST curves.

There are some additional dubious posts on Stack Overflow:

Should we trust the NIST-recommended ECC parameters?

How were the P-256 parameters chosen?

And Twitter:

https://twitter.com/sweis/status/1176542191994335234?lang=en

Matthew Green rebutts this argument, saying ECCs are fundamentally broken if the NSA was able to use seeds to break curve parameters, which mathematicians would have found. Also, NSA's push for ECC may come from quantum computers breaking ECCs earlier than RSA*:

https://blog.cryptographyengineering.com/2015/10/22/a-riddle-wrapped-in-curve/

*=added due to commenters

Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ This is a conspiracy theory that posits the NSA has, for decades, been secretly aware a vulnerability in elliptic curves that both affects a significant fraction of curves and has somehow eluded the cryptography research community all along. $\endgroup$
    – Mehdi Tibouchi
    Sep 9 at 2:24
  • 2
    $\begingroup$ Why did NIST use the unexplained seed c49d3608 86e70493 6a6678e1 139d26b7 819f7e90 as the pre-image of the SHA1 hash used to generate the P256 parameters, instead of a low entropy value like 0 or 1 instead? I agree that the chance that the NSA has deluded the cryptography community is small, but I want to make sure that I am making a future-proof decision by opting to use P256, and am worried about where this random string came from. Matthew Green does provide a good argument that ECCs are broken if the NSA can do this: blog.cryptographyengineering.com/2015/10/22/a-riddle-wrapped-in-curve/ $\endgroup$
    – John Targaryen
    Sep 19 at 9:13
  • 1
    $\begingroup$ @JohnTargaryen: did NIST actually generate that curve? The earliest reference I could find of that curve was as an example (J.5.3) in a 1998 draft of ANSI X9-62. While NIST may have contributed that curve to X9-62, I don't know if they did... $\endgroup$
    – poncho
    Sep 19 at 11:41
  • 2
    $\begingroup$ Most likely, the algorithm to pick that number was to pick random numbers and retry until the resulting curve had prime order, etc. I agree with the Koblitz–Menezes argument presented in Matthew Green's post that says that if one takes the conspiracy theory seriously, one shouldn't use elliptic curves at all (and if you ask, I don't expect any of them would tell you that they actually take the conspiracy theory seriously). $\endgroup$
    – Mehdi Tibouchi
    Sep 19 at 14:17
  • 1
    $\begingroup$ Regarding Matthew Green's article you linked to, one of the claims he makes has a straightforward explanation: "if quantum computing is a risk why (NSA suggests to) stop using ECC but keep on using RSA". Well quantum attacks are generic attacks, and RSA keylength is much larger than ECC keylength so in some sense as the QC [if it's ever built] scales up in capability ECC will be threatened much earlier than RSA. $\endgroup$
    – kodlu
    Sep 19 at 15:40

Your Answer

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

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