Holes in the Linux random number generator?

May 24, 2006

This article was contributed by Jake Edge.

Eye catching headlines are seen every day on the web, but one needs to be careful not to distort the contents of the article. A recent SecuriTeam article is headlined "Holes in the Linux Random Number Generator" but that title overstates the actual contents of the paper (PDF) it is announcing.

The three authors of the paper provide a nice detailed description of the Linux random number generator (RNG) and the algorithms that it uses, while also reporting a very theoretical attack. The basic attack is against the "forward security" of the RNG via a single compromise of the contents of the entropy pool. This value can be used to run the RNG algorithm in reverse and recover previous states of the entropy pool. Doing this enough times can recover keys that have been previously generated.

There are a number of reasons why this attack is considered to have little impact on real world systems. The most obvious is that if an attacker can access the state of the entropy pool, they have already broken the security of the system and can, as root, do any number of different things to the system. If recovering previously generated keys is the object of the attack, the paper outlines ways to do that, but the processing requirements are enormous as Ted Ts'o points out:

To put this in perspective, generating a 1024 bit RSA key will require approximately 14 turns of the crank, so if you are lucky with the positioning of the index *and* you penetrate the machine and capture the state of the pool (which as I mentioned, probably means you've rooted the box and the system will probably have to be reinstalled from trusted media anyway), *and* a 1024-bit RSA key had just been generated, you would be able to determine that 1024-bit RSA key with a work factor of approximately O(2**68) if you are lucky (probability 1 in 8), and O(2**96) if you are not.

The paper also describes a well known feature of the Linux RNG implementation as if it were a newly discovered denial of service issue. The /dev/random device was specifically designed to block when the entropy pool had insufficient entropy to satisfy the request. The /dev/urandom device is provided as an alternative that generates very good random numbers and does not block (and is therefore not vulnerable to a denial of service). For any but the most sensitive applications (key generation being an obvious choice), /dev/urandom is the recommended source for random numbers. Alan Cox sums up the situation nicely:

The denial of service when no true entropy exists is intentional and long discussed. User consumption of entropy can be controlled by conventional file permissions, acls and SELinux already, or by a policy daemon or combinations thereof. It is clearly better to refuse to give out entropy to people than to give false entropy.

The paper has sparked an interesting discussion on the linux kernel mailing list and has lead to some concrete suggestions for improving the algorithm, but it would be an exaggeration to conclude that the paper describes real world Linux security concerns. An administrator or security professional reading the SecuriTeam headline might easily be led astray.

Index entries for this article
GuestArticles	Edge, Jake

to post comments

Holes in the Linux random number generator?

Posted May 26, 2006 11:28 UTC (Fri) by zooko (guest, #2589) [Link] (5 responses)

"It is clearly better to refuse to give out entropy to people than to give false entropy."

This is not true, or at least is true only in specific and uncommon use cases.

(By the way, the output of /dev/urandom is not "false entropy".)

The overwhelming majority of uses of security-sensitive random numbers occur under many layers of software operated by security-naive users.

In that case, the failure mode from random number acquisition blocking is not "The user realizes that /dev/random has blocked and deals with it." (which is what happens if the user is Alan Cox), but "Timeouts cascade through the system and the user becomes confused.".

This can lead to the kind of security problems which are real, frequent, and widely exploited -- denial of service, social engineering, time-of-check-to-time-of-use gaps, exploitation of failover, exploitation of false alarm, etc. etc.. In contrast, the idea of a cryptanalytic attack which cracks /dev/urandom but not /dev/random is purely hypothetical and may not exist at all.

Alan Cox's stance (as quoted) seems reasonable enough at first, but this is one of those cases where security engineering defies our intuitive belief that being "safer" or "more conservative" is better. (Think of burglar alarms or watch dogs which are too sensitive and give off too many false alarms.)

Holes in the Linux random number generator?

Posted May 26, 2006 14:22 UTC (Fri) by jake (editor, #205) [Link] (4 responses)

the choice of /dev/random vs. /dev/urandom is made by the application. it would seem to me that providing both choices in the kernel is reasonable even if the threat to /dev/urandom is purely theorectical. For the paranoid, choose /dev/random and be prepared to deal with it blocking. If some applications have chosen incorrectly, it would seem that one should work with them to change their choice instead of removing the 'super paranoid' alternative from the kernel.

jake

Holes in the Linux random number generator?

Posted May 26, 2006 16:41 UTC (Fri) by zooko (guest, #2589) [Link] (3 responses)

That's a reasonable approach. The problem is that the majority of Linux programmers appear to have the misunderstanding that you ought to use /dev/random when you need "real randomness" (as opposed to "pseudo-randomness") or for "added security". In fact, nearly all of the applications that use /dev/random would be more secure against the kinds of attacks that I mentioned if they used /dev/urandom, and there is no particular reason to believe that they would be more susceptible to cryptanalysis that way.

It's a widespread and persistent myth that /dev/urandom isn't really secure, which is why I get so frustrated when I see it repeated. In fact, just last week our own LWN posted an article that repeated that myth.

http://lwn.net/Articles/182874/

I see that it has subsequently been edited so that it no longer constrasts /dev/urandom with /dev/random as "pseudo-random" vs. "true random", but it still constrasts them as "purely algorithmic" vs. "true random", which is still sadly incorrect (they are both algorithmic in the sense of being algorithms that could in principle be cracked by a cryptanalysis, and neither is "pure" in the sense of producing output without entropic input -- excepting perhaps the broken edge case of /dev/urandom producing output during system bootstrapping when it has never been properly seeded -- and /dev/random is not "true random" in the sense of being provably information-theoretically secure).

Holes in the Linux random number generator?

Posted May 27, 2006 13:22 UTC (Sat) by kleptog (subscriber, #1183) [Link] (2 responses)

There's a lot of confusion about the difference between /dev/random and /dev/urandom. This also partly because the definitions vary across different systems.

For example, at one point libgcrypt might read a few KB of data from /dev/urandom to initialise its internal PRNG. After all, /dev/urandom is not really random so we'll just take as much as we can. On Linux ofcourse this breaks terribly because anything using /dev/random will now be without entropy. Other systems apparently run /dev/random and /dev/urandom from seperate pools, so it's not a big problem.

I think what really needs to happen is that people *think* about how much randomness they really need, given it is a somewhat scare resource. Using a few KB of entropy to seed a PRNG that only a few bytes of random data are going to be generated from is silly, you may as well read those bytes directly from the random device and save yourself a lot of effort.

Holes in the Linux random number generator?

Posted Jul 4, 2006 16:51 UTC (Tue) by unruh (guest, #32389) [Link] (1 responses)

I think that the main source of the confusion about /dev/random and /dev/urandom is the man pages. There is (almost) no case in which /dev/random is a better choice than /dev/urandom. While the claim on the man page that /dev/urandom uses a PRNG which might be in danger of attack, it is like saying that eating grapes might make you susceptible to Alzheimers and lowered sperm count. Yes, it might. There is absolutely no evidence thereof, and using /dev/random WILL cause far more problems by its blocking. Ie, the man page leaves exactly the wrong impression for a naive reader. (I just responed to a newgroup article where someone was doing
dd if=/dev/random of=/dev/hdb1
and wondering why the program seemed to hang).

Also the claim that /dev/urandom will use up the entropy pool for /dev/random on Linux does not seem to be born out tests.
dd if=/dev/urandom of=/tmp/tt &
Wait a minute ( or a few GB in /tmp/tt) and while that comand continues running do
dd if=/dev/random of=/tmp/t bs=1024 count=1
It does not block for me. It fulfills its request immediately
(Linux kernel 2.6.12-22mdk on Mandrake 2006)
(Then of course kill the first dd before you run out of disk space)

Your tests do not agree w/ mine.

Posted Nov 15, 2006 7:30 UTC (Wed) by simoncion (guest, #41674) [Link]

> Also the claim that /dev/urandom will use up the entropy pool for /dev/random on Linux does not seem to be born out tests.

My tests do not agree with yours:

dd if=/dev/urandom of=/tmp/rand1 &

Wait for a few hundred MB (This takes a couple of minutes)

dd if=/dev/random of=/tmp/rand2 &

Wait a couple of minutes, check the size of /tmp/rand2... It's 512 bytes in size.

cat /proc/sys/kernel/random/entropy_avail

And I get a number in the low double digits. When I terminate the first instance of dd, /tmp/rand2 (the file fed by /dev/random) begins increasing in size much more quickly. catting /proc/.../entropy_avail still returns a number in the single digits, as is expected. When I terminate the remaining instance of dd, catting /proc/.../entropy_avail reveals a number that increases to ~3500; also as expected.
Tested on 2.6.18-ck1-r1, Gentoo Linux.

Cheers,
Simon C. Ion