Hardware random number generator

Last updated
A USB-pluggable hardware true random number generator NeuG HRNG (22539520445).png
A USB-pluggable hardware true random number generator

In computing, a hardware random number generator (HRNG), true random number generator (TRNG), non-deterministic random bit generator (NRBG), [1] or physical random number generator [2] [3] is a device that generates random numbers from a physical process capable of producing entropy (in other words, the device always has access to a physical entropy source [1] ), unlike the pseudorandom number generator (PRNG, a.k.a. "deterministic random bit generator", DRBG) that utilizes a deterministic algorithm [2] and non-physical nondeterministic random bit generators that do not include hardware dedicated to generation of entropy. [1]

Contents

Nature provides ample phenomena that generate low-level, statistically random "noise" signals, including thermal and shot noise, jitter and metastability of electronic circuits, Brownian motion, atmospheric noise. [4] Researchers also used the photoelectric effect, involving a beam splitter, other quantum phenomena, [5] [6] [7] and even the nuclear decay (due to practical considerations the latter, as well as the atmospheric noise, is not viable). [4] While "classical" (non-quantum) phenomena are not truly random, an unpredictable physical system is usually acceptable as a source of randomness, so the qualifiers "true" and "physical" are used interchangeably. [8]

A hardware random number generator is expected to output near-perfect random numbers ("full entropy"). [1] A physical process usually does not have this property, and a practical TRNG typically includes few blocks: [9]

Hardware random number generators generally produce only a limited number of random bits per second. In order to increase the available output data rate, they are often used to generate the "seed" for a faster PRNG. DRBG also helps with the noise source "anonymization" (whitening out the noise source identifying characteristics) and entropy extraction. With a proper DRBG algorithm selected (cryptographically secure pseudorandom number generator, CSPRNG), the combination can satisfy the requirements of Federal Information Processing Standards and Common Criteria standards. [10]

Uses

Hardware random generators can be used in any application that needs randomness. However, in many scientific applications additional cost and complexity of a TRNG (when compared with pseudo random number generators) provide no meaningful benefits. TRNGs have additional drawbacks for data science and statistical applications: impossibility to re-run a series of numbers unless they are stored, reliance on an analog physical entity can obscure the failure of the source. The TRNGs therefore are primarily used in the applications where their unpredictability and the impossibility to re-run the sequence of numbers are crucial to the success of the implementation: in cryptography and gambling machines. [11]

Cryptography

The major use for hardware random number generators is in the field of data encryption, for example to create random cryptographic keys and nonces needed to encrypt and sign data. In addition to randomness, there are at least two additional requirements imposed by the cryptographic applications: [12]

  1. forward secrecy guarantees that the knowledge of the past output and internal state of the device should not enable the attacker to predict future data;
  2. backward secrecy protects the "opposite direction": knowledge of the output and internal state in the future should not divulge the preceding data.

A typical way to fulfill these requirements is to use a TRNG to seed a cryptographically secure pseudorandom number generator. [13]

History

Physical devices were used to generate random numbers for thousands of years, primarily for gambling. Dice in particular are known for more than 5000 years (found on locations in modern Iraq and Iran), flipping coin (thus producing a random bit) dates at least to the times of ancient Rome. [14]

First documented use of physical random number generator for a scientific purpose was by Francis Galton (1890). [15] He devised a way to sample a probability distribution using a common gambling dice. In addition to the top digit, Galton also looked at the face of a dice closest to him, thus creating 6*4 = 24 outcomes (about 4.6 bits of randomness). [14]

