[tialaramex]

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.

My favourite also reasonable explanation for the mysterious Dual EC DBRG constants is that some senior person picked their favourite numbers (birthday of a niece, phone number of a friend, whatever) not realising that these should be Nothing Up My Sleeve Numbers. Later when a subordinate says "For documentation we need to explain these numbers" it was late to change them and so the agency can't do better than insist they were chosen at random.

If this was crucial technology we should do the work to re-make it with Nothing Up My Sleeve Numbers, but it's garbage, indeed that's one reason for the suspicion, this is a very complicated machine, well suited to hiding a backdoor, why do this at all?

[red_admiral]

As far as I'm aware, the other problem with Dual EC is there's two kinds of componets you can use to build a DRBG: "chaotic" (think hash functions, or components thereof) and "algebraic" (highly structured but guaranteed to have certain properties such as minimum period size).

Cryptographic common sense is that if you use an "algebraic" generator, you feed the output through a "chaotic" one at the end. This can't possibly harm security (as long as the output transformation doesn't depend on secret state) as there's a reduction in which the adversary just does the transformation themselves. This is even more important if the algebraic transformation is efficiently invertible in principle, for example if someone has extra secret knowledge (such as the dlog of the base point in use).

If they'd used Dual-EC followed by SHA1 or something that would have not only been better according to folk wisdom, and demonstrably no worse for security (and costing very little compared to the EC operations) but it would also have shut down a lot of conjectured attacks that one could do with twiddled constants.

Yet for some reason, Dual-EC decided to go with an algebraic approach without a "chaotic" output transformation, which is either extreme incompetence or strong evidence that someone is up to no good.

[tptacek]

This is really overthinking it. Dual EC is an asymmetric RNG; it "encrypts" its state to a public key, with an undisclosed private key. To believe it wasn't backdoored (as some people, me included, did --- long story!) you have to take on faith that nobody in the world actually has that private key. We're now fairly sure someone does. That's the whole story.

[red_admiral]

You're probably right, I'm just saying that if you want to design a RNG that doesn't look extremely suspicious, you do it in such as way that there is no way to have a private key to start with. For example with a hash function somewhere in the loop, since these are (presumably) one-way.

[less_less]

> 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 next state of the random number generator to a certain elliptic curve public key, cuts off a few bits, and outputs the truncated ciphertext as a "pseudorandom number". Given this framing, the backdoor is obvious: guess the truncated bits, decrypt the ciphertext, and check whether the decrypted next state is consistent with later data that depend on that DRBG.

This is a pretty fucking weird design unless you're intending a backdoor. It's orders of magnitude slower and more complex than just symmetric-key encryption or hashing, which are traditionally used for DRBGs, and elliptic curve ciphertexts aren't uniformly pseudorandom so it's slightly biased as a DRBG as well. The claimed justification is that it's secure based on properties of elliptic curves, but even aside from the backdoor this is false (since it's biased), and anyway you'd be going for provable security here but there isn't any proof (even aside from the bias AND the backdoor... except maybe in the generic group model, which is too strong to be relevant here). Also, the backdoor potentials of Dual_EC_DRBG were discussed both before and after standardization, but it was standardized and used anyway.

It is conceivable that NSA chose this design through a firm but misguided belief that it has superior security properties, and that they don't have the private key corresponding to that public key, and that they paid RSA security $10 million to make it the default DRBG in BSAFE because they were just that proud of their generator, and they didn't notice the backdoor before publication, and they didn't consider the need for nothing-up-my-sleeve numbers because they weren't paying any attention. But IMHO it's much more reasonable to believe that Dual_EC_DRBG's backdoor is intentional, and that NSA does know the private key corresponding to their published recommended public key.

Also note that even if NSA doesn't have the backdoor key, a malicious actor can substitute their own backdoor key and everything just keeps working. With this change of 64 bytes of code, fully permitted by the spec, that actor (and nobody else) now controls the backdoor. This happened to Juniper networks.

--

None of this is apparently the case for the NIST elliptic curves, though. While it is possible that NSA knows a secret weakness in them (or, indeed, in all elliptic curves!), even 25 years later there is no publicly known class of weak curves that could include the NIST curves. Furthermore, the spec does include the values that hash to the curves' coefficients: while this doesn't guarantee that those values were really generated randomly, it significantly constrains how a hypothetical backdoor could work, and what the families of vulnerable curves could look like. If there were a backdoor, it would also in some sense be a less powerful backdoor than in Dual_EC_DRBG: the Dual_EC backdoor is only exploitable to someone who has the private key, but given the constraints on the NIST elliptic curves, it is likely that anyone who figured out the math of a hypothetical backdoor could exploit it.

IMHO it is still reasonable to believe that the NIST curves are backdoored. But IMHO they are very likely not backdoored, and I think my view also matches the consensus of the crypto community.

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