[Cfrg] Proposed requirements for curve candidate evaluation

[Brian LaMacchia <[e-mail]>]

Folks,
 
As we are still in the requirements-generation phase of this exercise, I'm going to focus on just requirements in this email.  During my presentation at the Toronto meeting I described the requirements that drove the initial NUMS project research and proposed that CFRG adopt those requirements.  Here are what I believe to be the most important of those requirements (revised based on the conversation to date):
 
1.	CFRG-recommended curves should be generated by as rigid and deterministic a procedure as possible. 
 
As I stated at the beginning of my talk, our most important goal is to recommend new elliptic curves for the IETF that will restore trust and transparency in our protocols' use of elliptic curve cryptography.  Lowered confidence in NIST/NSA has moved IETF working groups (starting with TLS) to re-evaluate the elliptic curves in their standards based on the past 15 years of ECC research and seek additional curves which are rigid in their generation and more secure.  Other goals that have been suggested on this list, such as improving the overall performance of ECC operations for TLS, are certainly worthwhile but those additional goals do not address the primary concern of our collective customers.  
 
Each of the candidate curves that have been proposed to date have a rationale behind their choice -- no one has suggested a curve without a rational justification for it.  But there are differences among those rationales and variations in how rigid the generation procedure for a specific curve is.  All of the curves suggested started with a reasonable set of security criteria, but the amount of "wiggle room" invoked in order to get other desirable properties varies across the curves.  Having a lot of wiggle room in your generation process is certainly OK if your primary goal is one of the other desirable properties, but it makes it harder to rebuild trust and confidence among customers.  Requiring as rigid and deterministic a curve generation procedure as possible is the overriding requirement to address the primary goal.  
 
Additionally, I believe it is highly desirable to have a common, consistent generation mechanism across a range of security levels.  While TLS's request to CFRG focused on curve lengths of approximately 256, 384 and 512 bits, other IETF working groups may need curves at other security levels.  For example, if CFRG was asked by another WG to specify a 400-bit curve, a rigid, deterministic generation mechanism would yield such a curve.  Yes, the output might not be the overall most optimal choice at 400 bits -- it might be possible to search around that curve for something nearby that might be a bit faster -- but it would be a *consistent* choice and I believe that rigidity and consistency are the most important properties we need right now to address the loss of trust. 
 
2.	At each security level, the CFRG-recommended curve must be specified in a single curve model that is used for both digital signatures and key exchange algorithms (in particular ECDSA and ECDHE), without transformation to other models.

We have already discussed on the list the desire that the specified curve form should be used for both digital signatures and key exchange. We need to remember that we are choosing curves for Internet protocols that will be implemented by a wide variety of products, services, systems and devices. Requiring multiple curve forms, particularly in combination, significantly increases the complexity of implementation. Complex implementations are more likely to have subtle errors which compromise the security of the protocols.  As such, there is significant engineering benefit to using curve arithmetic corresponding to the same curve model for both digital signatures and key exchange. 

3.	The CFRG-recommended curves must be specified using the same curve model for all security levels.

This requirement achieves similar engineering benefits to Requirement 2 above. 
 
4.	When evaluating candidate curves for use in ECDHE, "ephemeral" should be defined as "use exactly once in a key exchange" (or for TLS "use in exactly one handshake"). 
 
During the second TLS meeting in Toronto, Kenny Paterson gave a presentation summarizing where CFRG was on this question at that time and one of the points he mentioned was that there was not consensus as to what "ephemeral" should mean for purposes of evaluating candidates.  Russ Housley then commented at the microphone that "ephemeral" should mean "used in exactly one handshake".  I strongly concur with Russ's position and suggest that we formally adopt that definition now during the Requirements phase.  The concrete implication of adopting this proposed requirement is that it means when we evaluate ECDHE performance for curve candidates we must include one fixed-base and one variable-base operation. 
 
I believe these proposed requirements are all necessary and should be adopted as official Requirements when this phase of the process concludes.  
 
Finally, I would remind folks that the overall goal of the process we are pursuing here in the CFRG is to first reach consensus on a list of requirements for whatever curves we're going to recommend to TLS, and then evaluate candidate curves against those requirements.  It is possible, of course, that none of the current set of candidate curves will satisfy all of the requirements the group decides are necessary and we'll have to go look for more candidates, but that is exactly how a requirements-driven process works and if it happens in this case so be it.  We must not weaken our requirements in order to make them fit the current set of candidates - our requirements must be generated independent of the candidates submitted.  
 
Thanks,
 
--bal