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

36

1 - How feasible is it that the chip's manufacturer can predict the output of this PRNG when it passed tests from the people applying the use of this RdRand instruction in kernels? A strong stream cipher's output is random and unpredictable to anyone not knowing the key. See where this is heading? Just because something looks random doesn't mean it's ...

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

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

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

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

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

14

I'd say that the whole argument hinges around a "secret attack" that possibly the NSA may know of, enabling them to break some instances of elliptic curves that the rest of the World considers as safe, because the secret attack is, well, secret. This yields to the only possible answer to your question: since secret attacks are secret, they are not known to ...

13

Have you heard of the strange story of Dual_EC_DRBG? A random number generator suggested and endorsed by the government that exhibits some very suspicious properties. http://www.schneier.com/blog/archives/2007/11/the_strange_sto.html From that article: This is how it works: There are a bunch of constants -- fixed numbers -- in the standard used to ...

13

Actually, if the RSA key generation is malicious, there are even more subtle ways that can someone can leak the key. The cleverest way I've seen works like this (assuming that we're generating an RSA-1024 key; for RSA-2048, we just use a larger curve): The attacker generates an EC public/private key pair; using a 192 bit curve for RSA-1024 is good. He ...

11

1 - How feasible is it that the chip's manufacturer can predict the output of this PRNG when it passed tests from the people applying the use of this RdRand instruction in kernels? As nightcracker correctly stated, any strong cryptographic PRNG will produce a stream of numbers that pass statistical tests. However, the manufacturer has some constraints: ...

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

can we say that it is fully conforming to the specification, and must have been implemented correctly? No. Is it possible to backdoor a cipher (or hash function, I suppose) in such a way that it still appears to be correct and is compatible with different implementations of the same cipher? Certainly. Say I have an function AES(k,m)=c where ...

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

9

I am the designer of the random number generator that is behind the Intel RdRand instruction. How feasible is it that the chip's manufacturer can predict the output of this PRNG when it passed tests from the people applying the use of this RdRand instruction in kernels? It isn't. We cannot. It passes the tests because it is a cryptographically ...

9

Mathematically, it can probably be done. There has been research into trapdoor block ciphers. See, e.g., A family of trapdoor ciphers by Rijmen and Preneel, and follow-up papers. In practice, though, the problem statement is not realistic. The assumptions are just not realistic. Today, there's no reason why Red would be limited to using Blue's ciphers. ...

9

Schneier's "A Self-study Course in Block-Cipher Cryptanalysis" is an excellent resource for what you are looking for. In particular, FEAL-4 would be a promising cipher to look at as it is breakable by almost every cryptanalysis technique. One thing you will notice when going through Schneier's course (or when looking at cryptanalysis research in general) is ...

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 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 The design of DES might give some insight into the problem. The NSA altered the S-box of DES. Many people thought they planted a backdoor. It wasn't until later that differential cryptanalysis was independently discovered by Biham and Shamir that people realized that the NSA actually made DES stronger. So the lesson to learn from this is: clearly the NSA ... 6 This has been basically asked already: Should we trust the NIST recommended ECC parameters? History Once it was found that NSA allegedly had inserted backdoor to a cryptographic standard, people started thinking what standard it was. The most common guess is that the Dual EC DRBG is the backdoored standard. However, some amount of (possibly justified) ... 6 Here is a "backdoored" hash function: Let$p = 2q + 1$be a big prime of length$2048$bits, such that$q$is also prime. Let$a$be an integer of order$q$modulo$p$, i.e.$a \neq 1$but$a^q = 1 \pmod p$; it can be shown that$a = 4$is always a valid solution. Let$s$be a (secret) integer between$1$and$q-1$, and let$b = a^s \pmod p$. Then define ... 6 The field of cryptography that you are looking for is called Kleptography. In kleptography, we are dealing with a setting where the device performing your cryptographic tasks is potentially malicious. Now this device tries to leak information to some attacker that allows this attacker to break the used cryptographic scheme. If I am not mistaken that scheme ... 5 You've asked two different questions here: Q1: how to put a trapdoor in a block cipher, and Q2: examples of block ciphers that are good for learning block cipher cryptanalysis. @mikeazo has answered question Q2 well. I'm going to answer question Q1. For an example of how to put a hidden backdoor (trapdoor) in a block cipher, see the following research ... 5 I think the thing you are looking for is "escrow" as in http://en.wikipedia.org/wiki/Key_escrow. Be aware though that the security of your system is reduced to the hardness for an attacker to find the master password which might be much easier than breaking the disk encryption scheme 4 This manuscript by Warren Smith claims to outline an approach to having a (otherwise very good) block cipher with a trapdoor. The idea is something like the following: Linear cryptanalysis has you make linear approximations of the S-boxes and then solve a noisy system of equations by getting lots of samples (known plaintext pairs). But this linear system of ... 3 State update takes$s$to$x(sP)\$, so you would have to compute d.log.s to run the state backwards.

3

The answer is "no", in two ways. First, the implementation of the algorithm could make use of side channels to leak data. The SSL timing attack permits an attacker who can execute multiple encryptions to "tease out" timing information that reveals bits of the key material. The original attack was based on the widely used OpenSSL implementation. ...

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