Hardware random number generator

This SSL Accelerator computer card uses a hardware random number generator to generate cryptographic keys to encrypt data sent over computer networks.

In computing, a hardware random number generator (TRNG, True Random Number Generator) is an apparatus that generates random numbers from a physical process, rather than a computer program. Such devices are often based on microscopic phenomena that generate low-level, statistically random "noise" signals, such as thermal noise, the photoelectric effect, and other quantum phenomena. These processes are, in theory, completely unpredictable, and the theory's assertions of unpredictability are subject to experimental test. A hardware random number generator typically consists of a transducer to convert some aspect of the physical phenomena to an electrical signal, an amplifier and other electronic circuitry to increase the amplitude of the random fluctuations to a measurable level, and some type of analog to digital converter to convert the output into a digital number, often a simple binary digit 0 or 1. By repeatedly sampling the randomly varying signal, a series of random numbers is obtained.

The main application for electronic hardware random number generators is in cryptography, where they are used to generate random cryptographic keys to transmit data securely. They are widely used in Internet encryption protocols such as Secure Sockets Layer (SSL).

Random number generators can also be built from "random" macroscopic processes, using devices such as coin flipping, dice, roulette wheels and lottery machines. The presence of unpredictability in these phenomena can be justified by the theory of unstable dynamical systems and chaos theory. Even though macroscopic processes are deterministic under Newtonian mechanics, the output of a well-designed device like a roulette wheel cannot be predicted in practice, because it depends on the sensitive, micro-details of the initial conditions of each use.

Although dice have been mostly used in gambling, and in more recent times as "randomizing" elements in games (e.g. role playing games), the Victorian scientist Francis Galton described a way to use dice to explicitly generate random numbers for scientific purposes in 1890.[1]

Hardware random number generators generally produce a limited number of random bits per second. In order to increase the data rate, they are often used to generate the "seed" for a faster Cryptographically secure pseudorandom number generator, which then generates the pseudorandom output sequence.

Uses

Unpredictable random numbers were first investigated in the context of gambling, and many randomizing devices such as dice, shuffling playing cards, and roulette wheels, were first developed for such use. Fairly produced random numbers are vital to electronic gambling and ways of creating them are sometimes regulated by governmental gaming commissions.

Random numbers are also used for non-gambling purposes, both where their use is mathematically important, such as sampling for opinion polls, and in situations where fairness is approximated by randomization, such as selecting jurors and military draft lotteries.

Cryptography

The major use for hardware random number generators is in the field of data encryption, for example to create random cryptographic keys to encrypt data. They are a more secure alternative to pseudorandom number generators (PRNGs), software programs commonly used in computers to generate "random" numbers. PRNGs use a deterministic algorithm to produce numerical sequences. Although these pseudorandom sequences pass statistical pattern tests for randomness, by knowing the algorithm and the conditions used to initialize it, called the "seed", the output can be predicted. Because the sequence of numbers produced by a PRNG is predictable, data encrypted with pseudorandom numbers is potentially vulnerable to cryptanalysis. Hardware random number generators produce sequences of numbers that are not predictable, and therefore provide the greatest security when used to encrypt data.

Early work

One early way of producing random 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, perhaps combined with mechanical agitation, and use some method to withdraw balls from the mixing chamber (U.S. Patent 4,786,056). This method gives reasonable results in some senses, but the random numbers generated by this means are expensive. The method is inherently slow, and is unusable in most automated situations (i.e., with computers).

On 29 April 1947, RAND Corporation began generating random digits with an "electronic roulette wheel", consisting of a random frequency pulse source of about 100,000 pulses per second gated once per second with a constant frequency pulse and fed into a five-bit binary counter. Douglas Aircraft built the equipment, implementing Cecil Hasting’s suggestion (RAND P-113)[2] for a noise source (most likely the well known behavior of the 6D4 miniature gas thyratron tube, when placed in a magnetic field[3]). Twenty of the 32 possible counter values were mapped onto the 10 decimal digits and the other 12 counter values were discarded.[4]

The results of a long run from the RAND machine, carefully filtered and tested, were converted into a table, which was published in 1955 in the book A Million Random Digits with 100,000 Normal Deviates. The RAND table was a significant breakthrough in delivering random numbers because such a large and carefully prepared table had never before been available. It has been a useful source for simulations, modeling, and even for deriving the arbitrary constants in cryptographic algorithms to demonstrate that the constants had not been selected for (in B. Schneier’s words) "nefarious purpose(es)." Khufu and Khafre do this, for example.[5] See: Nothing up my sleeve numbers.

