3 ms·

> The randomness requirement for DSA is such a huge problem for DSA that it forms the centerpiece of Daniel Bernstein's critique of the NIST standards process.

by j2kun 13y ago

> The randomness requirement for DSA is such a huge problem for DSA that it forms the centerpiece of Daniel Bernstein's critique of the NIST standards process. This is the bug that broke the PS3. I've been reading about this recently, but I'm confused. Wasn't the PS3 issue that the key was static? That's not the opposite of randomized, because there could be a deterministic, yet message-specific scheme for generating the secret key. Or is that known to be unacceptable? > there is concern that the NIST curves are backdoored and should be disfavored and replaced with Curve25519 and curves of similar construction. I've heard the opposite, that the curves are not the problem but the choice of basepoint. E.g. [1] states: "...the vulnerabilities in Dual-EC have precisely nothing to do with the specifics of the NIST standard elliptic curves themselves. The 'back door' in Dual-EC comes exclusively from the relationship between P and Q -- the latter of which is published only in the Dual-EC specification." Is it still a matter of dispute whether the curves themselves are suspect? Or is the referenced blog post outdated? [1]: http://blog.cryptographyengineering.com/2013/09/the-many-flaws-of-dualecdrbg.html http://blog.cryptographyengineering.com/2013/09/the-many-fla...

tptacek 13y ago
No, the PS3 problem was that the per-message DSA nonce ("k") was repeated (and thus not random). I'm not sure about the rest of your paragraph; if you're referring to deterministic alternatives to standard DSA, yes, they exist. Again, see Bernstein. Dual_EC isn't a curve standard, it's a random number generator standard. The NIST P- curves are thought to possibly be backdoored. Dual_EC is all but certainly a backdoored.
- ninguem2 13y ago
  If secp256k1 is backdoored, why hasn't someone stolen a shit ton of bitcoins?
  - tptacek 13y ago
    First, SECP256K1 isn't (IIRC) a NIST curve. Second, if NSA backdoored a curve standard, they probably did it in a fashion that only allows them privileges. Google [NOBUS NSA]. Dual_EC is a NOBUS backdoor, unless you can efficiently solve the ECDLP, in which case the backdoor doesn't matter anyways. Finally, even if you stipulate for argument that a curve was backdoored in such a way that a researcher might find the backdoor, who's to say that curve researchers care that much about Bitcoin?
- j2kun 13y ago
  So you're saying that there is something inherently insecure about the constants defining the curves themselves. I've read some of Bernstein's stuff on 25519, and everything there is about selling curve25519 as making the engineering challenges easier by avoiding common pitfalls of the Weierstrass normal form. And I can't find anyone anywhere giving evidence of mathematical insecurity of any NIST standard curves. Evidence might come in the form of a (significantly more than state of the art)-subexponential but still superpolynomial time algorithm. Dual_EC has something even better: a proof of insecurity.
  - tptacek 13y ago
    Here, just read Bernstein: http://www.hyperelliptic.org/tanja/vortraege/20130531.pdf http://www.hyperelliptic.org/tanja/vortraege/20130531.pdf
    - j2kun 13y ago
      And I quote, "So what's the problem? Answer: If you implement the NIST curves, chances are you're doing it wrong" This is just reinforcing my point. There is nothing known to be mathematically wrong with the standard curves. Bernstein just warns against all the (admittedly many) pitfalls in implementations, and that the Weierstrass normal form makes it easier to run into problems than the normal form he proposes. This is the only reason he says NIST doesn't guarantee security, and of course they don't guarantee against engineering errors. But that's extremely different from saying NSA planted backdoored curves intentionally. The only thing in Bernstein's analysis that I could possibly construe as suggesting malicious behavior is that the NIST curves are outdated (the suggestion being that they are intentionally left outdated).

by j2kun 13y ago

tptacek 13y ago

No, the PS3 problem was that the per-message DSA nonce ("k") was repeated (and thus not random). I'm not sure about the rest of your paragraph; if you're referring to deterministic alternatives to standard DSA, yes, they exist. Again, see Bernstein. Dual_EC isn't a curve standard, it's a random number generator standard. The NIST P- curves are thought to possibly be backdoored. Dual_EC is all but certainly a backdoored.

ninguem2 13y ago
If secp256k1 is backdoored, why hasn't someone stolen a shit ton of bitcoins?
- tptacek 13y ago
  First, SECP256K1 isn't (IIRC) a NIST curve. Second, if NSA backdoored a curve standard, they probably did it in a fashion that only allows them privileges. Google [NOBUS NSA]. Dual_EC is a NOBUS backdoor, unless you can efficiently solve the ECDLP, in which case the backdoor doesn't matter anyways. Finally, even if you stipulate for argument that a curve was backdoored in such a way that a researcher might find the backdoor, who's to say that curve researchers care that much about Bitcoin?
j2kun 13y ago
So you're saying that there is something inherently insecure about the constants defining the curves themselves. I've read some of Bernstein's stuff on 25519, and everything there is about selling curve25519 as making the engineering challenges easier by avoiding common pitfalls of the Weierstrass normal form. And I can't find anyone anywhere giving evidence of mathematical insecurity of any NIST standard curves. Evidence might come in the form of a (significantly more than state of the art)-subexponential but still superpolynomial time algorithm. Dual_EC has something even better: a proof of insecurity.
- tptacek 13y ago
  Here, just read Bernstein: http://www.hyperelliptic.org/tanja/vortraege/20130531.pdf http://www.hyperelliptic.org/tanja/vortraege/20130531.pdf
  - j2kun 13y ago
    And I quote, "So what's the problem? Answer: If you implement the NIST curves, chances are you're doing it wrong" This is just reinforcing my point. There is nothing known to be mathematically wrong with the standard curves. Bernstein just warns against all the (admittedly many) pitfalls in implementations, and that the Weierstrass normal form makes it easier to run into problems than the normal form he proposes. This is the only reason he says NIST doesn't guarantee security, and of course they don't guarantee against engineering errors. But that's extremely different from saying NSA planted backdoored curves intentionally. The only thing in Bernstein's analysis that I could possibly construe as suggesting malicious behavior is that the NIST curves are outdated (the suggestion being that they are intentionally left outdated).