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.
http://dilbert.com/dyn/str_strip/000000000/00000000/0000000/000000/00000/2000/300/2318/2318.strip.gif
.....wait! it's not what you think.
"a new paper analyzes the robustness of /dev/urandom and /dev/urandom."
So now we're putting the dupes together into the same summary? Jeez, can't we at least wait a few hours first?
The output of a software RNG, aka PRNG (pseudo random number generator), is completely determined by a seed. In other words, to a computer (or an attacker), what looks like a random sequence of numbers is no more random than, let's say,
(2002, 2004, 2006, 2008, 2010, 2012...)
However, the PRNG sequence is often sufficiently hashed up for many applications such as Monte Carlo simulations.
When it comes to secure applications such as cryptography and Internet gambling, things are different. Now a single SRNG sequence is pathetically vulnerable and one needs to combine multiple SRNG sequences, using seeds that are somehow independently produced, to provide a combined stream that hopefully has acceptable security. But using COTS PC or phone doesn't allow developers to create an arbitary stream of independent RNG seeds, so various latency tricks are used. In general, these tricks can be defeated by sufficient research, so often a secure service relies partly on "security through obscurity", i.e. not revealing the precise techniques for generating the seeds.
This is hardly news. For real security you need specialized hardware devices.
I swear, if I worked for the NSA I'd be pushing out headlines like this to make people ignore real security issues...
The article is a highly academic piece that analyzes the security of the linux rng against a bizarre and probably pointless criteria: What is an attacker's ability to predict the future output of the RNG assuming he knows the entire state of your memory at arbitrary attacker selected points in time and can add inputs to the RNG. 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. Instead they offer the laughable suggestion of using AES in counter mode as a "provably secure" alternative.
(presumably they couldn't get a paper published that said "don't stop adding entropy just because you think the pool is at maximum entropy", either because it was too obviously good a solution or because their reviewers might have noticed that Linux already did that)
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.
First of all, not all computers are PCs. A server running in a VM has no audio input, fan speed, keyboard, mouse, or other similar devices that are good sources of entropy. A household router appliance running Linux not only has no audio input, fan, keyboard, or mouse -- it doesn't even have a clock it can use as a last resort source of entropy.
Second, there are many services that require entropy during system startup. At that point, there are very few interrupts, no mouse or keyboard input yet, and some of the sources of entropy may even be initialized yet.
One problematic situation is a initializing a household router. On startup it needs to generate random keys for its encryption, TCP sequence numbers, and so on. Without a clock, a disk, a fan, or any peripherals, the only good source of entropy it has is network traffic, and there hasn't been any yet. A router with very little traffic on its network may take ages to get enough packets to make a decent amount of entropy.
dom
No, RNGs are easy. Super easy. Just take a trustworthy source of noise, such as zener diode noise, and accumulate it with XOR operations. I built a 1/2 megabyte/second RNG that exposed a flaw in the Diehard RNG test suite. All it took was a 40 MHz 8-bit A/D conversion of amplified zener noise XORed into an 8-bit circular shift register . The Diehard tests took 10 megabytes and said if it found a problem. My data passed several times, so I ran it thousands of times, and found one test sometimes failed on my RNG data. Turns out the Diehard tests had a bug in that code. Sometimes the problem turns out to be in the test, not the hardware.
Celebrate failure, and then learn from it - Nolan Bushnell
has some thoughts on the study and the subject:
https://www.schneier.com/blog/archives/2013/10/insecurities_in.html
Useless for you. But the NSA might disagree. The math is what keeps them at bay. If the math shows cracks, it'd be certain that the NSA has figured out some kind of exploit. Keep in mind that the NSA doesn't rely on just one technique, but can aggregate multiple data sources. So those interrupts that the RNG relies on can be tracked, and the number that results can be narrowed to a searchable space. Keep in mind that 2^32, which is big by any human standard, is minuscule for a GPU.
"If a nation expects to be ignorant and free in a state of civilization, it expects what never was and never will be."
No, RNGs are easy. Super easy. Just take a trustworthy source of noise
Therein lies the tricky part. Getting a trustworthy source of noise is harder than you may think. Especially when you're writing software with no control over the hardware it runs on.
Your attitude is exactly what is wrong with security. Quite a few still use MD5 because "it is not that broken". Linus really should take a look in this new provably better method and adapt it ASAP and not wait until it bites hard.
"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.
The nice thing about randomness though, is that it adds up. If you xor one stream of hopefully random bits with another stream of hopefully random bits, you get a result that is at least as random as the best of the two streams, quite possibly better than either. It's a rare and precious thing in cryptography: something you can't make worse by messing up. At worst you make no difference.
So if you're paranoid, come up personally with a ridiculously long phrase (you don't need to remember it), feed it through a key derivation function, and use it in a stream cipher with proven security guarantees (in particular one that passes the next-bit test for polynomial time). Instead of using this directly, xor it together with a source of hopefully random stuff.
If you write to /dev/random this is more or less what happens. Write to it to your heart's content - it can only make it better, not worse. (This is as I recall, please check with an independent source before you try).
Voila, no matter what NSA has done to your HRNG chip, this door is secured. Your time is better spent focusing on the other doors, or the windows.
(But you should be very careful in using HRNG output directly. I am very surprised to read that some open source OSes disable the stream cipher if a HRNG is present - this is a very bad idea!)
xkcd is not in the sudoers file. This incident will be reported.
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!