How secure is Linux's random number generator?
lists.randombit.net
lists.randombit.net
It used to be that most drivers contributed to the randomness pool, so it seldom ran short. It used to be that you could configure the size of the pool, so if you were running short you could make it larger. But then it was discovered that the pool resizing had a locally exploitable vulnerability so it was removed, leaving it always at the smallest value; and it was realized that many driver sources weren't very random and/or were externally controllable so most were removed.
The end effect is that much server hardware only gets about 50-100 bits per second added only to a pool of 4096, and /dev/random is constantly running out leading to weird performance problems (like ssh connections taking a long time). This results in a desperate need to replace /dev/random with something like RdRand when it could just otherwise be another untrusted contributor if the rest of the system around /dev/random were sane.
If you don't use RdRand then you have few sources of "true" randomness, hence, your RNG is predictable, manipulable and you're an idiot and a 5 year old can break your crypto
If you use RdRand then "blah blah blah this is opaque", hence, your RNG is predictable, manipulable and you're an idiot and a 5 year old can break your crypto
Perfect solutions exist only in labs and my impression is that most of these "experts" make things less secure.
No one is concerned about RdRand as a contributing source— with other genuine source of randomness RdRand isn't likely a back door once mixed in.
As in your example, the only source of entropy a network printer has: network data, easy to manipulate or even no activity. So no way to generate keys for example.
In some cases hardware sources are a must. Yes, in the end you'll need to trust them
Still, I think a common pattern is (1) notice funny symptom, (2) go look at code, puzzle through it for a while, and then "oh!" You're now in a much stronger position to fix the problem or petition for a fix.
With closed-source code, step (2) is a lot harder unless you're in a privileged position...
Open source code still needs people looking at it.
f(<Some number of previous outputs>, <Secret key known to Intel and the NSA>, <Your cpu identifier>) = <next output>
Also correct me if I am wrong, but wasn't this about using RdRand as entropy source to the linux /dev/random, which afaik is not injection-proof..
And I would consider /dev/random among the most critial of applications.
Yes it does. Closed source, to the extent it impairs audits, does mean something is insecure.
It does not prove that the software is backdoored, otherwise compromised, or defective in any way - if that is what you meant, you're correct. But security means not only absence of these conditions, but also that you can verify that these conditions are absent.
Security is relative. "Secure" is a short form of "high enough confidence". There can be a rational basis for high or low confidence, based on various factors, including testing and likely motives of the parties. Closed source itself is a bad factor. Collaboration with the USG is a very bad factor.
And, of course, if you make it the kernel /dev/random you're making it the source of randomness recommended for long term keys and other important things... while you don't know what the users will use it for, you can safely assume it will include some of "the most critical of applications".
These things are internet hell.
Not sure how to link a particular article in that view. The 'direct link' sends you to an article-only page. But the message by the OP appears as the third top-level thread in that view.
You get to that by clicking on the subject in the bottom frame.
Try the "Messages sorted by: ... [ thread ] ..." link, it gives you a hierarchical view that's pretty understandable / navigable IMO.
Let R = { people who read mailing list archives }
Let D = { people who design and implement mailing list archives }
My conjecture: R ∩ D = ∅.
I suppose I would just be feeding the conspiracy theories if I mentioned that NSA also pushed security work for X.org forward?
He says if you're in the government they're one of the good guys, if you're anyone else you want to mix the results of their RNG with some other source.
Which is apparently exactly what this patch does.
at https://lkml.org/lkml/2011/7/30/116 linus says We still do our own hashing on top of whatever entropy we get out of rdrand, and we would still have all our other stuff. but then goes on to say I'd be even more willing to just take something that just introduces a per-arch interface to get a "unsigned long [ptr]" that is random, and returning the number of bits of expected entropy in that thing. And for x86 CPU's with the RDRAND capability bit, I'd give Intel the benefit of the doubt and just make it do a single "rdrand" and return the full 64 bit [...] which sounds like it would not be mixed.
so what was the final outcome?
[also, perhaps worth mentioning explicitly - the argument that you shouldn't care too much about this is that if you don't trust intel then you're fucked anyway. which doesn't fill me with warmth and joy, but what can you do?]
The important commit here is:
http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.g...
Excerpted:
Change get_random_bytes() to not use the HW RNG, even if it is avaiable.
The reason for this is that the hw random number generator is fast (if it is present), but it requires that we trust the hardware manufacturer to have not put in a back door. (For example, an increasing counter encrypted by an AES key known to the NSA.)
It's unlikely that Intel (for example) was paid off by the US Government to do this, but it's impossible for them to prove otherwise --- especially since Bull Mountain is documented to use AES as a whitener. Hence, the output of an evil, trojan-horse version of RDRAND is statistically indistinguishable from an RDRAND implemented to the specifications claimed by Intel. Short of using a tunnelling electronic microscope to reverse engineer an Ivy Bridge chip and disassembling and analyzing the CPU microcode, there's no way for us to tell for sure.
http://en.wikipedia.org/wiki//dev/random
Gutterman, Pinkas, & Reinman in March 2006 published a detailed cryptographic analysis of the Linux random number generator[5] in which they describe several weaknesses. Perhaps the most severe issue they report is with embedded or Live CD systems such as routers and diskless clients, for which the bootup state is predictable and the available supply of entropy from the environment may be limited. For a system with non-volatile memory, they recommend saving some state from the RNG at shutdown so that it can be included in the RNG state on the next reboot. In the case of a router for which network traffic represents the primary available source of entropy, they note that saving state across reboots "would require potential attackers to either eavesdrop on all network traffic" from when the router is first put into service, or obtain direct access to the router's internal state. This issue, they note, is particularly critical in the case of a wireless router whose network traffic can be captured from a distance, and which may be using the RNG to generate keys for data encryption.
It shouldn't be a religious but an engineering problem. If you manage keep some state between reboots and use it after the next reboot, you're making it hard enough for anybody not having the physical access to that state. Then you can also use RdRand to mix it with the output of your stream based on your state, and with other sources of entropy if you have them. If RdRand turns out to be suspicious, you're at least much better off than using only hard coded states.
Anybody knows if some kind of described state is used now?
I see Ted Ts'o commented too, and as I understand, having RdRand is still much better compared to having the platforms without it. There's a lot more to care about than is RdRand "perfect" and once you have something like RdRand you can use it safely enough, compared to not having anything.
The seed that is saved at shutdown and reloaded at startup will alter the internal state of the /dev/random pool, but it won't add to the entropy estimate (which makes sense). This means that the output will be more robust, but it could still block waiting for "real" entropy.
"But what's the argument for _not_ mixing their probably-not-backdoored RNG with other entropy?"[1]
Does your answer to this really change that much "pre-Snowden"?
[1] http://lists.randombit.net/pipermail/cryptography/2013-July/...
You can trust Skype that calls are encrypted and cannot be eavesdropped, you can trust Verizon that your cellphone metadata are not passed to government automatically, and you can trust Intel that their rnd is not backdoored.
Or you don't.
It's possible that the HSM maker wasn't approached by the NSA and is secure, but there are very few of them in the US so chances of the NSA having missed one is very low. Plus, without a STM to inspect the silicon and reverse-engineer it, how would you know?
So what if you buy one made outside the US? Say, China. Well, there's the obvious possibility that the Chinese authorities have backdoored the silicon. But my guess is that the Chinese maker just cloned one of the US vendors, including the portions inserted by the NSA...
An "array of mutually untrustworthy opponents", if you like…
They'd looks something like Debian's OpenSSL. But I believe that was not an intentional backdoor.
Another class of randomness is that which is used to randomize the layout of shared libraries, stacks, etc. --- address space layout randomization (ALSR). If someone is able to guess the randomness used by ASLR, then they will be able to more easily exploit stack overrun attacks, since they won't need to guess where the stack is, and where various bits of executable segments might end up in the address space's layout.
Another case of randomness is to create crypto keys; either long-term keys such as RSA/DSA keys, or symmetric session keys. If someone screws this up, that's when the "bad guy" (in this case, people are worried about the NSA being the bad guy) can get access to encrypted information.
It is only the first two use cases where we use RDRAND without doing any further post-processing. These are cases where the failure of the RNG is not catastrophic, and/or performance is extremely critical.
We do not use RDRAND without first mixing it with other bits of randomness gather in the system for anything that is emitted via /dev/random or /dev/urandom, because we know that this is used for session keys and for long-term RSA/DSA keys.
The bigger problem, and it's one that we worry a huge amount about it, is the embedded ARM use cases which do not have RDRAND, and for which there is precious little randomness available when the system is first initialized --- and oh, did I mention that this is when long-term secrets such as SSH and x.509 keys tend to be generated in things like printers and embedded/mobile devices and when they are first unwrapped and plugged in, when the amount of entropy gathered by the entropy pool is usually close to zero? What we desperately need to do is to require that all such devices have a hardware random number generator --- but the problem is that there are product managers who are trying to shave fractions of a penny off of the BOM cost, and those folks are clueless about the difference between cost and value as far as high-quality random number generators are concerned.
What if the RNG has been compromised by the NSA? Well, that's where you need to mix in other sources of randomness into the entropy pool. The password used by the user when he or she first logs into an android device, for example. Screen digitizer input from the user while they are first going through the setup process. In the case of a consumer grade wireless router, it could sniff the network for a while and use packet inter-arrival times and mix that into the entropy pool. Yes, someone who is on the home network at that time will know those numbers, but hopefully someone who is in a position to spy on those numbers, isn't also going to have access at the same time the super-secret NSA key used to gimmick the RDRAND instruction (assuming that is gimmicked, which is effectively impossible for us to prove or disprove.) But then again, your wireless router isn't going to have access to unencrypted plaintext which is critical --- if you're sending anything out your wireless network without first encrypting it first, I would hope that you would consider it completely bare and exposed!
If you are super paranoid, you'll need to find a hardware random generator which you've built yourself --- and hopefully you are competent enough to actually build a real HWRNG, and not something which is sampling 60 Hz hum (or 50 Hz hum if you are in Europe :-), and mix that into the entropy pool as well. In that case, even if the Intel RDRAND is compromised six ways from Sunday, the NSA won't have access to the output from the HWRNG --- and if it turns out you were incompetent and your HWRNG is bogus, at least RDRAND is also getting mixed into the entropy pool.
And if I were in China, I'd use a hardware chip built in China for the RNG, and combine that with an Intel chip. That way even if the HWRNG chip is compromised by the MSS, and even if RDRAND is compromised by the NSA, the combination is hopefully stronger since presumably (hopefully!) it's unlikely that the MSS and the NSA are collaborating with each other at that deep a level. Ultimately, of course, if you don't trust Intel, you don't trust the silicon fab, etc., then you'll have to build your own computer from scratch, write your own compiler from scratch, etc.
(MIT CS undergrads used to have all of that knowledge, starting with building a computer out of TTL chips and how to build a Scheme interpreter from machine code, etc. But not any more, alas. Now they learn Python and it's assumed that it's impossible to understand the entire software stack, let alone the entire hardware stack, so you don't even try to teach it. But that's another rant....)
This is the first that I heard that he had resigned over the RDRAND getting used directly, and I track LKML discussions, especially on topics such as file systems and random number generators, pretty closely. What I suspect happened is someone pushed this patch to Linus without going through him, and he got annoyed and just stopped work.
What happened about 18 months ago was some researchers approached us about the deficiencies hey found documented at http://factorable.net. It when then that I discovered that Matt Mackall had resigned (although the MAINTINERS file still listed him as the maintainer --- normally when people resign in a huff they send a patch to remove themselves from the MAINTAINERS file). So at that point, I took over the maintenance duties.
It was at that point that I changed things so that RDRAND was only used directly for non-critical items, and started addressing how to gather as much entropy as possible for those platforms which do not have RDRAND --- which in fact was the bigger deal, and right now, probably the far greater set of problems.
That leads me to another important point --- don't get too focused on RDRAND. Yes, it's something we need to be concerned about, but there are many different ways people can screw up security, and not all of them require active collusion with the NSA.
For example, there are several years worth of HP printers where it's possible to push an unsigned firmware load to said printers over the network, at which point said printer could be sending copies of everything sent to it back to the NSA or the FBI. This would require no collusion between HP and the US government --- just the incompetence of HP firmware engineers. Could the NSA or the FBI be exploiting such a hole? I'd actually argue that given the FBI's mission, it would be malpractice for them not to develop such a trojan'ed firmware load. Hopefully they would only be using it after getting a search warrant, but if such a hole exists, and their mission is to get the bad guys, subject to US laws and the US constitution, I have no problem with them trying to create such exploits. Of course, I do blame HP for making it be possible to create such an exploit in the first place, and so we need to hold manufacturers accountable.
So we need to be vigilant, and worry about auditing all of the potential attack surfaces, and not just worry about one particular place where Intel might have colluded with the NSA. There are lots of other places where collusion is not required; just simple carelessness and incompetence by software engineers....
What do you propose as a low cost solution? I've seen some interesting suggestions, such as having a small fish bowl or tube or tank, having air pumped into the bottom, and sampling the patterns of bubbles with some CV solution. Sounds geeky, would make for a nice decoration on one's table, but building it seems like quite a job.
That Intel is cooperating with the TLAs and providing a weak on-chip random number generator? Or a random number generator that can be made to be weak? Or what?
And how credible is the risk when that information is used to seed a pool of entropy, rather than being used raw?
I still don't get it.
For what it's worth, the RDSEED instruction has been announced by Intel a while back (but not yet on current processors), which means to be an NRBG as well.
/*
* Force a reseed cycle; we are architecturally guaranteed a reseed
* after no more than 512 128-bit chunks of random data. This also
* acts as a test of the CPU capability.
*/[1] http://software.intel.com/en-us/articles/intel-digital-rando...
[2] http://www.cryptography.com/public/pdf/Intel_TRNG_Report_201...
* Degate, a somewhat automated "aid in reverse engineering of digital logic in integrated circuits" - http://www.degate.org/
* Silicon Zoo offers a tutorial / background info on this - http://siliconzoo.org/tutorial.html
* A blog about IC reverse engineering - http://uvicrec.blogspot.com/ (from the owner of http://siliconpr0n.org/ , which is currently down)
The reason it won't help is that the design is _explicitly_ microcoded. E.g. RDRAND triggers running loadable microcode which is supposed to read the real RNG and AES it. Maybe there is an unrelated "bug" that allows that microcode to be corrupted after some particular instruction sequence happens. All your investigation would turn up everything looking like normal.
* decap an Intel CPU and scan it
* decode the microcode encryption
* figure out how the hardware RNG works with the microcode (it's AES? ok.)
* and then analyzing the system of microcode and hardware for robustness and security.
Yeah, this is hand-wavey and probably incredibly implausible. But it seems like an interesting and challenging project or three.
> Not to mention, Intel have been in bed with the NSA for the longest time.
> Secret areas on the chip, pop instructions, microcode and all that ...
What does "pop instructions" refer to here?
i distrust