Showing posts with label Random Number Generator. Show all posts
Showing posts with label Random Number Generator. Show all posts

Friday, September 20, 2013

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 on that curve that are used during the generation of randomness. But it is not stated how these two points are generated. 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 compute 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?