19

"Linus Torvalds, in response to a petition on Change.org to remove RdRand from /dev/random, has lambasted the petitioner by called him ignorant for not understanding the code in Linux Kernel. Kyle Condon from UK raised a petition on Change.org to get Linus to remove RdRand from /dev/random in a bid 'to improve the overall security of the linux kernel.'

What is the problem with RdRand from /dev/random?

Luc
  • 31,973
  • 8
  • 71
  • 135
I'll-Be-Back
  • 361
  • 1
  • 3
  • 10
  • 1
    For the way RdRand is currently used in Linux, see also this related question: http://crypto.stackexchange.com/questions/10283/could-rdrand-intel-compromise-entropy/ – lxgr Sep 10 '13 at 16:06
  • I'm not sure I understand the implications correctly, but in my opinion, the "You're ignorant and stupid" statement seems to come from an utmost ignorant, stupid individual. At least if my understanding of the source code and the working of the xor operation is correct. What I see is "dadada cryptographic stuff, dadada" followed by "xor a 3-element array with RdRand". Xor is naturally a read-modify-write operation, so RdRand knows the to-be-xored values, and assuming it is "malicious", it could trivially, without anyone noticing, produce _any_ desired output, no matter what you do before. – Damon Feb 15 '19 at 13:27
  • To make that more concrete, once you do not trust your CPU, you are kinda lost anyway. _However_, designing a malicious CPU so it recognizes and modifies haphazard code, or designing a CPU which behaves generally maliciously without anyone noticing is very difficult, near impossible. Designing a single CPU instruction so the pipeline scheduler recognizes "three consecutive xors with this instruction" is easy. – Damon Feb 15 '19 at 13:42
  • @Polynomial could the `RNG deterministic mode` discovered in https://i.blackhat.com/asia-19/Thu-March-28/bh-asia-Goryachy-Ermolov-Intel-Visa-Through-the-Rabbit-Hole.pdf be related? – user2284570 Jul 25 '20 at 21:29
  • @Damon `without anyone noticing is difficult`. Not that much difficult if you activate the backdoor mode only for specific requested targets. – user2284570 Jul 25 '20 at 21:32

2 Answers2

23

It's a hardware implementation that hasn't been tested formally, and it's proprietary. The potential worry is that Intel could have backdoored the implementation at the NSA's demand.

The current way of mixing the rdrand output into the Linux kernel PRNG is that it's xor'ed into the pool, which mathematically means that there's no possible way for a weak output from the rdrand implementation to weaken the overall pool - it will either strengthen it or do nothing to the security.

However, the real risk is that the xor instruction is backdoored in a way that detects for the use of rdrand in a special scenario, then produces a different output when xor is called, causing only the purposefully weakened rdrand output to be placed into the pool.

Feasible? Yes. Plausible? Given recent revelations, maybe. If it is backdoored, is Linus complicit in it? Your guess is as good as mine.

Also, there's a great paper [PDF] on hiding hardware backdoors at transistor level in CPUs.

Edit, Feb 2019. User Luc commented below that things have changed since this answer was originally written:

As of Linux 4.19, the kernel trusts RDRAND to seed its CSPRNG fully, unless one passes the random.trust_cpu=0 flag on boot (or sets it compile time). This should not be an issue if this is not your first boot, but newly installed systems or newly created VMs might have a predictable startup seed file (or no seed file at all), so for those systems this is relevant to gather good entropy.

