5
$\begingroup$

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.

|improve this question
$\endgroup$
  • $\begingroup$ Note that I'm not particularly worried at this time that the instruction is broken. Then again, it may be in future CPU's that implement the instruction, possibly even by other chip makers. $\endgroup$ – Maarten - reinstate Monica♦ Sep 17 '13 at 11:50
  • 1
    $\begingroup$ Like Ilmary said in bis answer: Simplest fail-safe would be to XOR it's output with a well-vetted, cryptographically secure RNG... ;) Looking at crypto.stackexchange.com/questions/9603/…, has anyone seen the building plans and specs of Intel's crypto-chip yet? $\endgroup$ – e-sushi Sep 17 '13 at 15:33
7
$\begingroup$

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

|improve this answer
$\endgroup$
  • $\begingroup$ OK, point taken, but I presume that if you apply a one way function to the hash, and if there are no other methods of knowing what the state of the RNG is (hard to proof, another app. may leak this data) then the only way would be to regenerate the random states and test. With the number of CPU's and the amount of possible states, would that not be a very tall order? $\endgroup$ – Maarten - reinstate Monica♦ Sep 17 '13 at 23:58
  • 2
    $\begingroup$ The point of the Becker et al. attack is that they reduce the state space of the RNG to (e.g.) 32 bits (plus a 224-bit constant known only to the attacker). Testing each of $2^{32}$ possible states is generally not much of a challenge to an attacker with even a single modern CPU. $\endgroup$ – Ilmari Karonen Sep 18 '13 at 10:07
  • $\begingroup$ Yipes. OK. So the only other thing to do is to mix in some entropy from a different source and use a CSPRNG. In that case the RDRAND instruction would not be so useful anymore, at least not for generating secure random numbers directly in applications. $\endgroup$ – Maarten - reinstate Monica♦ Sep 18 '13 at 14:20
1
$\begingroup$

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.

|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.