Encyclopedia > Hardware random number generator

Article Content

Hardware random number generator

Most so-called "random numbers" generated by computers are usually pseudo-random numbers generated by an arithmetic algorithm.

There are several different informal definitions of randomness, usually based on either a lack of discernible patterns, or their unpredictability. Although the output from pseudo-random number generators may appear to lack a discernible pattern, they always have a pattern -- the pattern given by the algorithm that generates them, and its starting state. Nor are they unpredictable. Given the knowledge of the original state of the generator, and its algorithm, they are totally predictable.

As John von Neumann put it, "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin".

This article is about the attempts to generate and use "random numbers" generated from apparently random physical phenomena. It is a fundamentally difficult problem, and in practice questions about randomness generally degenerate into 'can I use this not really random series in my application without getting too badly burned?'. This is, truly, an even harder problem.

Table of contents

1 Uses of physically generated "random" numbers

2 Early attempts to generate true random numbers

3 Physical phenomena used for random number generation

4 Cleaning up the bit-stream

5 Estimating the size of the entropy pool

6 Software implementation of random number generators from observed events

7 Problems

8 Checking the performance of hardware random number generators

9 Controversial random number phenomena

10 External links

11 Random number services on the net

12 Manufacturers of random number generator devices

Uses of physically generated "random" numbers

'Unpredictable' random numbers were first used in gambling, and many randomizing devices such as dice, shuffling playing cards, and roulette wheels, were first developed for use in gambling.

'Random' numbers are also used for serious purposes such as draft lotteries, where "fairness" is approximated by randomization.

More recently developed uses of unpredictable random numbers include their uses in statistics and cryptography. They have occasional uses in physics (such as noise resonance studies), and operations research.

The big industrial use of real random numbers is to make unpredictable keys for encryption. Mere random munbers are not sufficient because the choice of a key (or other cryptographically required random value) must be maximally difficult for an attacker to predict. Accordingly, published random sequences are poor choices as are such sequences as the digits in an irrational or even trancendental number such as pi, or e, or phi. Since most keys are a few thousand bits at most, simple slow random number generators serve well -- if they are actually random. This use is important-enough that many designers believe every computer should have a way to generate true random numbers.

True random numbers are absolutely required for the only provably unbreakable encryption -- the one-time pads. Furthermore, those random sequences cannot be reused and must never become available to any attacker. See Venona for an example of what happens when these requirements are violated.

Cheap random numbers (if any can be made available) are handy for erasing files, and similar technical tasks.

It is important to understand (and so I repeat it) that, in cryptography, the random bits generally need to be not only unpredictable, but also secret: public or third-party sources of random values, or random values computed from publicly observable phenomena, are almost never of any use for cryptographic purposes.

Early attempts to generate true random numbers

One standard way of producing early radom numbers was by a variation of the same machines used to play keno or select lottery numbers. Basically, these mixed numbered ping-pong balls with blown air, and used some method to withdraw balls from the mixing chamber. This method gives reasonable results, but the random numbers generated by this means are very expensive.

[early random number tables- to be written]

An important 20th century work was the RAND Corporation million number table. It was produced by an electronic simulation of a roulette wheel attached to a computer. The RAND table was a significant break-through in delivering random numbers because such a large table had never before been available.

Physical phenomena used for random number generation

Many modern random number generators attempt to use some form of quantum-mechanical noise, widely considered the gold standard of randomness, but not yet proved to be so.

