[red_admiral]

Bernstein's argument is that, even if the NIST curves are not backdoored mathematically, they're designed in a way to strongly coerce implementors towards a route which leaves side-channels open, such as non-constant-time implementations or sloppy handling of invalid data such as points that do not lie on the curve, or in a small-order subgroup (all of which has been seen in practice).

[tptacek]

That was an argument that was more credible before than it is now, right? We have complete addition formulas for the Weierstrass P-curves now.

[red_admiral]

The complete addition formulas part is indeed solved, and could have been solved much earlier if people had read Lenstra's 1995 work. The complete formulas we have today are based on Renes et al. from Eurocrypt 2016, but that refers back to "We're essentially doing Lenstra". The technical detail here is that it's impossible under certain circumstances to get complete formulas that work over extension fields, but that's not necessary to do it over the NIST curves where you're working over the base field GF(p, 1).

That said, I still think the finite-field inversion in ECDSA signatures (instead of doing vanilla Schnorr) is dumb and risky. (Bernstein's deterministic signature improvement is even better, and would probably have prevented the PS3 hack, but I can't blame NIST for this because it was not known at the time. I think you're allowed to do it with the NIST curves too nowadays.)

FIPS 182 gives a non-constant-time implementation of point multiplication with the note "The algorithm given below is for reference purposes. Other (constant time) algorithms that produce an equivalent result may be used." which should be a MUST not a MAY, and in my opinion the non-constant-time one should never have been in the standard in the first place because that (and the accompanying note's wording) encourages people to go with it.

Checking for invalid curve points is also a solved problem in theory, but as far as I know not always implemented correctly in practice.

[less_less]

Yeah, and they're pretty performant too.

I also didn't notice when originally replying, but maybe it's worth tacking on:

> ... even if the NIST curves are not backdoored mathematically, they're designed in a way to strongly coerce implementors towards a route which leaves side-channels open ...

[emphasis mine]

The NIST curves are short Weierstrass curves with a=-3. I believe that before 2007 (Edwards), these were generally considered the best, fastest, easiest-to-implement elliptic curves for general operations. Yes, Montgomery curves are faster and simpler for ECDH, at the cost of having a cofactor, but not for signatures.

So it's worth noting that NIST/NSA/Certicom did not choose this family of curves as a trap for implementers. It was the best choice at the time, but Montgomery or Edwards curves are arguably a better choice now.

[less_less]

Bernstein has multiple arguments. Section 7 is about ways that the NIST curves could hypothetically be backdoored, and about designing curves in a "rigid" way such that they are less likely to be backdoored ... at least assuming that small parameters, or parameters near powers of 2, aren't more likely to be weak.

But yeah, he also argues that Montgomery / Edwards curves are easier to implement securely. IMHO he's right, but he exaggerates the difference. Montgomery and Edwards curves still have plenty of footguns, and some of these are not present in prime-order short Weierstrass curves like the NIST curves. In particular, the fact that Montgomery and Edwards curves must have a cofactor of at least 4 leads to problems: side-channel attacks like "May the 4th be with you", EdDSA signature validity not actually being defined, needing additional complexity (Ristretto/Decaf) to avoid protocol changes, etc.