The Dual Elliptic Curve Deterministic Random Bit Generator, or “Dual EC” is an algorithm standardized by the NIST and presented as a cryptographically secure random number generator. Due to widespread suspicions about the algorithm being deliberately weakened, it was officially withdrawn as a standard in 2014. This article explains how this flaw works and how it might be exploited.

How it works

The random number generator works on the basis of an elliptic curve. The curve itself forms a finite cyclic group G, and as you can probably sense, the security of the random generator works on the basis of the insolvability of the discrete log problem. The elliptic curve itself was chosen by the NSA, as were two magic values P and Q, which are elements of G (or geometrically, locations on the curve). Importantly, how these points were chosen was not stated – they were just defined and the world was told to use them.

 

 

The algorithm works similarly to many other random number generators in that there is some internal state, and with each iteration of the algorithm, a new random number is emitted and the internal state is updated. Importantly, the internal state must be kept secret as it fully determines the next number in the sequence.

With that said, here’s the basics of the algorithm:

• Let s1 be the existing state. We calculate s1*P and call this intermediate value r.
• We calculate r*P and call this s2. This will be the next internal state value, which must be kept secret.
• Finally, we compute r*Q, and take a fixed number of lower bits from the result, and that’s the random number.
• Update the internal state to be s2.

This on its own is a good construction. Note that in order to break the random generator you need to obtain r*P, but doing so requires you to solve r = rQ which is, again, the discrete log problem and at present, computationally intractable.

So far, so good. But what if we assume that there exists some e such at P = eQ. If this is the case, then someone could in theory compute e(rQ) = r(eQ) = rP (though associativity of the group) and thus find the internal state of the generator. This is not really a problem though because finding e is essentially impossible (yep – it means solving the discrete log problem again).

But recall that we have no idea where P and Q came from. It’s entirely feasible that the NSA chose a random value for e and then generated P and Q. If this were the case, it means that they would have the capability of predicting the next number in the sequence because they (and only they) can determine the internal state. P and Q should be chosen at random, but in this specification, they weren’t. As such it’s lead most people to believe some group element e exists that gives the NSA backdoor knowledge of the random number generator.