[CFRG] Why we use ECDH instead of traditional DH

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

Filippo Valsorda writes:
> Any work that can be pushed up the pyramid should be, because it
> reduces duplication.

Often that saves work, but not always: sometimes the work becomes bigger
when it's pushed up. Furthermore, the goal is not to minimize total
work; the goal is security, and there are cases where reviewer time is
more important for this than implementor time.

Here's a pre-quantum example illustrating these effects.

Traditional DH uses a group of size q-1 for a prime power q, namely the
multiplicative group of the finite field F_q, or sometimes a subgroup of
whichever order dividing q-1. Traditional DH is easier for implementors
than ECDH. (I'm assuming in both cases that there's a single group that
everyone uses---otherwise traditional DH becomes considerably more
complicated and ECDH becomes much more complicated.)

How about we further simplify implementations by moving to _additive_
DH? Use a group of size q, the additive group of F_q. Sure, it's
completely broken, but look at how much easier the code is!

Okay, okay, obviously we don't use something that we know is broken. The
_reason_ we know additive DH is broken is that people thinking about its
security say "Hey, Euclid's algorithm breaks that".

For traditional DH, trying to figure out how to choose q for any
particular security level is a nightmare for security reviewers. For
example, the case of q being a power of 2 is in many ways the nicest
case for implementors, but 1984 Coppersmith found a much faster attack
against this case, and then there were more advanced "FFS" algorithms,
and finally, three decades after Coppersmith, there was a flurry of
papers breaking this case in quasi-polynomial time. Large primes q seem
quantitatively safer, but the "NFS" analysis is super-complicated (see
https://blog.cr.yp.to/20151120-batchattacks.html for some highlights),
and much faster attacks would be unsurprising.

ECDH, despite its implementation disadvantages, is _much_ easier for
security reviewers. Taking prime fields eliminates any attacks that
exploit extra subfields, including any risk from FFS. Taking large field
discriminants avoids any risk from further automorphisms. The occasional
curves for which NFS applies are easily recognized and avoided. What
we're left with are curves where the state-of-the-art attacks are _much_
simpler and _much_ easier to analyze than state-of-the-art attacks
against traditional DH. The last big excitement in these attacks was a
1.4x speedup decades ago.

Would taking traditional DH instead of ECDH push work up the pyramid?
Yes, obviously. Would it reduce total work? No. Most importantly, would
it reduce security risks? No: it would _increase_ them.

I've identified and addressed various risks in ECDH implementations. I
wouldn't say that what we have now is risk-free. If the only concern
were implementations then I would advocate traditional DH (again, with
a single shared group). But the ECDH implementation situation is getting
to be _almost_ non-scary, for example with recent full formal proofs
from John Harrison that some fast ECDH software works correctly for all
inputs, assuming the CPU correctly handles various machine instructions.
Meanwhile the cryptanalysis of _traditional_ DH isn't on a path to any
expert being willing to say "Okay, that's the end of the speedups".

This is the real reason that we use ECDH. It is, fortunately, correlated
with something much easier to explain, namely ECDH being smaller than
traditional DH (since the _known_ security losses in traditional DH
force big q) and faster than traditional DH (since the big q outweighs
the extra operations in ECDH)---but efficiency is really just another
subsidiary goal in service of the real goal, namely security.

Sophie Schmieg writes:
> avoiding FF-DH wherever I can means I don't have to care whether we
> should use safe primes or use larger private keys or both, one less
> thing I need to tell people about.

These are not advantages of ECDH over traditional DH. They are
advantages of taking standard, shared, reviewed, big enough groups.

Committees in the dark ages had tendencies towards traditional DH,
towards sizes being too small, and towards allowing each implementation
to pick its own adventure; but these mistakes aren't tied to each other.
openssl-3.2.1 ecparam -list_curves still shows secp112r1, for example. I
would rip that code out of the code base---along with the underlying
general-purpose curve support---so that reviewers can easily see that
attackers can't trigger it.

---D. J. Bernstein