Kendall and Babington-Smith (1938) [16] used a fast-rotating 10-sector disk that was illuminated by the periodic bursts of light. The sampling was done by a human who wrote the number under the light beam onto a pad. The device was utilized to produce a 100,000-digit random number table (at the time such tables were used for statistical experiments, like PRNG nowadays). [14]

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) [17] for a noise source (most likely the well known behavior of the 6D4 miniature gas thyratron tube, when placed in a magnetic field [18] ). Twenty of the 32 possible counter values were mapped onto the 10 decimal digits and the other 12 counter values were discarded. [19] The results of a long run from the RAND machine, filtered and tested, were converted into a table, which originally existed only as a deck of punched cards, but was later published in 1955 as a book, 50 rows of 50 digits on each page [14] ( 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 for deriving the arbitrary constants in cryptographic algorithms to demonstrate that the constants had not been selected maliciously ("nothing up my sleeve numbers"). [20]

Since the early 1950s, research into TRNGs has been highly active, with thousands of research works published and about 2000 patents granted by 2017. [14]

Physical phenomena with random properties

A lot of different TRNG designs were proposed over time with a large variety of noise sources and digitization techniques ("harvesting"). However, practical considerations (size, power, cost, performance, robustness) dictate the following desirable traits: [21]

Stipčević & Koç in 2014 classified the physical phenomena used to implement TRNG into four groups: [3]

Electrical noise-based RNG

Noise-based RNGs generally follow the same outline: the source of a noise generator is fed into a comparator. If the voltage is above threshold, the comparator output is 1, otherwise 0. The random bit value is latched using a flip-flop. Sources of noise vary and include: [22]

The drawbacks of using noise sources for an RNG design are: [23]

Chaos-based RNG

An idea of the chaos-based noise is using a complex system that is hard to characterize and observing its behavior over time. For example, lasers can be put into (undesirable in other applications) mode with chaotically fluctuating power, with power detected using a photodiode and sampled by a comparator. The design can be quite small, as all photonics elements can be integrated on-chip. Stipčević & Koç characterize this technique as "most objectionable", mostly due to the fact that chaotic behavior is usually controlled by a differential equation and no new randomness is introduced, thus there is a possibility of the chaos-based TRNG to produce a limited subset of possible output strings. [25]

Free-running oscillators-based RNG

The TRNGs based on a free-running oscillator (FRO) typically utilize one or more ring oscillators (ROs), outputs of which are sampled using yet another oscillator. Since inverters forming the RO can be thought of as amplifiers with a very large gain, an FRO output exhibits very fast oscillations in phase in frequency domains. The FRO-based TRNGs are very popular due to their use of the standard digital logic despite issues with randomness proofs and chip-to-chip variability. [25]

Quantum-based RNG

Quantum random number generation technology is well established with 8 commercial quantum random number generator (QRNG) products offered before 2017. [26]

Herrero-Collantes & Garcia-Escartin list the following stochastic processes as "quantum":

To reduce costs and increase robustness of quantum random number generators, [37] online services have been implemented. [26]

Performance test

The failure of a TRNG can be quite complex and subtle, necessitating validation of not just the results (the output bit stream), but of the unpredictability of the entropy source. [8] Hardware random number generators should be constantly monitored for proper operation to protect against the entropy source degradation due to natural causes and deliberate attacks. FIPS Pub 140-2 and NIST Special Publication 800-90B [38] define tests which can be used for this.

The minimal set of real-time tests mandated by the certification bodies is not large; for example, NIST in SP 800-90B requires just two continuous health tests: [39]

  1. repetition count test checks that the sequences of identical digits are not too long, for a (typical) case of a TRNG that digitizes one bit at a time, this means not having long strings of either 0s or 1s;
  2. adaptive proportion test verifies that any random digit does not occur too frequently in the data stream (low bias). For bit-oriented entropy sources that means that the count of 1s and 0s in the bit stream is approximately the same.

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, if this source were used directly. Failure modes in such devices are plentiful and are complicated, slow, and hard to detect. Methods that combine multiple sources of entropy are more robust.

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 incorporate some such tests into the software that reads the device.

Attacks

Just as with other components of a cryptography system, a cryptographic random number generator should be designed to resist certain attacks. Defending against these attacks is difficult without a hardware entropy source.[ citation needed ]

The physical processes in HRNG introduce new attack surfaces. For example, a free-running oscillator-based TRNG can be attacked using a frequency injection. [40]

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. This problem is avoided by the conservative use of hardware entropy sources.

See also

Related Research Articles

<span class="mw-page-title-main">One-time pad</span> Encryption technique

In cryptography, the one-time pad (OTP) is an encryption technique that cannot be cracked, but requires the use of a single-use pre-shared key that is larger than or equal to the size of the message being sent. In this technique, a plaintext is paired with a random secret key. Then, each bit or character of the plaintext is encrypted by combining it with the corresponding bit or character from the pad using modular addition.

A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process. Simply put, the problem is that many of the sources of randomness available to humans rely on physical processes not readily available to computer programs.

<span class="mw-page-title-main">Quantum information</span> Information held in the state of a quantum system

Quantum information is the information of the state of a quantum system. It is the basic entity of study in quantum information theory, and can be manipulated using quantum information processing techniques. Quantum information refers to both the technical definition in terms of Von Neumann entropy and the general computational term.

A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed. Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom number generators are important in practice for their speed in number generation and their reproducibility.

<span class="mw-page-title-main">Stream cipher</span> Type of symmetric key cipher

A stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream, to give a digit of the ciphertext stream. Since encryption of each digit is dependent on the current state of the cipher, it is also known as state cipher. In practice, a digit is typically a bit and the combining operation is an exclusive-or (XOR).

A key in cryptography is a piece of information, usually a string of numbers or letters that are stored in a file, which, when processed through a cryptographic algorithm, can encode or decode cryptographic data. Based on the used method, the key can be different sizes and varieties, but in all cases, the strength of the encryption relies on the security of the key being maintained. A key's security strength is dependent on its algorithm, the size of the key, the generation of the key, and the process of key exchange.

A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also loosely known as a cryptographic random number generator (CRNG).

<span class="mw-page-title-main">/dev/random</span> Pseudorandom number generator file in Unix-like operating systems

In Unix-like operating systems, /dev/random and /dev/urandom are special files that serve as cryptographically secure pseudorandom number generators. They allow access to a cryptographically secure pseudorandom number generator that is seeded with entropy from environmental noise, collected from device drivers and other sources. /dev/random typically blocks if there was less entropy available than requested; more recently. It usually blocks at startup until sufficient entropy has been gathered, then unblocks permanently. The /dev/urandom device typically was never a blocking device, even if the pseudorandom number generator seed was not fully initialized with entropy since boot. Not all operating systems implement the same methods for /dev/random and /dev/urandom.

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. Modern cryptographic protocols often require frequent generation of random quantities. Cryptographic attacks that subvert or exploit weaknesses in this process are known as random number generator attacks.

A random password generator is a software program or hardware device that takes input from a random or pseudo-random number generator and automatically generates a password. Random passwords can be generated manually, using simple sources of randomness such as dice or coins, or they can be generated using a computer.

<span class="mw-page-title-main">Diceware</span> Method for generating passphrases using dice

Diceware is a method for creating passphrases, passwords, and other cryptographic variables using ordinary dice as a hardware random number generator. For each word in the passphrase, five rolls of a six-sided die are required. The numbers from 1 to 6 that come up in the rolls are assembled as a five-digit number, e.g. 43146. That number is then used to look up a word in a cryptographic word list. In the original Diceware list 43146 corresponds to munch. By generating several words in sequence, a lengthy passphrase can thus be constructed randomly.

<span class="mw-page-title-main">Ring oscillator</span>

A ring oscillator is a device composed of an odd number of NOT gates in a ring, whose output oscillates between two voltage levels, representing true and false. The NOT gates, or inverters, are attached in a chain and the output of the last inverter is fed back into the first.

Randomness has many uses in science, art, statistics, cryptography, gaming, gambling, and other fields. For example, random assignment in randomized controlled trials helps scientists to test hypotheses, and random numbers or pseudorandom numbers help video games such as video poker.

<span class="mw-page-title-main">Random number generation</span> Producing a sequence that cannot be predicted better than by random chance

Random number generation is a process by which, often by means of a random number generator (RNG), a sequence of numbers or symbols that cannot be reasonably predicted better than by random chance is generated. This means that the particular outcome sequence will contain some patterns detectable in hindsight but impossible to foresee. True random number generators can be hardware random-number generators (HRNGs), wherein each generation is a function of the current value of a physical environment's attribute that is constantly changing in a manner that is practically impossible to model. This would be in contrast to so-called "random number generations" done by pseudorandom number generators (PRNGs), which generate numbers that only look random but are in fact pre-determined—these generations can be reproduced simply by knowing the state of the PRNG.

CryptGenRandom is a deprecated cryptographically secure pseudorandom number generator function that is included in Microsoft CryptoAPI. In Win32 programs, Microsoft recommends its use anywhere random number generation is needed. A 2007 paper from Hebrew University suggested security problems in the Windows 2000 implementation of CryptGenRandom. Microsoft later acknowledged that the same problems exist in Windows XP, but not in Vista. Microsoft released a fix for the bug with Windows XP Service Pack 3 in mid-2008.

In computing, entropy is the randomness collected by an operating system or application for use in cryptography or other uses that require random data. This randomness is often collected from hardware sources, either pre-existing ones such as mouse movements or specially provided randomness generators. A lack of entropy can have a negative impact on performance and security.

A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weak entropy source, together with a short, uniformly random seed, generates a highly random output that appears independent from the source and uniformly distributed. Examples of weakly random sources include radioactive decay or thermal noise; the only restriction on possible sources is that there is no way they can be fully controlled, calculated or predicted, and that a lower bound on their entropy rate can be established. For a given source, a randomness extractor can even be considered to be a true random number generator (TRNG); but there is no single extractor that has been proven to produce truly random output from any type of weakly random source.

Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks. The best known example of quantum cryptography is quantum key distribution, which offers an information-theoretically secure solution to the key exchange problem. The advantage of quantum cryptography lies in the fact that it allows the completion of various cryptographic tasks that are proven or conjectured to be impossible using only classical communication. For example, it is impossible to copy data encoded in a quantum state. If one attempts to read the encoded data, the quantum state will be changed due to wave function collapse. This could be used to detect eavesdropping in quantum key distribution (QKD).

RDRAND is an instruction for returning random numbers from an Intel on-chip hardware random number generator which has been seeded by an on-chip entropy source. Intel introduced the feature around 2012, and AMD added support for the instruction in June 2015.

References

  1. 1 2 3 4 Turan et al. 2018, p. 64.
  2. 1 2 Schindler 2009, p. 7.
  3. 1 2 Stipčević & Koç 2014, p. 279.
  4. 1 2 Sunar 2009, p. 56.
  5. ↑ Herrero-Collantes & Garcia-Escartin 2017, p. 8.
  6. ↑ Jacak, Marcin M.; Jóźwiak, Piotr; Niemczuk, Jakub; Jacak, Janusz E. (2021). "Quantum generators of random numbers". Scientific Reports . 11 (1): 16108. doi: 10.1038/s41598-021-95388-7 . PMC   8352985 . PMID   34373502.
  7. ↑ Ma, Xiongfeng; Yuan, Xiao; Cao, Zhu; Qi, Bing; Zhang, Zhen (2016). "Quantum random number generation". npj Quantum Information . 2 (1): 1–9. arXiv: 1510.08957 . doi: 10.1038/npjqi.2016.21 .
  8. 1 2 Herrero-Collantes & Garcia-Escartin 2017, p. 4.
  9. ↑ Turan et al. 2018, p. 6.
  10. ↑ Saarinen, Newell & Marshall 2020.
  11. ↑ Templ 2016, p. 90.
  12. ↑ Herrero-Collantes & Garcia-Escartin 2017, p. 6.
  13. ↑ Herrero-Collantes & Garcia-Escartin 2017, p. 7.
  14. 1 2 3 4 5 L'Ecuyer 2017.
  15. ↑ Galton, Francis (1890). "Dice for statistical experiments" (PDF). Nature. 42 (1070): 13–14. Bibcode:1890Natur..42...13G. doi: 10.1038/042013a0 . S2CID   4038609. Archived (PDF) from the original on 4 March 2016. Retrieved 14 May 2014.
  16. ↑ Kendall, M. G., and B. Babington-Smith. 1938. “Randomness and other random sampling numbers”. Journal of the Royal Statistical Society 101:147–166.
  17. ↑ Brown, George W. (January 1949), P-113, Papers, Rand Corporation, archived from the original on 2007-06-05, retrieved 2009-05-10.
  18. ↑ Cobine, Curry (1947), "Electrical Noise Generators", Proceedings of the I.R.E. (September 1947): 875–9
  19. ↑ Monograph report, Rand Corporation, January 2001, archived from the original on 2018-04-15, retrieved 2009-01-29.
  20. ↑ Schneier, Bruce (1995-11-01). "Other Stream Ciphers and Real Random-Sequence Generators". Applied Cryptography (Second ed.). John Wiley & Sons, Inc. p. 423. ISBN   978-0-471-11709-4.
  21. ↑ Sunar 2009, p. 57.
  22. ↑ Stipčević & Koç 2014, pp. 279–280.
  23. ↑ Stipčević & Koç 2014, p. 280.
  24. ↑ Stipčević & Koç 2014, p. 286.
  25. 1 2 Stipčević & Koç 2014, pp. 288–289.
  26. 1 2 Herrero-Collantes & Garcia-Escartin 2017, p. 2.
  27. ↑ Herrero-Collantes & Garcia-Escartin 2017, pp. 10–13.
  28. ↑ Herrero-Collantes & Garcia-Escartin 2017, pp. 13–14.
  29. ↑ Herrero-Collantes & Garcia-Escartin 2017, p. 15.
  30. ↑ Herrero-Collantes & Garcia-Escartin 2017, p. 17.
  31. ↑ Herrero-Collantes & Garcia-Escartin 2017, p. 20.
  32. ↑ Herrero-Collantes & Garcia-Escartin 2017, pp. 20–21.
  33. ↑ Herrero-Collantes & Garcia-Escartin 2017, pp. 21–22.
  34. ↑ Herrero-Collantes & Garcia-Escartin 2017, pp. 23–24.
  35. ↑ Herrero-Collantes & Garcia-Escartin 2017, pp. 24–25.
  36. ↑ Herrero-Collantes & Garcia-Escartin 2017, pp. 27–28.
  37. ↑ Huang, Leilei; Zhou, Hongyi; Feng, Kai; Xie, Chongjin (2021-07-07). "Quantum random number cloud platform". npj Quantum Information. Springer Science and Business Media LLC. 7 (1). doi: 10.1038/s41534-021-00442-x . ISSN   2056-6387.
  38. ↑ Turan et al. 2018.
  39. ↑ Turan et al. 2018, pp. 25–27.
  40. ↑ Markettos, A. Theodore; Moore, Simon W. (2009). "The Frequency Injection Attack on Ring-Oscillator-Based True Random Number Generators". Lecture Notes in Computer Science (PDF). Berlin, Heidelberg: Springer Berlin Heidelberg. p. 317–331. doi:10.1007/978-3-642-04138-9_23. ISBN   978-3-642-04137-2. ISSN   0302-9743.

Sources

General references

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.