The Strange Tale of Dual_EC_DRBG

Julian Assange being arrested recently brought back memories of how he leaked Edward Snowden’s memos around the possible existence of an NSA-sourced cryptographic backdoor — the Dual EC standard (Dual_EC_DRBG). So let’s dive into the method and the trap door, and see the “magic” behind it.

With Elliptic Curve methods, we take an elliptic curve (y²=x³+ax+b), and then use a base point (G). Next, we generate a random number (n) and determine a point (P) by adding the point n times (G+G…+G). We represent this as:

P = n G

The point P is our public key, and n is our private key. With current computing power, we cannot determine n, even if we know P and G. This is known as the Elliptic Curve Discrete Logarithm Problem (ECDLP).

A core part of encryption is the generation of random numbers, as they are often used to create keys and salt values. If they can be guessed, it would break the whole foundation of cryptography, and significantly weaken the core of our security infrastructure. And so some thought that the NSA set out to create a backdoor function of the generation of random numbers, and that only they could break. Along the way, they are alleged to have paid RSA Security $10 million to push the method (and also for its integration into the BSAFE library).