# Is it possible to calculate the 'skeleton key' for DUAL_EC_DRBG? What would it take?

According to Bruce Schneier the constants used in the spec of DUAL_EC_DRBG may be related to a secret set of numbers, that could function as a master key for encryption using on this random number generator:

This is how it works: There are a bunch of constants -- fixed numbers -- in the standard used to define the algorithm's elliptic curve. These constants are listed in Appendix A of the NIST publication, but nowhere is it explained where they came from.

What Shumow and Ferguson showed is that these numbers have a relationship with a second, secret set of numbers that can act as a kind of skeleton key. If you know the secret numbers, you can predict the output of the random-number generator after collecting just 32 bytes of its output. To put that in real terms, you only need to monitor one TLS internet encryption connection in order to crack the security of that protocol. If you know the secret numbers, you can completely break any instantiation of Dual_EC_DRBG.

source

Is it possible to calculate these secret numbers given these constants? What would it take to calculate them?

-
At least is is not that easy that everybody can do it, otherwise the skeleton key would already be public, and the Dual_EC_DRGB not only "potentially undermined by NSA", but actually undermined by everyone. –  Paŭlo Ebermann Mar 4 at 21:48
I suppose it is easier to first have the skeleton key and from them generate those "fixed constants". –  Paŭlo Ebermann Mar 4 at 21:49
I would consider that a dangerous assumption. How many black hats does it take to take advantage of this, and how would we know? –  oɔɯǝɹ Mar 4 at 21:52
Please don't understand me wrong: I don't recommend using Dual_EC_DRGB, even if one is not considering NSA a potential attacker. It is a bad PRNG anyways (compared to existing alternatives based on symmetric crypto), even if it would be secure. And actually I have no idea how hard your problem is – I hope someone answers. –  Paŭlo Ebermann Mar 4 at 22:06

I've found this attack to be poorly documented, all-in-all. Below is a technical explanation of the matter, or one can skip to the conclusion if uninterested in the details.

# Dual_EC_DRBG

First, let me give a short description of Dual_EC_DRBG using the notation of Shumow and Ferguson (see the presentation). As a preliminary, we are working with some prime-order elliptic curve, and we have two points $P$ and $Q$ on that curve. $P$ is a generator of the curve; on the other hand, $Q$ is defined to be some arbitrary point.

Also, let $\varphi$ be a map that takes a point on the elliptic curve and returns the $x$-coordinate of that point. That is, $\varphi(x,y) = x$.

In any particular round $i$, we have a starting state $s_i$. From there, we compute $$r_i = \varphi(s_i P)$$ where $s_i P$ denotes repeated point addition: $$s_i P = \underbrace{ P + P + \dots + P.}_{s_i \text{ times}}$$

Now, from here there are two "paths" that happen at the same time: generation of the output and updating the state. The order in which we discuss them is irrelevant, really, but first, we'll generate the output of round $i$. This is defined as $$t_i = \operatorname{LSB}_{\mathrm{bitlen}-16}(\varphi(r_i Q)).$$ So, this is what the attacker has to work with. Here, $\operatorname{LSB}$ means "least significant bits": thus we chop off 16 bits before we output. If we had removed more bits, this would foil the attack below.

On the other hand, we have the state update as well. The next round's state is defined by $$s_{i+1} = \varphi(r_i P).$$

# The Attack

The point $P$ is defined to be a generator of the curve and $Q$ is "arbitrary". Since $P$ is a generator, there is some integer $e$ such that $P = eQ$. If one knows this $e$ offhand, what can one do?

Well, given any output $t_i$, we know all but 16 bits of the value $\varphi(r_i Q)$. So, we can generate those $2^{16}=65536$ possible values pretty easily. One of those values is $\varphi(r_i Q)$ itself. And since elliptic curves have a defining equation $y^2 = x^3 + ax + b$, given some $x$-coordinate, we can simply solve the quadratic to get the two possible $y$ values.

So, somewhere among our $2\cdot 2^{16}$ $(x,y)$ pairs, we have the real $r_i Q$. Pretend for a moment that we know it. Offhand, this doesn't seem so bad, does it? But we are assuming we know some $e$ such that $P = eQ$. Multiply: $$e (r_i Q) = r_i (e Q) = r_i P.$$ And if you recall from above ... $$s_{i+1} = \varphi(r_i P).$$ So if you know this special $e$, you can predict the future state of the generator. Whoops!

I am glossing over a point here: figuring out the proper $r_i Q$ requires you to take the output, generate all the missing 16 bit possibilities, and then try the above attack (comparing the real output $t_{i+1}$ against your predicted next state, iteratively) until you find the real state of the generator. From there, you can predict all future values with no problems. Shumow and Ferguson, in their testing, found that approximately 32 bytes of output was sufficient.

# Conclusion

Is it possible to calculate these secret numbers given these constants? What would it take to calculate them?

It is possible, but not feasible.

The secret integer $e$ (where $P = eQ$) is the necessary value to find. Computing this $e$ from scratch (with arbitrary $P,Q$) requires solving an instance of the discrete logarithm problem in the elliptic curve: $e = \log_Q P$. At present, it is considered computationally infeasible to solve this equation, so you needn't worry particularly about this case.

However, if you are the one picking the point $Q$, you can select a random integer $d$ (to use Shumow and Ferguson's notation again) and set $Q = d P$. Then $e = d^{-1}$, which is quite easy to compute.

Thus: unless you are the one who picked the point $Q$, you have basically no hope of finding $e$. On the other hand, if you did pick $Q$, then you could have very easily picked $Q$ such that you know $e$. This is pretty much the textbook definition of a backdoor, I think.

-
nice answer! Nitpick: since the group has prime order, any $Q$ will also be a generator (unless $Q$ is the neutral element, which would make no sense here). –  DrLecter Mar 5 at 7:36

The value in question is the logarithm of one point to the base of a second point. Computing discrete logarithms on the curves in question is generally considered to be very hard.

-