[Cfrg] ECC desiderata

["D. J. Bernstein" <[e-mail]>]

Suggestions are summarized at the bottom. These are mainly tweaks to the
list suggested by David McGrew and discussed by quite a few people. I'll
send a separate message to comment on Brian's new list from yesterday.

Benjamin Black writes:
> 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.

Surely everyone would agree that we want crypto implementations to be
secure, and in particular to

   * work correctly for all valid inputs, and
   * avoid compromising security when inputs are invalid, and
   * avoid all data flow from secrets to timing.

Would anyone argue that an implementation flunking these requirements
is "production-quality" or "appropriate for large scale deployment"?

On the other hand, there clearly isn't agreement that crypto should

   * be written in JavaScript, or
   * trust typical compilers, or
   * avoid vector intrinsics, or
   * avoid assembly language, or
   * be written as "completely portable" code,

even though for each of these items I've seen people in various venues
vociferously arguing that the item is critical for "production" or
"deployment" or some similar phrase. As an example of the subtlety of
these issues, the strongest formally verified guarantees available today
for ECC software are for software written in assembly language, and this
situation is likely to persist.

I think it's perfectly legitimate to ask how much simplicity is
sacrificed from, e.g., having F_p arithmetic tuned separately for Intel
chips and for ARM chips. However, for many people the resulting speedups
are more important than the loss of simplicity, and it would be crazy to
demand that those people ignore those speedups just because someone else
refers to multiple implementations as not being "appropriate for large
scale deployment".

I conclude that the concept of "production-quality" should not appear in
a list of ECC requirements (or desiderata): it includes some items that
are uncontroversial but other items that compromise security and speed.

David McGrew writes:
> R8.  Required: amenable to constant-time implementations, to avoid
> side channel attacks [2]

I don't think that "amenable" works as a yes/no requirement: every
cryptographic function _can_ be implemented in constant time. What we
care about is how simple and fast the resulting implementations are---
and the extent to which non-constant-time implementations would have
been simpler or faster, creating bad incentives for implementors.

I'd suggest stating the core desiderata as follows (where "secure"
includes the first three items I listed above):

   D1. Speed and simplicity (and speed-simplicity combinations) for
   secure implementations.

   D2. Avoiding speed incentives and simplicity incentives towards
   insecure implementations.

Curves with cofactor 1 obviously score so badly on these axes---without
having any compensating advantages---that I think they should be taken
off the table. Each new curve should have a unique point of order 2 and
points of order 4, for compatibility with the Montgomery ladder and
complete Edwards addition. Such curves should still be quantitatively
evaluated against the same desiderata.

> R2.  Required: amenable to compact implementations and fast
> implementations, across both small and large processors [1]

I again don't think that "amenable" works as a yes/no requirement. The
processor comment applies to any mention of speed (e.g., both D1 and
D2 above), so I'd suggest turning R2 into a modular statement:

   "Speed" includes speed on many different platforms: e.g., speed on
   64-bit desktop CPUs, speed on 32-bit smartphone CPUs, speed on
   embedded microcontrollers, and speed of hardware implementations.
   
As for "compact": Obviously small implementations can contribute to
speed (avoiding cache misses, fitting into available chip area for a
hardware accelerator, etc.), and there's a huge correlation between
compactness and simplicity. Is there an argument to identify compactness
per se as a separate desideratum---something where compactness will help
select ECC mechanisms in ways that simplicity and speed won't?

> R3.  Desired: re-use components between signatures and key exchange
> algorithms [3]

I would suggest naming more of the important operations:

   "Speed" includes speed of many important ECC operations inside TLS,
   PKIX, SSH, IKE, and other protocols: e.g., key generation, signing,
   verification, and DH shared-secret computation. "Simplicity" includes
   the simplicity of implementations supporting all of these operations,
   the simplicity of implementations supporting only DH, the simplicity
   of implementations supporting only signatures, etc.

It's important for the metric to be simplicity rather than reuse. For
example, it's obviously much better to have

   * complexity 300 for DH implementation (keygen+sharedsecret)
   * complexity 500 for signatures implementation (keygen+sign+verify)
   * complexity 600 for combined implementation

than to have

   * complexity 10000 for DH implementation
   * complexity 10000 for signatures implementation
   * complexity 11000 for combined implementation

even though the second option would score better on any "reuse" metric.

> R1.  Desired: easy to understand and implement [1]

This is one aspect of simplicity. Is there evidence that different types
of ECC simplicity are in conflict? If not then I'd suggest simply saying
"simplicity" and not getting caught up in weighing the details.

> R9.  Required: resist twist attacks [2]

The reason that this is important is that

   * _with_ twist-security the simplest secure DH implementation is the
     Montgomery ladder, while

   * _without_ twist-security the simplest secure DH implementation is
     the Montgomery ladder _plus_ checking that the input is on the
     curve---omitting the check produces security problems.

