Tag Info

Hot answers tagged

39

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


35

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


34

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


17

(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

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


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


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

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


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


8

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


8

I think you are referring to Colin Percival's Everything you need to know about Cryptography, in one hour in which he observes: An asymmetric authentication scheme is considered to be broken if an attacker with access to the verification key can generate any valid ciphertext, even if he can convince you to sign arbitrary other plaintexts. This is ...


8

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


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

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


7

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


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

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


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

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


3

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


3

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


2

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


2

In the asymmetric encryption context I think something can be done in this direction with a double trapdoor function. I studied few examples of them in the past and briefly you can build up an encryption scheme with a "local" trapdoor and a "global" one. If you keep the secret for the global trapdoor for you you'll have a sort of escrow key allowing you to ...


2

There are two ways I can see for the RNG to be cooked. (For the record, I don't see any reason at all to suspect this of Intel, but I also think prudent cryptographic design requires us to think through what would happen if our RNG were flawed or backdoored.) First, your RNG could not have enough entropy. That's what got the Netscape RNG many years ago, ...


2

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


2

You need to clearly distinguish between the DualEC DRBG algorithm and the elliptic curves over which it is defined. The backdoor in DualEC DRBG needs the attacker to choose P and Q such that they know the scalar $k$ for which $P=kQ$. Pretty much any algorithm which fixes both public keys at the same time without going through private keys is fine. For ...



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