115

I am currently renewing an SSL certificate, and I was considering switching to elliptic curves. Per Bernstein and Lange, I know that some curves should not be used but I'm having difficulties selecting the correct ones in OpenSSL:

$ openssl ecparam -list_curves
  secp112r1 : SECG/WTLS curve over a 112 bit prime field
  secp112r2 : SECG curve over a 112 bit prime field
  secp128r1 : SECG curve over a 128 bit prime field
  secp128r2 : SECG curve over a 128 bit prime field
  secp160k1 : SECG curve over a 160 bit prime field
  secp160r1 : SECG curve over a 160 bit prime field
  secp160r2 : SECG/WTLS curve over a 160 bit prime field
  secp192k1 : SECG curve over a 192 bit prime field
  secp224k1 : SECG curve over a 224 bit prime field
  secp224r1 : NIST/SECG curve over a 224 bit prime field
  secp256k1 : SECG curve over a 256 bit prime field
  secp384r1 : NIST/SECG curve over a 384 bit prime field
  secp521r1 : NIST/SECG curve over a 521 bit prime field
  prime192v1: NIST/X9.62/SECG curve over a 192 bit prime field
  prime192v2: X9.62 curve over a 192 bit prime field
  prime192v3: X9.62 curve over a 192 bit prime field
  prime239v1: X9.62 curve over a 239 bit prime field
  prime239v2: X9.62 curve over a 239 bit prime field
  prime239v3: X9.62 curve over a 239 bit prime field
  prime256v1: X9.62/SECG curve over a 256 bit prime field
  sect113r1 : SECG curve over a 113 bit binary field
  sect113r2 : SECG curve over a 113 bit binary field
  sect131r1 : SECG/WTLS curve over a 131 bit binary field
  sect131r2 : SECG curve over a 131 bit binary field
  sect163k1 : NIST/SECG/WTLS curve over a 163 bit binary field
  sect163r1 : SECG curve over a 163 bit binary field
  sect163r2 : NIST/SECG curve over a 163 bit binary field
  sect193r1 : SECG curve over a 193 bit binary field
  sect193r2 : SECG curve over a 193 bit binary field
  sect233k1 : NIST/SECG/WTLS curve over a 233 bit binary field
  sect233r1 : NIST/SECG/WTLS curve over a 233 bit binary field
  sect239k1 : SECG curve over a 239 bit binary field
  sect283k1 : NIST/SECG curve over a 283 bit binary field
  sect283r1 : NIST/SECG curve over a 283 bit binary field
  sect409k1 : NIST/SECG curve over a 409 bit binary field
  sect409r1 : NIST/SECG curve over a 409 bit binary field
  sect571k1 : NIST/SECG curve over a 571 bit binary field
  sect571r1 : NIST/SECG curve over a 571 bit binary field
  c2pnb163v1: X9.62 curve over a 163 bit binary field
  c2pnb163v2: X9.62 curve over a 163 bit binary field
  c2pnb163v3: X9.62 curve over a 163 bit binary field
  c2pnb176v1: X9.62 curve over a 176 bit binary field
  c2tnb191v1: X9.62 curve over a 191 bit binary field
  c2tnb191v2: X9.62 curve over a 191 bit binary field
  c2tnb191v3: X9.62 curve over a 191 bit binary field
  c2pnb208w1: X9.62 curve over a 208 bit binary field
  c2tnb239v1: X9.62 curve over a 239 bit binary field
  c2tnb239v2: X9.62 curve over a 239 bit binary field
  c2tnb239v3: X9.62 curve over a 239 bit binary field
  c2pnb272w1: X9.62 curve over a 272 bit binary field
  c2pnb304w1: X9.62 curve over a 304 bit binary field
  c2tnb359v1: X9.62 curve over a 359 bit binary field
  c2pnb368w1: X9.62 curve over a 368 bit binary field
  c2tnb431r1: X9.62 curve over a 431 bit binary field
  wap-wsg-idm-ecid-wtls1: WTLS curve over a 113 bit binary field
  wap-wsg-idm-ecid-wtls3: NIST/SECG/WTLS curve over a 163 bit binary field
  wap-wsg-idm-ecid-wtls4: SECG curve over a 113 bit binary field
  wap-wsg-idm-ecid-wtls5: X9.62 curve over a 163 bit binary field
  wap-wsg-idm-ecid-wtls6: SECG/WTLS curve over a 112 bit prime field
  wap-wsg-idm-ecid-wtls7: SECG/WTLS curve over a 160 bit prime field
  wap-wsg-idm-ecid-wtls8: WTLS curve over a 112 bit prime field
  wap-wsg-idm-ecid-wtls9: WTLS curve over a 160 bit prime field
  wap-wsg-idm-ecid-wtls10: NIST/SECG/WTLS curve over a 233 bit binary field
  wap-wsg-idm-ecid-wtls11: NIST/SECG/WTLS curve over a 233 bit binary field
  wap-wsg-idm-ecid-wtls12: WTLS curvs over a 224 bit prime field
  Oakley-EC2N-3:
        IPSec/IKE/Oakley curve #3 over a 155 bit binary field.
        Not suitable for ECDSA.
        Questionable extension field!
  Oakley-EC2N-4:
        IPSec/IKE/Oakley curve #4 over a 185 bit binary field.
        Not suitable for ECDSA.
        Questionable extension field!

Could a kind cryptographer point out to me which curves are still considered safe?

