Re: [Cfrg] On the use of Montgomery form curves for key agreement

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

Brian LaMacchia writes:
> For the case of ECDHE, Dan Bernstein has argued for a definition of
> “ephemeral” that would allow keys to be re-used for some amount of
> time

Several reports have indicated that Microsoft's standard TLS library
(SChannel) reuses ephemeral DH keys (specifically TLS ECDHE keys) for
two hours. Are those reports not accurate?

Even if keygen were implemented as variable-base scalarmult without the
complication of a separate fixed-base scalarmult function, wouldn't you
agree that this key reuse makes the cost of key generation irrelevant?
Wouldn't you expect other implementors to reuse keys for this reason?

Obviously two hours is not the right choice: repressive police states
can certainly seize equipment within that time interval. In my message
dated 1 Aug 2014 01:36:59 -0000, I suggested 10 seconds as an upper
limit. However, this doesn't change the DH performance picture!
Variable-base scalarmult is dominant for DH, including ephemeral DH.

I concluded that CFRG should consider the performance of variable-base
scalarmult (for DH), fixed-base scalarmult (for signing), and
double-base scalarmult (for signature verification). But I don't expect
this to produce different curve choices from considering solely
variable-base scalarmult---which is also the most fundamental operation
and the usual focus of DH performance analyses in the literature.

> allowing X25519 implementations to amortize
> the cost of operations which are particularly expensive for X25519
> over multiple uses of the same key. 

The "expensive for X25519" claim here is completely wrong. X25519 allows
all the usual speed benefits from all the usual fixed-base speedups. As
Mike Hamburg put it in his mail message dated 7 Aug 2014 11:57:45 -0700,
optimized fixed-base scalarmult "will pretty much always cost about a
third of what the variable-base scalar multiply costs."

Concretely,

   https://github.com/floodyberry/ed25519-donna
   https://github.com/agl/curve25519-donna
   
support all Curve25519/X25519/Ed25519 operations under discussion: DH
keygen (curved25519_scalarmult_basepoint is the fast version), DH
shared-secret computation, signature keygen, signing, and verification.
These are faster than the speeds announced by Microsoft for each of
these operations (and of course also for combinations of operations in
ECDHE etc.) on the CPU that Microsoft has selected for benchmarks. Also,
unlike Microsoft's library, these actually do the work of signing etc.

There are many X25519 implementations, reflecting the wide use of X25519
in many real-world protocols. It's of course true that reusing DH keys
practically eliminates keygen cost, which is exactly why typical users
don't care about DH keygen time, which is exactly why typical DH
implementations prioritize simplicity over DH keygen optimizations. This
has given you the flexibility to cherry-pick X25519 implementations that
don't bother speeding up keygen, and to misrepresent the performance of
those implementations as the keygen performance of X25519, even though
faster X25519 keygen code has been available for longer than Microsoft's
library has. Your position is not defensible.

> There has been no legitimate argument put forward for
> repeated use of ephemeral keys in ECDHE.

If a server notices keygen time, it can gain far more performance by
reusing a key 100 times than by switching to fixed-base scalarmult.
Reusing keys also costs less code in many settings than implementing
fixed-base scalarmult, but even without this simplicity argument you
have to admit that there's a legitimate performance argument.

Out of curiosity: If it wasn't for performance, why did Microsoft's TLS
library ever reuse ephemeral DH keys in the first place? Would you say
that the Microsoft reason was illegitimate? Even if you're sure that it
was illegitimate, wouldn't you agree that taking this reuse off of the
CFRG radar screen would require a blanket prohibition on this reuse in
all IETF protocols, and that no such prohibition exists?

> Assuming that implementations will implement more than one security 
> level, choosing X25519 for ECDHE at the 128 bit security level will require
> implementations to use different curve arithmetic for the 128 bit security
> level than other security levels.  

No. All Edwards (and twisted Edwards) curves, at all security levels,
are compatible with choosing Montgomery coordinates for ECDHE. See my
message dated 25 Aug 2014 23:43:05 -0000 for the relevant formulas.

When Tanja Lange and I introduced Edwards-curve cryptography, we
correctly and publicly predicted that Edwards coordinates would be close
in performance to Montgomery coordinates. However, nothing has ever
matched the amazing _simplicity_ of the Montgomery X-coordinate for DH.
This simplicity is more than just a time-saver; it also removes many
opportunities for DH implementors to screw up security.

> clear drawback to requiring different curve forms for key agreement
> and digital signature at the same security level.

The Montgomery approach to DH is exceptionally simple---costing very few
lines of code for a unified DH+signatures implementation (as TweetNaCl
demonstrates), and at the same time saving many more lines of code for a
pure DH implementation. If the picture looks like

   * complexity 300: DH using Montgomery
   * complexity 500: DH using Edwards
   * complexity 600: DH using Edwards + signatures using Edwards
   * complexity 610: DH using Montgomery + signatures using Edwards

you can't claim that there is a "clear drawback" to DH using Montgomery.

---Dan