Subject: [Cfrg] Proposed requirements for curve candidate evaluation

From: Brian LaMacchia <[email-masked]>
Date: Thu, 7 Aug 2014 14:20:36 +0000

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

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 7 Aug 2014 11:57:45 -0700

> On Aug 7, 2014, at 7:20 AM, Brian LaMacchia <[email-masked]> wrote:

To be clear, this “requirement” means that the curve must be specified in short Weierstrass form, right?

You’re suggesting that CFRG disregard the state of the art in ECC simplicity, security and performance (Edwards curves) because it’s too complicated to compute (y+1)/(y-1) + k?

I believe that this should absolutely not be a requirement for curve candidate evaluation.

> 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 conse…

I agree that this is what “ephemeral” should mean for evaluation.  But I don’t understand how this clarification could possibly change anything.

You can use a fixed-based precomputed combset (or similar table) for any elliptic curve.  It will pretty much always cost about a third of what the variable-base scalar multiply costs.  This is true for Edwards curves, Montgomery curves, short Weierstrass curves, Hessian curves, Jacobi quartics … anything that is an Elliptic curve and not just a Kummer surface.

You’re driving awfully hard for a definition which doesn’t matter, particularly considering that the first half of your email argues strenuously against performance considerations.  Can you explain why we should care about this at all?  Is this going to turn into a convoluted argument against Curve25519?

Cheers,
— Mike

---

From: Benjamin Black <[email-masked]>
Date: Thu, 7 Aug 2014 12:01:06 -0700

On Thu, Aug 7, 2014 at 11:57 AM, Michael Hamburg <[email-masked]> wrote:

> > 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.
>
This requirement permits twisted Edwards. What it excludes is using
different models for different purposes.

Ben

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 7 Aug 2014 15:19:27 -0400

> This requirement permits twisted Edwards. What it excludes is using different models for different purposes.

And why is that important?  To reduce code size?

--
Principal Security Engineer
Akamai Technologies, Cambridge MA
IM: [email-masked]<mailto:[email-masked]> Twitter: RichSalz

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 7 Aug 2014 13:46:03 -0700

> On Aug 7, 2014, at 12:19 PM, Salz, Rich <[email-masked]> wrote:

> [Benjamin Black wrote:]

Does it?  ANSI X9.62 specifies ECDSA only over curves in short Weierstrass form.

If this requirement is not intended to force short Weierstrass, perhaps it should be rephrased as:

“”"
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 without transformation to other models.  It must be suitable for ECDSA and ECDHE with a straightforward transformation to and from short Weierstrass form.
“”"

> And why is that important?  To reduce code size?

Or perhaps for simplicity of specification?

Interestingly, I think that in combination with Requirement 1, this might nix both Curve25519 and the Microsoft NUMS curves.

— Mike

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 7 Aug 2014 16:48:36 -0400

As the person who proposed the requirement, I really want to know why Benjamin wants to do this:

> What it excludes is using different models for different purposes.

--  
Principal Security Engineer
Akamai Technologies, Cambridge MA
IM: [email-masked] Twitter: RichSalz

---

From: Watson Ladd <[email-masked]>
Date: Thu, 7 Aug 2014 18:03:45 -0700

> 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 cr…

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…

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?"

> 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 Inter…

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.

> 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 conse…

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.

> 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 recommen…

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
> [email-masked]
> 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

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 7 Aug 2014 18:24:16 -0700

> On Aug 7, 2014, at 6:03 PM, Watson Ladd <[email-masked]> wrote:
> 
> shape. How would we make the process "more rigid?”

On a related note, Brian, do you know why E-521 (or rather, a curve isogenous to E-521 or its twist) isn’t the Microsoft ed-521-mers curve?  Is there something simple I’m missing here?  It seems like that gives a smaller d0 coefficient than the one you chose.

— Mike

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 07 Aug 2014 19:22:17 -0700

> 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 conse…

IMO I would prefer to see the actual numbers, i.e. the break-down of 
performance measurements instead of assuming some "package" of a likely 
usage pattern or combination of fixed-based+variable-based operations.

There is always one variable-base operation (time A).

In addition, there is either of these:
* a fixed-based operation or (a textbook case, time B)
* a fixed based operation plus the precomputation time attributed to the 
fixed base optimization (a short-lived context case, time B+P)
* an (un-optimized) fixed-based operation that uses the same code as 
variable-based operation (a small-footprint case, time A)
* reuse (time ~0)
( + There are other middle-of the road cases... )

A is the most important metric. B<A; the ratio B/A is needed to 
evaluate if the extra implementation effort and complexity is worth it. 
P is penalty and is important in some cases.

---

From: "D. J. Bernstein" <[email-masked]>
Date: 8 Aug 2014 18:06:23 -0000

> deterministic a procedure as possible.

If one "procedure" allows 26 different curves, and another "procedure"
allows only 23 different curves, then requiring the maximum rigidity
would prohibit the first procedure.

Is this really what you meant? If this isn't what you meant, then what
exactly _did_ you mean?

