Slashdot Mirror
Linux RNG May Be Insecure After All
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.
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.
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.
There are quantum effects involved in this process. Quantum effects (more specifically wave function collapse) are thought to be a source of true, inherent and perfectly unpredictable randomness. Throw that into a massive (from an atomistic point of view) chaotic system and you get a gigantic mess that is impossible to simulate with sufficient precision to predict the noise that comes out (and far, far beyond our computational means even if you don't care about precision).
I would say "read more about it here, but a lot of what's written there is inaccurate. Both resistor noise and avalanche noise have important quantum nature and classifying them under "physical phenomena without quantum-random properties" is factually incorrect. The second comment by user "agr" in the discussion nails it. Pretty much anything involving electrons is quantum at the microscopic level.
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.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
"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?
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.
Celebrate failure, and then learn from it - Nolan Bushnell
Not all Linux systems use the GNU userspace.
has some thoughts on the study and the subject:
https://www.schneier.com/blog/archives/2013/10/insecurities_in.html
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.
"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.
If builders built buildings the way programmers wrote programs, then the first woodpecker would destroy civilization.
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
New things are always on the horizon
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, such as Damn Small Linux.
Etc.
See also: Toybox.
HELP MY ACCOUNT HAS BEEN HACKED BY AN ILLIBERAL ART STUDENT SET TO DESTROY THE INTERWEBZ!