News and updates

Backdoors in NIST elliptic curves

Cryptography is a lot about trust. And in the real world cryptography depends on standards, as the standardization of cryptographic algorithms is how cryptography is projected into the real world.

For years people have trusted the US based NIST – National Institute for Standards in Technology, with headquarters in Gaithersburg just outside Washington DC. I was there once at a conference*.

But now thanks to the reckless actions of the NSA (National Security Agency), as exposed by various whistle-blowers, that trust has been blown, with incalculable consequences. Already there is a strong and well founded suspicion that at least one standard was “dumbed-down” to suit the NSA agenda.

http://en.wikipedia.org/wiki/Dual_EC_DRBG

Of particular concern are the NIST standard elliptic curves. There is a concern that these were some-how “cooked” to facilitate an NSA backdoor into elliptic curve cryptography. The suspicion is that while the vast majority of elliptic curves are secure, these ones were deliberately chosen as having a mathematical weakness known only to the NSA. Apparently, according to the leading authorities on Elliptic Curve Cryptography Dan Bernstein and Tanja Lange, back in 1999 I was the first to raise such a possibility.

http://safecurves.cr.yp.to/rigid.html

But at the time my concerns were not taken too seriously. The curves themselves were suggested by Jerry Solinas who worked at the NSA. In fact Jerry came over to Ireland for the first ever Pairing-Based crypto workshop in 2005. 

I must say I liked Jerry a lot, and on balance I believe that the NIST curves were more likely to have been designed out of naivety rather than malice. 1999 was another world. However once trust is tarnished, there is really no way back. And all for some short-term gain by the NSA of dubious value.

Now, belatedly, there is a move away from the NIST curves to a set of curves generated by academics in such a way that they are demonstrably not chosen from a particular small weak set. One way of doing this that I suggested at the time was to generate the curves using the digits of the universal constant pi. For some recent proposals see the link above and

http://eprint.iacr.org/2013/647.pdf

Indeed these new curves have properties which make them stronger in some senses than the NIST curves, even if they were not “back-doored”. So the future for elliptic curve cryptography is assured.