51

I wouldn't try to explain the mathematics of the backdoor. Just explain that the NSA hid a secret backdoor in there. Instead, I would suggest focusing on the history and the context. For instance, you could explain about Crypto.AG, how they spiked their RNG to help the NSA spy on their customers. You could explain how random number generators are a ...


23

Here is a list of products and companies who have had their EC DRBG algorithm validated by NIST. http://csrc.nist.gov/groups/STM/cavp/documents/drbg/drbgval.html The validation lists all modes that have been validated, so you can see which ones have gone to the effort of having their implementation of Dual_EC_DRBG validated. Tim Dierks points out that, for ...


22

RSA BSAFE Libraries (Both for Java and C/C++) use it as their default PRNG. Java: http://developer-content.emc.com/docs/rsashare/share_for_java/1.1/dev_guide/group__LEARNJSSE__RANDOM__ALGORITHM.html C/C++: https://community.emc.com/servlet/JiveServlet/previewBody/4950-102-2-17171/Share-C_1.1_rel_notes.pdf This obviously impacts users of the library such ...


19

Frankly, I'd be surprised if anyone did use it. Even before the potential backdoor was discovered back in 2007, the Dual_EC_DRBG was known to be much slower and slightly more biased than all the other random number generators in NIST SP 800-90. To quote Bruce Schneier: "If this story leaves you confused, join the club. I don't understand why the NSA ...


18

The Government's elliptic curve backdoor is real, isn't it? We don't know for sure, but there are indicators into that direction. More importantly though, yes, you can backdoor the RNG, as was pointed out shortly after its publication (PDF) yes, the parameters have been replaced in-the-wild by attackers to break VPN appliances using this RNG. Does this ...


11

As of 9 Sep. 2013, the NIST recommendation is that Dual_EC_DRBG SHOULD NOT be used. Quoting from the link: Recommending against the use of SP 800-90A Dual Elliptic Curve Deterministic Random Bit Generation: NIST strongly recommends that, pending the resolution of the security concerns and the re-issuance of SP 800-90A, the Dual_EC_DRBG, as specified in ...


10

The September 2013 supplemental ITL bulletin released by NIST has drawn attention to NIST publication SP 800-90A, Random Number Generation using Deterministic Random Number Generation; specifically the trustworthiness of the Dual Elliptic Curve Deterministic Random Bit Generator (Dual EC DRBG) algorithm. As a result, NIST strongly discourages the use of ...


8

For those who are wondering if Microsoft (being a big vendor) uses it… Windows does not use it. In fact, you must explicitly change from the default RNG which is AES-CTR RNG. Specifically: Debugging on Windows7 shows CryptGenRandom uses AES256-CTR with a 48 byte seed, which re-keys by XORing with its next 48 bytes output after each invocation to provide ...


6

Define the Mutual Information of a pair of random variables. $$I(X; Y) = H(X) - H(X\mid Y)$$ For discrete random variables we hae that $H(X\mid X) = 0$, so: $$I(X; X) = H(X)$$ The Data-Procesing Inequality states that for any function $f$, we have that: $$I(f(X); f(Y)) \leq I(X; Y)$$ While we won't need it here, this includes randomized functions, provided ...


6

Not quite, but you're close. I will write $[n]A$ for scalar multiplication of the point $A$ on the curve in question by the scalar $n$, as is more typical notation, and I will write $x(A)$ for the least nonnegative integer representative of the $x$ coordinate of $A$. Let $E/k$ be an elliptic curve over the field $k$, and $P$ and $Q$ be two $k$-rational ...


6

We, for the most part, don't bother with elliptic curve-based pseudorandom generators. DUAL_EC_DRBG was shoehorned into a NIST standard that also included a block cipher generator, CTR_DRBG, and two hash-based ones—Hash_DRBG and HMAC_DRBG—that are actually used in the field. Number-theoretic generators, which include Blum-Blum-Shub, DUAL_EC_DRBG, and ...


5

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-...


4

You can do something like what you are suggesting. But, the EC_Dual_DBRG also has biases in the stream and so you cannot use it without changes (e.g., truncating much more). However, this is based on the same operations as ElGamal. The public key is set up exactly as proposed. Then, to encrypt a message $m$ of any length, do: Choose a random $r\in\mathbb{Z}...


4

According to the BCryptGenRandom documentation The default random number provider implements an algorithm for generating random numbers that complies with the NIST SP800-90 standard, specifically the CTR_DRBG portion of that >standard. Specifically, according to this the default value is BCRYPT_RNG_ALGORITHM which is: The random-number generator ...


3

State update takes $s$ to $x(sP)$, so you would have to compute d.log.s to run the state backwards.


3

On the Practical Exploitability of Dual EC in TLS Implementations by Stephen Checkoway et al. (Usenix 2014) is some research that has been done on how much this NSA backdoor has affected the internet. In short: It's hard to say. What saved a lot of systems from being compriomised is the fact that Dual_EC_DRBG was poorly executed and recommended against early....


2

Well, I think OpenSSL has documented this pretty well: If an alternative RAND_METHOD implementation is being used (either set directly or as provided by an ENGINE module), then it is entirely responsible for the generation and management of a cryptographically secure PRNG stream. The mechanisms described below relate solely to the software PRNG ...


Only top voted, non community-wiki answers of a minimum length are eligible