Nit: the hard dependency on good randomness for ECDSA is a property of DSA in general, and not of elliptic curve cryptography. The DSA construction has what is probably the strictest randomness requirement in all of mainstream cryptography; a bias of just a few bits is, with repeated signatures, sufficient to recover private keys! (The attack that makes this work on ECDSA is extraordinarily cool).
The problem with NIST Dual_EC_DRBG is simpler than the article makes it sounds. A good mental model for Dual_EC is that it's a CSRPNG specification with a public key baked into it (in this case, an ECC public key) --- but no private key. The "backdoor" in Dual_EC is the notion that NSA --- err, Clyde Frog --- who is confirmed to have generated Dual_EC, holds the private key and can reconstruct the internal state of the CSPRNG using it. I think this problem is simple enough that we may do a crypto challenge on a toy model of Dual_EC.
Nobody in the real world really uses Dual_EC, but that may not always have been historically true; the circumstantial evidence about it is damning.
The NIST ECC specifications are in general now totally discredited. If you want to see where the state of the art is on ECC, check out http://safecurves.cr.yp.to/.
You should never, ever, never, nevern, nervenvarn build your own production ECC code. ECC is particularly tricky to get right. But if you want to play with the concepts, a great place to start is the Explicit Formulas Database at http://www.hyperelliptic.org/EFD/; the fast routines for point multiplication are mercifully complicated, so copying them from the EFD is a fine way to start, instead of working them out from first principles.
And surely it would be better to have many implementations than a couple?
Its probably better to have more qualified people working on (analyzing and validating, particularly) a smaller number of production implementations than fewer people per implementation doing that with a larger number of production implementations.
Encryption is an area where doing one, very precisely defined, task correctly is critically important; the considerations in that domain are different than in many other domains of software.
I'm not sure I'd go with 'discredited'. Paranoia aside, I'd go with 'superseded' by better choices that weren't around in 1999. We probably mean the same thing, but this has become one of my pet peeves.
I'd have said the same thing a few weeks ago. You may have better information than I do; I'm working from the (new) presumption that the supposed random curves aren't likely to be random based on their structure.
It's a Cryptography Research paper from earlier this year and involves both a series of lattice reductions and the inverse fourier transform, which smooths out a very sharply defined bound into a much broader bound to make a search faster --- the latter trick is due to Bleichenbacher and referred to in the CRI paper as an "underground" attack.
Alex Balducci in our office actually got this attack working from the paper and walked us through the code --- the lattice reduction steps take 8 hours to run, and are followed by an IFFT-aided search that I would have zero chance of getting right and so never would have bothered waiting 8 hours to try, but he did it anyways.
Maybe I can get him to write it up.
Moral of this story by the way: hire people smarter than you are, and give them semi-unreasonable problems to work on.
The first time I heard about attacks on crypto that monitored processor power consumption, I was pretty skeptical. It seems crazy to me that it could work. But of course it does.
Same thing with timing attacks, til I learned how to code one for myself.
Comments
Nit: the hard dependency on good randomness for ECDSA is a property of DSA in general, and not of elliptic curve cryptography. The DSA construction has what is probably the strictest randomness requirement in all of mainstream cryptography; a bias of just a few bits is, with repeated signatures, sufficient to recover private keys! (The attack that makes this work on ECDSA is extraordinarily cool).
The problem with NIST Dual_EC_DRBG is simpler than the article makes it sounds. A good mental model for Dual_EC is that it's a CSRPNG specification with a public key baked into it (in this case, an ECC public key) --- but no private key. The "backdoor" in Dual_EC is the notion that NSA --- err, Clyde Frog --- who is confirmed to have generated Dual_EC, holds the private key and can reconstruct the internal state of the CSPRNG using it. I think this problem is simple enough that we may do a crypto challenge on a toy model of Dual_EC.
Nobody in the real world really uses Dual_EC, but that may not always have been historically true; the circumstantial evidence about it is damning.
The NIST ECC specifications are in general now totally discredited. If you want to see where the state of the art is on ECC, check out http://safecurves.cr.yp.to/.
You should never, ever, never, nevern, nervenvarn build your own production ECC code. ECC is particularly tricky to get right. But if you want to play with the concepts, a great place to start is the Explicit Formulas Database at http://www.hyperelliptic.org/EFD/; the fast routines for point multiplication are mercifully complicated, so copying them from the EFD is a fine way to start, instead of working them out from first principles.
I've implemented ECC and you are 100% correct. Nobody should implement ECC unless you really really know what you're doing.
Mapping points to the curve, multiplying points, point addition, there is too much math stuff to mess up on.
Just don't do it. If you read one thing tptacek says, read the last paragraph.
Well, ultimately, somebody has to.
Sure; Adam Langley, or Daniel Bernstein.
Preferably the latter.
Yeah, but then you get opinionated curves. :)
Luckily, djb's opinions seem to usually be right!
And surely it would be better to have many implementations than a couple?
Its probably better to have more qualified people working on (analyzing and validating, particularly) a smaller number of production implementations than fewer people per implementation doing that with a larger number of production implementations.
Encryption is an area where doing one, very precisely defined, task correctly is critically important; the considerations in that domain are different than in many other domains of software.
No, I don't see how that's surely better.
I'm not sure I'd go with 'discredited'. Paranoia aside, I'd go with 'superseded' by better choices that weren't around in 1999. We probably mean the same thing, but this has become one of my pet peeves.
I'd have said the same thing a few weeks ago. You may have better information than I do; I'm working from the (new) presumption that the supposed random curves aren't likely to be random based on their structure.
Would it be possible to get a link to a technical exposition of the extraordinarily cool attack?
It's a Cryptography Research paper from earlier this year and involves both a series of lattice reductions and the inverse fourier transform, which smooths out a very sharply defined bound into a much broader bound to make a search faster --- the latter trick is due to Bleichenbacher and referred to in the CRI paper as an "underground" attack.
Alex Balducci in our office actually got this attack working from the paper and walked us through the code --- the lattice reduction steps take 8 hours to run, and are followed by an IFFT-aided search that I would have zero chance of getting right and so never would have bothered waiting 8 hours to try, but he did it anyways.
Maybe I can get him to write it up.
Moral of this story by the way: hire people smarter than you are, and give them semi-unreasonable problems to work on.
Is the paper "Using Bleichenbacher's Solution to the Hidden Number Problem to Attack Nonce Leaks in 384-bit ECDSA"?
That would be the one.
The first time I heard about attacks on crypto that monitored processor power consumption, I was pretty skeptical. It seems crazy to me that it could work. But of course it does.
Same thing with timing attacks, til I learned how to code one for myself.
It's funny how very very careful you have to be.
Worth pointing out that you don't need to have an attacker watching your power consumption to have the partial nonce leak problem.