Polynomial
  • 132,208
  • 43
  • 298
  • 379
  • 11
    By the way, the cryptographically _good_ way to mix randomness sources together is not a XOR but hashing them together. Otherwise, a malicious randomness source with access to the machine RAM (that's what we are talking about here) could just grab the current pool contents and return exactly that, and the XOR would yield a very predictable sequence of zeros. In that sense, what the Linux kernel does is somewhat sloppy. – Thomas Pornin Sep 10 '13 at 15:34
  • 6
    It sounds like RdRand gets special treatment, it's xor-ed into the output, not mixed into the pool using a hash as the other entropy sources. Certainly a bit weird and possibly a bad idea. – CodesInChaos Sep 10 '13 at 15:39
  • Doesn't it work in 2 steps? 1st read a byte from the device, 2nd xor the byte. The device is rather passive, it cannot sneak into kernel code what will happen to the data read from it. – ott-- Sep 10 '13 at 16:05
  • 1
    Interesting read: https://plus.google.com/117091380454742934025/posts/XeApV5DKwAj – I'll-Be-Back Sep 10 '13 at 16:07
  • @ott-- Not necessarily. The CPU is a very complex state machine, so it can be designed to react to a particular pattern of instructions in an unexpected way. Would explain why Linus is so fervently rejecting modifications to it. – Polynomial Sep 10 '13 at 16:07
  • 1
    @CodesInChaos I agree, it is implemented in a weird way. Maybe they don't want to rule out a very specific weakness in the hash function used? But then /dev/random shouldn't be world-writable in the first place... – lxgr Sep 10 '13 at 16:14
  • 1
    Making `/dev/random` writable allows for manually inserting some "initial seed". Linux distributions do that: at boot time, they inject the contents of a file in `/var`, then immediately regenerate a new file for next boot. This allows a machine to have good randomness right from boot, even if it did not have enough hardware events yet (given that Linux's `/dev/urandom` never blocks, this mechanism is somewhat necessary). – Thomas Pornin Sep 10 '13 at 18:39
  • 1
    But.. can't we simply test RdRand with randomness tests? Or test /dev/random to see if it's doing something funky? Surely if there is any backdoor neither would pass the randomness tests. Also, if XOR would indeed be backdoored couldn't we notice this (RdRand output being equal as the pool)? – cen Sep 10 '13 at 22:10
  • @cen Maybe. You'd have to implement the RNG in the exact same way and verify the pool at runtime (difficult if the CPU is watching you!). However, it could be that there are countermeasures against this, or that it only poisons the pool in a very surreptitious way that the NSA can use in conjunction with other cryptographic attacks. – Polynomial Sep 11 '13 at 09:24
  • 2
    @cen, the problem is that a simple counter fed through a cryptographic hash function is statistically indistinguishable from a cryptographic random number generator, except to the person who knows what value the counter started with. – Mark Apr 07 '14 at 03:18
  • You should link to the wonderful PoC||GTFO article on backedoored `/dev/urandom` implementations. – forest Feb 15 '19 at 12:23
  • "The current way of mixing the rdrand output into the Linux kernel PRNG is that it's xor'ed into the pool" Is this still the case? If I read (I'm in a hurry so I might have missed something) [1] correctly in section 9.10.1.1 bullet point 1, it's no longer strictly true. [1] https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/Studies/LinuxRNG/LinuxRNG_EN.pdf – Luc Feb 15 '19 at 17:09
  • 2
    Looking at the document a little more carefully, it seems this answer is outdated. As of Linux 4.19, the kernel trusts RDRAND to seed its CSPRNG fully, unless one passes the `random.trust_cpu=0` flag on boot (or sets it compile time). This should not be an issue if this is not your first boot, but newly installed systems or newly created VMs might have a predictable startup seed file (or no seed file at all), so for those systems this is relevant to gather good entropy. I think this would be useful info to update the answer with. – Luc Feb 27 '19 at 14:20
  • @Polynomial could the `RNG deterministic mode` discovered in https://i.blackhat.com/asia-19/Thu-March-28/bh-asia-Goryachy-Ermolov-Intel-Visa-Through-the-Rabbit-Hole.pdf be related? – user2284570 Jul 25 '20 at 21:25
  • @Polynomial `The current way of mixing the rdrand output into the Linux kernel PRNG is that it's xor'ed into the pool, which mathematically means that there's no possible way for a weak output from the rdrand` but what if it s not about the output being weak but the instruction operating in full deterministic mode on demand as suggested by the recent Intel microcode hacks? – user2284570 Dec 18 '20 at 10:45
2

The RdRand instruction is broken on Ivy Bridge due to a hardware bug that has appeared on those processors. It is not implausible that there is a reason other than error for that. Cryptographic algorithms that have been seeded using deterministic pseudo-random algorithms probably are 100's of millions of times easier to break that those seeded with genuine random numbers. I actually have an engineering application that would benefit from that instruction but it causes an illegal instruction exception of my new Ivy Bridge laptop. Can I get my money back? You can see the Wikipedia entry on RdRand for initial information on the hardware bug.

SeanVN
  • 21
  • 1
  • RDRAND on affected processors can be fixed via a BIOS update. Check if your laptop/motherboard manufacturer has released one. A CSPRNG seeded with sufficient entropy is believed to be safe. The math is, as far as we know, solid. The question, of course, is whether RDRAND is backdoored to **not** use enough entropy, **not** use the CSPRNG it claims to, or if NSA has developed shocking new capabilities. We may never know for sure. ("100's of millions" is a very small number, BTW.) – Matt Nordhoff Apr 06 '14 at 05:59
  • I still want $50 back from Intel. I don't see updating the BIOS as feasible. Most PRNG's are only a few lines of code long. Most are published with fixed recommended constants. You can predict they will be seeded from the system clock or via the RDTSC instruction. My interest however is in evolutionary algorithms where I could have gotten very nice random numbers with no lurking correlation hidden in the data. If you could see in thousands of dimensions I am sure you would see striking patterns in the output of any PRNG known today. Statistics are poor eyes to see with.They are aggregates – SeanVN Apr 06 '14 at 13:10