Random Number in Linux

Question

In linux /dev/random is based of "environmental variables" and /dev/urandom is based off an algorithm and the time. My questions are:

Where does /dev/random gather these variables from.

And if you have two machines set to the same time (down to the millisecond-if possible) and have the same speed, OS, etc...and take a hexdump of /dev/urandom with X number of bytes, will they have the same exact value (because the time was the same)?

Answer 1

Where does /dev/urandom gather these variables from.

Everywhere it can, primarily interrupt timing. For example, if you have a network card, the precise time a packet arrives will be affected by the offset between the crystal timebase on the network card and the crystal timebase that clocks the CPU. The offset between two quartz crystal oscillators is affected by microscopic zone temperature variations that are believed to be truly physically random.

If you have a rotating disk, the time reads will complete is dependent on the speed the disk rotates. This is affected by turbulent shear force between the disk surface and the air inside the disk assembly. While this is not believed to be true physical randomness, it is entirely unpredictable or repeatable by any known mechanism.

And if you have two machines set to the same time (down to the millisecond-if possible) and have the same speed, OS, etc...and take a hexdump of /dev/random with X number of bytes, will they have the same exact value (because the time was the same)?

Well, millisecond wouldn't be nearly good enough. You'd need to be at the same level the CPU measures time -- billionths of a second. But, of course, that is how it must be. Otherwise, if you saw the state of one machine, you could know with 100% certainty that the other machine could not have that same state. And since the state is supposed to be random, you should not be able to look at any other machine and know anything about the state with 100% certainty. So long as the odds this could be accomplished are sufficiently low (say, less than one in 2^100), then it's perfectly fine.

Even if you roll two dice, each with a billion sides, they may come up the same. Provided they only do so once every billion times, then that's as it should be.

Answer 2

Take a look at urandom's manual, specifically the description:

When read, the /dev/random device will only return random bytes within the estimated number of bits of noise in the entropy pool. /dev/random should be suitable for uses that need very high quality randomness such as one-time pad or key generation. When the entropy pool is empty, reads from /dev/random will block until additional environmental noise is gathered.

A read from the /dev/urandom device will not block waiting for more entropy. As a result, if there is not sufficient entropy in the entropy pool, the returned values are theoretically vulnerable to a cryptographic attack on the algorithms used by the driver. Knowledge of how to do this is not available in the current unclassified literature, but it is theoretically possible that such an attack may exist. If this is a concern in your application, use /dev/random instead.

Unfortunately I can't really answer your second question, I'm use someone else can, though my guess would be that it'd be very hard to get the exact same on both machines.

Answer 3

In linux /dev/urandom is based of "environmental variables" and /dev/random is based off an algorithm and the time.

Both assumptions are false.

According to random(4) - Linux man page¹, /dev/random gathers environmental noise from device drivers and other sources into an entropy pool.

An example of such a device is the mouse.² Try executing

head -c 1024 /dev/random | base64

to clear the entropy pool (abort after a couple of seconds) and then

head -c 40 /dev/random | base64

to read 40 bytes from /dev/random. Do nothing and observe that head stalls a log time, since there's no new entropy in the pool.

Abort, then execute

head -c 40 /dev/random | base64

again. This time, mouse your mouse quickly from left to right. head will finish its task quickly.

Again, according to random(4) - Linux man page, /dev/urandom uses the same entropy pool, but it does not block. If the entropy pool isn't big enough, it falls back to a pseudorandom number generator (PRNG) to create more (pseudo-)random output.

---

¹ Actual behavior might vary from distro to distro.

² Example applies to Ubuntu 12.04. Other distros might differ.