Physical phenomena with quantum-random properties

There are two fundamental sources of practical quantum mechanical physical randomness: quantum mechanics at the atomic or sub-atomic level and thermal noise (some of which is quantum mechanical in origin). Quantum mechanics predicts that certain physical phenomena, such as the nuclear decay of atoms, are fundamentally random and cannot, in principle, be predicted (for a discussion of empirical verification of quantum unpredictability, see Bell test experiments). And, because we live at a non-zero temperature, every system has some random variation in its state; for instance, molecules of gases composing air are constantly bouncing off each other in a random way (see statistical mechanics.) This randomness is a quantum phenomenon as well (see phonon).

Because the outcome of quantum-mechanical events cannot in principle be predicted, they are the ‘gold standard’ for random number generation. Some quantum phenomena used for random number generation include:

Physical phenomena without quantum-random properties

Thermal phenomena are easier to detect. They are (somewhat) vulnerable to attack by lowering the temperature of the system, though most systems will stop operating at temperatures low enough to reduce noise by a factor of two (e.g., ~150 K). Some of the thermal phenomena used include:

Another variable physical phenomenon that is easy to measure is clock drift.

In the absence of quantum effects or thermal noise, other phenomena that tend to be random, although in ways not easily characterized by laws of physics, can be used. When several such sources are combined carefully (as in, for example, the Yarrow algorithm or Fortuna CSPRNGs), enough entropy can be collected for the creation of cryptographic keys and nonces, though generally at restricted rates. The advantage is that this approach needs, in principle, no special hardware. The disadvantage is that a sufficiently knowledgeable attacker can surreptitiously modify the software or its inputs, thus reducing the randomness of the output, perhaps substantially. The primary source of randomness typically used in such approaches is the precise timing of the interrupts caused by mechanical input/output devices, such as keyboards and disk drives, various system information counters, etc.

This last approach must be implemented carefully and may be subject to attack if it is not. For instance, the forward-security of the generator in Linux 2.6.10 kernel could be broken with 264 or 296 time complexity.[8] The random number generator used for cryptographic purposes in an early version of the Netscape browser was certainly vulnerable (and was promptly changed).

One approach in using physical randomness is to convert a noise source into a random bit sequence in a separate device that is then connected to the computer through an I/O port. The acquired noise signal is amplified, filtered, and then run through a high-speed voltage comparator to produce a logic signal that alternates states at random intervals. At least in part, the randomness produced depends on the specific details of the 'separate device'. Care must also always be taken when amplifying low-level noise to keep out spurious signals, such as power line hum and unwanted broadcast transmissions, and to avoid adding bias during acquisition and amplification. In some simple designs, the fluctuating logic value is converted to an RS-232 type signal and presented to a computer’s serial port. Software then sees this series of logic values as bursts of "line noise" characters on an I/O port. More sophisticated systems may format the bit values before passing them into a computer.

Another approach is to feed an analog noise signal to an analog to digital converter, such as the audio input port built into most personal computers. The digitized signal may then be processed further in software to remove bias. However, digitization is itself often a source of bias, sometimes subtle, so this approach requires considerable caution and care.

Some have suggested using digital cameras, such as webcams, to photograph chaotic macroscopic phenomena. A group at Silicon Graphics imaged Lava lamps to generate random numbers (U.S. Patent 5,732,138). One problem was determining whether the chaotic shapes generated were actually random — the team decided that they are in properly operating Lava lamps. Other chaotic scenes could be employed, such as the motion of streamers in a fan air stream or, probably, bubbles in a fish tank (fish optional). The digitized image will generally contain additional noise, perhaps not very random, resulting from the video to digital conversion process. A higher quality device might use two sources and eliminate signals that are common to both — depending on the sources and their physical locations, this reduces or eliminates interference from outside electric and magnetic fields. This is often recommended for gambling devices, to reduce cheating by requiring attackers to exploit bias in several "random bit" streams.

Clock drift

Main article: Clock drift

There are several ways to measure and use clock drift as a source of randomness.

The Intel 82802 Firmware Hub (FWH) chip included a hardware RNG[9] using two free running oscillators, one fast and one slow. A thermal noise source (non-commonmode noise from two diodes) is used to modulate the frequency of the slow oscillator, which then triggers a measurement of the fast oscillator. That output is then debiased using a von Neumann type decorrelation step (see below). The output rate of this device is somewhat less than 100,000 bit/s. This chip was an optional component of the 840 chipset family that supported an earlier Intel bus. It is not included in modern PCs.

