Re: [CFRG] Why we use ECDH instead of traditional DH

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

Daniel Brown writes:
> Beyond historical interest, is the main point here ("why ECDH, not FFDH")
> to help work out clearer criteria for future CFRG decisions?

There was a claim that "Any work that can be pushed up the pyramid
should be, because it reduces duplication".

I was giving a counterexample to both "should" and "reduces": namely,
taking traditional DH instead of ECDH pushes work from implementors up
to security reviewers, but increases the total amount of work and, more
importantly, increases security risks.

To be clear, I'm not saying the claim is _always_ wrong. Over the years
I've pointed out many examples where shifting work from implementors to
designers reduces total work and reduces failures. Obviously designers
should talk to implementors and think about what designers can do to
help implementors. But a rule that forces a regression from ECDH to
traditional DH is going too far.

  [ regarding large discriminants ]
> Nonetheless, I'd hope for more clarity on:
> 1) the level of risk difference,
> 2) specific rationale for the relative risk assessment,

The rationale is that fast automorphisms play a central role in many
attacks---sometimes giving just small speedups such as fast negation in
ECDL, but sometimes leading to outright disasters such as fast
low-characteristic multiplicative-group discrete logs---so we should
take those away from the attacker when we can.

Obviously this is stating only the direction of this risk, not the
magnitude. Quantifying risks takes more work, as in my recent paper
https://cr.yp.to/papers.html#qrcsp: you need large enough samples for
statistical validity, criteria that avoid "p-hacking", etc.

> On 1) risk difference, I quote [KKM, Sec. 11, p.30]: "Rather, our point is
> that conventional wisdom may turn out to be wrong and that, as far as
> anyone knows, either choice has risks. The decision about what kind of
> curve to use in ECC is a subjective one based on the user's best guess
> about future vulnerabilities."

This quote comes from setting up a comparison between two options where
one option gets rid of one type of fast morphism and another option gets
rid of another type of fast morphism (with the algorithms available at
that time). Choosing between the options (in the absence of other
considerations and in the absence of an option avoiding both risks
simultaneously) means deciding which risk is more important.

I see no justification in KKM for the conclusion that decisions are
subjective. Evaluating factors that point in multiple directions is a
standard engineering problem, and the literature on risk analysis is
full of examples of rationally weighing multiple risks. Furthermore, as
illustrated by DES and DSA and Dual EC, sabotage of security standards
is continually accompanied by hyping of some risks and downplaying of
others; our best defense against this is setting up objective,
transparent procedures for evaluating risks.

A standard idea in computer security is to design TCBs to be simple to
review; the point is that if the TCB is complicated to review then we'll
miss vulnerabilities. TCB size is often used as an easy-to-measure proxy
for the cost of review. In cryptography, it's more obvious that security
review isn't just looking at code, but we can still evaluate the review
complexity and pick the easiest-to-review options. For the KKM examples,
it's easy to see that that the special curves considered in KKM incur
higher review cost than typical curves.

> Does there hold a general correlation between discriminant size and the
> availability of a pairing needed for a MOV-type attack?  If so, is that the
> specific rationale for deeming greater risk of small-discriminant curves?

Field discriminants are an important predictor of performance of a wide
range of algorithms in algebraic number theory. CM computations in
setting up pairings are one example of this.

> So, how much and why is using a special-form field in ECDH less risky than
> using a special-equation low-discriminant curve in ECDH?

These are not orthogonal questions. If you choose a small embedding
degree then you should be able to make NFS run faster by also choosing a
prime represented by a small polynomial.

But the overhead from a large polynomial contributes only a small factor
to the final NFS norm size, while embedding degrees make an exponential
contribution. A reviewer working through the failure of index calculus
(and xedni calculus) for, say Curve25519 doesn't bother looking at this
overhead: the attack already fails when the overhead is ignored.

> Note that GLV proposed using low-discriminant special-equation curves
> for their greater efficiency, by way of efficient endomorphisms.

Indeed. Also, GLV curves acquired a big application after the patent
expired in 2020. But if I try https://github.com/bitcoin-core/secp256k1
on a Zen 3 core running at 2.3GHz then I see 21.1 us and 38.0 us for
"ec_keygen" and "ecdh" respectively, around 50000 and 87000 cycles. For
comparison, X25519 on the same machine is 26000 and 73000 cycles with
lib25519, or 26000 and 90000 cycles with the formally verified code from
https://github.com/awslabs/s2n-bignum (which you can also include in
lib25519 with the new use-s2n-bignum option).

> i) As to "avoid any risk".  Is this claiming that the risk of the
> preferred alternative is lower?

>From the risk source specified after "risk from", yes.

> ii) As to "large".  Does this mean "typically large" or "especially
> large"?

I meant typically large. Computing the field requires checking for the
occasional square divisors of t^2-4p, but will basically never find a
big square divisor---unless you use CM to force t^2-4p to be something
small times a big square in the first place.

> iii) As to "automorphism".  Should this have been "efficient
> endomorphism"?

I was thinking about the speed of automorphisms of the group. Of course,
fast curve endomorphisms are a big source of fast group automorphisms,
and the curve structure is useful for understanding pairings etc.

---D. J. Bernstein