Linus on /dev/random: "We actually know what we are doing. You don't." (opens in new tab)

Yep.

The main concern about random number generation is that if you use the output of RdRand exclusively, it's fairly easy to backdoor in such a way that it looks completely random to all outside observers, but the NSA has a key that could allow them to predict the output based on past output. However, mixing it with the state of an already good random number generator (which the kernel needs to have anyhow for platforms without an RdRand instruction) pretty much negates that attack.

No one (reasonable) is actually particularly concerned that Intel themselves has backdoored RdRand. But they do want to ensure that they are protected in the case that at some point in the future, some other architecture adds a random number generation instruction and that is backdoored. And since you need to continue to do software random number generation anyhow, the best way to use RdRand is to use both, mix them, and get the best of both worlds (fast entropy available in environments with limited entropy sources, and an auditable software random number generator).

All of the other attacks that people are suggesting require a whole hell of a lot more silicon, require changing the behavior of unrelated instructions, and so on. They're just too complex and too fragile to be feasible.

Instead, why don't we spend our time naming and shaming the companies that actually do use backdoored random number generation, like RSA security:

> Apparently, RSA Security BSAFE Share for Java 1.1 has DUAL_EC_DRBG as a default:

> "The default Pseudo Random Number Generator (PRNG) is the Dual EC-DRBG using a P256 curve with prediction resistance off."

> I didn't find an obvious link for the equivalent C/C++ library documentation, but the RSA BSAFE CNG Cryptographic Primitives Library 1.0 FIPS 140-1 Security Policy document from RSA Security at the NIST site says (p.14):

> "The Module provides a default RNG, which is the Dual EC DRBG, using a P256 curve and SHA-256."

> Additionally, the RSA BSAFE Crypto-C Micro-Edition 3.0.0.2 FIPS 140-1 Security Policy says (p.17):

> "For R_FIPS140_MODE_FIPS140_ECC and R_FIPS140_MODE_FIPS140_SSL_ECC, Crypto-C ME implements a Dual ECDRBG (Cert. #137) internally"

> I'd be more than a bit wary of any product using RSA Security libraries.

From: https://lwn.net/Articles/566329/

For a while, people were confused about why the NSA would have gotten the Dual EC DRBG random number generator introduced into a standard, as it's so much slower than most of the other available random number generators, and it was only a year after the standard was released that the potential backdoor was pointed out. Well, apparently RSA has decided that it's the best RNG available, perhaps with some influence from the NSA.

This is true. I think it is unlikely that rdrand is this deeply backdoored. However, I do think for something this critical the comments should match the code better and working on fixing the problems identified in the article is probably prudent.

It is worth noting that police used to be able to exploit firewire DMA to bypass disk encryption and copy encryption keys out of memory from any system with a firewire port. This has been fixed and a CPU-level exploit for crypto seems unlikely to me because making something that not only worked consistently but didn't slow down general purpose programming when it worked, would be an engineering marvel.

This being said, having clear, unimpeachable code in these areas is a good start because it helps ensure that other problems are not lurking under the surface.

> We allow the wild web to have access to our closed source GPU driver blobs but we elaborate tinfoil hat theories about rdrand. This is insane.

This isn't cryptography, it's politics. The 'taint' is ideological.

> why would you choose to trust all instructions but rdrand

Presumably, there are limits to the amount of silicon that Intel/NSA can devote to backdooring everyone. Since other instructions are supposed to behave deterministically, it could be expensive to backdoor them in a way that would not easily be discovered.

On the other hand, RDRAND could be a straightforward Dual_EC_DRBG implementation, which would be a very cheap and effective backdoor that would also have the nice benefit of keeping people's communications secure against everyone except the NSA.

Of course, there's also the possibility that there's no backdoor, but that the implementation is still buggy.

There's no reason why our trust in the hardware has to be all or nothing.

