Monday, March 24, 2014

How the Dual EC DRBG Backdoor Works

In December 2013, Reuters reported that the National Security Agency had paid RSA ten million dollars to use a random number generation algorithm that contained a backdoor.  The algorithm, Dual_EC_DRBG, is the default random number generation algorithm in RSA's BSAFE toolkit which is used by other companies to implement cryptography in their products.  These allegations have seriously damaged the reputations of RSA and of the NSA who had established itself as a partner in the security community.

A great number of articles were published about the RSA-NSA deal after Reuters first reported on the matter.  Many of these make misleading or untrue technical assertions and few of them have attempted to provide any explanation as to how this supposed backdoor works.  Some commentators have claimed that this backdoor (if true) made the products that used the BSAFE toolkit more vulnerable to attack.  This is (mostly) not true.  Because the backdoor, whose possibility was first speculated on by Dan Shumow and Niels Ferguson of Microsoft, relies on techniques from public key cryptography, it is only usable by a person that knows the key and that key cannot be discovered by another party, even if that party knows the full details of the algorithm.

This post explains the Dual_EC_DRBG algorithm and how a backdoor could be implemented.  It is meant to be accessible to non-cryptographers. We’ll begin with a really brief review of modular arithmetic and the discrete logarithm problem, discuss basic operations on elliptic curves and introduce the discrete logarithm problem over elliptic curves (ECDLP).  Then, we’ll see how Dual_EC_DRBG can be engineered to contain a backdoor and explain why the backdoor is only usable to someone who knows the key.  If all of this is new to you, I recommend reading an introductory text such as this one.

Note: I originally wrote this as a paper for a graduate class.  In revising this for my blog, I've removed all of the in-text citations and tried to replace them with links.  My original references are listed at the end.  The point of this post is to explain ideas originated by others; the original ideas are not mine.

Understanding Scope in Go

As per my New Year's resolution, I've been learning to program in Go and reading  The Go Programming Language .   On page 141 of the...