7.1.2. The /dev/random Device

Several versions of the UNIX operating system provide a kernel-resident random number generator. Some of these generators use events captured by the Kernel during normal system operation.

For example, on some versions of Linux, the generator consists of a random pool of 512 bytes represented as 128 words of 4 bytes each. When an event occurs, such as a disk drive interrupt, the time of the event is XOR'ed into the pool, and the pool is stirred via a primitive polynomial of degree 128. The pool itself is treated as a ring buffer, with new data being XOR'ed (after stirring with the polynomial) across the entire pool.

Each call that adds entropy to the pool estimates the amount of likely true entropy the input contains. The pool itself contains a accumulator that estimates the total over all entropy of the pool.

Input events come from several sources, as listed below. Unfortunately, for server machines without human operators, the first and third are not available, and entropy may be added slowly in that case.

1. Keyboard interrupts. The time of the interrupt and the scan code are added to the pool. This in effect adds entropy from the human operator by measuring inter-keystroke arrival times.

2. Disk completion and other interrupts. A system being used by a person will likely have a hard-to-predict pattern of disk accesses. (But not all disk drivers support capturing this timing information with sufficient accuracy to be useful.)

3. Mouse motion. The timing and mouse position are added in.

When random bytes are required, the pool is hashed with SHA-1 [SHA*] to yield the returned bytes of randomness. If more bytes are required than the output of SHA-1 (20 bytes), then the hashed output is stirred back into the pool and a new hash is performed to obtain the next 20 bytes. As bytes are removed from the pool, the estimate of entropy is correspondingly decremented.

To ensure a reasonably random pool upon system startup, the standard startup and shutdown scripts save the pool to a disk file at shutdown and read this file at system startup.

There are two user-exported interfaces. /dev/random returns bytes from the pool but blocks when the estimated entropy drops to zero. As entropy is added to the pool from events, more data becomes available via /dev/random. Random data obtained from such a /dev/random device is suitable for key generation for long term keys, if enough random bits are in the pool or are added in a reasonable amount of time.

/dev/urandom works like /dev/random; however, it provides data even when the entropy estimate for the random pool drops to zero. This may be adequate for session keys or for other key generation tasks for which blocking to await more random bits is not acceptable. The risk of continuing to take data even when the pool's entropy estimate is small in that past output may be computable from current output, provided that an attacker can reverse SHA-1. Given that SHA-1 is designed to be non-invertible, this is a reasonable risk.

To obtain random numbers under Linux, Solaris, or other UNIX systems equipped with code as described above, all an application has to do is open either /dev/random or /dev/urandom and read the desired number of bytes.

(The Linux Random device was written by Theodore Ts'o. It was based loosely on the random number generator in PGP 2.X and PGP 3.0 (aka PGP 5.0).)