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 '14 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 '14 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 '14 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 '14 at 22:06
The answer is: very practical to do and has even been demonstrated. See dualec.org – Thomas M. DuBuisson Apr 3 '15 at 5:16

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. Since the group is prime-order, both $P$ and $Q$ are generators.

Since we'll be working with integers ultimately, we need a way to "convert" a point on the curve into an integer. For that purpose, we will define $\varphi(x, y) = x$, i.e., we just use the $x$-coordinate of the point.

In any round $i$, we have a starting state $s_i$. Next, 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}}$$ This $r_i$ will be used to (1) generate the output and (2) update the state of the generator.

The output of round $i$ is $$t_i = \operatorname{LSB}_{\mathrm{bitlen}-16}(\varphi(r_i Q)).$$ The attacker will be working with these values. Here, $\operatorname{LSB}$ means "least significant bits," so we chop off 16 bits before we output.

The state of the next round is defined by $$s_{i+1} = \varphi(r_i P).$$

The Attack

Since $P$ is a generator, there is some integer $e$ such that $P = eQ$. Suppose we know this $e$.

Given any output $t_i$, we know all but sixteen bits of the value $\varphi(r_i Q)$. We can generate all possible combinations of those missing sixteen bits, which leaves us with $2^{16} = 65536$ possible values — one of which is $\varphi(r_i Q)$, the "real" output. Since all $(x,y)$ points on an elliptic curve satisfy the equation $y^2 = x^3 + ax + b$, if we are given some $x$-coordinate, we can solve the quadratic to obtain two possible $y$ values. That is, if we have $2^{16}$ values that might be $\varphi(r_i Q)$, we can use each of those values in the previous equation, and thus obtain $2 \cdot 2^{16} = 2^{17}$ values, one of which is the real $r_i Q$.

What happens if we have $r_i Q$? Since we're assuming we know the $e$ such that $P = eQ$, we can simply multiply $r_i Q$ by $e$ to get: $$e(r_i Q) = r_i (e Q) = r_i P.$$ Recall that the state of the next round is defined to be $$s_{i+1} = \varphi(r_i P).$$ So if you know the $e$ such that $P = eQ$, you can predict all future states of the generator, which means you can predict all future outputs of the generator.

How do we determine which of the $2^{17}$ values is $r_i Q$? Simple: we try to predict the next round's output, using the above attack, for multiple rounds. When one value fails to predict the next state, it is obviously not the real $r_i Q$, and so it can be thrown out. This process eliminates all but the real $r_i Q$. Shumow and Ferguson found that approximately 32 bytes of output was sufficient for this attack to succeed.

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 compute the discrete log in 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.

Note that two problems in tandem cause this attack: first, if we had picked a better way of integer-izing an elliptic curve point (a better $\varphi$), it wouldn't be possible to use $\varphi(r_i Q)$ to find $r_i Q$. Second, since we only chopped off sixteen bits before output, it is easy to brute-force test all missing sixteen bits. If we had chopped off more bits, the attack would maybe have been thwarted.

-

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.

-