User: Password:
|
|
Subscribe / Log in / New account

Holes in the Linux random number generator?

Holes in the Linux random number generator?

Posted May 26, 2006 11:28 UTC (Fri) by zooko (guest, #2589)
Parent article: Holes in the Linux random number generator?

"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.)


(Log in to post comments)

Holes in the Linux random number generator?

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

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]

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]

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]

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


Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds