Safe curves for Elliptic Curve Cryptography [pdf] • Hacker News Board

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#71

Post by tptacek » Thu, Aug 15, 2024, 3:28 AM UTC

red_admiral wrote: post #50

less_less wrote: post #39

Earlier quoted context omitted.

> Dual EC DRBG is a bad design and so you shouldn't use it. It is reasonable to believe it's backdoored, but only the same way it would be reasonable to believe David Cameron stuck his dick in a dead pig. Some people say he did, he says he didn't, there's no conclusive proof available - and it's worth noting the "source" is a man who has a grudge against Cameron. Hard disagree. Dual_EC_DRBG more-or-less encrypts the…

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).

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.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#72

Post by tptacek » Thu, Aug 15, 2024, 3:29 AM UTC

TacticalCoder wrote: post #70

mike_hearn wrote: post #7

The naming is unfortunate. Some people (Ubuntu...) have concluded that because some curves are branded "safe" that must mean all the other curves are therefore "unsafe" and must be aggressively phased out as if they were MD5. They're changing apt to refuse to download from repositories signed using NIST curves, for instance. This doesn't make a whole lot of sense unless you think the NSA have an unknown backdoor that…

> They're changing apt to refuse to download from repositories signed using NIST curves, for instance. > > This doesn't make a whole lot of sense unless you think the NSA have an unknown backdoor... It's "only" a CSPRNG (Cryptographically IN secure PRNG in this case) but the NIST recommending a backdoored curve in the past is an undisputable fact . So I don't think it's that non-sensical to go for something simple li…

I don't think you should be using words like "undisputable fact" in this thread, because Dual EC isn't a curve; it's a construction that uses curves.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#73

Post by tptacek » Thu, Aug 15, 2024, 3:30 AM UTC

marcosdumay wrote: post #46

mike_hearn wrote: post #7

The naming is unfortunate. Some people (Ubuntu...) have concluded that because some curves are branded "safe" that must mean all the other curves are therefore "unsafe" and must be aggressively phased out as if they were MD5. They're changing apt to refuse to download from repositories signed using NIST curves, for instance. This doesn't make a whole lot of sense unless you think the NSA have an unknown backdoor that…

[flagged]

Again: NSA did not in fact add a backdoor to a curve; they published a backdoored RNG that used curves.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#74

Post by mike_hearn » Thu, Aug 15, 2024, 8:25 AM UTC

marcosdumay wrote: post #46

mike_hearn wrote: post #7

The naming is unfortunate. Some people (Ubuntu...) have concluded that because some curves are branded "safe" that must mean all the other curves are therefore "unsafe" and must be aggressively phased out as if they were MD5. They're changing apt to refuse to download from repositories signed using NIST curves, for instance. This doesn't make a whole lot of sense unless you think the NSA have an unknown backdoor that…

[flagged]

I didn't assume that, and laid out the argument why it might have happened above.

I don't take a stance on the question of whether the NIST curves are OK either way, other than to defend those who argue there might be a problem (in the past I've seen this take dismissed as a conspiracy theory, which is clearly absurd). There isn't any specific evidence that there's a problem, only a failure to uphold the highest possible standards, which is a fairly weak form of evidence.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#75

Post by less_less » Thu, Aug 15, 2024, 8:55 AM UTC

tptacek wrote: post #71

red_admiral wrote: post #50

Earlier quoted context omitted.

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).

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.

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.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#76

Post by red_admiral » Thu, Aug 15, 2024, 12:02 PM UTC

tptacek wrote: post #71

red_admiral wrote: post #50

Earlier quoted context omitted.

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).

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.

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.