This has been brewing since I read Linus’ response to the petition to
RDRAND from /dev/random.
For those of you who don’t know,
RDRAND is a CPU instruction
introduced by Intel on recent CPUs. It (supposedly) uses a hardware
entropy source, and runs it through AES in CBC-MAC mode, to produce
Out of fear that
RDRAND may somehow be backdoored, someone
petitioned to remove
RDRAND support to “improve the overall security
of the kernel”. If
RDRAND contains a back door, and an unknown
attacker can control the output, that could break pretty much all
Linus fulminated, as he is wont to do. He suggested we go read
drivers/char/random.c. I quote (expletives and insults omitted):
we use rdrand as one of many inputs into the random pool, and we use it as a way to improve that random pool. So even if rdrand were to be back-doored by the NSA, our use of rdrand actually improves the quality of the random numbers you get from /dev/random.
I went ahead and read
random.c. You can read it for yourself in
Disclaimer: I am not an expert in this piece of code. I have no doubt Linus is far more familiar with it than I am. I’d love to be proven wrong. I’m just taking his advice and reading some code.
The function I’m interested in is
1 2 3 4 5 6 7 8 9 10
This is in the extraction phase. This is after the hash is being mixed
back in to the pool (and that’s for backtracking attacks: not intended
as an input to the pool). It seems to me like the output of
arch_get_random_long is being XORed in with the extracted output,
not with the pool.
If I were to put on my tin-foil hat, I would suggest that the difficulty has now been moved from being able to subvert the pool as one of its entropy sources (which we think is impossible), versus being able to see what you’re about to be XORed with. The latter seems a lot closer to the realm of stuff a microcode instruction can do.
To put it into Python:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
Why can’t RDRAND work like this?
Some comments based on feedback I’ve gotten so far:
- This attack does not need to know where the PRNG state lives in memory. First of all, this isn’t an attack on the PRNG state, it’s on the PRNG output. Secondly, the instruction only needs to peek ahead at what is about to happen (specifically, what’s about to be XORed with) the RDRAND output. That doesn’t require knowing where the PRNG state (or its output) is being stored in memory; we’re already talking register level at that point.
- While it’s certainly true that if you can’t trust the CPU, you
can’t trust anything, that doesn’t really make this problem go away.
RDRANDbeing broken wouldn’t make software crash, which is a lot harder for almost all other instructions.
RDRANDbeing broken wouldn’t result in measurable side-effects, unlike what would happen if
PCLMULDQcontained a back door. Furthermore, it’s a lot easier to backdoor one single microcode instruction and a lot more plausible and feasible for a CSPRNG to be backdoored than it is to think of a CPU as some kind of intelligent being that’s actively malicious or being remotely controlled.
For what it’s worth, it seems Zooko agrees with me.