Random Number Generators—Principles and Practices

A Guide for Engineers and Programmers

David Johnston

• Publisher: De|G Press
• Year: 2018
• eBook ISBN: 9781501506260
• Edition: 1
• Topic: Computer Science
• Subtopic: Programming Algorithms
• Index: Computer Science

Random Number Generators, Principles and Practices has been written for programmers, hardware engineers, and sophisticated hobbyists interested in understanding random numbers generators and gaining the tools necessary to work with random number generators with confidence and knowledge.

Using an approach that employs clear diagrams and running code examples rather than excessive mathematics, random number related topics such as entropy estimation, entropy extraction, entropy sources, PRNGs, randomness testing, distribution generation, and many others are exposed and demystified.

If you have ever

• 
  
  

• Wondered how to test if data is really random

• 
  
  

  
  
  

• Needed to measure the randomness of data in real time as it is generated

• 
  
  

  
  
  

• Wondered how to get randomness into your programs

• 
  
  

  
  
  

• Wondered whether or not a random number generator is trustworthy

• 
  
  

  
  
  

• Wanted to be able to choose between random number generator solutions

• 
  
  

  
  
  

• Needed to turn uniform random data into a different distribution

• 
  
  

  
  
  

• Needed to ensure the random numbers from your computer will work for your cryptographic application

• 
  
  

  
  
  

• Wanted to combine more than one random number generator to increase reliability or security

• 
  
  

  
  
  

• Wanted to get random numbers in a floating point format

• 
  
  

  
  
  

• Needed to verify that a random number generator meets the requirements of a published standard like SP800-90 or AIS 31

• 
  
  

  
  
  

• Needed to choose between an LCG, PCG or XorShift algorithm

Then this might be the book for you.

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...

Table of contents

• Cover
• Title Page
• Copyright
• Dedication
• About De|G PRESS
• Contents
• Preface
• 1 Introduction
• 2 Entropy Sources
• 3 Entropy Extraction
• 4 Cryptographically Secure Pseudorandom Number Generators
• 5 Nondeterministic Random Number Generators
• 6 Statistically Uniform Noncryptographic PRNGs
• 7 Gaussian or Normally Distributed PRNGs
• 8 Testing Random Numbers
• 9 Online Random Number Testing
• 10 SP800-22 Distinguishability Tests
• 11 Software Tools
• 12 RdRand and RdSeed Instructions in x86 CPUs
• 13 Accessing RNGs from Software
• 14 Floating-Point Random Numbers
• 15 Making a Uniform Random Number Between Nonpower of Two Bounds
• 16 Generating Random Prime Numbers
• 17 Additive Distributions
• 18 Probability Distributions
• 19 Quantifying Entropy
• 20 Random Methods to Generate π
• Appendix A Adaptive Proportion Test Cutoff Tables
• Appendix B High-Precision Incomplete Beta Function Implementation
• Appendix C Incomplete Gamma Function Implementation
• Bibliography
• Index