18

"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?

  • 1
    For the way RdRand is currently used in Linux, see also this related question: crypto.stackexchange.com/questions/10283/… – 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 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 at 13:42
22

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.

  • 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
  • 1
    Interesting read: plus.google.com/117091380454742934025/posts/XeApV5DKwAj – I'll-Be-Back 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
  • 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 7 '14 at 3:18
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.

  • 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 6 '14 at 5: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 6 '14 at 13:10

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.