Could RDRAND (Intel) compromise entropy?

Question

I was recently discussing the issue of RDRAND in Intel chips and the whole issue about how NSA could potentially be influencing Intel to weaken or create backdoors in their design.

This petition was posted asking Linus Torvalds to ignore RDRAND and not include it as a source of entropy in /dev/random/. You can see Linus' response here.

My main question is, would using RDRAND as one source of entropy (amongst many others) potentially compromise the 'randomness' of /dev/random by adding some predictability? Or is he correct in saying that It really does not make any difference as long as its not the only thing entropy is generated from?

Answer 1

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, but no harm either.

If, on the other hand, you write to /dev/random using a special ioctl (and that does require superuser privileges), you can actually increase the entropy estimate.

If you are able to do that (and if you are, you could as easily replace /dev/random with /dev/notsorandom and be done with it), /dev/random degenerates to the behavior of /dev/urandom: Usually, reads from random are supposed to block until at least as many bits of entropy have been written to the internal pool than are requrested, while urandom returns as much "randomness" as requested.)

If you manage to write predictable bits to the pool, but tell the kernel to credit them as unpredictable data, the next reader(s) of /dev/random will receive random numbers that only deterministically depend on the current internal state of the entropy pools, and not on "truly random" events like disk seek times and keyboard inputs.

However, unless you are able to perform that attack from the very installation of the operating system, you don't actually know that internal state! Predicting it from /dev/random outputs is at least as hard as reversing SHA-1 (and that's perceived to be very difficult). This is also why it can be reasoned that, for the exception of directly after a fresh OS install, urandom can be considered to be "random enough" for all purposes, cryptographic or not.

Now let's have a look at the actual implementation of RdRand in drivers/char/random.c:

The only place the possibly malicious RdRand instruction is ever used is in the output functions of the random devices. It is XORed with the "actual" output of the "classical" Linux RNG right before that output is returned to the caller.

Since information theory tells us that when we XOR a chosen string with an unknown string, we can't predict anything about how the resulting string will look after the transformation, there is nothing to be gained from subverting the RdRand instruction, at least the way it is currently used in Linux.

Update: Some suggest that a very clever CPU might interpret calls to RdRand as a trigger for a backdor that, for example, replaces the subsequent XOR with a MOV.

I'd say that's theoretically possible, but exponentially harder to implement than to just skew the output of RdRand directly, e.g. by returning the keystream of AES-CTR under a key known only to the adversary as "random numbers".

There would have to be checks for the specific code sequence used in the Kernel; if that ever changes (e.g. by surrounding the RdRand call with some dummy XOR operations), a microcode update to adapt the heuristic would have to be widely deployed or people would get suspicious very soon.

Treating the RdRand instruction (or an equivalent on a different architecture) as just another entropy input (without increasing the estimated entropy, to be safe), would probably make the RNG even harder to subvert.

Second update: The issue has been discussed on the kernel mailing list twice: Once in 2011, started by a patch submitted by an Intel engineer and followed by a lot of discussion about security, and once again in 2012, which eventually lead to a patch implementing the current approach. Even the concerns about triggering a backdoor that changes the behavior of some instructions (e.g. XOR or MOV) has been mentioned. As far as the XOR construction is concerned: The Linux folks claim that the XOR approach is supposedly more secure than hashing the RdRand output into the entropy pool, though some of us here are not really persuaded about that.

Answer 2

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 XOR, ADD, possibly other instructions to check if the value is observed. If not, change it as needed.

The cost of this solution would be around 30 extra transistors in a billion transistor chip.

If using the RDRAND output, it might be a good idea to move the output around a bit and do some computations so "it's wave function will collapse", and then using it

Answer 3

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

As a user-space application you should never use RDRAND directly, at least not without mixing it e.g. with a output from a stream cipher seeded from /dev/urandom or something like that.

Answer 4

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;
            if (!arch_get_random_long(&v))
                    break;
            hash.l[i] ^= v;
    }
    /* ... pass hash.l to userspace ... */

seems vulnerable to microcode-based tricks to suppress the XOR mixing, and instead substitute vulnerable data. We'd never know it's there, because microcode is closed-source and updated whenever Intel likes.

Update: see also http://www.metzdowd.com/pipermail/cryptography/2013-December/019065.html

Answer 5

A XOR B can be replicated in multiple instructions as ((NOT A) AND B) or (A and (NOT B)). This could be used to validate the result of XOR with some confidence that a targeted backdoor would be increasingly difficult to implement over multiple instructions.