13

Recent developments have cast some doubt on the elliptic curves specified by NIST and used in many standards like TLS (for signatures with ECDSA and key agreement with ECDHE).

It seems like the standard allows for custom, server-generated ECDH-curves that are transmitted during the handshake (just like with non-elliptic DH).

  • Do common implementations actually support that, or are they restricted to the NIST-specified curves? I've traced TLS handshakes with Google Chrome and iOS; it seems like the elliptic_curves extension only specifies the curves secp{256,384,521}r1, and not arbitrary_explicit_{prime,char2}_curves.

  • What is the situation for elliptic curve certificates? TLS seems to require X.509 certificates complying to RFC3279 or any RFC that replaces it (which would be RFC5480). According to RFC3279, it's possible; in RFC5480, explicit or implicit curves are specifically excluded.

In general, to what extent are custom elliptic curves permitted by today's standards (TLS, S/MIME etc.) and supported by the various implementations (OpenSSL, NSS, proprietary ones)?

If they are not supported: Why? Is it more difficult to find "good" curves than to find suitable DH parameters? Are common curves easier to verify and/or implement? Are they faster?

Community
  • 1
lxgr
  • 4,094
  • 3
  • 28
  • 37
  • Finding curves is easy. Implementing curves is a bit annoying, especially if you can't take advantage of the particular properties of that curve. – CodesInChaos Sep 09 '13 at 17:14

2 Answers2

13

The NIST has "defined" 15 "standard curves", specified in FIPS 186-4. Actually, they did not define them themselves; they inherited them from SEC. These 15 curves aggregate into 3 groups:

  • The P-* curves work in a "prime field" (point coordinates are integers modulo a prime p).
  • The B-* curves work in a "binary field" (point coordinates are values in GF(2m)).
  • The K-* curves work in the same fields as the B-* curves, but have a special structure which allows for faster computations.

NIST found out that there was a huge reluctance to implement support for these 15 curves, let alone for "general" curves, for a variety of reasons:

  • The involved mathematics are felt to be "hard" (that's harder to grasp than RSA or plain Diffie-Hellman).
  • ... even more so for curves in binary fields.
  • While it is possible to write "generic" curve-handling code, code which targets a specific curve is often simpler to implement and faster. In particular, the P-* curves work modulo prime values whose format makes implementation more efficient (fast modular reduction).
  • There have been recurrent and long-standing claims of patents, making the use of elliptic curve "risky".
  • ... especially for curves in binary fields;
  • ... and more generally for generic curves chosen to have some characteristic which is beneficial to implementation. It is not known whether a curve can be patented (as opposed to an implementation technique supported by a special curve structure), but uncertainty already does powerful dissuasion.

Thus, people were wary of implementing generic support for elliptic curves, because it seemed to be hard, detrimental to performance, and a legal minefield. Sticking to a few of the simpler curves seemed easier, faster and safer; and that's what happened. NIST (well, NSA) formalized this trend as their "suite B" cryptography suite, which mandates implementation of exactly two curves: P-256 and P-384.

In SSL/TLS and in X.509, arbitrary curves may be used. However, most implementations won't support arbitrary curves. OpenSSL supports all 15 NIST curves, but not arbitrary curves. Firefox supports only P-256 and P-384; I am not sure Microsoft's code (Windows, hence Internet Explorer) will accept more than that either (maybe P-521 as well). If you try to use any other curve than P-256 or P-384, then you will encounter interoperability issues (more issues than what you already get by trying to use elliptic curves at all). Some standard writers, feeling that they must "be practical", have fully admitted this fact, and just banned the use of other curves, as you see in RFC 5480.

Generating your own curve is not hard, but substantially harder than generating your own DH parameters. It involves point counting with Schoof's algorithm or a variant thereof. You won't be able to slap together a curve generator in one hour and a hundred lines of Java code, whereas producing DH parameters can be done under these constraints. The computational cost is also higher (you will still get a nice curve in a minute, but not in 100ms). To be brief, people don't do that often, or at all.

Community
  • 1
Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • 1
    Thanks, that was very detailed and helpful! One more question: What about djb's Curve25519 and Ed25519? Could they be implemented by specifying a custom curve, or do the limitations you mentioned in your answer to a similar question still apply? (http://stackoverflow.com/a/2517052/1016939) – lxgr Sep 12 '13 at 18:26
  • 2
    Curve25519 has a special format which does not fit in the way a TLS server can specify a "generic curve". This does not preclude the existence of a future TLS extension which specifies Curve25519, but this has not happened yet; and even if that standard was written tomorrow, it would still take some substantial time (years, maybe decades) before non-negligible adoption occurs. – Thomas Pornin Sep 12 '13 at 18:33
  • 2
    Hm, maybe we're better off that way - having to explicitly specify/announce it will probably avoid many compatibility issues (for example, libs that only support 25519 as a custom curve). Somebody apparently submitted a draft for Curve25519's use in TLS three days ago; maybe somebody will do the same for X.509 and Ed25519. Let's hope we'll see an implementation this decade :) http://ietfreport.isoc.org/idref/draft-josefsson-tls-curve25519/ – lxgr Sep 12 '13 at 19:06
0

There are multiple families of curves.

NIST choice was about short weiertstrass equation for prime fields (y^2 = x^3 + ax + b) %p with order n, cofactor h.

Custom curves in SSL is the choice of different a,b,p,n,h for the same equation

NIST binary fields is a different curve family

ed25519 is from the family of twisted edwards curve

c25519 is a curve from the montgomery family of curves

For each family, you need more than a few parameters in a protocol exchange, you also need source code to implement them. New code does not self-generate in your TLS/SSL library. You have to wait for the opensource community to adopt the new curves families. Then you also need to battle against the reluctance of the product maintainers to overbloat their source code. You can find more and more curve families here https://hyperelliptic.org/EFD/ , the fastest ones might be Huff curves and are not listed.

Pierre
  • 1