5 ms·
Suppose for the moment that the output of RdRand is known at all times to the NSA. In the relevant Linux code it is mixed in as follows: /* * If we
by jgrahamc 13y ago
Suppose for the moment that the output of RdRand is known at all times to the NSA. In the relevant Linux code it is mixed in as follows:
/*
* 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;
}
http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/drivers/char/random.c#n948 http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.g...
i.e. the output is XORed with the bits being returned. (Note that the output of RdRand is not added to the entropy pool itself; it's used to modify the value being returned via an XOR).
This seems reasonable given that the intent is to XOR together two random streams.
And if RdRand is known to NSA then NSA can do the XOR and get back to what would have been returned if RdRand wasn't there. Thus if NSA knows all about RdRand then the effect would be to downgrade the random number generator to the situation before RdRand was used at all. This doesn't seem to provide much vector for an attack on Linux's random number generation, it would just make RdRand useless.
Of course, if RdRand is the only thing you trust...
PS Linus' reply is disappointing, however, because it doesn't explain the situation.
- marvin 13y agoThanks for the excellent answer. As a non-cryptographer who can't read crypto code and also can't be bothered to download the Linux sources and find the part where random numbers are generated, this is a much better response than Linus'. "Read the source" isn't a suitable answer even for most technical people. For regular people, it is completely out of the question.
- tptacek 13y agoRespectfully, if you can't read the code, you're not really entitled to have opinions about it. Instead, try asking people you trust who can read code what they think.
- jgrahamc 13y agoAlthough, I should add that there's this API which uses the output of RdRand straight up: /* * Get a random word for internal kernel use only. Similar to urandom but * with the goal of minimal entropy pool depletion. As a result, the random * value is not cryptographically secure but for several uses the cost of * depleting entropy is too high */ static DEFINE_PER_CPU(__u32 [MD5_DIGEST_WORDS], get_random_int_hash); unsigned int get_random_int(void) { __u32 *hash; unsigned int ret; if (arch_get_random_int(&ret)) return ret; [...] There's one interesting use of this in the Linux kernel: the output is used for randomization of the address space. So, I suppose we could say that if NSA can predict RdRand then they can predict memory layout and which might enable some sorts of interesting attacks.
- tptacek 13y agoAs I understood it, TCP sequence numbers also got the direct output of rdrand. In neither case do I think that's meaningful; the needs of both are sub-cryptographic, due to environmental constraints (ie, no matter how high-quality the randomness you feed it, TCP seqnos and executable address space aren't going to be cryptographically random anyways.)
- simias 13y agoThe only use of randomized address space I know is to mitigate other attack vectors (stack smashing and other arbitrary code execution exploits). So it would just make exploiting an other vulnerability easier, it wouldn't be a vulnerability on its own. So it's still a bit far fetched conspiracy-wise as far as I'm concerned.
- zurn 13y agoI think it would be a justified move (in an evil kind of way). Most of the interesting exploits these days need to leverage more than one vulnerability. This kind of thing would give you a marked advantage in penetrating systems, and do so in a non-obvious way without exposing the targets to other attackers. The advantage would be something like 10x, or whatever the difficulty factor is that ASLR adds to the average exploit. It would also be a good match for probabilistic/big picture kind of approach that a big organization can afford to take. But will owning RdRand give you good enough control over ASLR, that's another question.
- unwind 13y agoNo need to download anything, the Linux kernel has a web interface to Git, of course. The relevant code is here: http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/drivers/char/random.c#n976 http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.g....
- ape4 13y agoInteresting comment... /* * This function will use the architecture-specific hardware random * number generator if it is available. The arch-specific hw RNG will * almost certainly be faster than what we can do in software, but it * is impossible to verify that it is implemented securely (as * opposed, to, say, the AES encryption of a sequence number using a * key known by the NSA). So it's useful if we need the speed, but * only if we're willing to trust the hardware manufacturer not to * have put in a back door. */ void get_random_bytes_arch(void *buf, int nbytes)
- btilly 13y agoOf course if RdRand is aware of how it is to be used and looks at the place it is supposed to be XORed with, then including it would hurt. But it would need to be actively aware of what is where in memory to do this.
- jgrahamc 13y agoYes, sure, that's a possibility. You could imagine a situation where a microcode update to the Intel processor is written to modify RdRand in the knowledge of specific Linux versions and it would alter the values being returned because it would be aware of where it is used. You might even imagine some cleverness that actually alters the surrounding program's execution. In a past life I did stuff like this where a device driver actually modified a running program to patch it to fix bugs/compatibility. It's not a complete fantasy to imagine that this might be possible. But, hey, it's software. Anything possible; with computers it's best to look for what's likely, not what's possible.
- btilly 13y agoBut, hey, it's software. Anything possible; with computers it's best to look for what's likely, not what's possible. When it comes to security, this is a horrible assumption. It is the nature of the game that an attacker should be expected to use whatever piece that they control in the most malicious way possible. Thus if it is possible, and they are motivated, then you should never assume that they wouldn't do that. Because push comes to shove, why wouldn't they? And if you're wrong, well, a little paranoia never hurt anyone. Particularly since in this case exercising paranoia is a simple matter of mixing in hardware randomness BEFORE doing all of the other complicating stuff, as opposed to the current order of doing all of the other complicating stuff AND THEN grabbing from potentially untrustworthy hardware that could be playing tricks.
- jgrahamc 13y agoThus if it is possible, and they are motivated, then you should never assume that they wouldn't do that. Because push comes to shove, why wouldn't they? That's sort of my point. "Push comes to shove" -> they'll do the easy thing first.