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.
Linus always says Linux is perfect. Linus can be wrong.
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?
At what scope/scale of time or range of values does it really matter if a PRNG is robust?
A PRNG seeded by a computer's interrupt count, process activity, and sampled I/O traffic (such as audio input, fan speed sensors, keyboard/mouse input, which I believe is a common seeding method) is determined to be sufficiently robust if only polled once a second, or for only 8 bits of resolution, exactly how much less robust does it get if you poll the PRNG say, 1 million times per second, or in a tight loop? Does it get more or less robust when the PRNG is asked for a larger or smaller bit field?
Unless I'm mistaken, the point is moot when the only cost of having a sufficiently robust PRNG is to wait for more entropy to be provided by its seeds or to use a larger modulus for its output, both rather trivial in the practical world of computing.
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.
So, with all the 'revelations' and discussion surrounding this and encryption over the past several weeks, I've been wondering if a local hardware based entropy solution could be developed. By 'solution', I mean an actual piece of hardware that takes various static noise from your immediate area, ranging from 0-40+kHz( or into MHz or greater?), both internal and external to case, and with that noise builds a pool for what we use as /dev/random and /dev/urandom. Perhaps each user would decide what frequencies to use, with varying degrees of percentage to the pool, etc.. etc...
It just seems that with so much 'noise' going on around us in our everyday environments, that we have an oppurtunity to use some of that as an entropy source. Is anyone doing this, cause it seems like a fairly obvious implementation.
From a practical side, we also give a precise assessment of the security of the two Linux PRNGs, /dev/random and /dev/urandom
The internet must have finally run out of porn.
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)
zener diodes biased into avalanche mode to generate random noise? I don't think even the NSA has figured out how to hack laws of thermodynamics.
That's not quite the point.
The two random devices are there not to be alternate sources of randomness, but to be a good source of provably random numbers gained from hardware randomness mixed into the entropy pool, and another source of cryptographically random numbers seeded from the first - but with perhaps orders of magnitude less entropy per output bit compared to input bits.
The first source will stop outputting when it runs low on entropy.
He "confirmed" he'd been asked to backdoor linux, he never confirmed whether or not he agreed... :)
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.
Bad call, in a fight to the death a tie doesn't help you any...
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.
has some thoughts on the study and the subject:
https://www.schneier.com/blog/archives/2013/10/insecurities_in.html
I think the only question on my mind is what exactly is deemed insecure for? Generating public/private key pairs? Doing encryption for SSL/TLS?
I've been around computers for a good number of years and I know no computer can be truly random, but isn't there a point where we say, "It's random enough."? Is this OP saying.. Linux's RNG isn't "Random Enough." and my question is.. what isn't it random enough for?
"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.
I'm having a security panic over here!
as a quick fix I deleted /dev/random and did ln -s /dev/zero /dev/random
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
Plan 9 failed simply because it fell short of being a compelling enough improvement on Unix to displace its ancestor. Compared to Plan 9, Unix creaks and clanks and has obvious rust spots, but it gets the job done well enough to hold its position. There is a lesson here for ambitious system architects: the most dangerous enemy of a better solution is an existing codebase that is just good enough.
â"Eric S. Raymond[3]
I think it is past time for CPUs to provide hardware random numbers. Via CPUs have done this for years, but Via CPUs are just too slow for most uses. (I used to run my mail server on a Via C3... I am a lot happier now that my server runs on an AMD low-power dual-core.)
Recent Intel chips do have some sort of random number generator (RdRand).
Hardware RNG accessories are available but expensive.
There is the LavaRnd project, which I think is really darn cool. However, I downloaded the source code, and it hasn't been updated since 2003... a decade later, GCC won't even compile the code. (GCC now issues warnings about some of the code and they set the "treat warnings as errors" flag. I didn't experiment with disabling that flag and trying the code out.) Also, the supported hardware list is a short list of decade-old webcams.
(Note: this would be a good project for a high school student or college student who knows C: update LavaRnd so it builds with GCC or Clang, get it working with at least one currently-available webcam, and write a report about it.)
The Raspberry Pi has a hardware RNG as part of the system-on-a-chip, and Linux on the Pi supports it. You could set one up as a randomness server to your VMs, and that would be quite inexpensive. At least the VMs could reseed their PRNGs with random values pulled from the Pi.
http://vk5tu.livejournal.com/43059.html
If you have a sound device, Audio Entropy Daemon may work.
http://www.vanheusden.com/aed/
P.S. Haveged looks interesting... I just discovered it and I don't know how well it actually works.
https://www.digitalocean.com/community/articles/how-to-setup-additional-entropy-for-cloud-servers-using-haveged
lf(1): it's like ls(1) but sorts filenames by extension, tersely