28
$\begingroup$

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?

| improve this question | |
$\endgroup$
  • 3
    $\begingroup$ If the PRNG doesn't suck, it doesn't cause any security issues to mix in attacker controlled input. $\endgroup$ – CodesInChaos Sep 10 '13 at 12:10
  • 5
    $\begingroup$ But I agree with Dale Emmon's comment that it should be mixed in through the hash and not xor-ed into the output. $\endgroup$ – CodesInChaos Sep 10 '13 at 12:11
  • 2
    $\begingroup$ If the CPU is completely compromised (in a way that RdRand would "know" the values it's being XORed against), why assume that only the RdRand instruction is malicious? Couldn't the CPU simply heuristically detect the get_random_bytes function and silently change the return value to be whatever it wants? $\endgroup$ – Stephen Touset Jan 6 '14 at 23:07
  • $\begingroup$ The really annoying thing is that we have a high-performing true random number source and Linux reads it in a way that it does not at all help with the entropy draining blocks. Granted, it should not be used but it is a shame that it is not also mixed in smaller doses with entropy accounting. After all when you run your os on intel you have to trust intel anyway. $\endgroup$ – eckes Apr 24 '17 at 18:21
  • $\begingroup$ I've always wondered why people don't trust Intel to implement RDRAND without a backdoor, but are perfectly happy to trust Intel otherwise. After all, if Intel were willing to compromise their chips, they could design the CPU to misexecute instructions (say, the ones found in the Linux PRNG) in a way that compromises security $\endgroup$ – poncho May 20 at 16:58
22
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ The point being raised by Dale Emmons here change.org/en-GB/petitions/… is that the hardware random bits are fetched after the other entropy has already been both collected and processed. This means that one might question the claim that the chosen string is really XORed with an unknown string. $\endgroup$ – Henrick Hellström Sep 10 '13 at 16:55
  • 1
    $\begingroup$ @MichaelAquilina It does not increase the entropy, just the "estimated entropy" of the entropy pool. So the estimated entropy becomes higher than the actual entropy. $\endgroup$ – Paŭlo Ebermann Sep 10 '13 at 18:02
  • 2
    $\begingroup$ One thing I do not get in the updated answer is: (in case of code change) "a microcode update to adapt the heuristic would have to be widely deployed or people would get suspicious very soon". If the compiled code for random.c changes and no longer triggers the XOR, the RNG output would go from rigged to good (until some hypothetical microcode update, it the XOR thing is in microcode; forever, otherwise), and I fail to see how anyone could notice, beside those trying to exploit the rigging. Note: RdRand (and XOR) rigging is very low in my prioritized list of threats I am vulnerable to. $\endgroup$ – fgrieu Sep 11 '13 at 6:54
  • 3
    $\begingroup$ Consider a (highly hypothetical) hardware/microcode backdoor with an heuristic to detect code similar to this. It modifies RdRand to output (X xor Rigged) when it guesses the running code wants (X xor RdRand); and otherwise makes RdRand output Rigged. Rigged is such that its seed is a 64-bit random chosen at physical power-up, and otherwise a deterministic CSPRNG. This is exploitable when the heuristic works, but requires $2^{32}$ power-up cycles to detect, even when the heuristic fails due to a code change. $\endgroup$ – fgrieu Sep 11 '13 at 18:36
  • 5
    $\begingroup$ As for the last paragraph, they more or less say that XOR is more secure because it is easier to implement (previous implementations had bugs). That's not an extremely strong argument in my opinion. $\endgroup$ – Maarten Bodewes♦ Sep 17 '13 at 10:34
9
$\begingroup$

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

| improve this answer | |
$\endgroup$
9
$\begingroup$

Yes, it can: see http://people.umass.edu/gbecker/BeckerChes13.pdf [archived] 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.

| improve this answer | |
$\endgroup$
4
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ (the update removes the XOR) $\endgroup$ – David 天宇 Wong Sep 2 '19 at 9:10
  • $\begingroup$ ... by replacing it with an assignment. That too seems vulnerable to the same sort of attack, just somewhat more noticeably so. $\endgroup$ – fche Sep 3 '19 at 12:07
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Only if you continue to have access to B, which you don't in this case? $\endgroup$ – Cryptographeur Apr 10 '14 at 16:58
  • 1
    $\begingroup$ “…validate the result of XOR with some confidence…” – based on what exactly? It's really not clear to me how you would practically “validate” randomness (without introducing additional security problems). Also, you have to assume a backdoor might be modified to adapt to such validation attempts, which would practically render your gained confidence void. Fact is, you’re not able to validate any backdoor hiding in a CPU by running some validation function on a system that actively depends on that CPU… it might simply influence the returned result of your validation function and your hosed. $\endgroup$ – e-sushi Apr 10 '14 at 20:03

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.