# Tag Info

34

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

27

Edit: I have made some tests and I found something weird. See at the end. Initial answer: At least the Koblitz curves (K-163, K-233... in NIST terminology) cannot have been specially "cooked", since the whole process is quite transparent: Begin with a binary field $GF(2^m)$. For every m there is only one such field (you can have several ...

20

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

16

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

16

(That Tor mailing list link appears to be broken at the moment) Your question is at least partially answered in FIPS 186-3 itself… Appendix A describes how to start with a seed and use an iterative process involving SHA-1 until a valid elliptic curve is found. Appendix D contains the NIST recommended curves and includes the seed used to generate each one ...

16

The standard in question was the Dual Elliptic Curve Deterministic Random Bit Generator (Dual_EC_DRBG), standardized in NIST Special Publication 800-90. In this case, it was not a protocol, but instead a random number generator. It wasn't exactly "broken"; instead, it was proven that there existed a "master key", if you will, that would allow someone to ...

15

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

12

First of all, there is a difference between writing to /dev/random and/or /dev/urandom and increasing the entropy count maintained in the Kernel. This is the reasony why, by default, /dev/random is world-writable - any input will only augment, but never replace the internal state of the RNG; if you write completely predictable data, you're doing no good, ...

10

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

8

If the NSA knew a sufficiently large weak class of elliptic curves, it is possible for them to have chosen weak curves and have them standardized. As far as I can tell, there is no hint about any sufficiently large class of curves being weak. Regarding choosing the curves: It would have been better if NIST had used an "obvious" string as the seed, e.g. ...

7

I don't think that rigging the xor instruction and possibly others would be as hard as lxgr suggests. What I would do if I were the hardware designer: add an extra bit to the output register of RDRAND. This bit means something like "unobserved". Until the user "opens the box" there could be anything in the register. (Think Schrodinger's Cat :-)) update ...

7

There is no such method. The only reliable way to "fix" a backdoored RNG is to mix its output with another, secure RNG. Specifically, let's consider a backdoor similar to that described by Becker et al. (2013), which essentially transforms the Intel TRNG into a deterministic PRNG using AES in OFB mode, with a 32-bit initial seed (occasionally reseeded) and ...

7

Analyzable in this case means "simple to study". If your cipher consists of a small function that mixes a few things together, and then you repeat that often then your cipher is more easily understood and more easily fit into previous research knowledge than a overclomplicated large design. This is the case with Simon and Speck. Being easy to analyze is a ...

6

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

Bernstein and Lange says that there has been no progress for prime-field elliptic curves since about 1999, when the NIST curves were chosen. No large class of weak curves were known then, and no large class is known now. Some small classes are known, (as Neves says) the curves with small embedding degree and the anomalous curves (order $n$ equals the prime ...

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

4

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

4

Yes, it can: see http://people.umass.edu/gbecker/BeckerChes13.pdf for how to backdoor the bare metal without it being detectable by optical microscopes. On the other hand, adding Intel RDRAND output into a pool where it’s not the only entropy source is usually safe (always safe if it cannot dominate the output). That’s what is being discussed for Linux at ...

3

The way in which RDRAND's output is mixed into the /dev/random output buffers linux drivers/char/random.c, extract_buf() /* ... compute a hash.l[i] PRNG ... */ /* * If we have a architectural hardware random number * generator, mix that in, too. */ for (i = 0; i < LONGS(EXTRACT_SIZE); i++) { unsigned long v; ...

2

The Key schedule appendix of the RC6 paper (Rivest et al.) defines two arbitrary constants in hexadecimal notation. They also appear in RC5. $P_{32} = \tt{B7E15163}$ $Q_{32} = \tt{9E3779B9}$ Be aware that the binary coding of these constants will vary based on the endian-ness of the computer architecture. There seems to be nothing 'special' about these ...

2

Your summary of exhaustive search is essentially correct; the attacker just tries every possible key until he finds one that works. This works against almost any cryptosystem (exceptions: OTP, secret sharing, quantuum cryptography). It's not practical against any modern system (mostly because 'has a key too large to be brute forced' is an essential ...

2

We don't know what NSA (or any other spy agency--the US isn't the only country with code breakers) has broken. Other than Dual EC DRBG, we are left with everyone making their best guess, just like before. The NIST elliptic curves and the SHA2 hashes and DSA all came from NSA, but that seems to be the only real reason to suspect anything bad about them. ...

1

The Unix/Linux /dev/random source code has a concept of 'stirring' the entropy pool. If you stirred the RDRAND entropy an unknown, variable amount of times then an attacker isn't going to be able to reverse that easily. Better if you mix entropy from other sources as well into the entropy pool. Never rely on one source of entropy. Also after stirring the ...

1

A lot of companies use BSAFE: for a long time, BSAFE was the most successful supported cryptographic toolkits: it predates the success of open source software, it predates the availability of crypto APIs in operating systems, and it predates the expiration of patents on RSA and public-key cryptography in general. And it's always been a reliable, well-tested, ...

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