Pseudo Random Generator is not initialized from the (entropy pool)?

Question

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 :)

Answer 1

/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

Answer 2

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!)

Answer 3

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:

• Is a rand from /dev/urandom secure for a login key?

• Feeding /dev/random entropy pool?

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.