Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

The RHEL5 manuals state that /dev/urandom will use the entropy pool until it's exhausted, and then it will resort to a fall-back pseudo-random algorithm, so that it will never block.

But when investigating the system, I've found that the pseudo-random generator (/dev/urandom) is initialised by /var/lib/random-seed as stated in the /etc/rc.sysinit start-up script.

But the /var/lib/random-seed itself gets its data from /dev/urandom o.O !! as stated in /etc/init.d/halt file script when entering runlevel 0 (shutdown) or runlevel 6 (reboot).

So /dev/urandom never uses the entropy pool?!

I am confused... any help would be appreciated please :)

share|improve this question
    
known issue - this may help: serverfault.com/questions/303935/… –  user9426 Apr 29 '12 at 6:52
add comment

3 Answers

/dev/urandom will always try and return the most random value it can. In the worst case, it will use cryptography to "stretch" the last bits of entropy in the pool to fill your request. By contrast /dev/random will block until the entropy pool is full enough to fill the requested bytes, so /dev/random will guarantee a more random value. However /dev/random will block until the entropy store is large enough to fill the requested bytes, which is unacceptable in almost all uses. If the entropy pool is full, then /dev/urandom and /dev/random are identical.

When rc.sysinit shuts down it copies 512 bytes from /dev/urandom. At this point its likely that the machine has been on for a while so the entropy pool has had a chance to fill. There for this file is most likely a pure chunk of the entropy pool. However if the entropy pool is not full, its better to having something than nothing at all (Or even worse, block until the entropy pool is full enough before shutting down).

On a Linux system it is very important that the entropy pool is populated during boot. To fill this need the shutdown action is to save the entropy pool to disk, and the start-up is to re-load this entropy pool very early in the boot process. On a Linux system the ASLR'ed memory locations and TCP sequence values are calculated with this entropy pool. If the pool was flushed, then on each boot the memory space layout of daemon processes would not be very random and there for a process like your SMTP daemon could be exploited via a buffer overflow more easily. This also affects your susceptibility to MITM attacks. This is because it would be easier for an attacker to predict your TCP sequence values needed to complete the TCP 3-way handshake.

If you ever see a Linux distribution that doesn't restore isn't entropy pool at boot, then its a vulnerability that need to be reported.

If you would like more information, try reading the code comments in random.c

share|improve this answer
    
Thanks sir. I got it now, why a random-seed is saved between boots :) But, still one question (and sorry for disturbing you again).. when /dev/urandom is re-seeded from /random-seed and started to produce random numbers, what if the entropy-pool has sufficient bytes ? –  Michael Bloomberg Apr 29 '12 at 10:37
    
