NSA's SP800-90 Dual EC DRBG

I am quite shocked. In one of my last blog posts i wrote about my concern that the NSA could have implemented backdoors in international standards, and that there are reasons to speculate that in particular the SP800-90 Dual EC DRBG seems suspicious. Meanwhile, i took a look at the paper from Shumow and Ferguson that was presented at the crypto rump session 2007.

What is the most important property a (pseudo) random number generator should have? Right - given the current output, one should not be able to compute/predict the next output in a better way than random guessing the bits. For a pseudo random generator this means, since it is actually deterministic, an attacker should not be able the deduce the inner state from a given output. The access to the inner state (that are values of private variables or keys that the algorithm uses to generate its random) should be prevented by some known computationally hard problems or one-way functions.

The SP800-90 Dual EC DRBG uses Elliptic Curves for that purpose, in particular the Elliptic Curve Diffie-Hellman Problem. The NIST standard specifies the curve as well as two points $P$ and $Q$ on that curve that are used during the generation of randomness. But it is not stated how these two points are generated. In [1 - Appendix A] you can find three different setups for each of the NIST curves P-256, P-384, P-521. For example for P-384 you have:

 P-384
 Curve: y^2 = x^3 + ax + b mod p
 p :3940200619639447921227904010014361380
    5079739270465446667948293404245721771
    4968703290472660882589380018616069731
    12319
 a :-3
 b :2758019355995970587784901184038904809
    3056905856361568521428707301988689241
    3098608651362607648837451077654397612
    30575
 
 P :(px,py)
 px:2624703509579968926862315674456698189
    1852923491109213387815615900925518854
    7380500890223880539757197866508724767
    32087
 py:8325710961489029985546751289520108179
    2878530488613155947092059024805031998
    8441922443864376039294733307808651162
    7871
 
 Q :(qx,qy)
 qx:2192444794636910863468193981803196826
    2144539646886075638513519060543201496
    3849096914210820127189619247138431084
    34021
 qy:3433531171552689071139037136125944672
    5737188237841222732783121724109202580
    8152604551590470438702352839201257948
    125

This is the crucial fact. Normally, a standard would describe how points like these were chosen. It should be something like: Hash this and that object and than map the value to the nearest point on the curve. It has to be a way, that allows everyone to reconstruct the points independently and that everyone can convince himself that the two points are generated randomly.

The problem that arises with the SP800-90 Dual EC DRBG standard is, that the points $P$ and $Q$ could actually be chosen to be of the form $Q = eP$. And the secret integer $e$ is only known to the creators of the standard. Furthermore, $e$ can not be computed by anyone else due to the hardness of the Elliptic Curve Diffie-Hellman problem. If this is the case, then the inner state and hence all future output could be deduced from only two output blocks (that are two 240bit block) of this DRBG. Furthermore, one single output block is already enough break the TLS/RSA handshake protocol.

And this is not hidden. It is actually easy to see. How could something like this become a standard?

The generator

Assume that indeed the points are connected via $Q = eP$. We define $\varphi: (x,y) \rightarrow x$, that is a function that maps a point $(x,y)$ on the curve to its $x$-value. Then the SP800-90 Dual EC DRBG uses the following equations/functions to generate random (we use here the $256$-bit curve):

1. The generator is seeded with $s_0$ = SEED

2. $s_{i+1} = \varphi(s_iP)$

   // $P$ is used to interate points

3. $r_i = \varphi(s_iQ)$

   // $Q$ is used to output the random

4. $r^*_i = \mathsf{LSB}_{240}(r_i)$

   // $r^*_i$ is the $i$-th output and is equal to the $240$ least significant bit of $r_i$. Hence, only the $16$ most significant bits of $r_i$ are cut of.

Points 2) to 4) are iterated to output succesive blocks of random. The inner state (our target) is only the integer $s_i$.

Let's break it

Assume you have intercepted the $i$-th output $r^*_i$. First, we have to guess to complete value $r_i$ from $r^*_i$. This is not hard, since $r_i$ only has $16$-bit (65536 possibilities) more than $r^*_i$. We extend $r^*_i$ by all possible $16$-bits integers and get potential candidates for the correct $r_i$: $$r_{i,j} = b_{j}|r^*_i, 0 \leq j \leq 2^{16}-1$$ We get $2^{16}$ possible values for each $r_{i}$, so we write $r_{i,j}$ for $0 \leq j \leq 2^{16}-1$. For one of those, say $j^c$, it holds $$\varphi(s_iQ) = r_{i,j^c}$$ Next we compute the $y$-values for all the possible $r_{i,j}$ values for the given curve. This would thin out around half of the $r_{i,j}$ values. For those that are valid points on the curve, we now know $$s_iQ = (r_{i,j},y_{i,j})$$ Lets apply the secret knowledge. If now someone knows the secret integer $e$ (i.e. $Q=eP$), he can compute $$\varphi(e((r_{i,j},y_{i,j}))) = \varphi(es_{i,j}Q) = \varphi(s_{i,j}P) = s_{i+1,j}$$ So he gets $2^{16}$ [or less, dependent of many points were actually valid points on the curve] possible values for $s_{i+1,j}$. Using the possible $s_{i+1,j}$ candidates one computes $$r^*_{i+1,j} = \mathsf{LSB}_{240}(\varphi(s_{i+1,j}Q))$$ and compares each of the $r^*_{i+1,j}$ with the next intercepted output block. With very very high probability there will be only one $s_{i+1,j}$ the leads to the correct $r^*_{i+1}$.

Congratulations. You just reconstructed the entire inner state. And if you have only one intercepted output block $r^*_i$ at hand, you can at least narrow the next output block down to at least $2^{16}$ minus those that are not valid curve points.

Practise

That's the theory. And really it looks suspicious. But how easy it is in practise to get one or even two (at best) successive output blocks $r^*_i$ from the generator? Some systems do post-processing on the data received from a DRBG. But this is a deterministic and mostly public known procedure. I will neglect this here and will assume that the random from the DRBG is directly used in the cryptographic protocols.
In what cases can a eavesdropper gain knowledge about these data? For example, in the Diffie-Hellmann key agreement protocols, the random data is used to form the secret exponents or scalars, e.g., $g^\text{random} \pmod{p}$, and can not be accessed directly.

Lets look the TLS protocol. Its the most used protocol for secure transport data. The very first step in the handshake procedure is for the client to generate a random number. And in the second step, this random number is transmitted in plaintext to the server in the server_hello packet. If the client chooses RSA, he executes a key-exchange protocol (not key-agreement protocol). The second random number the client creates is the encryption key. He sends it to the server encrypted with the server's public key.
With the help of the first intercepted random number, the attacker could decrease the number of potential encryption keys below $2^{16}$ possibilities. Then he encrypts each of those candidates with the public key of the server, and compares the result with the generated ciphertext of the client. With high probability, this will leave only one remaining candidate for the key. This is also due to the fact, that RSA is not semantic secure, i.e., having the property ciphertext indistinguishability. Switching to the Diffie-Hellman suite helps as long as the server does not use the same weak DRBG.

[1] https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-90a.pdf

Related Posts:

• Backdooring SSL encryption