20

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

Improve this question
5
  • 1
    For the way RdRand is currently used in Linux, see also this related question: crypto.stackexchange.com/questions/10283/…
    – lxgr
    Commented Sep 10, 2013 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
    Commented Feb 15, 2019 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
    Commented Feb 15, 2019 at 13:42
  • @Polynomial could the RNG deterministic mode discovered in i.blackhat.com/asia-19/Thu-March-28/… be related?
    – user2284570
    Commented Jul 25, 2020 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
    Commented Jul 25, 2020 at 21:32

2 Answers 2

Reset to default
24

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.

Improve this answer
15
  • 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
    Commented Sep 10, 2013 at 15:34
  • 7
    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
    Commented Sep 10, 2013 at 15:39
  • 1
    Interesting read: plus.google.com/117091380454742934025/posts/XeApV5DKwAj
    – I'll-Be-Back
    Commented Sep 10, 2013 at 16:07
  • 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
    Commented Apr 7, 2014 at 3:18
  • 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
    Commented Feb 27, 2019 at 14:20
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.

Improve this answer
2
  • 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
    Commented Apr 6, 2014 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
    Commented Apr 6, 2014 at 13:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .