Torvalds shoots down call to yank 'backdoored' Intel RdRand in Linux crypto

Back to the crib

"...conspiracy theorists are terrified that RdRand is compromised. "

Only days later and we're back to "terrified conspiracy theorists."

How we do love a comforting story (or insult) instead of facts, eh?

"...but it's claimed that mix is trivial (involving just an exclusive OR) and can be circumvented by g-men."

Erm, "claimed" by whom? That statement is just wrong/stupid in so many ways it beggars belief.

"Trivial"? Go and read drivers/char/random.c

"just an exclusive OR"... "just"? No idea what a stream cipher is then... or how THE ONLY UNBREAKABLE cipher - a one time pad - is used.

"can be circumvented by g-men." Really? Any chance of an elaboration/reference on that? No? Thought not.

As long as the suspect stream is *a* source of entropy, not *the* source of entropy, and is *thoroughly* mixed into the pool of other sources (as it is) then even if it's malignant it'll still can't damage the overall entropy of the system, even a tiny bit.

Simple thought illustration: I have a byte of well mixed random data derived from multiple entropy sources, I shall now inadvertently "just" XOR it against a patently malicious quasi-random stream from the NSA - eight 0s. What is my random byte now?

Torvalds needs a paranoia transplant

Torvalds is correct, in that if you have some random numbers in your entropy pool and XOR some new numbers into them (from the CPU), then you increase the entropy even if those new numbers have very little entropy themselves (i.e. are somewhat predictable). Even if the new numbers are completely predictable, you still do no harm.

However, I'd disagree with Torvalds that this therefore makes it all OK. That's because you still need to estimate how much entropy you've accumulated. To produce random bytes by hashing, you need an estimate of the entropy per byte in your entropy pool because this determines how many pool bytes you need to feed into a hash function to produce each of the random hashes you'll actually use.

If the CPU is believed to be supplying most of the entropy (because it's the fastest source) but in fact it's producing a predictable sequence, then you will have far less entropy in your pool than you thought. I can see that might be a genuine cause for concern because any secure key you then generate may have less entropy than you thought too (i.e. its bits may not be independent). Yes, exploiting this might require cracking a SHA hash, but that's the sort of advantage that it's plausible for the NSA to have.

So my approach would be to keep using RDrand but to downgrade its entropy estimate by a large factor to reflect its now much reduced trustworthiness.

drivers/char/andom.c

A few comments after throwing another glance at random.c in a recent version of kernel code - it's been a few years since the last time:

* Assume that rdrand is not reliable. Yes, one can run a battery of tests on its output. Note that the best-known battery of tests comes from NIST, and it's been alleged that NSA have influenced NIST. The argument is that rdrand is mixed with other sources of entropy, so it is OK.

* These other sources of entropy are: user input, disk seek times, and interrupt times. In servers there is no input to speak of (no keyboard or mouse attached). The randomness of disk seek times is due to the turbulence generated in the thin layer of air between the rapidly rotating magnetic disk an its enclosure. Once magnetic disks give way to SSDs this source will disappear. Interrupt times can be affected by external sources (a quick - too quick - glance at the code leads me to believe nothing in the implementation of add_interrupt_randomness() in drivers/char/random.c or in the only call to it from handle_irq_event_percpu() in kernel/irq/handle.c distinguishes between interrupts.), e.g., if my server does a lot of networking I expect most interrupts to come from network cards, and it is at least theoretically possible to send a lot of packets at regular intervals to the server to reduce the overall randomness of this component. This is why historically network cards were excluded from the entropy pool. This last potential problem is probably mitigated to a large extent by taking only the least significant bits into account.

* The total amount of entropy is limited (without rdrand). It would be exhausted rather quickly if random numbers were used to encrypt everything, to run Monte Carlo simulations, etc. It would also be rather slow. However, normally the random numbers are only used to generate the seed for a PRNG (much faster). Hopefully encryption software does not use PRNGs from standard libraries (they are not very random). However, even a good PRNG is by definition deterministic if you know/guess/recover the seed. The output is statistically indistinguishable from random, but random it is not. Once you've covered the seed space the sequence is known (it's not all there is to encryption, of course, but it is a significant part).