Did you actually look at how the Linux kernel is mixing RDRAND output with other randomness, or read the comments by the author of the original change.org petition? Because of the way Linux mixes RDRAND output with other entropy using XOR, a malicious RDRAND implementation can easily make the output of /dev/random totally determinisitc whilst being completely indistinguishable from a correctly-functioning implementation except to the attacker.

All it has to do is detect the code sequence in question and XOR the output of RDRAND with the randomness from the other entropy sources before returning it. The two XORs cancel out, and this is completely undetectable because there's no way to distinguish between a true random bitstream, a good PRNG, and a good PRNG XORed with data you provided based on the bits themselves.

get_random_bytes() documentation:

    This function is the exported kernel interface.  It returns some
    number of good random numbers, suitable for key generation, seeding
    TCP sequence numbers, etc.

Here is the accepted commit that makes get_random_bytes() use RDRAND directly:

http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.g...

Note that this was version 3 of that patch. Versions 1 and 2 also took control of /dev/urandom. Here is v2:

http://thread.gmane.org/gmane.linux.kernel/1173350/focus=117...

A year later, Ted Ts'o made get_random_bytes() go through the usual entropy pool and added get_random_bytes_arch() for a consumer that doesn't want to go through the entropy pool. (The core kernel does not currently use get_random_bytes_arch() anywhere.)

http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.g...

Note that the heated discussion came before v3 of Anvin's patch, and thus /dev/urandom was included. Matt's objections were perhaps not expressed very clearly, but Linus was pretty cavalier in overruling Matt Mackall (the /dev/random maintainer at that time) and I think his retort to George Spelvin's very rational objection was unreasonable:

http://thread.gmane.org/gmane.linux.kernel/1173350/focus=117...

I find it scary that these commits made it as far as they did. Note also that on the day of the leaks (ironic timing), Ts'o had to shoot down a RedHat engineer proposing to once again make get_random_bytes() bypass the kernel entropy pool.

https://lkml.org/lkml/2013/9/5/212

As for other locations, the point is to be undetectable while deployed at massive scale. Keyloggers and active backdoors are much higher risk. Great for a targeted investigation, but terrible for untargeted passive surveillance.

https://plus.google.com/u/0/117091380454742934025/posts/XeAp...

Agreed. This article is very one-sided, and after posting a calmly worded comment regarding Linus's standpoint[1] on his attitude, it was deleted. The article is simply link bait and is not professional journalism.

That being said, I have more confidence in Linus's knowledge regarding /dev/random. Mostly because XOR in this context is secure:

1. XOR is an incredibly powerful encryption algorithm (not primitive); one of the best we have. The problem with XOR is that you MUST use a UNIQUE one time pad (that is the length of the data) for every message AND you need to be able to securely transmit that one time pad. AES CTR is effectively using AES to create a one time pad for XOR encryption, as an example.

2. The prior steps are effectively creating a irrecoverable OTP meaning that any malicious intent in RRAND is effectively encrypted away.

[1]: http://marc.info/?l=linux-kernel&m=137391223711946&w=2

Mucking with RDRAND can easily be done in such a way that it's provably impossible to detect any differences in behaviour. It's much harder to guarantee that if you start mucking with buffers in memory, since there are so many clever ways a developer could check their work and catch you out.

You think 500MB/s [1] is slow? Or are you concerned with the latency of each call?

Also I don't understand why you rant against PRNGs. Do you know that this stretching of actual random data makes RDRAND considerable faster than using actual randomness?

[1]Source: http://stackoverflow.com/questions/10484164/what-is-the-late...

Bruce Schneier

I have all the respect for the guy, really, but then I read his guardian article "how to keep your data safe and secure" and mentions keeping "air gap" between computers with sensitive data but then he himself admits after all his methods and safeguards for the leaks he is working with, he uses Windows and usb-sticks to transfer (encrypted) files between them.

He uses Windows.

He uses Windows.

