[TLS] Re: Disallowing reuse of ephemeral keys

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

Filippo Valsorda writes:
> Both ECDH and KEMs support key share (or public key) reuse *in theory*
> but in practice it makes implementation issues much more likely to be
> practically exploitable

Is there quantification and justification for the "much" claim?

Perhaps the allusion here is to examples of implementation-attack demos
that reuse keys---e.g., https://kyberslash.cr.yp.to recovering Kyber
keys from timings of the Kyber reference software with some compilers.
But it's an error to leap from ~"this demo reuses keys" to ~"avoiding
key reuse will make the Kyber reference software hard to exploit". I'm
not aware of any papers studying the latter claim.

I'm not saying that it's clear that switching keys doesn't help security
overall. I'm saying we shouldn't overstate the evidence that it helps.

Meanwhile the normal ways to set up TLS servers are reusing identity
keys for _at least_ months. If key reuse is a security problem, should
we be recommending faster rotation of identity keys? Or is signature
software being claimed to be somehow immune to implementation attacks?

As a side note, one of the attractions of replacing signatures with KEMs
for identity keys is removing the signing software as an attack target
(even if verification software is still used for signatures from CAs).
But this needs the KEM software to be safe for keys used many times.

> the hypothetical performance gain of reuse is marginal

This is not hypothetical. For example, kyber768 is reported in

    https://bench.cr.yp.to/results-kem/amd64-alder2,1f626960,5600000.html

to take slightly over 30000 cycles for key generation on Golden Cove
(Intel Alder Lake performance cores). Sure, there's also a cost to
retrieving an existing key from cache, but the measurements in

    https://chipsandcheese.com/p/alder-lakes-caching-and-power-efficiency

show 4 P-cores on a Core i9-12900K together sustaining 800GB/second from
L2 cache, so (given that the CPU runs between 3.2GHz and 5.2GHz) reading
a few KB on one core is on the scale of 100 cycles, never mind the time
saved for cache misses for usually skipping the key-generation code.

People who use, e.g., ntruhrss701 to stay away from Kyber's patent
issues are incurring nearly 200000 cycles for key generation on the same
cores, although https://cr.yp.to/papers.html#opensslntru explains how to
reduce this cost. For X25519, https://lib25519.cr.yp.to/speed.html shows
24000 cycles for key generation on Golden Cove.

As for "marginal": On an absolute scale? By comparison to something
else? Looking at the big picture of costs is good, but this "marginal"
claim is ambiguous, missing quantification, and missing justification.

In ongoing discussions over on CFRG, some of us have proposed requiring
extra hashing in hybrids, but there has been an objection claiming that
"saving a single hash in TLS saves compute time worth millions of
dollars/CO2 emissions/energy" (at Internet scale or at Google scale;
hasn't been clarified). Key reuse in the cryptosystems under discussion
saves more computation than that. It's inconsistent for IETF/IRTF to
have a larger cost dismissed as "marginal" while a smaller cost is
treated as a decision-making factor. (And, yes, this is _exactly_ the
sort of thing that exposes IETF to antitrust liability.)

I should emphasize that using cost arguments to hold back security
mechanisms is very often a mistake, and I wouldn't be surprised if
further consideration ends up settling on thread option 2 or 3. But cost
arguments in any direction should be clear, quantified, and justified.

---D. J. Bernstein