* Hopefully there is enough entropy for seeds even if rdrand is used. However, if rdrand is randomized and it is a major contributor to the entropy pool I would expect the overall randomness to be lower than without it. This by itself is not enough to demand that Linus gets rid of it, but it is a theoretical concern. See Ted T'so's blurb quoted in the article.

* I expect it should be considerably easier for NSA to break into most computers exploiting bugs in various programs than cracking somewhat weakened random sequences. I am sure they are ready to use all the attack vectors where needed.

Android

Does anyone know what the Android code does? I know it's weak enough to have compromised BitCoin, but I haven't looked at it myself.

drivers/char/andom.c (T.F.M.Reader)

What I learned of numerically intensive computing, is if your code needs random numbers, you go find a RNG that suites your needs. If your RNG needs a random seed in starting, you can call /dev/random once for that seed. But making a string from process id, the time, free space on partitions, and what not, and running that through something like MD5 for your seed is probably about as good. But you don't use /dev/random for general user programming. And look at the source for your RNG, to make sure it isn't using /dev/random in some way.

Linus is correct in both form and substance.

I too looked at the code.

Thought experiment:

Stream prior to tempering with RDRAND has been encrypted with a secure one time pad.

Use good RDRAND or bad RDRAND makes no difference in this case, you cannot inspect the plain text without the one time pad key.

Stream prior to tempering with RDRAND has been encrypted with a non-secure key.

Use good RDRAND, it is stronger. Use bad RDRAND and it is no stronger but it is no weaker either.

No matter how compromised RDRAND is, the worst it can do leave the stream as strong as it would be without RDRAND.

Practically speaking, you can expect RDRAND to add good entropy to most things for most purposes.

I do not trust the NSA and I think it would be foolish to *rely* upon RDRAND, but a cursory examination of the file below shows that the Linux Kernel gets the use of any entropy there and is unharmed by any compromise no matter how extreme:

http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/drivers/char/random.c

random numbers

I always pick '2'. Nobody expects that.

Linus is totally wrong

There was a famous example of... Netscape(?) did a mix of different random sources. They used a random number generator, added the current millisecond, how much space was left on the harddrive, etc to create a "truly" random number. But researchers succeeded in breaking it, because they knew what was the building blocks, they could infer things, such as "typical hard drive is this big", etc. So, the researchers succeeded in discarding lot of the search universe, so they could decipher everything. It was lot of work, but it was doable. To mix different sources does not make better randomness. The Linux kernel developers would have known this if they studied cryptography (which I have).

Donald Knuth has a very interesting story on this in his epitome "Art of computer programming". He was supposed to create a random number generator many years ago, so he mixed lot of different random sources, the best he could. And Donald Knuth is a smart mathematician, as we all know. After his attempt, he analyzed it and discovered a very short range. It quickly repeated itself. That learned Donald Knuth that he should never try to make a random generator (or cryptosystem), just because you can not break your crypto or random number generator, it does not mean it is safe. Donald Knuth concludes in his book: it is much better to use a single well researched random generator / cryptosystem than make one yourself. Much better. If you start to mix different sources, you might introduce bias which is breakable. It suffices if the adversary can discard some number in the huge search space to be able to break it.

So, NSA and the like, would be more concerned if Linus used a proven high quality random generator. As Snowden said: NSA can break cryptos by cheating. NSA has not broken the mathematics. The math is safe, so use a mathematically proven strong random generator instead of making your own. That is very bad. If you study basic cryptography.

The Linux kernel developers seem to have very high thoughts of themselves, without knowing the subject? Probably they would also claim that their own home brewn crypto system is safe, just because it is complex and themselves can not break it. That would also be catastrophic. They should actually study the subject, instead of having hybris. But, with such a leader....

Who can tell?

I have respect for Torvalds, but the NSA has literally hundreds/thousands of PhD mathematicians working on encryption/breaking encryption, so weighing Torvald's smarts against all that brainpower, computing power, and sheer money power, who can say for sure whether his random function/method is compromised or not?