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

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

As said, I don't believe everything written here, but I find it very interesting to discuss the possibility technically.

-
I just removed all comments because they were not related to the topic of the question, or about cryptography at all. Please constrain yourself to clarifications and similar comments about the question. –  Paŭlo Ebermann Jul 15 '13 at 18:33
This question appears to be off-topic because it is about Hardware backdooring of a system. Probably belongs elsewhere. –  minar Jul 18 '13 at 6:13
Steve Blank thinks it's feasible, in fact, it sounds like he'd be surprised if there weren't a back door: steveblank.com/2013/07/15/… –  Kinnard Hockenhull Jul 23 '13 at 3:00

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.

-
I think it wouldn't be that hard for hardware experts to reverse-engineer the RdRand algorithm so as to establish whether it is a legitimate TRNG or is doing something strange like generating some kind of keystream to introduce a backdoor (publishing their research, of course). Though again, as said in the question's link, entropy pool poisoning is rather difficult to exploit. –  Thomas Jul 14 '13 at 4:29
@Thomas I heard that Linux uses RdRand directly in some places instead of just mixing it into the pool. In that case you don't need to poison the entropy pool. –  CodesInChaos Jul 14 '13 at 8:53
Hmm I think I get it. I was thinking "how'd you make it seem random while knowing the output" and an encryption algorithm is the obvious answer. But then how do you know how far into the output stream the PRNG is? Well you don't really need to, deducing that is much faster (just reproduce the output stream and test everything) than cracking true randomness. Use the chip's serial + a static salt as first input, then make the PRNG's state persistent between reboots. That could probably totally work. Waiting for other answers, but I'll accept soon if none are added. Thanks for your answer! –  Luc Jul 14 '13 at 13:16
Can this be tested? Is there a way to know if this is true? Can some test suite be written which can be run on our machines to test if RdRand function is doing something nefarious? –  notthetup Jul 14 '13 at 15:06
@notthetup Yes and no. It might be possible that hardware experts are capable of opening the chip and study the circuit and deduce from that what RdRand does, but this is extremely hard to do due to the small scale (not to mention expensive). But if we assume Intel does have nefarious purposes with RdRand and built it around a cipher of which they know the key, then no we can't detect it from a test suite, if the used cipher is strong. A strong cipher is explicitly designed to be indistinguishable from random noise - in fact, it's considered to be broken if it is. –  nightcracker Jul 14 '13 at 16:51

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.

-
Useful information, thanks for your answer! And you mention a very legitimate question: What's in it for Intel besides becoming good mates with the NSA? Merely being good mates doesn't bring them much profit. Yet they could still say it's secure crypto, and it is as long as nobody knows the initial state. They might just get away with it in the corporate world. But I'm just guessing really. –  Luc Jul 14 '13 at 22:54
@Luc, can you say "government contracts"? Sure, I knew you could. –  John Deters Jul 15 '13 at 22:37

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.

-
This attack reminds me of the attack on the Netscape browser's PRNG back in the 1990s: cs.berkeley.edu/~daw/papers/ddj-netscape.html Today, people better understand the need for a secure PRNG, so it should be better tested. But all it would take is some espionage and skullduggery, and a weak algorithm could be dropped into the chip after testing. Unless a production chip is retested, it would go unnoticed. It's like the old joke: how do you really know when a random number generator is broken? –  John Deters Jul 15 '13 at 22:03
Also it's worth noting that a similar method has the added property that even the chip manufacture would not necessarily know they where introducing a back door. In their eyes they are just using a government approved algorithm, and would naturally assume it is secure. –  Joshua Kolden Jul 16 '13 at 2:10

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.

-
Just playing devils advocate: A cryptographically secure RNG being fed about no input (or the current timestamp + device serial number or such) would also pass the same tests, wouldn't it? –  Paŭlo Ebermann Sep 10 '13 at 19:19

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