SunSoft Tech Conf '96
Menlo Park CA, April 29, 1996
High quality random numbers are critical to cryptographic systems and protocols which may use them for key generation, authentication and replay protection. Poorly generated random numbers can lead to weak keys, protocol failure, and ultimately to front-page news [1]. This paper describes a mechanism for generating cryptographic-quality random numbers based on the varying state of the entire computer system sampled over an extended period of time. Application programs obtain the random numbers from the generator by reading from a special file, /dev/random.
The objective of CryptoRand is to provide a general-purpose cryptographic-quality random number generator for use by Unix applications.
Cryptographic-quality random numbers are:
The generator must have a minimum of dependencies on the configuration of the system on which it is installed or the manner in which the system is used. In particular, there are a number of schemes which rely on various I/O devices as a source of randomness: disk, keyboard, mouse, audio/video inputs, etc. None of these schemes are acceptable because none of these devices are guaranteed to be present on a particular system. Even when a keyboard and mouse are present, they still might not be usable if the system is unattended.
The generator consists of a user-mode daemon process which is started at boot-time and never terminates. Figure 1 shows the basic architecture of the generator. The daemon continuously samples the state of the system and generates random numbers which are made available to the application via a FIFO special file.
Traditional software random number generators are implemented as library functions which are called by the application whenever the next number is needed. This approach is undesirable for generating cryptographic quality random numbers because it requires that whatever resources are required by the generator be available at (or near) the instant the application requests the numbers. This would be a considerable handicap for a system that depends on system state as a source of entropy. Taking a single snapshot of the system state, or even taking several samples over a short period of time, increases the chances that an attacker may be able to predict or influence enough of the state to reduce the search space necessary for a brute-force attack on (for example) the encryption key that was derived from the random numbers. It is only by collecting entropy from a large number of samples of the system state taken over an extended period of time that we can be reasonably assured that the results of the generator will be truly unpredictable even under a determined attack by a non-root user.
The choice to implement the generator as a user-mode daemon was made after carefully considering the possible advantages to a kernel-based driver weighed against the general desire to minimize the amount and complexity of code added to the kernel. The principal advantage of a kernel-based generator is the ability to snoop on physical I/O devices to derive entropy from variations in timing. Since these devices are not guaranteed to be present in the system (see \xa4 1.) there is insufficient justification for a kernel-based generator.
The application interface to the generator utilizes a special file, /dev/random, rather than a traditional API. Advantages include:
/usr/bin/od -tu4 -An -N4 /dev/random)
if (stat(``/dev/random'', &sb))...).
Some features of the interface that are worthy of note are:
read() will block until usable data is available (will not return weak numbers)
read() may return fewer than the number of bytes requested (caller must loop)
poll() and select()
The daemon generates random numbers by sampling physical memory, swap space, system statistics and the high-resolution clock. It whitens the samples using a cryptographic hash function and it measures the samples to estimate the amount of entropy obtained from each sample. Output is generated only when sufficient entropy has been collected to support it.
The generator continues to sample the system state even when there is no demand from an application for new random number. The effect is to maximize the distribution (in time) of samples from which the internal pool derives its entropy. Since the entropy accumulates in the pool, this forces an attacker to not only know the state of the system at the time a random number was generated, but the attacker must also know the state as it was at thousands of distinct points of time in the past.
CryptoRand is installed by pkgadd which installs the following files:
d
d
d
When the system is booted, the rc script starts the daemon as the system enters init level 2. The daemon makes sure that /dev/random is a FIFO special file, removing and/or creating it as necessary. The FIFO is placed in the /dev/ directory for compatibility with other implementations.[10][20]
There is no configuration.
The daemon consists of three parts: init(), generate(), and bleed(). It keeps an internal pool of entropy in an array, pool[].
The init() function is called to initialize the daemon. It is responsible for collecting enough entropy into pool[] to begin generating random numbers. This can take a long time, so to improve performance, and to maximize the period of time over which the entropy was collected, the file /var/tmp/cryptorand is used to prime the pool with random data from the previous invocation of the daemon. If this file does not exist or is not the correct size or does not pass reasonable statistical tests, then the initial entropy is slowly collected from swap space and memory.
The generator() function does all the work of sampling the system state, estimating the entropy, updating the entropy pool, and generating output. generator() calls one_round() repeatedly until it is estimated that enough entropy has been collected to generate output at which time the digest is written to the FIFO and usleep() is called. The purpose of sleeping is to allow the system state a reasonable chance to change between samples.
The heart of the generator algorithm is the one_round() function shown in Figure 2. Each time it is invoked, it takes the low-order 32 bits from the entropy pool and uses that to select a block of physical memory. The block is processed with MD5.[13]
The low-order bit of the MD5 context buffer is ``peeked'' at and used as a parity bit for the block (but the context is not closed). The parity bit is compared with a saved copy of the parity bit that was computed the last time the same block of memory was sampled. If the parity bits are different, then it is known that the state of this block has changed since the last time it was sampled. (There is a 50% chance that a change in the block may be undetected by the parity. This is compensated for by weighting the entropy calculation by a factor of 2.)
The hashing process continues by processing the entire entropy pool through MD5 with the same context buffer, followed by a block of data collected from system calls such as gethrtime(). The context is then closed by calling MD5Final().
At this point the decision is made if enough entropy has been added to the pool to support generating another block of output. The entropy is estimated by counting each block that is known to have changed since it was last sampled as contributing two bits to the entropy pool (one bit per changed block divided by the 50% probability of the change being detected by the parity check). Also each time the output of gethrtime() is included is counted as contributing a small amount of entropy (about 0.1 bits due to variations in the time required to compute the digests due to variations in servicing of interrupts). If the total is equal to or greater than the number of bits in an MD5 digest, then the digest is returned to be output, otherwise the digest replaces the oldest data in the entropy pool and one_round() will get called again. Because at least some entropy is contributed by each round, the loop is guaranteed to terminate.
The bleed() function slowly reads data from /dev/random and writes it into /var/tmp/cryptorand (treating it as a ring). This process serves two purposes: (1) to prevent the generator from being idle for extended periods and wasting the entropy that could have been collected from sampling the system state, and (2) to keep a fresh pool of random data available in case the system reboots and the daemon is restarted.
The bleed function reads from the front of the FIFO buffer. Those are the oldest numbers. As the FIFO empties, the generator refills it with fresh numbers. In this way, the stale numbers in the buffer are continually replaced with fresh numbers.
The exact bleed rate must be carefully chosen to balance performance impact of throwing away generator output versus the risk due to poor temporal diversity of the samples. bleed() is called from a timer signal which is set to a random value in order to reduce the risk of the samples synchronizing to other system events.
There are three basic performance questions that pertain to cryptorand:
The rate that numbers can be generated is affected by (1) the amount of sleep between rounds, and (2) how many rounds are required to find enough blocks of memory that have changed. On a lightly loaded system, many rounds may be required to find enough changed blocks. In the worst case, no changed blocks will be found and the state taken from system calls will be the only source of entropy. If the system calls contribute 0.1 bits per round, then a maximum of 1280 rounds would be required to generate 128 bits of output.
The amount of CPU utilized when there are no applications consuming numbers is determined by the bleed rate. This can be made arbitrarily small by using a low bleed rate. The bleed timer can be set for a small value (a few hundred milliseconds) whenever an application consumes one or more numbers, then be exponentially backed off as long as no more numbers are consumed.
The primary use of kernel memory is the FIFO buffer. The FIFO will be full whenever the generator is caught up with the demand. A FIFO buffer holds about 9 KB.