Also, do you expect CFRG to evaluate "as rigid as possible" on the basis
of advertisements, or on the basis of actual analyses of wiggle room?
For example, if Brainpool were a proposal rather than an existing RFC,
would you expect CFRG to start from Brainpool's advertisement of being
"generated in a systematic and comprehensive way", or to start from
analyses showing that this "way" actually allows >1 million curves?

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

So you're saying that using a "procedure" that allows 26 different
curves wouldn't restore "trust and transparency" if there's another
"procedure" that allows only 23 different curves?

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

The ECDSA standard uses short-Weierstrass coordinates to specify the
transmission format for public keys, so you're saying that all curves
must be specified in short-Weierstrass coordinates, and that CFRG can't
consider other coordinates for digital signatures and key-exchange
algorithms. (If this isn't what you meant, please clarify!)

For choosing _curves_ this requirement is content-free. For example,
Curve25519 is Y^2 = X^3-(236839902241/3)X+(230521961007359098/27) in
short-Weierstrass form---simply shift the x-coordinate by 486662/3.

For choosing _coordinates_ this requirement has content---and that
content is contrary to the fundamental goals of security, simplicity,
and speed. See my "curves, coordinates, and computations" message for
much more detail.

> curve model for all security levels.

This is a superficial presentation requirement, of no help in choosing
curves. Also, the previous requirement forced short Weierstrass in all
cases, so this requirement is redundant.

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

https://www.imperialviolet.org/2013/06/27/botchingpfs.html explains how
keys can be kept around for months---despite meeting your definition of
"ephemeral". These keys are clearly _not_ ephemeral and do _not_ provide
perfect forward secrecy.

As I explained in a previous message, "use for exactly one session" is
the wrong policy; "use for exactly one connection" is the wrong policy;
and Microsoft's current reuse-for-two-hours is also the wrong policy.
These all fail to accomplish what the user wants, namely for keys to be
erased very soon---I suggested 10 seconds as an upper limit.

An implementation that reuses keys for just 1 second will have
negligible keygen time on typical CPUs, even if the implementor uses a
simple Montgomery ladder rather than a more complicated keygen method.
Concretely, http://bench.cr.yp.to/results-dh.html shows one of the
curves under discussion taking 145907 cycles for Montgomery-ladder
variable-base-point scalar multiplication on a 3.5GHz Intel Haswell CPU.
That's just 0.000042 seconds on a single core, completely unnoticeable
even if it's repeated every second.

This implementation strategy is simpler _and_ faster than the strategy
you're talking about, and there's no security problem with it, so it's a
perfectly valid benchmark target. I don't mean to suggest that it's the
only valid benchmark target; I'm just saying that there's no basis for
insisting that this target be ignored.

As a side note, cryptographers for years have known a better protocol
design in which "use a long-term signing key to sign a short-term DH
key" is replaced by "use a long-term DH key to authenticate a short-term
DH key". This makes variable-base-point scalar multiplication much more
frequent while reducing overall costs. My understanding is that the
dns-privacy group is already evaluating some protocols that use this
better design, and I wouldn't be surprised to see TLS eventually moving
in this direction. But I also think that the current TLS situation, in
which key reuse is widespread and has obvious performance benefits, is
already ample justification for carrying out relevant benchmarks.

---Dan

---

From: Tanja Lange <[email-masked]>
Date: Fri, 8 Aug 2014 20:44:04 +0200

> > On Aug 7, 2014, at 7:20 AM, Brian LaMacchia <[email-masked]> wrote:
[..]
 
> I agree that this is what “ephemeral” should mean for evaluation.  But I don’t understand how this clarification could possibly change anything.

I would like to clarify that we're talking about different kinds of 
evaluations:
a) For performance evaluations one can argue that ephemeral means
   one handshake (or a short time or a small number of connections).
b) For security evaluations we must take into account that users
   may keep reusing the same key; this must not be a problem for the
   security of the curve or the implementation.

	Tanja

---

From: David Jacobson <[email-masked]>
Date: Fri, 08 Aug 2014 20:06:51 -0700

On 8/8/14 11:06 AM, D. J. Bernstein wrote:
> <snip>
> <snip>
Dan is actually doing something much more fundamental that one might at 
first think.  He is changing the threat model.

Most people probably have the idea that ephemeral keys are more secure 
that longer term keys because they limit they amount of data relating to 
a particular key that a passive eavesdropper has access to, and thus 
make a cryptanalytic attack harder.  (I had that idea.)  But Dan is 
changing the treat model.    The threat is an attacker who can from time 
to time grab some amount of system state.  By Little's Law, the mean 
number of sensitive keys in the system is the throughput (sessions 
established per second) times the mean residence time of each key (in 
seconds), so the shorter the residence time, the fewer keys are there to 
get snitched.

Note that this depends on attacks grabbing some system info from time to 
time, perhaps by something like Heartbleed.  It also applies to things 
like the system state getting paged to swap, or written out in a crash 
dump.  It does not apply to an attacker who has thoroughly gotten 
control of the system and can grab and export data from every crypto 
operation.  In that scenario, the attacker gets everything, and 
shortening the residence time provides no benefit. (This is not an 
argument against Dan's proposal, rather just an observation.)

      --David Jacobson