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.
