Re: [Cfrg] Proposed requirements for curve candidate evaluation

[Watson Ladd <[e-mail]>]

On Thu, Aug 7, 2014 at 7:20 AM, Brian LaMacchia <[e-mail]> wrote:
> 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.

The reason I don't trust the use of ECC in the IETF is that I have
repeatedly found flaws in standards and implementations that use ECC.
This has nothing to do with any hidden weaknesses of the NIST curves.
Furthermore, the biggest weakness of the NIST curves is the low
performance of the fastest addition laws, leading to no cryptography
instead of some on constrained devices.

>
> 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.

E-521 was discovered by three groups independently. There are not that
many primes near a power of two, and not that many choices of curve
shape. How would we make the process "more rigid?"

>
> 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.

The biggest part of any implementation is the field arithmetic. Adding
an implementation of one shape or another is a handful of lines and
some constants. Furthermore, this isn't a constraint on the curve: any
curve  with points of the right order can be used for any shape. This
has not slowed adoption of curve25519 measurably: it's a nonissue for
many users.

>
> 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.

Any curve with a point of order 2 and a point of order 4 can be used
in Montgomery form, Weierstrass form, or Edwards form, so the
performance of the multiplication law with fixed vs. variable base is
irrelevant to picking a curve. DJB pointed this out last week.

Even if we adopt Edwards point format, ignoring the existing adoption
of Curve25519 in Montgomery form that still leaves the question of
which parameters open. I would prefer a complete addition law on the
points for increased security, but even that still leaves the question
of which parameters open. We could say minimal Edwards parameter d
over the prime nearest the power of two such that -1 is a QR (so the
fast twisted addition formula is complete), but the reason to pick
this choice is primarily for performance and security.

1:
>
> 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.

Remember, this started because Leif Johansson had a draft for
curve25519 in TLS. If at the end of this we say "well, we made the
requirements so demanding because of applications your draft was never
intended to cover that your draft failed, and we don't have a
replacement for you until next year" people, including myself, are
going to be very, very unhappy. Furthermore, people are not waiting
from 2006 to 2014 for us to get our act together to start deployment.

Just flip a coin if we have to: I don't see that much difference
between the various options, and to the extent people have preferences
for shape or standards, they can be accommodated via isogenies
trivially. We don't have requirements that discriminate among curves,
because you can always adjust to the correct shape.

Sincerely,
Watson Ladd

>
> Thanks,
>
> --bal
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin