Tag Info

48

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

45

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

21

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

21

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

18

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

18

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

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

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

12

What choice did they have? F1 is a bitwise function with three inputs and one output. There are $2^8 = 256$ such functions. Only 70 of them are "unbiased" (i.e. have as many 0 and 1 outputs in their image). If you further require that each input, as well as the order of inputs, matters for the output, you are left with only 36. However, those 36 are all ...

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

10

The real question isn't "Why doesn't Suite B use P-521?" It is, "Why doesn't Suite B use AES-192?" NSA were only interested in 192-bit security for Suite B, but they chose to use AES-256 because AES-192 wasn't widely supported. "In fact we had wanted to use AES -128 and AES-192, but a quick survey of AES implementations (hardware centric, I believe) ...

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

9

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

9

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

8

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 $... 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 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 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 Since the rationale for the exclusion of P-521 and AES-192 is not explained, you can assume that either the curve is "too good" or that the cipher is "not good enough". The exclusion of SHA-512 implies a limit to 192-bit security for the standard, so AES-192 would be the logical choice. Its exclusion implies it is in someway not adequate for protecting TOP ... 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-... 5 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 ... 5 A length extension attack doesn't let you find a collision. It lets you predict the hash for an input with an unknown component in the prefix. If you have$h = H(x)$for unknown (or partially unknown)$x$, you can generate$h_y = H(x \vert\vert y)$for arbitrary$y$(this is not strictly correct; I've ignored padding, but for the purposes of this discussion ... 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 Assuming you manage to safely generate RSA keys which are sufficiently large, i.e. >= 2048 bits, no TLS configuration flaw on your side, and the lack of security bugs in the TLS library used by your server or the one used by the client user agent, I do not believe TLS_ECDH_RSA_WITH_AES_128_GCM can, at this point, be decrypted by surveillance agencies. Here'... 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; ... 3 In the introduction of the Logjam paper, it is stated that After a week-long precomputation for a specified 512-bit group, we can compute arbitrary discrete logs in that group in about a minute. So it seems that what it actually does is attack the discrete logarithm problem, so any discrete-logarithm-based system which uses a common prime should ... 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. ...

2

This answers a comment to Stephen Touset's fine answer. With SHA-256, or any collision-resistant hash, no known attack (including length extension) allows producing a file different from the original file and that has the same hash as the original, even if an adversary could choose the original. Even with the practically-broken MD5, or the broken SHA-1, no ...

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