will the PRNG use those bytes or it continues to re-using the bytes from /dev/urandom ? –  Michael Bloomberg Apr 29 '12 at 10:39
1  
"I think that we all agree that un-streched values are more random" - I don't agree with that. Talking about "more random" in this context doesn't make sense. The output is either cryptographically strong, or it isn't. There is no "a little bit pregnant". With /dev/urandom, the output is cryptographically strong; for engineering purposes, that's as good it gets and as good as you'll likely ever need. (The situations where one might prefer /dev/random are very rare.) –  D.W. Apr 30 '12 at 3:18
1  
So long as the pool was seeded at some time after system boot with a value that has at least 256-bits that are unknown to any attacker, /dev/urandom is always 100% fine to use. The difference is like the difference between water and holy water -- there is no known test that can distinguish one from the other, and if you use one instead of the other, nobody will ever know unless you tell them or they catch you. –  David Schwartz Apr 30 '12 at 6:59
1  
The pool is always the same size. When we talk about how many bits are "in the pool", we just mean how many bits an attacker cannot guess. The PRNG always hashes the pool, outputs part of the hash, and mixes part of the hash back in. There is no alternation. Entropy is always mixed into the pool (whenever the system gets any) and the PRNG always hashes the pool and mixes some of the hash back into the pool. (This is a simplification, because there is more than one pool. But it doesn't affect the behavior.) –  David Schwartz Apr 30 '12 at 10:53
show 10 more comments

Overview. I don't blame you for being confused. There is a lot of bad information out there that (unjustly) casts aspersions on /dev/urandom.

In point of fact, /dev/urandom is secure. The short version is: use /dev/urandom and ignore the stuff you might hear about it. /dev/urandom is the right choice for almost every situation where you need strong, cryptographic-quality random numbers. /dev/random is almost never the right choice.

Technical details. For the rationale behind my claims, see the following questions:

There is a lot written there, and I'm not going to repeat it.

The random-seed file. To a first-order approximation, you can ignore the random-seed file. That is a standard mechanism that is present in the Linux distribution to ensure that /dev/urandom will be secure. As an application developer, you don't need to worry about it. It happens under the hood. All you need to know is that it is present by design, and it is there for a good reason, and it is beneficial.

Oh, you want the full explanation? OK, here it is. For it to be secure, /dev/urandom needs to get at least 128 bits or so of true random bits from somewhere. Once it has 128 bits or so of true entropy, from then on you can count on its output to be secure, cryptographically strong, and unpredictable -- no matter how much output you draw from it. So the only question is, where do those bits of true randomness come from?

The Linux kernel has many sources from which it gathers true randomness: e.g., the timing of interrupts (e.g., key presses, I/O) and other such low-level stuff. The kernel gradually accumulates this randomness into a pool that /dev/urandom uses, and once these sources have produced an aggregate or 128 bits or so of true randomness, you're good. However, these sources produce entropy at a relatively low rate. Therefore, immediately after you boot up, they probably haven't produced enough entropy yet. To address this, the Linux distribution has a mechanism to retain entropy that has been gathered across reboots. when you shut the computer down, the computer draws some randomness from /dev/urandom's entropy pool (remember, the entropy pool probably has adequate entropy by now, so this should be good strong randomness) and saves it to the random-seed file. The next time you start the computer up, at boot time the operating system takes entropy from the random-seed file, ensuring that /dev/urandom's pool now has at least 128 bits or so of good randomness. Thus, once your computer accumulates enough entropy into the pool, /dev/urandom's output will be good from then on, no matter how many times you reboot the computer.

share|improve this answer
1  
You said: "Thus, once your computer accumulates enough entropy into the ((((pool))), /dev/urandom's output will be good from then on. so, 1- You mean the original kernel "entropy pool" or /dev/urandom's "entropy pool" ? 2- When /dev/urandom gets initialized from the random-seed file, does PRNG goes on and on producing randoms till a reboot or a shutdown or it gets re-seeded when the kernel "entropy pool" has sufficient bytes and goes on an on till again the kernel entropy pool has sufficient bytes and again and again ? Thanks sir for your detailed answers :) –  Michael Bloomberg Apr 30 '12 at 10:14
3  
The internal details of the entropy pool have changed with different versions of Linux. At one time, there was only one entropy pool. In modern versions, there are three. But it basically doesn't matter. The PRNG is re-seeded additively, that is, seeds are mixed in and added to the pool. If an attacker couldn't predict the pool before it is re-seeded or PRNG data is output from it, he can't predict is afterwards. The PRNG and seeding are carefully designed so that there is no way to acquire information about the pool. Once unpredictable, always unpredictable. –  David Schwartz Apr 30 '12 at 10:33
add comment

Let me supplement the other answers by explaining, in some level of detail, how a PRNG with an entropy pool works. This is a bit of an oversimplification, as the current Linux implementation uses multiple pools. But it should help give you the basic idea of how the scheme works.

First, it contains three key parts:

  1. An entropy pool. This is basically just an array of bytes. A key goal of the system is to ensure an attacker does not know these bytes.

  2. A PRNG. This is an algorithmic component that operates on the entropy pool to produce random output.

  3. A collection of entropy probes. These 'mine' randomness from things like network and disk activity and add them to the entropy pool.

The PRNG "draws off" the entropy pool. The exact algorithm is complicated, but the basic idea is that it performs a cryptographically secure hash operation on the pool, outputs some of the hash, and mixes some of the hash back into the pool. (In the current Linux code, it actually uses two SHA1 operations.)

The probes "fill up" the entropy pool. The exact algorithm is even more complicated (twisted GFSR), but the basic idea is that the pool is mixed around and then various information from the probes is XORed into the pool.

In addition, the system keeps a measure of how much entropy is in the pool. It assumes that producing random output "depletes" the pool and that adding entropy "fills" the pool. There is a theoretical sense in which this is true, but effectively it doesn't matter.

For example, assume a 2,048 byte pool and an attacker who knows nothing about the contents of the pool. And then suppose he sees 8 bytes of output from the pool. In theory, that rules out all but 1 in 2^64 possible initial conditions and leaves only those that would produce those exact 8 bytes. But there is no known, or even conceivable, way an attacker could use that information.

With no additional entropy added and with 1GB of output from the PRNG, an attacker has all the information he needs to figure out the pool's initial condition and predict the next output from the pool. The problem is, there is no known method of doing that other than trying all 2^(8*2048) possible initial conditions.

For practical purposes, there are only two attacks possible:

  1. Guess the added contents of the pool. This fails if there are more than, say, 128-bits of unknown data mixed into the pool An attacker cannot try 2^128 or more combinations.

  2. Guess the contents of the pool at some later point. But this requires guessing the entire pool.

In sum, unless there's a defect in the algorithm, output from the pool doesn't reveal useful information about the contents of the pool. So long as an attacker cannot predict or guess all the information mixed into the pool up until the point you drew off the pool, he cannot predict what will come out of the pool. (Assuming he can't look inside the pool itself, of course!)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.