Some thoughts on the NSA and elliptic curve cryptography
Sep 13, 2013Below is an amalgamation of some posts that I made recently on a popular microblogging platform:
========
I’ve been reading a lot today about what I believe is a super-likely NSA backdoor into modern cryptosystems.
There are these things called elliptic curves that are getting used more and more for key generation in cryptography, especially in forward-secrecy-enabled SSL (which is the EFF-recommended way to secure web traffic). The problem is that the choice of parameters for the elliptic curves most used in practice are set by NIST, and we know for sure that the NSA has some influence on NIST standards.
In 2006, NIST published an algorithm for elliptic-curve based random number generation that was shown to be easily breakable but ONLY by whoever chose the elliptic curve parameters. Luckily this algorithm was crazy slow so nobody used it, even though it was the (only?) NIST-recommended way of generating random bits with elliptic curves.
But it turns out there are some relatively-obscure papers that suggest that you can gain a decent cryptographic advantage by picking the elliptic curve parameters! [Edit: It was later pointed out to me that this particular attack is not close to anything the NSA could be doing right now, for various reasons. It is of course unclear whether they have knowledge of other elliptic curve parameter-based attacks that are not in the academic literature.]
This is terrifying, because the elliptic curve parameters chosen for relatively-mysterious reasons by NIST (probably via NSA) are used by Google, OpenSSL, and any RFC-compliant implementation of elliptic curves in OpenPGP (gnupg-ecc, for instance).
==========
Some people might be wondering if they can trust companies who issue statements that their closed-source software products don’t contain NSA backdoors (Microsoft, Google, Apple, etc.). Here is an example of why not.
It has been known since 2006 that Dual EC DRBG (a NIST-standardized random bit generation algorithm) has a major vulnerability that makes no sense except as an NSA backdoor. Essentially, the algorithm contains some constant parameters that are left unexplained; some researchers then showed that whoever determined these parameters could easily predict the output of the algorithm if they had access to a special set of secret numbers (analogous to an RSA private key). This is a beautiful design for a crytographic backdoor, because the secret numbers are difficult to find except by the person who set the constant parameters in the algorithm.
Despite being slower than other random bit generators, Dual EC DRBG is implemented in a bunch of software products by major companies like RSA Security, Microsoft, Cisco, BlackBerry, McAfee, Certicom, and Samsung. For a full list, see: http://csrc.nist.gov/groups/STM/cavp/documents/drbg/drbgval.html
Most of these products are closed-source, so you can’t check whether your encryption keys are being generated with Dual EC DRBG.
This is a pretty strong argument that secure software is necessarily open source software.
========
Additional citations:
Bruce Schneier on the 2006 backdoor discovery in Dual_EC_DRBG: https://www.schneier.com/…/2007/11/the_strange_sto.html
Google’s blog post announcing SSL w/ forward secrecy, specifically mentioning that they use the P-256 curve: https://www.imperialviolet.org/2011/11/22/forwardsecret.html
Wiki section on NIST-recommended curves: https://en.wikipedia.org/wiki/Elliptic_curve_cryptography…
RFC section stating that P-256 is REQUIRED for ecc in openpgp: http://tools.ietf.org/html/rfc6637#section-12.1
Description of elliptic curve usage in OpenSSL: http://wiki.openssl.org/…/Elliptic_Curve_Cryptography
Presentation on security dangers of NIST curves: http://cr.yp.to/…/slides-dan+tanja-20130531-4×3.pdf
NSA page recommending you use elliptic curves lol: http://www.nsa.gov/business/programs/elliptic_curve.shtml
UPDATE (9/23/13): RSA security has issued an advisory to stop using some of their products where DUAL_EC_DRBG is the default random number generator (http://arstechnica.com/security/2013/09/stop-using-nsa-influence-code-in-our-product-rsa-tells-customers/). Matthew Green also made an excellent blog post about this topic over at http://blog.cryptographyengineering.com/2013/09/the-many-flaws-of-dualecdrbg.html.