Fast post-processing for broken RDRAND

Question

Let's assume that the Intel RDRAND instruction does not return fully random numbers, e.g. because it has been engineered with a backdoor for the NSA.

If the Intel RDRAND instruction is used directly by a software implementation, what post-processing could be performed to make sure that the output would be indistinguishable from random again? The procedure should not be CPU intensive as an application could as well use the OS provided random number generator if that was the case.

Presumption: the random numbers returned by RDRAND do at least comply with FIPS tests against the output for random numbers.

Answer 1

There is no such method. The only reliable way to "fix" a backdoored RNG is to mix its output with another, secure RNG.

Specifically, let's consider a backdoor similar to that described by Becker et al. (2013), which essentially transforms the Intel TRNG into a deterministic PRNG using AES in OFB mode, with a 32-bit initial seed (occasionally reseeded) and a fixed key chosen by the attacker.

Between reseedings, the output stream of the compromised RNG is completely determined by the initial seed, which can take only $2^{32}$ distinct values. Thus, an attacker who knows the hidden key can, after observing only slightly more than 32 bits of the output, look them up in a database to recover the seed (or just iterate through all possible seeds to find the correct one).

Alternatively, if the RNG output is used, say, to generate an public/private key pair, an attacker who knows the hidden key and the keypair generation method can easily generate all the possible keypairs and check which one of them matches a given public key.

The important point to realize is that no amount of deterministic post-processing can prevent these attacks — the attacker just needs to incorporate the same post-processing into their own output generation code. The only thing that can stop such an attack is the addition of some other source of randomness, not predictable by the attacker, to the output.

(Actually, if I read the Becker et al. paper right, the specific attack they describe can be thwarted even without any external source of randomness, simply by feeding the compromised RNG output into a sufficiently large (e.g. 128-bit) entropy pool. The reason this works is that their attack does still allow about 32 bits of true randomness to be output whenever the compromised RNG is reseeded, and mixing this into a non-compromised entropy pool will build up a considerable amount of randomness over time. That said, presumably their backdoor could be modified to leak even less actual randomness into the output.)

Answer 2

The Unix/Linux /dev/random source code has a concept of 'stirring' the entropy pool. If you stirred the RDRAND entropy an unknown, variable amount of times then an attacker isn't going to be able to reverse that easily. Better if you mix entropy from other sources as well into the entropy pool. Never rely on one source of entropy. Also after stirring the pool, run it through a randomness extractor before using anything from it.

Though if RDRAND/CPU has a secret trigger event, say it detects a key being generated, or TLS session being initiated, then it could start pumping out lots of zero's. That would be very hard to detect and even if you were mixing it into the entropy pool it would still suffer. You would need to verify all output from the Intel RNG directly before using but that might be difficult. There was a paper written on this not long ago, I'll see if I can find it.