Technical feasibility of decrypting https by replacing the computer's PRNG

Question

Intel has an on-chip RdRand function which supposedly bypasses the normally used entropy pool for /dev/urandom and directly injects output. Now rumors are going on that Intel works together with the NSA... and knowing that PRNGs are important for cryptography is enough to get this news spreading.

I personally don't believe this is true, so this is entirely hypothetical: Let's assume that indeed RdRand does what news says it does and that it indeed outputs randomness into a place where applications and libraries would look for cryptographically secure randomness.

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?

2. If the chip's manufacturer can predict the output of the PRNG to some extent, how feasible is it that they can decrypt any https traffic between two systems using their chips? (Or anything else requiring randomness, https is only an example.)

My reason for asking: http://cryptome.org/2013/07/intel-bed-nsa.htm
As said, I don't believe everything written here, but I find it very interesting to discuss the possibility technically.

Answer 1

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

2 - If the chip's manufacturer can predict the output of the PRNG to some extent, how feasible is it that they can decrypt any https traffic between two systems using their chips? (Or anything else requiring randomness, https is only an example.)

If you can predict the PRNG you can basically predict the secrets used for key exchange, and from that deduce the shared secret. Then you can simply decrypt the communication.

Answer 2

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 define the algorithm's elliptic curve. These constants are listed in Appendix A of the NIST publication, but nowhere is it explained where they came from.

What Shumow and Ferguson showed is that these numbers have a relationship with a second, secret set of numbers that can act as a kind of skeleton key. If you know the secret numbers, you can predict the output of the random-number generator after collecting just 32 bytes of its output. To put that in real terms, you only need to monitor one TLS internet encryption connection in order to crack the security of that protocol. If you know the secret numbers, you can completely break any instantiation of Dual_EC_DRBG.

So the short answer is yes, it is possible to create a random number generating algorithm that has exploitable weaknesses, in particular weakness that only the creator of the algorithm may be able to exploit.

Answer 3

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:

• Independent tests will be performed on multiple processors that are set up in an identical manner, so each processor must produce different outputs.
• Any given processor must produce a different output stream on each power up.

A simple scheme would be to use the processor serial number as an input to the PRNG to ensure different processors had different outputs, and have an undisclosed non-volatile register (e.g. a power-on counter) to ensure each boot was different.

A scheme such as this would probably resist any attempts at analysis using only its outputs: a standard cryptographic PRNG with a global secret (common across all processors), processor ID and power on counter as inputs. At this point, a large scale surveillance infrastructure on observing a new user would only have a space of a few millions of possible processor IDs, plus a few hundreds or thousands of possible boot counts. This could all be easily precomputed too, so would be very practical to hook into a surveillance infrastructure with today's computing power. (Once a user's processor ID and boot count have been identified once, it is of course much easier to keep track of this than have to do a full search each time).

However, the odds are that Intel aren't betting their international sales solely on another fab not having the inclination to open up their chip and check this (e.g. ARM would have a strong incentive to identify such foul play). Update: but they could be compelled by the government to put such a back door in whether it is in their commercial interests or not. Update 2: They, or their fab, could also use stealthy dopant-level modifications to make it extremely hard to detect the modifications, even by someone with Intel-like capabilities (see the first case study, Chapter 3 in the referenced paper).

