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?

NSA, Decryption and Backdoors

Edward Snowden, a former NSA employee, copied and now is releasing confidential material from internal operations of the NSA and its partners. I don't want do judge his decision to do so, but i want to discuss the information that the NSA can decrypt most of the current internet traffic.

The question that comes up is: How is the NSA able to do this? The cryptographic protocols in question are using hard and well known cryptographic assumptions, e.g., RSA, DH, ECDH etc..., or are based on official and world-wide reviewed scramble routines, e.g., AES. Does the NSA really know much more about cryptanalysis than the rest of the world, especially than its academic counterpart? And if they have secret full blown factoring and discrete logarithm algorithms, why should they pay companies for letting them get access to the user informations? Is it 250 million dollar of distraction money?