executifs
  • 4,772
  • 4
  • 23
  • 25
  • 9
    Aren't NIST curves considered a little risky since the NSA is said to have had some input/influence on these? –  Mar 02 '16 at 04:16
  • Can you generate your own curve using an even bigger prime and have it work with unmodified clients? I imagine that if you picked the right and large enough prime that would be the safest. Something over 1024 bit (no such thing as overkill). Could you even use the same size primes as with rsa (so 4k or 8k)? Generating the curve would obviously take a long time but so would brute forcing it + I doubt anyone has precalculated values for them. – Mr. C Oct 12 '16 at 00:05
  • 2
    NO. People used to think allowing the two sides to agree on parameters for a curve and then perform operations on a custom curve defined by those parameters was a good idea. Currently CFRG think it's a bad idea. Also overkill is a bad idea - people perform crypto on smart cards and the like. The procedure to generate safe curve at a specified size is complicated and needs to be performed only a few times by experts. That is how Curve25519 and Curve448 were defined. Software will probably use assembly code specific to those curves to get side channel safe fast implementations. – Z.T. Oct 12 '16 at 00:32

3 Answers3

124

You are misreading Bernstein and Lange's advice (admittedly, their presentation is a bit misleading, with the scary red "False" tags). What they mean is not that some curves are inherently unsafe, but that safe implementation of some curves is easier than for others (e.g. with regards to library behaviour when it encounters something which purports to be the encoding of a valid curve point, but is not).

What you really want is a curve such that:

  • the software which you will entrust with your private key (your SSL server) is properly implemented and will not leak details about your private key;
  • interoperability will be achieved.

For a SSL server certificate, an "elliptic curve" certificate will be used only with digital signatures (ECDSA algorithm). The server will sign only messages that it generates itself; and, in any case, the only "private" operation involving a curve in ECDSA is multiplication of the conventional base point (hardcoded, since it is part of the curve definition, hence correct) by a random value that the server generates. Therefore, in your use case, there is no risk of private key leakage that would be specific to the used curve. If your SSL implementation is poor, it will be poor for all curves, not for just some of them.

"Interoperability" means that you would probably prefer it if SSL clients can actually connect to your server; otherwise, having a SSL server would be rather pointless. This simplifies the question a lot: in practice, average clients only support two curves, the ones which are designated in so-called NSA Suite B: these are NIST curves P-256 and P-384 (in OpenSSL, they are designated as, respectively, "prime256v1" and "secp384r1"). If you use any other curve, then some widespread Web browsers (e.g. Internet Explorer, Firefox...) will be unable to talk to your server.

Use P-256 to minimize trouble. If you feel that your manhood is threatened by using a 256-bit curve where a 384-bit curve is available, then use P-384: it will increases your computational and network costs (a factor of about 3 for CPU, a few extra dozen bytes on the network) but this is likely to be negligible in practice (in a SSL-powered Web server, the heavy cost is in "Web", not "SSL").

Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • 52
    My manhood is feeling threatened indeed. Thank you very much for your clear answer! – executifs Jan 07 '15 at 18:09
  • 2
    The site linked to by the OP explicitly lists P-256 and P-384 as unsafe, and says "Secure implementations of the standard curves are theoretically possible but very hard.". Both your answer and that site lost me in the details, but I'm wondering if this means there is no such thing as a good elliptic curve SSL cert, and we should avoid them completely? – Darren Cook Jan 13 '15 at 09:56
  • 11
    The point is that when the site lists a curve as "unsafe", it means that "there might exist some kind of protocol that involves the curve in such a way that it would be hard to implement it securely". However, this does not apply to all usages of the curve. In particular, in X.509 certificates and in SSL/TLS, elliptic curves are used in a rather simple and direct way where such risks don't apply. – Thomas Pornin Jan 13 '15 at 11:25
  • 1
    @ThomasPornin Aren't there some concerns regarding those two curves' rigidity though? [This page](http://safecurves.cr.yp.to/rigid.html) implies that the "nothing up my sleeve" principle has not been applied. – executifs Feb 01 '15 at 09:08
  • 9
    The "nothing up my sleeve" principle (which is more about psychology than mathematics) has been _partially_ applied, in that the parameters were produced with a fully specified PRNG -- but starting with a seed that was not "justified". For these curves to be weak, one still has to postulate an hitherto unknown attack that can break a substantial proportion of random curves. – Thomas Pornin Feb 01 '15 at 15:56
  • 1
    "it will increases your computational and network costs (a factor of about 3 for CPU)" Only for the handshake or also for transmission? – ig-dev Nov 08 '19 at 21:31
11

I'd say stick to secp521r1 - even DJB says P-521 is pretty nice prime, and it's also supported in every modern crypto library.

In the same time, we should push forward adoption of non-NIST curves like Curve25519, which will be fully rigid, less prone to implementation errors and may become nice alternative for those who need faster solutions than secp521r1.

Michał Staruch
  • 396
  • 2
  • 4
  • 4
    I love me some 25519. Hoping it gets more widespread acceptance and implementation. – Naftuli Kay Jul 31 '15 at 18:36
  • 3
    @naftuli-tzvi-kay We should have both Curve25519 and Curve448 (even stronger, also safe and efficient) standardized for TLS in near future (see [this IETF draft](https://tools.ietf.org/html/draft-ietf-tls-curve25519-01), and I hope TLSv1.3 implementations will have those already included. – Michał Staruch Aug 01 '15 at 19:41
  • I'm not sure but I think he's talking about E-521, not P-521. (that being the one listed in https://safecurves.cr.yp.to/) – lapo Jun 05 '18 at 13:12
  • 1
    @lapo What DJB lists as `E-521` is the same as `secp521r1` and what he's calling `P-521`. – Les Hazlewood Jul 19 '21 at 18:40
4

At least do not use the secp112r1, secp112r2, secp128r1, secp128r2, secp160k1, secp160r1, secp160r2, secp192k1 curves. they have a too small size for security application according to NIST recommendation!

sylvain
  • 149
  • 4