And he was claiming in the article that free and open source are better for security. Oh really, so your encrypted files on your usb-sticks for sure cant spread malware through your airgap through a file-system exploit? For sure it has never been done before that a file system could be used to take over an OSs internals, oh never.

The problem with this argument is that it would also apply to any low quality random source, and linux (and other OSes) all use sources of dubious quality. The reason to use them is that when we mix, they only improve matters.

Ah but that is not quite as easy as you might think. Maybe RDRAND is actually a keyed PRNG, so it is computationally hard to distinguish from "true" randomness. Maybe there are only 1000000000 possible keys, so while you could theoretically detect the back door, it is impractical/unlikely for anyone with less than NSA resources to do so. Conveniently, the NSA has the resources to exploit such a bias.

To further throw you off, it could be the case that the back door is only exploitable after, say, 1kB of output, and it is "truly random" prior to that. That would be plenty useful for the NSA's purposes. It might even be that the back door is only exploitable for some part of the output, maybe the part where you are most likely to find a suitable prime number during some key generation process. Intel periodically releases new products, so the NSA would have plenty of chances to update the backdoor as software changes.

One counter argument I can think of:

The rougue RDRAND would become active only in a CPU which the back-door has been exploited. It wouldn't be active off-the-shelf.

How would you distinguish actual randomness from the output of a CSPRNG with a known or weak seed? Patterns won't be apparent in either output.

I would agree with you if the Linux RNG was build according to common cryptographic wisdom. But as far as I can tell by reading the article the random sources are compressed in a common randomness pool using CRC. If RDRAND was added to this pool it might reduce the randomness of this pool. If these sources were added by a cryptographically secure mixing primitive this would not be possible. A faster alternative would be to maintain one pool for every randomness source that is added to via CRC and then only mix all pools together with a cryptographically secure primitive when randomness is requested.

I assume your post was intended to be ironic?

> "Write an operating system that is used by millions of people and powers a large part of the Internet (together with BSD and friends)."

Linux wrote a kernel, not the full OS user land. What's more, most of the code in Linux (the kernel) isn't actually written by him - these days he's job is more that of a maintainer. Not that I'm trying to undermine his achievements - just pointing out that you're making the same exaggerated arguments as the blogger you're condemning.

> " Stop writing bullet lists about people."

You mean like the bullet list you've just written?

> "Stop trying to attract hits to your tech blog and create something of use to the human species."

Again, like you've just done. Let me explain with a little code:

    ($potkettleblack = $_) =~ s/tech blog/forums/;

> "Criticize what people say, not how they say it."

Which would be fine if the whole premise of your argument is complaining about not what the blog said by how the blogger said it.

Don't get me wrong, I have a lot of respect for Torvalds, but your comments were -at best- hypocritical. Though I'd say they were much worse than that as at least the blog in question added some content to compliment their clickbait headline. You've not even touched on the real subject matter of this topic.

Regardless of how the author has presented his arguments, why don't _we_ focus on the actual arguments? This is getting rather too meta.

Also, what's the use of an open-source OS that is used by millions if it is shrouded in esoteric arguments? I would certainly like Linux developers to better express themselves even if _I_ can't build such a system myself.

>The author of the article is just another "tech blogger"

So ridiculing him instead attacking his arguments is A-OK but he has to keep silent because Thorwalds is a great coder?

He has the same right as you, as me, and as Linus Torvalds to criticize something. There are better programmers than Torvalds out there that are not as successful as he is, and the other way around.

Excellent trolling. Now lets everyone ignore this post.

The author makes an argument that is somehow both adhom and slippery slope. By pointing out something that everyone knows (Torvalds is rude, which not necessarily a bad thing depending on who you ask) he adds weight to his second argument about /dev/random being insecure (which is complete bollocks). I christen this logical fallacy the "Ducklinism".

And I have to agree with you about his obvious lack of expertise in the department. Where he fails to make a compelling article is not his lack of expertise, rather the lack of interviewing many people who do have that expertise.

> * Stop writing bullet lists about people.