1Introduction
My first professional encounter with random numbers happened while implementing the 802.11 WEP (Wired Equivalent Privacy) protocol in a WiFi chip. This required that random numbers be used in the protocol and the approach I took was to take noisy data from the wireless receive hardware and pass it through an iterated SHA-1 hash algorithm. Once a sufficient amount of noisy data had been fed in, the output of the hash was taken to be a random number.
Given that at the time I was largely ignorant of the theory behind random number generation in general and entropy extraction in particular, the solution was not terrible, but with hindsight of a decade of working on random number generators there are some things I would have done differently.
Subsequent to attending the IEEE 802.11i working group to work on the replacement protocol to WEP (one of the security protocol standards famously back-doored by the NSA and thereby introducing bad cryptography into standards) and later on the 802.16 PKMv2 security protocol, the need for random numbers in security protocols and the problems specifying and implementing them, led to my career being diverted into a multiyear program to address how to build practical random number generators for security protocols that can be built in chips, tested, mass manufactured, and remain reliable and secure while being available to software in many contexts. Ultimately this emerged as the RdRand instruction and later the RdSeed instruction in Intel CPUs. A decade later, the requirements are still evolving as new needs for random number generators that can operate in new contexts emerge.
My initial model for this book was for it to be the book I needed back when first implementing a hardware random number generator for the 802.11 WEP protocol. I would have benefited greatly from a book with clear information on the right kinds of design choices, the right algorithms, the tradeoffs, the testing methods, and enough of the theory to understand what makes those things the correct engineering choices. The scope of the book grew during its writing, to cover nonuniform RNGs, a much expanded look at various types of random number testing, nonuniform RNGs, software interfaces for RNGs, and a mix of software tools and methods that have been developed along the way.
Since the early 2000s, the requirements for random number generators have evolved greatly. For example, the need for security against side channel and fault injection attacks, security from quantum computer attacks, the need for smaller, lower power random number generators in resource-constrained electronics, and the need for highly efficient RNGs and floating point hardware RNGs for massively parallel chips.
Random numbers are used in many other fields outside of cryptography and the requirements and tradeoffs tend to be different. This book explores various noncryptographic random number applications and related algorithms. We find examples of random number uses occurring in simulations, lotteries, games, statistics, graphics, and many other fields.
To give a taste of what will be covered in this book, the following are three examples of random bits represented in hex format. They all look similarly random, but the first is statistically uniform and is generated using a very secure, nonpredictable random number generator suitable for cryptography, while the second is statistically uniform but completely insecure and predictable and the third is neither statistically uniform nor cryptographically secure.
Listing 1.1: Output of a Cryptographically Secure RNG
Listing 1.2: Output of a Uniform, Insecure RNG
Listing 1.3: Output of a Nonuniform, Insecure RNG
The first is generated from a random number generator in an Intel CPU that has a metastable entropy source, followed by an AES-CBC-MAC entropy extractor and an SP800-90A and 90C XOR construction NRBG, with an AES-CTR-DRBG. This RNG uses algorithms that are mathematically proven to be secure in that it is algorithmically hard to infer the internal state from the output and impossible to predict past and future values in the output when that state is known.
The second is generated with a PCG (Permuted Congruential Generator) RNG. PCGs are deterministic RNGs that have excellent statistical properties, but there is no proof that it is hard to infer the internal state of the algorithm from the output, so it is not considered secure.
The third is generated with an LCG (Linear Congruential Generator) RNG. LCGs are simple deterministic RNG algorithms for which there are a number of statistical flaws. It is trivial to infer the internal state of the algorithm and so to predict future outputs. So, it is proven to be insecure.
Later chapters on NRBGs, DRBGs, entropy extractors, uniform noncryptographic random number generators and test methods will explore the differences between these different types of random number generator and how to test for their properties.
1.1Classes of Random Number Generators
Things that make random numbers are generically called Random Number Generators (RNGs). These fall into two major types: Pseudo-Random Number Generators (PRNGs) and True Random Number Generators (TRNGs). Unfortunately, TRNG is a term that is not well defined. It is interpreted in different ways by different people in industry and academia.
PRNGs are deterministic algorithms that generate a ārandom lookingā sequence of numbers. However, given the same starting conditions, a PRNG will always give the same sequence. Hence, the name āPseudo-Randomā Number Generator.
Typically, a PRNG will be implemented as software or digital hardware. As we will see later, there is a special class of PRNG, the āCryptographically Secureā PRNG or CS-PRNG, which while producing a deterministic sequence, provides guarantees on how hard it is to predict numbers in the sequence, such that the PRNG is usable for cryptographic purposes.
TRNGs are nondeterministic systems. They inevitably require a hardware component to sense ānoiseā or āentropyā in the environment that can be turned into nondeterministic numbers. Since a computer algorithm follows a fixed set of instructions, it is impossible to write a nondeterministic random number generator algorithm that works in isolation. You must have a physical hardware component to pass a nondeterministic source of data into the system to form what is often called a TRNG.
For example, the command line program ādjenrandomā is a program to generate random numbers of various types. The āpureā model only produces random numbers that should be indistinguishable from random. However, by default, it internally uses a deterministic PRNG without any source of physical randomness. In th...
