Re: [Cfrg] Proposed requirements for curve candidate evaluation

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

Brian LaMacchia writes:
> 1. CFRG-recommended curves should be generated by as rigid and
> 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?

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

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.

> 3. The CFRG-recommended curves must be specified using the same
> 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