Re: [Cfrg] Curve selection revisited

[Yoav Nir <[e-mail]>]

On Jul 25, 2014, at 1:10 AM, Benjamin Black <[e-mail]> wrote:

> Inspired by some comments from other and in hopes of returning to a more productive debate rather than the pointed back and forth, of which I am absolutely guilty, I'm suggesting a few constraints. These are not priority ordered and none of them deal with the math, instead focusing on process and practice.
> 
> 1) As we are discussing this in the context of TLS, the performance of various kx options must be evaluated for ECDHE as typically deployed. ECDH is neither common nor recommended in the TLS BCP draft. In addition, I hope there will be discussion of benchmarking methodology, with the understanding the ultimate choice is for the CFRG chairs.

The ultimate choice is with the group, with the chairs refereeing. We are also interested in digital signatures, not only key agreement. I agree that we need a benchmark methodology, but before that, we need to agree on selection criteria. There’s no point in testing if the results don’t point you towards a choice. The obvious criterion is speed of operation (for generate, derive, sign, and verify) on one or more platforms (probably need more than one). Another criterion could be memory requirements for the operation (matters for small platforms, but also limits scalability of large servers). Yet another criterion that isn’t measured in a benchmark is complexity, although I don’t think the candidate curves differ on this.

> 2) Performance must be measured using "production-quality" implementations. By this I mean implementations which employ the sort of techniques/optimizations appropriate for large scale deployment. This is specifically intended to exclude discussion of how simple or fast an implementation _could_ be, in favor of what they actually are in practice. However, the goal is to select curves which strike the best balance between various requirements, not simply the fastest.

I think “production-quality” should be simply the kind of code that a vendor or open source project might “ship”. This is not necessarily the fastest. For example, if Microsoft ships this curve in Windows (or Google in Chrome for Windows), they are going to need the code to run on any platform that Windows runs on, from Atom to the latest i7. If the latest i7 has some instructions that make the implementation faster, they are faced with the choice of including multiple implementations, tailored to different chips, or coding for the lowest common denominator. In practice, they will only include multiple implementations if the performance difference is noticeable (no idea what their threshold would be, but for me it would need to be at least 50% before I recommended including multiple implementations). 

So optimizing code for the target processor does not necessarily yield “production quality” code. That said, I don’t really know how we could control for that.

> 3) The timeframe for a decision constrains the scope of this process. If a decision is desired within a few months, then it is difficult to include options beyond new curves. If a decision can take a year, new algorithms could be considered. Given the importance, impact, and contentiousness of new algorithms, I believe it would be difficult to complete a thorough, careful algorithm and curve selection process in a short amount of time.

There’s also the question of (lack of) resources. NIST or the NSA can assign six cryptographers to spend the next year examining curves and algorithms. We are all volunteers, so if we get someone with the cryptographic chops to take several hours from his or her busy schedule to examine and comment on a proposal, or if we get someone with the programming chops to spend a few days implementing and benchmarking, we should consider ourselves lucky.

> 4) The precise set of security levels needed should be specified in advance (whether by TLS or CFRG) and curve recommendations delivered together for all levels. A stated goal is to use these curves in new drafts, and it minimizes work to specify all security levels for a proposal in the same draft. This is strictly a practical matter recognizing the chairs and area directors have limited bandwidth and implementors can get everything done in a single go.

Agree.

> 5) Selections must efficiently support TLS 1.2. Adoption of new curves, and potentially new algorithms, can't be gated on completion and widespread deployment of TLS 1.3.

Agree. It shouldn’t be gated on TLS at all. The same curves will probably be adopted by whoever else uses ECDHE and elliptic curve signatures. So whatever choice is made here will affect IKE, SSH, certificate authorities. There is nothing special about TLS.

> 6) Drop-in replacement for the NIST curves is _not_ a requirement in this process.

Totally agree.

> 7) I don't think the chairs are signing up for a full-on, NIST-style selection competition and we should aim to keep things are lightweight as possible while still achieving the required level of rigor. I hope they will address this point soon.

Agree.

Yoav