Linux RNG May Be Insecure After All 240
Okian Warrior writes "As a followup to Linus's opinion about people skeptical of the Linux random number generator, a new paper analyzes the robustness of /dev/urandom and /dev/random . From the paper: 'From a practical side, we also give a precise assessment of the security of the two Linux PRNGs, /dev/random and /dev/urandom. In particular, we show several attacks proving that these PRNGs are not robust according to our definition, and do not accumulate entropy properly. These attacks are due to the vulnerabilities of the entropy estimator and the internal mixing function of the Linux PRNGs. These attacks against the Linux PRNG show that it does not satisfy the "robustness" notion of security, but it remains unclear if these attacks lead to actual exploitable vulnerabilities in practice.'"
Of course, you might not even be able to trust hardware RNGs. Rather than simply proving that the Linux PRNGs are not robust thanks to their run-time entropy estimator, the authors provide a new property for proving the robustness of the entropy accumulation stage of a PRNG, and offer an alternative PRNG model and proof that is both robust and more efficient than the current Linux PRNGs.
Re:Incorrect and irresponsible headline (Score:5, Informative)
Their analysis that the linux rng is insecure under this (rather contrived) model rests on an _incorrect_ assumption that Linux stops adding to the entropy pool when the estimator concludes that the entropy pool is full.
Exactly. The maintainer of the /dev/random driver explained this and a lot more about this paper here [ycombinator.com].
many times a day he says Linux needs changes (Score:5, Informative)
Linus signs off on many changes everyday. He does expect you to read the code before trying to change it. That was the problem before - someone put up a change.org petition that made clear they had no idea how it worked.
Comment removed (Score:3, Informative)
This is only for recovery after state compromise (Score:5, Informative)
If the CPRNG state is not compromised, the Linux random generators are secure. In fact the property required for robustness is quite strong: Recovery from compromise even if entropy is only added slowly. For example, the OpenSSL generator also does not fulfill the property. Fortuna does, as it is explicitly designed for this scenario.
I also have to say that the paper is not well-written as the authors seem to believe the more complicated formalism used the better. This may also explain why there is no analysis of the practical impact: The authors seem to not understand what "practical" means and why it is important.
Re:Yawn (Score:4, Informative)
"For real security you need specialized hardware devices."
Indeed. And it's worth considering that the Raspberry Pi has a Hardware RNG built in. Also, the tools to make it functional are in the latest updates to Raspian...
Did I mention that an RPi B is actually cheaper than the least expensive HWRNG-device (the Simtec Entropy Key - which is waaaayyyy backordered at the moment) - and about three times faster?
Re:Hear me out: Locally Generated Entropy Pool (Score:4, Informative)
Yes. Hardware high-speed super-random number generators are trivial. I did it with amplified zener noise through an 8-bit 40MHz A/D XORed onto an 8-bit ring-shift register, generating 0.5MB/second of random noise that the Diehard tests could not differentiate from truly random numbers. XOR that with an ARC4 stream, just in case there's some slight non-randomness, and you're good to go. This is not rocket science.
Re: Random number generators are hard (Score:4, Informative)
Not all Linux systems use the GNU userspace.
Ted Ts'o on Schneier.com (Score:5, Informative)
has some thoughts on the study and the subject:
https://www.schneier.com/blog/archives/2013/10/insecurities_in.html [schneier.com]
Re:Random number generators are hard (Score:4, Informative)
Good for you. That is still not a viable solution for generating cryptographic keys, IVs, salts, and so on. Two drawbacks with your idea:
1. Too slow. You need far more random data than a zener diode can generate. You could combine many of them, but then you need to combine them in the right way.
2. Unreliable. Zener diodes are easy to affect with temperature, and you need to make sure that hardware flaws don't make them produce 1 more often than 0 (or the other way around).
This is why we need software RNGs. We take a good hardware-based seed from multiple sources (combined using SHA256 or something), and then use that to seed the CSPRNG (not just a PRNG). The CSPRNG then generates a very long stream of secure random data which can then be used.
I'm not too pleased about the design of Fortuna, but it seems like one of the better choices for how to combine HW input and generate an output stream.
Re:So write a better one (Score:5, Informative)
"Not so random" means that you can mathematically calculate how likely it is that you can predict the next number over a long time. If you can predict the next number with an accuracy of 1 in 250 while the random generator provides 1 in 1000 then the random generator isn't that random.
Many random generators picks the previous value as a seed for the next value, but that is definitely predictable. Introduce some additional factors into the equation and you lower the predictability. One real problem with random generators using previous value as a seed without adding a second factor is that they can't generate the same number twice or three times in a row (which actually is allowed under the randomness rules).
It's a completely different thing to create a true random number. For a 32 bit number you essentially should have one generator source for each bit that don't care about how the bit was set previously. It is a bit tricky to create that in a computer in a way that also allows for fast access to a large number of random numbers and prevent others from reading the same random number as you do.
For computers it's more a question of "good enough" to make prediction an unfeasible attack vector.
Re:Very Informative. (Score:5, Informative)
If you are gonna do that, might as well link to the comment:
https://www.schneier.com/blog/archives/2013/10/insecurities_in.html#c1909001 [schneier.com]
Re: Random number generators are hard (Score:5, Informative)
Android. Many embedded systems. Many micro systems, such as tomsrtbt or similar (now virtually unneeded, due to the lack of floppy discs on new computers, and the prevalence of booting of CDs or USB flash drives). Many lightweight systems [wikipedia.org], such as Damn Small Linux.
Etc.
See also: Toybox.