People have used a radiation source (some from a smoke-alarm) to drive Geiger counters attached to a PC, as at HotBits (http://www.fourmilab.ch/hotbits/). This site claims to deliver private random numbers on demand.

They have also measured atmospheric noise with a radio receiver attached to a PC, as at random.org (http://www.random.org). This site claims to deliver private random numbers on demand.

Optical quantum random number generators have been prototyped. A group at Silicon Graphics[?] even used digital cameras to watch Lava Lamps[?] (TM) to generate random numbers.

A convenient form of hardware random number generator uses either thermal or quantum-mechanical noise to provide a random voltage source. The favored source of quantum mechanical noise is Johnston noise, usually generated from a reverse-biased zener diode. The thermal noise from a resistor could also be amplified and used.

The generated noise signal is amplified and filtered, then run through a high-speed voltage comparator to make a logic signal that alternates states at random intervals.

In some simple designs, this logic value is converted to an RS-232 level signal and sent directly to a computer's serial port. Software then sees this series of logic values as bursts of "line noise[?]" characters on its I/O port.

More sophisticated systems may format the bit values before passing them to the computer. Because of problems with bias (see below) analog to digital converters are rarely used.

The bit-stream from such a system is prone to be biased, with 1s or 0s predominating. One method to correct this feeds back the generated bit stream, filtered by a low-pass filter, to adjust the bias of the generator. By the central limit theorem, the feedback loop will tend to be well-adjusted almost all the time. Ultra-high speed random number generators use this method. Even then, the numbers generated are somewhat biased.

A quality device might use two diodes and eliminate signals that are common to both - this eliminates interference from outside electric and magnetic fields. This is recommended for gambling devices, to prevent cheating.

The Intel RNG (supplied in their board-level chip sets for a PC), uses most of the above tricks and adds another: The non-common-mode noise from two diodes controls a voltage-controlled oscillator, which clocks bits from a rapid oscillator (the new trick), which then go through a von Neumann decorrelator.

A completely unrelated method uses two uncoupled oscillators, and counts events in one from the time-base of another. This method has been used on PCs to generate pure-software true-random number generators. It requires a PC with two clock crystals, one for the real-time clock, and another for the processor. The program loops, counting the time that one of the bits of the counter of the real-time clock is a 1. The least significant bit of the loop-counter is quite random.

Cleaning up the bit-stream

Even after all these measures have been taken, the bit-stream should still be assumed to contain bias and correlation.

John von Neumann invented a simple algorithm to fix simple bias, and reduce correlation: it considers bits two at a time. When two successive bits are the same, they are not used as a random bit. A sequence of 1,0 becomes a 1. A sequence of 0,1 becomes a zero. This eliminates simple bias, and is easy to implement in a computer program or digital logic. It reduces the bit rate available by a factor of four, on average. This technique works no matter how the bits have been generated.

One of the more popular methods of improving a random bit stream is to exclusive-or the bit stream with the output of a high-quality cryptographically secure pseudo-random number generator such as Blum Blum Shub. This can cheaply improve decorrelation and digit bias.

Another method to "improve" a random sequence is to perform data compression on it. Efficient data compression algorithms must increase the entropy (i.e. reduce the predictability) of the compressed data. This roughly means that the compressed data is more random. Although mathematically robust, many engineering types find this approach wasteful. Compression may be one of the best clean-up methods to make cryptographic keys, which tend to be small, and need to be reliably random.

Sometimes people apply cryptographic hash functions such as Yarrow[?] or a CRC to a part of the bit stream, and then use the stream of signatures as the random bit stream.

When a high-speed source of lower-quallity random digits is needed, sometimes the true random source is used to generate the seed for a pseudo random number generator. The PRNG is run for a fixed number of digits, while the hardware device generates a new seed.

Estimating the size of the entropy pool

to be written

Software implementation of random number generators from observed events

Software engineers without true random number generators often try to develop them by measuring physical events available to the software. The classic is to measure the time between key-strokes, and then take the least significant bit (or two or three) of the count as a random digit. The same approach has been applied by measuring task-scheduling, network hits, disk-head seek times and other internal events.

The method is quite risky when it uses computer-controlled events because a clever, malicious programmer might be able to predict a cryptographic key or wager by controlling the external events.

to be written -- mention:

/dev/random
/dev/urandom

Problems

It is very easy to mis-construct devices that generate random numbers. Also, they break silently, often producing decreasingly random numbers before failing.

Because they are quite fragile, and fail silently, statistical tests should be performed constantly. Many such devices build the tests into the software that reads the device.

Checking the performance of hardware random number generators

to be written

Controversial random number phenomena

The "global consciousness project (http://noosphere.princeton.edu/)" maintains TRNGs in many cities, and reported chi-square[?] fluctuations during the 9/11 attacks. This event was not controlled for power fluctuations and the like. Many researchers involved in paranormal research use random number generators in their test designs.