Hardware Random Number Generator - Using Observed Events

Using Observed Events

Software engineers without true random number generators often try to develop them by measuring physical events available to the software. An example is measuring the time between user keystrokes, and then taking the least significant bit (or two or three) of the count as a random digit. A similar approach measures task-scheduling, network hits, disk-head seek times and other internal events. One Microsoft design includes a very long list of such internal values (see the CSPRNG article).

The method is risky when it uses computer-controlled events because a clever, malicious attacker might be able to predict a cryptographic key by controlling the external events. It is also risky because the supposed user-generated event (e.g., keystrokes) can be spoofed by a sufficiently ingenious attacker, allowing control of the "random values" used by the cryptography.

However, with sufficient care, a system can be designed that produces cryptographically secure random numbers from the sources of randomness available in a modern computer. The basic design is to maintain an "entropy pool" of random bits that are assumed to be unknown to an attacker. New randomness is added whenever available (for example, when the user hits a key) and an estimate of the number of bits in the pool that cannot be known to an attacker is kept. Some of the strategies in use include:

• When random bits are requested, return that many bits derived from the entropy pool (by a cryptographic hash function, say) and decrement the estimate of the number of random bits remaining in the pool. If not enough unknown bits are available, wait until enough are available. This is the top-level design of the "/dev/random" device in Linux, written by Theodore Ts'o and used in many other Unix-like operating systems. It provides high-quality random numbers so long as the estimates of the input randomness are sufficiently cautious. The Linux "/dev/urandom" device is a simple modification which disregards estimates of input randomness, and is therefore rather less likely to have high entropy as a result.
• Maintain a stream cipher with a key and Initialization vector (IV) obtained from an entropy pool. When enough bits of entropy have been collected, replace both key and IV with new random values and decrease the estimated entropy remaining in the pool. This is the approach taken by the yarrow library. It provides resistance against some attacks and conserves hard-to-obtain entropy.