I think this is adequately covered by D2 ("Avoiding speed incentives and
simplicity incentives towards insecure implementations"). Furthermore,
if someone comes up with an argument that twist-security is outweighed
by something else then D2 will handle the variation better than a
separate requirement would.

> R11.  Desired for key exchange: resist invalid curve attacks [2];
> note that complete addition laws help and are thus desirable [2].
> (Note that the use of ephemeral keys also resist such attacks.)

This was later clarified as covering "implementation attacks in general,
not just invalid curve attacks"; and again I think this is covered by D1
and D2.

> R12.  Required for PAKE: indistinguishability of curve points from
> random strings [2]

I see indistinguishability as being more important for simplifying
anti-censorship protocols than for simplifying PAKE protocols. However,
I would suggest that CFRG not bother making separate requirements along
these lines, primarily because I don't see how it could actually end up
making a difference in CFRG's selection of ECC mechanisms.

> R6.  Desired: can be used with current software implementations
> (using different curve parameters) of TLS, PKIX, SSH, and IKE [4]

Suppose an implementation is limited to the NIST P-256 prime---including
the ECDSA-specified NIST P-256 reduction procedure, which looks quite
different from the reduction procedure for better primes. Does CFRG want
this implementor objecting to any prime other than the NIST P-256 prime,
on the basis of the code changes required?

Obviously there is some value in being able to reuse existing code. For
example, suppose

   * a server wants the speed benefits of optimized code for a new
     curve, or the security benefits of simple code for that new curve,
     or both; and
     
   * the client already has secure code, doesn't care about speed, and
     can support the new curve with a very small code change, making the
     server happy.

This code reuse can allow faster deployment than demanding a more
serious code change from the client. However, if the client's existing
code is _not_ secure, then it's actually better for security to pressure
the client to throw that code away.

Let me suggest a different way to handle R6:

   "Simplicity" includes the simplicity of new implementations, and the
   simplicity of modifying preexisting implementations.

This works nicely with both D1 and D2. For example, if it's simple to
modify a preexisting implementation to obtain a secure implementation of
a new ECC mechanism---for example, "using different curve parameters"
without further effort---then that's positively valued under D1. If it's
simpler to modify a preexisting implementation to obtain an _insecure_
implementation, then that's negatively valued under D2.

> R7.  Desired: can be used within current ECC standards of TLS,
> PKIX, SSH, and IKE [4]

As a desideratum for new _curves_ this is content-free: all of the
proposed _curves_ can be used with the existing standards. See my
"curves, coordinates, and computations" message.

My understanding is that CFRG isn't considering replacement _algorithms_
such as Schnorr signatures. However, there are strong reasons for CFRG
to consider recommending better _coordinates_ on the wire, because this
has clear benefits for simplicity of implementations. Obviously this has
a transition cost---but the whole reason for CFRG to consider it is that
it's desirable _despite_ this cost!

Something to keep in mind is that the cost of redeploying software has
very little to do with the amount of code changed. There isn't some
magical dividing line between deploying a new curve with an old
coordinate system and deploying a new curve with a new coordinate
system. Both of these are code changes (including whatever protocol
extensions are necessary) and incur very similar deployment costs.

Something else to keep in mind is that only a small fraction of the
Internet is cryptographically protected today. This suggests that CFRG
should put a high value on simplifying new implementations that will do
a better job at protecting the Internet than today's implementations.

David Jacobson writes:
> Performance needs to be measured with the defenses deployed.

Right. D1 makes this explicit ("Speed ... for secure implementations").

As I wrote earlier, there are two reasons to highlight timing attacks
rather than power attacks, EM attacks, acoustic attacks, etc.: first,
timing is naturally visible through the Internet; second, I highly doubt
that considering side-channel attacks beyond timing will affect any
curve decisions. All of the major sources of timing variation in
software are documented in various attack papers and defense papers
(despite the caveat in http://blog.cr.yp.to/20140517-insns.html).

Simon Josefsson writes:
> Instead of R8-R11, I suggest to summarize this more generally as:
> R8'. Required: the solution should be secure against reasonable and
> well-understood threats, including (but not limited to and necessarily
> not all of) brute-force, side-channel, invalid-curve, twist attacks, or
> maliciously chosen curve parameters.

Every proposal will be resistant to brute-force attacks, side-channel
attacks (with enough implementation effort), invalid-input attacks (with
enough implementation effort), and twist attacks (with enough
implementation effort). But this has a cost, in speed and in simplicity,
and the variations in these costs are exactly what make some proposals
better than others.

Michael Hamburg writes:
> complete addition laws should probably be on the list as nice-to-have

The importance of a complete addition law is that it allows a simpler
secure implementation of (e.g.) signature verification. This is
analogous to twist-security and is similarly covered by D2.

> it’s important that the constructs should allow relatively simple
> and efficient secure implementations.

Agreed (and David also indicated that he agrees). This is what I'm
labelling D1.

Putting all of this together, I'd suggest replacing R1+R2+R3,
R6+R7+R8+R9, and R11+R12 with the statement of desiderata shown below.

---Dan


D1. Speed and simplicity (and speed-simplicity combinations) for
secure implementations.

D2. Avoiding speed incentives and simplicity incentives towards insecure
implementations.

"Secure" includes the following properties: an implementation works
correctly for all valid inputs; avoids compromising security when
inputs are invalid; and avoids all data flow from secrets to timing.

"Speed" includes speed on many different platforms: e.g., speed on
64-bit desktop CPUs, speed on 32-bit smartphone CPUs, speed on
embedded microcontrollers, and speed of hardware implementations.

"Speed" includes speed of many important ECC operations inside TLS,
PKIX, SSH, IKE, and other protocols: e.g., key generation, signing,
verification, and DH shared-secret computation. "Simplicity" includes
the simplicity of implementations supporting all of these operations,
the simplicity of implementations supporting only DH, the simplicity
of implementations supporting only signatures, etc.

"Simplicity" includes the simplicity of new implementations, and the
simplicity of modifying preexisting implementations.