Hardware random number generator
Encyclopedia
In computing
, a hardware random number generator is an apparatus that generates random number
s from a physical process. Such devices are often based on microscopic phenomena that generate a low-level, statistically random "noise" signal, such as thermal noise or the photoelectric effect
or 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 macroscopic 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 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 pseudo-random number generators (PRNGs), software programs commonly used in computers to generate "random" numbers. PRNGs use a deterministic
algorithm
to produce numerical sequences. Although these pseudo-random 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.
Random number generators can also be built from "random" macroscopic processes, using devices such as coin flipping
, dice
, roulette
wheels and lottery machine
s. The presence of unpredictability in these phenomena can be justified by the theory of unstable dynamical system
s 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 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.
Hardware random number generators are often relatively slow, that is they 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 cryptographic PRNG
, which then generates the output sequence.
, 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 poll
s, and in situations where fairness is approximated by randomization
, such as selecting jurors and military draft lotteries
.
Random numbers are used in both symmetric and asymmetric cryptography
as a way of generating keys and for the random values used in the operation of some algorithms. Since integrity of the communication between the two parties is conditional on the continued secrecy of these keys, using a random number generator which does not have adequate randomness may be expected to compromise the security of messages.
, as a means of investigating the possibility of consciousness
-induced anomalies
in the resulting distribution, also known as micro-psychokinesis
. Meta-analyses of available data generally find very small deviations from the expected probability distribution which, while apparently suggestive of a direct effect of consciousness, may also be explainable by publication bias
.
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 . 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 5-bit binary counter. Douglas Aircraft built the equipment, implementing Cecil Hasting’s suggestion (RAND P-113) for a noise source (most likely the well known behavior of the 6D4 miniature gas thyratron tube, when placed in a magnetic field). Twenty of the 32 possible counter values were mapped onto the 10 decimal digits and the other 12 counter values were discarded.
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. See: Nothing up my sleeve number
s.
The RAND book is still in print, and remains an important source of random numbers.
.) And, because we live at a finite, non-zero temperature, every system has some random variation in its state; for instance, molecules of 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:
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
CSPRNG
s), 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 interrupt
s 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. 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 webcam
s, to photograph chaotic macroscopic phenomena. A group at Silicon Graphics
imaged Lava lamp
s to generate random numbers . 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.
as a source of randomness.
The Intel 80802 Firmware Hub chip included a hardware RNG 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, a cryptographic routine library (JB Lacy, DP Mitchell, WM Schell, CryptoLib: Cryptography in software, Proc 4th USENIX Security Symp, pg 1-17, 1993). 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).
, 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.
" 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 not used as a random bit; a sequence of 1,0 becomes a 1; and a sequence of 0,1 becomes a zero. 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 random bit stream with a frequency of 1’s different from 50% into a stream closer to that frequency.
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 function
s 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) can extract more output bits – output bits that are just as random and unbiased – from such a highly biased bit stream.
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.
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:
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 cryptosystem, a software random number generator should be designed to resist certain attacks. Defending against these attacks is difficult. See: random number generator attack
.
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 pseudo-random generator.
Pub 140-2
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.
that claims to generate actual random numbers from interrupt timing discrepancies..
Computing
Computing is usually defined as the activity of using and improving computer hardware and software. It is the computer-specific part of information technology...
, a hardware random number generator is an apparatus that generates random number
Random number
Random number may refer to:* A number generated for or part of a set exhibiting statistical randomness.* A random sequence obtained from a stochastic process.* An algorithmically random sequence in algorithmic information theory....
s from a physical process. Such devices are often based on microscopic phenomena that generate a low-level, statistically random "noise" signal, such as thermal noise or the photoelectric effect
Photoelectric effect
In the photoelectric effect, electrons are emitted from matter as a consequence of their absorption of energy from electromagnetic radiation of very short wavelength, such as visible or ultraviolet light. Electrons emitted in this manner may be referred to as photoelectrons...
or other quantum
Quantum
In physics, a quantum is the minimum amount of any physical entity involved in an interaction. Behind this, one finds the fundamental notion that a physical property may be "quantized," referred to as "the hypothesis of quantization". This means that the magnitude can take on only certain discrete...
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
Transducer
A transducer is a device that converts one type of energy to another. Energy types include electrical, mechanical, electromagnetic , chemical, acoustic or thermal energy. While the term transducer commonly implies the use of a sensor/detector, any device which converts energy can be considered a...
to convert some aspect of the physical phenomena to an electrical signal, an amplifier
Amplifier
Generally, an amplifier or simply amp, is a device for increasing the power of a signal.In popular use, the term usually describes an electronic amplifier, in which the input "signal" is usually a voltage or a current. In audio applications, amplifiers drive the loudspeakers used in PA systems to...
and other electronic circuitry to increase the amplitude of the random fluctuations to a macroscopic 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 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 pseudo-random number generators (PRNGs), software programs commonly used in computers to generate "random" numbers. PRNGs use a deterministic
Deterministic algorithm
In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states...
algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
to produce numerical sequences. Although these pseudo-random 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
Cryptanalysis
Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...
. Hardware random number generators produce sequences of numbers that are not predictable, and therefore provide the greatest security when used to encrypt data.
Random number generators can also be built from "random" macroscopic processes, using devices such as coin flipping
Coin flipping
Coin flipping or coin tossing or heads or tails is the practice of throwing a coin in the air to choose between two alternatives, sometimes to resolve a dispute between two parties...
, dice
Dice
A die is a small throwable object with multiple resting positions, used for generating random numbers...
, roulette
Roulette
Roulette is a casino game named after a French diminutive for little wheel. In the game, players may choose to place bets on either a single number or a range of numbers, the colors red or black, or whether the number is odd or even....
wheels and lottery machine
Lottery machine
A lottery machine is the machine used to draw the winning numbers for a lottery.Early lotteries were done by drawing numbers, or winning tickets, from a container...
s. The presence of unpredictability in these phenomena can be justified by the theory of unstable dynamical system
Dynamical system
A dynamical system is a concept in mathematics where a fixed rule describes the time dependence of a point in a geometrical space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a pipe, and the number of fish each springtime in a...
s and chaos theory
Chaos theory
Chaos theory is a field of study in mathematics, with applications in several disciplines including physics, economics, biology, and philosophy. Chaos theory studies the behavior of dynamical systems that are highly sensitive to initial conditions, an effect which is popularly referred to as the...
. 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
Gambling
Gambling is the wagering of money or something of material value on an event with an uncertain outcome with the primary intent of winning additional money and/or material goods...
, and in recent times as "randomizing" elements in games (e.g. role playing games), the Victorian
Victorian era
The Victorian era of British history was the period of Queen Victoria's reign from 20 June 1837 until her death on 22 January 1901. It was a long period of peace, prosperity, refined sensibilities and national self-confidence...
scientist Francis Galton
Francis Galton
Sir Francis Galton /ˈfrɑːnsɪs ˈgɔːltn̩/ FRS , cousin of Douglas Strutt Galton, half-cousin of Charles Darwin, was an English Victorian polymath: anthropologist, eugenicist, tropical explorer, geographer, inventor, meteorologist, proto-geneticist, psychometrician, and statistician...
described a way to use dice to explicitly generate random numbers for scientific purposes in 1890.
Hardware random number generators are often relatively slow, that is they 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 cryptographic PRNG
Cryptographically secure pseudorandom number generator
A cryptographically secure pseudo-random number generator is a pseudo-random number generator with properties that make it suitable for use in cryptography.Many aspects of cryptography require random numbers, for example:...
, which then generates the output sequence.
Uses
Unpredictable random numbers were first investigated in the context of gamblingGambling
Gambling is the wagering of money or something of material value on an event with an uncertain outcome with the primary intent of winning additional money and/or material goods...
, and many randomizing devices such as dice
Dice
A die is a small throwable object with multiple resting positions, used for generating random numbers...
, shuffling playing cards, and roulette
Roulette
Roulette is a casino game named after a French diminutive for little wheel. In the game, players may choose to place bets on either a single number or a range of numbers, the colors red or black, or whether the number is odd or even....
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 poll
Opinion poll
An opinion poll, sometimes simply referred to as a poll is a survey of public opinion from a particular sample. Opinion polls are usually designed to represent the opinions of a population by conducting a series of questions and then extrapolating generalities in ratio or within confidence...
s, and in situations where fairness is approximated by randomization
Randomization
Randomization is the process of making something random; this means:* Generating a random permutation of a sequence .* Selecting a random sample of a population ....
, such as selecting jurors and military draft lotteries
Selective Service Act
Selective Service Act may refer to:* Selective Service Act of 1917, or Selective Draft Act, which was passed by the Congress of the United States on May 18, 1917. It was for men to go to WWI at a young age....
.
Random numbers are used in both symmetric and asymmetric cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
as a way of generating keys and for the random values used in the operation of some algorithms. Since integrity of the communication between the two parties is conditional on the continued secrecy of these keys, using a random number generator which does not have adequate randomness may be expected to compromise the security of messages.
Uses in parapsychology
Hardware RNG based on quantum randomness (also called random event generators) find use in parapsychologyParapsychology
The term parapsychology was coined in or around 1889 by philosopher Max Dessoir, and originates from para meaning "alongside", and psychology. The term was adopted by J.B. Rhine in the 1930s as a replacement for the term psychical research...
, as a means of investigating the possibility of consciousness
Consciousness
Consciousness is a term that refers to the relationship between the mind and the world with which it interacts. It has been defined as: subjectivity, awareness, the ability to experience or to feel, wakefulness, having a sense of selfhood, and the executive control system of the mind...
-induced anomalies
Anomaly
Anomaly may refer to:-Astronomy and celestial mechanics :* In astronomy, an anomaly is a quantity measured with respect to an apsis, usually the periapsis...
in the resulting distribution, also known as micro-psychokinesis
Psychokinesis
The term psychokinesis , also referred to as telekinesis with respect to strictly describing movement of matter, sometimes abbreviated PK and TK respectively, is a term...
. Meta-analyses of available data generally find very small deviations from the expected probability distribution which, while apparently suggestive of a direct effect of consciousness, may also be explainable by publication bias
Publication bias
Publication bias is the tendency of researchers, editors, and pharmaceutical companies to handle the reporting of experimental results that are positive differently from results that are negative or inconclusive, leading to bias in the overall published literature...
.
Early work
One early way of producing random numbers was by a variation of the same machines used to play kenoKeno
Keno is a lottery or bingo gambling game often played at modern casinos, and is also offered as a game in some state lotteries. A traditional live casino keno game uses a circular glass enclosure called a "bubble" containing 80 balls which determine the ball draw result. Each ball is imprinted...
or select lottery
Lottery
A lottery is a form of gambling which involves the drawing of lots for a prize.Lottery is outlawed by some governments, while others endorse it to the extent of organizing a national or state lottery. It is common to find some degree of regulation of lottery by governments...
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 . 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 5-bit binary counter. Douglas Aircraft built the equipment, implementing Cecil Hasting’s suggestion (RAND P-113) for a noise source (most likely the well known behavior of the 6D4 miniature gas thyratron tube, when placed in a magnetic field). Twenty of the 32 possible counter values were mapped onto the 10 decimal digits and the other 12 counter values were discarded.
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
A Million Random Digits with 100,000 Normal Deviates
A Million Random Digits with 100,000 Normal Deviates is a 1955 book by the RAND Corporation. The book, consisting primarily of a random number table, was an important 20th century work in the field of statistics and random numbers...
. 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
Bruce Schneier
Bruce Schneier is an American cryptographer, computer security specialist, and writer. He is the author of several books on general security topics, computer security and cryptography, and is the founder and chief technology officer of BT Managed Security Solutions, formerly Counterpane Internet...
’s words) "nefarious purpose(es)." Khufu and Khafre
Khufu and Khafre
In cryptography, Khufu and Khafre are two block ciphers designed by Ralph Merkle in 1989 while working at Xerox's Palo Alto Research Center...
do this, for example. See: Nothing up my sleeve number
Nothing up my sleeve number
In cryptography, nothing up my sleeve numbers are any numbers which, by their construction, are above suspicion of hidden properties. They are used in creating cryptographic functions such as hashes and ciphers. These algorithms often need randomized constants for mixing or initialization purposes...
s.
The RAND book is still in print, and remains an important source of random 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 experimentsBell test experiments
The Bell test experiments serve to investigate the validity of the entanglement effect in quantum mechanics by using some kind of Bell inequality...
.) And, because we live at a finite, non-zero temperature, every system has some random variation in its state; for instance, molecules of air are constantly bouncing off each other in a random way (see statistical mechanics
Statistical mechanics
Statistical mechanics or statistical thermodynamicsThe terms statistical mechanics and statistical thermodynamics are used interchangeably...
.) This randomness is a quantum phenomenon as well (see phonon
Phonon
In physics, a phonon is a collective excitation in a periodic, elastic arrangement of atoms or molecules in condensed matter, such as solids and some liquids...
.)
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:
- Shot noiseShot noiseShot noise is a type of electronic noise that may be dominant when the finite number of particles that carry energy is sufficiently small so that uncertainties due to the Poisson distribution, which describes the occurrence of independent random events, are of significance...
, a quantum mechanical noise source in electronic circuits. The name ‘shot noise’ refers to the sound of shotgun pellets, dropped, striking a taut membrane. A simple example is a lamp shining on a photodiode. Due to the uncertainty principleUncertainty principleIn quantum mechanics, the Heisenberg uncertainty principle states a fundamental limit on the accuracy with which certain pairs of physical properties of a particle, such as position and momentum, can be simultaneously known...
, arriving photons create noise in the circuit. Collecting the noise for use poses some problems, but this is an especially simple random noise source. However, shot noise energy is not always well distributed throughout the bandwidth of interest. Gas diode and thyratron electron tubes in a crosswise magnetic field can generate substantial noise energy (10 volts or more into high impedance loads) but have a very peaked energy distribution and require careful filtering to achieve flatness across a broad spectrum
- A nuclear decay radiation source (as, for instance, from some kinds of commercial smoke detectorSmoke detectorA smoke detector is a device that detects smoke, typically as an indicator of fire. Commercial, industrial, and mass residential devices issue a signal to a fire alarm system, while household detectors, known as smoke alarms, generally issue a local audible and/or visual alarm from the detector...
s), detected by a Geiger counterGeiger counterA Geiger counter, also called a Geiger–Müller counter, is a type of particle detector that measures ionizing radiation. They detect the emission of nuclear radiation: alpha particles, beta particles or gamma rays. A Geiger counter detects radiation by ionization produced in a low-pressure gas in a...
attached to a PC.
- PhotonPhotonIn physics, a photon is an elementary particle, the quantum of the electromagnetic interaction and the basic unit of light and all other forms of electromagnetic radiation. It is also the force carrier for the electromagnetic force...
s travelling through a semi-transparent mirrorBeam splitterA beam splitter is an optical device that splits a beam of light in two. It is the crucial part of most interferometers.In its most common form, a rectangle, it is made from two triangular glass prisms which are glued together at their base using Canada balsam...
, as in the commercial product, Quantis from id QuantiqueId Quantiqueid Quantique is a small company located in Geneva, Switzerland. It sells quantum key distribution systems, single photon counters, and physical random number generators...
. The mutually exclusive events (reflection — transmission) are detected and associated to ‘0’ or ‘1’ bit values respectively.
- AmplificationElectronic amplifierAn electronic amplifier is a device for increasing the power of a signal.It does this by taking energy from a power supply and controlling the output to match the input signal shape but with a larger amplitude...
of the signal produced on the base of a reverse-biased transistorTransistorA transistor is a semiconductor device used to amplify and switch electronic signals and power. It is composed of a semiconductor material with at least three terminals for connection to an external circuit. A voltage or current applied to one pair of the transistor's terminals changes the current...
. The emitter is saturated with electrons and occasionally they will tunnel through the band gapBand gapIn solid state physics, a band gap, also called an energy gap or bandgap, is an energy range in a solid where no electron states can exist. In graphs of the electronic band structure of solids, the band gap generally refers to the energy difference between the top of the valence band and the...
and exit via the base. This signal is then amplifiedElectronic amplifierAn electronic amplifier is a device for increasing the power of a signal.It does this by taking energy from a power supply and controlling the output to match the input signal shape but with a larger amplitude...
through a few more transistorsTransistorA transistor is a semiconductor device used to amplify and switch electronic signals and power. It is composed of a semiconductor material with at least three terminals for connection to an external circuit. A voltage or current applied to one pair of the transistor's terminals changes the current...
and the result fed into a Schmitt trigger.
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:- Thermal noise from a resistorResistorA linear resistor is a linear, passive two-terminal electrical component that implements electrical resistance as a circuit element.The current through a resistor is in direct proportion to the voltage across the resistor's terminals. Thus, the ratio of the voltage applied across a resistor's...
, amplified to provide a random voltage source.
- Avalanche noiseAvalanche breakdownAvalanche breakdown is a phenomenon that can occur in both insulating and semiconducting materials. It is a form of electric current multiplication that can allow very large currents within materials which are otherwise good insulators. It is a type of electron avalanche...
generated from an avalanche diodeAvalanche diodeIn electronics, an avalanche diode is a diode that is designed to go through avalanche breakdown at a specified reverse bias voltage. The junction of an avalanche diode is designed to prevent current concentration at hot spots, so that the diode is undamaged by the breakdown...
, or Zener breakdown noise from a reverse-biased Zener diodeZener diodeA Zener diode is a special kind of diode which allows current to flow in the forward direction in the same manner as an ideal diode, but will also permit it to flow in the reverse direction when the voltage is above a certain value known as the breakdown voltage, "Zener knee voltage" or "Zener...
.
- Atmospheric noiseNoise (radio)In radio reception, noise is the superposition of white noise and other disturbing influences on the signal, caused either by thermal noise and other electronic noise from receiver input circuits or by interference from radiated electromagnetic noise picked up by the receiver's antenna...
, detected by a radio receiver attached to a PC (though much of it, such as lightning noise, is not properly thermal noise, but most likely a chaoticChaos theoryChaos theory is a field of study in mathematics, with applications in several disciplines including physics, economics, biology, and philosophy. Chaos theory studies the behavior of dynamical systems that are highly sensitive to initial conditions, an effect which is popularly referred to as the...
phenomenon).
Another variable physical phenomenon that is easy to measure is clock drift
Clock drift
Clock drift refers to several related phenomena where a clock does not run at the exact right speed compared to another clock. That is, after some time the clock "drifts apart" from the other clock. This phenomenon is also used for instance in computers to build random number generators...
.
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
Yarrow algorithm
The Yarrow algorithm is a cryptographically secure pseudorandom number generator. The name is taken from the yarrow plant, the stalks of which are dried and used as a randomising agent in I Ching divination....
or Fortuna
Fortuna (PRNG)
Fortuna is a cryptographically secure pseudorandom number generator devised by Bruce Schneier and Niels Ferguson. It is named after Fortuna, the Roman goddess of chance.- Design :Fortuna is a family of secure PRNGs; its design...
CSPRNG
Cryptographically secure pseudorandom number generator
A cryptographically secure pseudo-random number generator is a pseudo-random number generator with properties that make it suitable for use in cryptography.Many aspects of cryptography require random numbers, for example:...
s), enough entropy can be collected for the creation of cryptographic keys and nonces
Cryptographic nonce
In security engineering, nonce is an arbitrary number used only once to sign a cryptographic communication. It is similar in spirit to a nonce word, hence the name. It is often a random or pseudo-random number issued in an authentication protocol to ensure that old communications cannot be reused...
, 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 interrupt
Interrupt
In computing, an interrupt is an asynchronous signal indicating the need for attention or a synchronous event in software indicating the need for a change in execution....
s 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. The random number generator used for cryptographic purposes in an early version of the Netscape
Netscape
Netscape Communications is a US computer services company, best known for Netscape Navigator, its web browser. When it was an independent company, its headquarters were in Mountain View, California...
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
RS-232
In telecommunications, RS-232 is the traditional name for a series of standards for serial binary single-ended data and control signals connecting between a DTE and a DCE . It is commonly used in computer serial ports...
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 webcam
Webcam
A webcam is a video camera that feeds its images in real time to a computer or computer network, often via USB, ethernet, or Wi-Fi.Their most popular use is the establishment of video links, permitting computers to act as videophones or videoconference stations. This common use as a video camera...
s, to photograph chaotic macroscopic phenomena. A group at Silicon Graphics
Silicon Graphics
Silicon Graphics, Inc. was a manufacturer of high-performance computing solutions, including computer hardware and software, founded in 1981 by Jim Clark...
imaged Lava lamp
Lava lamp
A lava lamp is a decorative novelty item that contains blobs of colored wax inside a glass vessel filled with clear liquid; the wax rises and falls as its density changes due to heating from a incandescent light bulb underneath the vessel. The appearance of the wax is suggestive of pāhoehoe lava,...
s to generate random numbers . 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
Aquarium
An aquarium is a vivarium consisting of at least one transparent side in which water-dwelling plants or animals are kept. Fishkeepers use aquaria to keep fish, invertebrates, amphibians, marine mammals, turtles, and aquatic plants...
(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
There are several ways to measure and use clock driftClock drift
Clock drift refers to several related phenomena where a clock does not run at the exact right speed compared to another clock. That is, after some time the clock "drifts apart" from the other clock. This phenomenon is also used for instance in computers to build random number generators...
as a source of randomness.
The Intel 80802 Firmware Hub chip included a hardware RNG 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
John von Neumann
John von Neumann was a Hungarian-American mathematician and polymath who made major contributions to a vast number of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, geometry, fluid dynamics, economics and game theory, computer science, numerical analysis,...
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
VIA C3
The VIA C3 is a family of x86 central processing units for personal computers designed by Centaur Technology and sold by VIA Technologies. The different CPU cores are built following the design methodology of Centaur Technology.-Samuel 2 and Ezra cores:...
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, a cryptographic routine library (JB Lacy, DP Mitchell, WM Schell, CryptoLib: Cryptography in software, Proc 4th USENIX Security Symp, pg 1-17, 1993). 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 theoremCentral limit theorem
In probability theory, the central limit theorem states conditions under which the mean of a sufficiently large number of independent random variables, each with finite mean and variance, will be approximately normally distributed. The central limit theorem has a number of variants. In its common...
, 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
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 "whiteningDecorrelation
Decorrelation is a general term for any process that is used to reduce autocorrelation within a signal, or cross-correlation within a set of signals, while preserving other aspects of the signal. A frequently used method of decorrelation is the use of a matched linear filter to reduce the...
" 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
John von Neumann
John von Neumann was a Hungarian-American mathematician and polymath who made major contributions to a vast number of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, geometry, fluid dynamics, economics and game theory, computer science, numerical analysis,...
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 not used as a random bit; a sequence of 1,0 becomes a 1; and a sequence of 0,1 becomes a zero. 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 random bit stream with a frequency of 1’s different from 50% into a stream closer to that frequency.
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
Cryptographically secure pseudorandom number generator
A cryptographically secure pseudo-random number generator is a pseudo-random number generator with properties that make it suitable for use in cryptography.Many aspects of cryptography require random numbers, for example:...
such as Blum Blum Shub or a strong stream cipher
Stream cipher
In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
. 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
Piling-up lemma
In cryptanalysis, the piling-up lemma is a principle used in linear cryptanalysis to construct linear approximation to the action of block ciphers...
).
Some designs apply cryptographic hash function
Hash function
A hash function is any algorithm or subroutine that maps large data sets to smaller data sets, called keys. For example, a single integer can serve as an index to an array...
s such as MD5
MD5
The MD5 Message-Digest Algorithm is a widely used cryptographic hash function that produces a 128-bit hash value. Specified in RFC 1321, MD5 has been employed in a wide variety of security applications, and is also commonly used to check data integrity...
, SHA-1, or RIPEMD-160 or even a CRC
Cyclic redundancy check
A cyclic redundancy check is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data...
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) can extract more output bits – output bits that are just as random and unbiased – from such a highly biased bit stream.
PRNG with periodically refreshed random key
Other designs use what are believed to be true random bits as the keyKey (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
for a high quality block cipher
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
algorithm, taking the encrypted output as the random bit stream. Care must be taken in these cases to select an appropriate block mode
Block cipher modes of operation
In cryptography, modes of operation is the procedure of enabling the repeated and secure use of a block cipher under a single key.A block cipher by itself allows encryption only of a single data block of the cipher's block length. When targeting a variable-length message, the data must first be...
, 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 CSPRNGCryptographically secure pseudorandom number generator
A cryptographically secure pseudo-random number generator is a pseudo-random number generator with properties that make it suitable for use in cryptography.Many aspects of cryptography require random numbers, for example:...
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
Spoofing attack
In the context of network security, a spoofing attack is a situation in which one person or program successfully masquerades as another by falsifying data and thereby gaining an illegitimate advantage.- Spoofing and TCP/IP :...
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/dev/randomIn Unix-like operating systems, /dev/random is a special file that serves as a random number generator or as a pseudorandom number generator. It allows access to environmental noise collected from device drivers and other sources. Not all operating systems implement the same semantics for /dev/random...
" device in Linux, written by Theodore Ts'oTheodore Ts'oTheodore Y. "Ted" Ts'o is a software developer mainly known for his contributions to the Linux kernel, in particular his contributions to file systems.He graduated in 1990 from MIT with a degree in computer science...
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 cipherStream cipherIn cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
with a key and Initialization vectorInitialization vectorIn cryptography, an initialization vector is a fixed-size input to a cryptographic primitive that is typically required to be random or pseudorandom...
(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 yarrowYarrow algorithmThe Yarrow algorithm is a cryptographically secure pseudorandom number generator. The name is taken from the yarrow plant, the stalks of which are dried and used as a randomising agent in I Ching divination....
library. It provides resistance against some attacks and conserves hard-to-obtain entropy.
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 cryptosystem, a software random number generator should be designed to resist certain attacks. Defending against these attacks is difficult. See: random number generator attack
Random number generator attack
The security of cryptographic systems depends on some secret data that is known to authorized persons but unknown and unpredictable to others. To achieve this unpredictability, some randomization is typically employed...
.
Estimating entropy
There are mathematical techniques for estimating the entropyInformation entropy
In information theory, entropy is a measure of the uncertainty associated with a random variable. In this context, the term usually refers to the Shannon entropy, which quantifies the expected value of the information contained in a message, usually in units such as bits...
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 pseudo-random generator.
Performance test
Hardware random number generators should be constantly monitored for proper operation. RFC 4086 and FIPSFederal Information Processing Standard
A Federal Information Processing Standard is a publicly announced standardization developed by the United States federal government for use in computer systems by all non-military government agencies and by government contractors, when properly invoked and tailored on a contract...
Pub 140-2
FIPS 140
The 140 series of Federal Information Processing Standards are U.S. government computer security standards that specify requirements for cryptography modules...
include tests which can be used for this. Also see the documentation for the New Zealand cryptographic software library cryptlib
Cryptlib
cryptlib is an open source cross-platform software security toolkit library. It is distributed under the Sleepycat License, a free software license compatible with the GNU General Public License...
.
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
- Comparison of hardware random number generatorsComparison of hardware random number generatorsIn computing, a hardware random number generator is an apparatus that generates random numbers from a physical process. Such devices are often based on microscopic phenomena that generate a low-level, statistically random "noise" signal, such as thermal noise or the photoelectric effect or other...
- Pseudorandom number generatorPseudorandom number generatorA pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...
- Random number generator
- List of random number generators
- /dev/random/dev/randomIn Unix-like operating systems, /dev/random is a special file that serves as a random number generator or as a pseudorandom number generator. It allows access to environmental noise collected from device drivers and other sources. Not all operating systems implement the same semantics for /dev/random...
- Randomness extractorRandomness extractorA randomness extractor, often simply called "an extractor," is a function which, when applied to a high-entropy source , generates a random output that is shorter, but uniformly distributed...
- Bell test experimentsBell test experimentsThe Bell test experiments serve to investigate the validity of the entanglement effect in quantum mechanics by using some kind of Bell inequality...
- ERNIEErnieErnie is a fictional character, a Muppet on the Public Broadcasting Service's long-running children's television show, Sesame Street. He and his roommate Bert form a comic duo that is one of the program's centerpieces, with Ernie acting the role of the naïve troublemaker and Bert the world-weary foil...
- Lottery machineLottery machineA lottery machine is the machine used to draw the winning numbers for a lottery.Early lotteries were done by drawing numbers, or winning tickets, from a container...
Code
..., a Perl modulePerl module
A Perl module is a discrete component of software for the Perl programming language. Technically, it is a particular set of conventions for using Perl's package mechanism that has become universally adopted....
that claims to generate actual random numbers from interrupt timing discrepancies..