I'm not an expert in microprocessor hardware, so can't comment on techniques that might introduce biases or other predictable features without being detected. One possible backdoor might be to severely constrain the next requested output from RdRand only after performing a computation such as would be needed to verify the authenticity of a certificate signed by one of a set of long-lived root CAs (perhaps China's CNNIC would be a useful candidate?).

2 - If the chip's manufacturer can predict the output of the PRNG to some extent, how feasible is it that they can decrypt any https traffic between two systems using their chips? (Or anything else requiring randomness, https is only an example.)

Being able to predict that the output of RdRand is within a searchable subset of possible outputs doesn't alone mean an attacker could break the system - it depends how that output is used. For example if the consuming application uses it as just another optional input to its entropy pool, then being able to predict that input means the user is no better than without RdRand, but equally is not worse off.

CodesInChaos points out that Linux has used RdRand directly at times; Intel are also encouraging direct use of the instruction. So it is not unreasonable to imagine a browser or other TLS client that uses output from RdRand as its sole source of entropy. If this is the case then an observer who can predict the output from RdRand can indeed compromise your security.

Most cryptosystems fail if the entropy input can be predicted, including SSL/TLS.

To pick a couple of examples in use by popular websites from the many possible TLS key exchange options:

1. My TLS connection to gmail currently uses Ephemeral Elliptic Curve Diffie-Hellman (ECDHE; I believe this is Google's default these days if your browser supports it). If an observer can enumerate the possible random numbers used by my browser, then the observer knows my secret key $d$, so can compute the shared secret $x_k$ by calculating $x_k = dQ$, where Q is the Google server's ephemeral public key (and vice versa if the observer can predict Google's secret key). $x_k$ is used as the premaster secret - the secret from which all other secrets are derived, so obtaining it breaks all of the assurances that TLS aims to provide.

2. Your TLS connection to Wikipedia uses an RSA based key exchange, as that's all they support (e.g. mine is currently TLS_RSA_WITH_RC4_128_SHA). With these ciphersuites, the premaster secret is generated by the client using its random number generator, and sent to the server. Being able to predict the random number directly gives an attacker the secrets they need.

Answer 4

I am the designer of the random number generator that is behind the Intel RdRand instruction.

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?

It isn't. We cannot. It passes the tests because it is a cryptographically secure random number generator being fed by a 2.5Gbps TRNG source.

1. If the chip's manufacturer can predict the output of the PRNG to some extent, how feasible is it that they can decrypt any https traffic between two systems using their chips? (Or anything else requiring randomness, https is only an example.)

The manufacturer would not intercept traffic at this point. The plaintext is present on the system. The attacker would attack the place in the system that the plaintext resides. E.G. in the network stack where the encryption/decryption of the link cipher takes place, or in the key establishment code. This is more the realm of traditional software vulnerability attacks. There's no need to pull off the very difficult task of injecting known non-random numbers into an RNG and trying to make sure it gets used on the right cycle by the right instruction in the right bit of the software such that you can reverse engineer the key.

Answer 5

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, and also what is apparently behind all those RSA keys with shared prime factors that Lenstra et al and Henninger et al found a couple years ago. And it's what got the Taiwanese smart cards that have been in the news more recently. If you don't get enough entropy, then you will not get any security. You can imagine the Intel RNG having some kind of flaw or intentional weakness where it never gets more than, say, 40 bits of entropy, and then generates outputs using CTR-DRBG with AES (from SP 900-90).

Second, your RNG could have an actual trapdoor or an unintentional weakness. That's what's alleged to have with the Dual EC DRBG in SP 800-90. If an attacker knows the relationship between P and Q, and sees one full DRBG output, he can recover the future state of the DRBG and predict every future output. You can imagine something like this--the Intel RNG uses CTR-DRBG, but if it wired all but 40 bits of the key to some known values, then the outputs would pass statistical tests, but would be weak to an attacker who knew those bits.

In either case, if you used the RNG outputs directly, you would be vulnerable. In the first case, anything you do with the RNG outputs that doesn't add in some other entropy will be vulnerable, since the attacker can just guess the entropy and then generate everything himself. In the second case, you'd need to give the attacker a little output to run his attack on, but (depending on details of the backdoor) a couple IVs for the encryption algorithm might be enough to leak the secret.

The best way to avoid both of these potential attacks is to combine the Intel RNG outputs with OS-collected entropy. There are several ways to do this, but I think the best one is something you can find in SP 800-90--you can seed an RNG, and then keep generating outputs with prediction resistance.

a. Use /dev/random to get at least 128 bits of entropy, concatenate that with a few outputs from RDRAND, and use the result to seed a software instance of CTR-DRBG using AES.

b. Each time you get a request to generate some bits of output, you do the following:

(i) Get an output from RDRAND.

(ii) Reseed the CTR-DRBG instance using that output as the new seed material. (The previous state's entropy is preserved by reseeding, so this can't weaken what you already had.)

(iii)Generate your outputs.

If /dev/random gives you 128 bits of entropy and CTR-DRBG is secure, then you could let your attacker choose every value you get from RDRAND, and he couldn't make your random numbers any less secure.

If RDRAND is good, then the attacker could choose the bits you get from /dev/random and your random numbers would still be secure.

Alternatively, you could simply XOR RDRAND outputs with /dev/urandom outputs. It's easy to see that this can't be any weaker than the stronger of the two, as long as neither one is able to predict the other's values. That's discussed in the draft SP 800-90C.

Disclaimer: I'm one of the authors of the 800-90 standards, and the designer of CTR-DRBG.