How many curves should a UA support?

Forking off just my #4 and Ryan’s answer below to start a separate thread on just this topic.

Ryan asked whether I expected that all six of the NUMS curves would be present in an implementation, and I answered that I thought that the underlying math libraries would so but that individual protocols would choose what they need.  Ryan then said that he wanted to confirm that it was my intent that a UA would either make all six or none available, which made me realize that my answer about “underlying math libraries” didn’t answer the question Ryan was actually asking, and since the answer to that question is a bit involved/subtle I’m forking this separate thread to discuss it.

The NUMS curves (as defined in our IETF draft) are a set of six curves, divided into two subfamilies (Weierstrass and twisted Edwards) with each subfamily having one curve for each of the three security levels 128-, 192- and 256-bits.  There are three levels of implementation one has to worry about:


1)      The underlying math library

2)      The programmer-accessible API

3)      The needs of the protocol you’re building

My answer was about #1 and #3, skipping #2 (which is what Ryan was asking about).  Let me take each of #1 and #2 in turn:

The underlying math library:  At the core of any ECC implementation, you need an implementation of the field arithmetic and an implementation of the curve arithmetic.  The field arithmetic for all of the NUMS curves is the same (they’re all prime fields) and it’s the same math that you’d already have if you have an implementation of the NIST prime curves.  There’s a difference, however, in the curve arithmetic between the two subfamilies: the Weierstrass subfamily uses the same curve arithmetic as the NIST prime curves (because the NIST curves are also Weierstrass-form), but the twisted Edwards family uses different curve arithmetic.  Once you have the field and curve math, implementing a specific curve requires just defining the curve parameters, so it’s easy to support any and all security levels in a subfamily once you have the math.

What this means is that if you’re starting from scratch and writing your own math library for the NUMS curves, you could just implement one subfamily if you knew that’s all everyone above you in the stack was going to need, or you can implement both subfamilies at the cost of writing both types of curve math.  It’s not that big a deal, and you can look at the code we’ve released to see the difference.

The reason NUMS defines the two subfamilies is that we expect that for some folks with existing implementations of the NIST curves, they’re going to prefer to just add additional curve definitions on top of their existing NIST implementation and not add any new math code.  The NUMS Weierstrass subfamily is aimed at those situations – they’re better curves than the NIST curves but they build on the same field and curve math so it’s easy to add them to an existing implementation.  What you give up is perf -- the NUMS twisted Edwards subfamily is faster than the Weierstrass family.

The programmer-accessible API:  The next level up the stack is what do you expose in the API surface, and here it’s a matter both of what you have in the math, what is mandatory-to-implement (if anything), as well as what you’re willing to test.  If I’m writing a general-purpose crypto library API, then I’d probably lean toward exposing everything I have in the math library that I believe is safe to use, with appropriate defaults.  But there’s a test hit to do that (every curve you expose is more you have to test) so I know some developers who don’t want to expose everything that is in the math library but will implement only what’s MTI or equivalent to whatever is MTI.

Since we’re still working through whether Web Crypto will have any MTI algorithms or curves, I think a UA implementing NUMS would at a minimum look to match what it’s providing from the NIST set in terms of security level, and then either one subfamily or both from NUMS.  So, for example, if we chose to make NIST P-256 and NIST P-521 MTI, I could see the UA also offering numsp256d1 and numsp512d1 (matching the NIST security levels, drawing from the Weierstrass subfamily), and I’d probably suggest in that case that a UA NUMS implementation minimally had to offer both of those curves and optionally the other four. If we have no MTI curves for ECC then we have no MTI curves, and everything happens through runtime curve discovery and negotiation.  And of course if we have a protocol spec with a hard dependency on Web Crypto that needed something else, the two spec WGs would need to negotiate that.

Bottom line: I don’t think we want a situation where a UA has to implement 9 curves (3 NIST, 6 NUMS) in order to implement ECDSA/ECDH, although that’s the net effect of the language I submitted since the WG hasn’t decided yet on MTI and extensibility.  I think it would be perfectly reasonable for the WG to choose a subset of curves to make MTI (or say must be MTI if ECC is offered) and then we can argue over what the reasonable subset is to make MTI.

Hope that helps, and sorry for the length,

--bal

From: Ryan Sleevi [mailto:sleevi@google.com]
Sent: Friday, July 11, 2014 9:37 PM
To: Brian LaMacchia
Cc: public-webcrypto@w3.org
Subject: Re: Changes required to add the NUMS curves to Web Cryptography API


4)      As for whether all of the NUMS curves would be supported, my expectation is that the underlying math libraries would support all six curves (as our implementation does) but that individual protocols would choose a subset of the NUMS family that is appropriate to their needs.  This is the approach we have taken with our IETF drafts – all six curves are in the base CFRG-targeted draft but we’ve choses a subset of just two twisted Edwards curves for the TLS-targeted draft.  We made that choice based on engineering feedback from protocol implementers in the TLS community and a preference for the additional performance of the twisted Edwards curves over the reduced additional code required by the Weierstrass-form curves.  However, that preference is one of the issues I believe the TLS WG needs to discuss more fully.

Right, I certainly appreciate that protocols/applications will want to make informed choices based on the needs of their users (hence the ongoing debate about security considerations), I just wanted to confirm that from a library implementation perspective, the idea was that a UA would always make either all 6 curves available or no NUM curves available (mod the discussion on #1 above as to whether 'no NUMS curves available' is a valid answer)

Without getting into the merits of the answer, just wanted to make sure that was intended.