All VIA C3 microprocessors have included a hardware RNG on the processor chip since 2003. Instead of using thermal noise, raw bits are generated by using four freerunning oscillators which are designed to run at different rates. The output of two are XORed to control the bias on a third oscillator, whose output clocks the output of the fourth oscillator to produce the raw bit. Minor variations in temperature, silicon characteristics, and local electrical conditions cause continuing oscillator speed variations and thus produce the entropy of the raw bits. To further ensure randomness, there are actually two such RNGs on each chip, each positioned in different environments and rotated on the silicon. The final output is a mix of these two generators. The raw output rate is tens to hundreds of megabits per second, and the whitened rate is a few megabits per second. User software can access the generated random bit stream using new non-privileged machine language instructions.

A software implementation of a related idea on ordinary hardware is included in CryptoLib,[10] a cryptographic routine library. The algorithm is called truerand. Most modern computers have two crystal oscillators, one for the real-time clock and one for the primary CPU clock; truerand exploits this fact. It uses an operating system service that sets an alarm, running off the real-time clock. One subroutine sets that alarm to go off in one clock tick (usually 1/60th of a second). Another then enters a while loop waiting for the alarm to trigger. Since the alarm will not always trigger in exactly one tick, the least significant bits of a count of loop iterations, between setting the alarm and its trigger, will vary randomly, possibly enough for some uses. Truerand doesn't require additional hardware, but in a multi-tasking system great care must be taken to avoid non-randomizing interference from other processes (e.g., in the suspension of the counting loop process as the operating system scheduler starts and stops assorted processes).

Dealing with bias

The bit-stream from such systems is prone to be biased, with either 1s or 0s predominating. There are two approaches to dealing with bias and other artifacts. The first is to design the RNG to minimize bias inherent in the operation of the generator. 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 often use this method. Even then, the numbers generated are usually somewhat biased.

Limitation: This bias is only observed in case of uniform type random number generator. There are other types of random number generation method, and the most common way is exponential distribution. This distribution was proofed in the discussion of dice rollings. Once the number of dice rolling between the same dice number, can be measured, it is the exponential distribution: P(x)= (1/6)*(5/6)^x In such case, the generated random number is free from the bias problem.

Software whitening

Main article: Randomness extractor

A second approach to coping with bias is to reduce it after generation (in software or hardware). Even if the above hardware bias reduction steps have been taken, the bit-stream should still be assumed to contain bias and correlation. There are several techniques for reducing bias and correlation, often called "whitening" algorithms, by analogy with the related problem of producing white noise from a correlated signal. There is another way, the dynamic-statics test, which makes a statics randomness check in each random number block dynamically. This can be done usably in a short time, 1 gigabyte per second or more. In this method, if one block shall be determined as a doubtful one, the block is disregarded and canceled. This method is requested in the draft of ANSI(X9F1).

John von Neumann invented a simple algorithm to fix simple bias and reduce correlation. It considers bits two at a time, taking one of three actions: when two successive bits are equal, they are discarded; a sequence of 1,0 becomes a 1; and a sequence of 0,1 becomes a zero. It thus represents a falling edge with a 1, and a rising edge with a 0. This eliminates simple bias, and is easy to implement as a computer program or in digital logic. This technique works no matter how the bits have been generated. It cannot assure randomness in its output, however. What it can do (with significant numbers of discarded bits) is transform a biased random bit stream into an unbiased one.

Another technique for improving a near random bit stream is to exclusive-or the bit stream with the output of a high-quality cryptographically secure pseudorandom number generator such as Blum Blum Shub or a strong stream cipher. This can improve decorrelation and digit bias at low cost; it can be done by hardware, such as an FPGA, which is faster than doing it by software.

A related method which reduces bias in a near random bit stream is to take two or more uncorrelated near random bit streams, and exclusive or them together. Let the probability of a bit stream producing a 0 be 1/2 + e, where −1/2 ≤ e ≤ 1/2. Then e is the bias of the bitstream. If two uncorrelated bit streams with bias e are exclusive-or-ed together, then the bias of the result will be 2e². This may be repeated with more bit streams (see also the Piling-up lemma).

Some designs apply cryptographic hash functions such as MD5, SHA-1, or RIPEMD-160 or even a CRC function to all or part of the bit stream, and then use the output as the random bit stream. This is attractive, partly because it is relatively fast compared to some other methods, but depends entirely on qualities in the hash output for which there may be little theoretical basis.

Many physical phenomena can be used to generate bits that are highly biased, but each bit is independent from the others. A Geiger counter (with a sample time longer than the tube recovery time) or a semi-transparent mirror photon detector both generate bit streams that are mostly "0" (silent or transmission) with the occasional "1" (click or reflection). If each bit is independent from the others, the Von Neumann strategy generates one random, unbiased output bit for each of the rare "1" bits in such a highly biased bit stream. Whitening techniques such as the Advanced Multi-Level Strategy (AMLS)[11] can extract more output bits – output bits that are just as random and unbiased – from such a highly biased bit stream.[12]

PRNG with periodically refreshed random key

Other designs use what are believed to be true random bits as the key for a high quality block cipher algorithm, taking the encrypted output as the random bit stream. Care must be taken in these cases to select an appropriate block mode, however. In some implementations, the PRNG is run for a limited number of digits, while the hardware generating device produces a new seed.

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:

Problems

It is very easy to misconstruct hardware or software devices which attempt to generate random numbers. Also, most 'break' silently, often producing decreasingly random numbers as they degrade. A physical example might be the rapidly decreasing radioactivity of the smoke detectors mentioned earlier. Failure modes in such devices are plentiful and are complicated, slow, and hard to detect.

Because many entropy sources are often quite fragile, and fail silently, statistical tests on their output should be performed continuously. Many, but not all, such devices include some such tests into the software that reads the device.

Just as with other components of a cryptography system, a software random number generator should be designed to resist certain attacks. Defending against these attacks is difficult.

Estimating entropy

There are mathematical techniques for estimating the entropy of a sequence of symbols. None are so reliable that their estimates can be fully relied upon; there are always assumptions which may be very difficult to confirm. These are useful for determining if there is enough entropy in a seed pool, for example, but they cannot, in general, distinguish between a true random source and a pseudorandom generator.

Performance test

Hardware random number generators should be constantly monitored for proper operation. RFC 4086, FIPS Pub 140-2 and NIST Special Publication 800-90b[13] include tests which can be used for this. Also see the documentation for the New Zealand cryptographic software library cryptlib.

Since many practical designs rely on a hardware source as an input, it will be useful to at least check that the source is still operating. Statistical tests can often detect failure of a noise source, such as a radio station transmitting on a channel thought to be empty, for example. Noise generator output should be sampled for testing before being passed through a "whitener." Some whitener designs can pass statistical tests with no random input. While detecting a large deviation from perfection would be a sign that a true random noise source has become degraded, small deviations are normal and can be an indication of proper operation. Correlation of bias in the inputs to a generator design with other parameters (e.g., internal temperature, bus voltage) might be additionally useful as a further check. Unfortunately, with currently available (and foreseen) tests, passing such tests is not enough to be sure the output sequences are random. A carefully chosen design, verification that the manufactured device implements that design and continuous physical security to insure against tampering may all be needed in addition to testing for high value uses.

See also

References

  1. ↑ Galton, Francis (1890). "Dice for statistical experiments" (PDF). Nature 42: 13–14. doi:10.1038/042013a0. Retrieved 14 May 2014.
  2. ↑ P-113, Papers, Rand Corporation.
  3. ↑ Cobine, Curry (1947), "Electrical Noise Generators", Proceedings of the I.R.E. (September 1947): 875–9
  4. ↑ Monograph report, Rand Corporation.
  5. ↑ Schneier, Bruce, Applied Cryptography.
  6. ↑ 6D4 electron tube reference, Sylvania.
  7. ↑ Marandi, A.; N. C. Leindecker; K. L. Vodopyanov; R. L. Byer (2012). "All-optical quantum random bit generation from intrinsically binary phase of parametric oscillators". Opt. Express 20: 19322–19330. doi:10.1364/OE.20.019322.
  8. ↑ Analysis of the Linux Random Number Generator (PDF), IACR
  9. ↑ Intel Corporation Intel® 810 Chipset Design Guide, June 1999 Ch. 1.3.5, p. 1-10.
  10. ↑ Lacy, J.B.; D.P. Mitchell, W.M. Schell (1993). "CryptoLib: Cryptography in Software" (PDF). Proc. 4th USENIX Security Symp.: 1–17.
  11. ↑ Peres, Yuval (March 1992), "Iterating Von Neumann's Procedure for Extracting Random Bits", Annals of Statistics 20 (1): 590–97, doi:10.1214/aos/1176348543.
  12. ↑ Crowley, Paul, Generating random binary data from Geiger counters, Cipher Goth.
  13. ↑ Elaine Barker and John Kelsey, Recommendation for the Entropy Sources Used for Random Bit Generation, NIST SP 800-90b

General references

External links

Code