Random Number Generators—Principles and Practices

David Johnston, Principal Engineer, Intel Corporation

1 Introduction

1.1 Tools

1.2 Terminology

1.3 The Many Types of Random Numbers

1.3.1 Uniform Random Numbers

2 Random Number Generators

2.1 Classes of Random Number Generators

2.2 Names for RNGs

3 Making Random Numbers

3.1 A Quick Overview of the RNG Types

3.2 The Structure of Full RNG Implementations

3.3 Pool Extractor Structures

3.4 Multiple Input Extractors

4 Physically Uncloneable Functions 21

4.1 The other kind âAS Static vs. Dynamic Random Number Generators .

5 Testing Random Numbers

5.1 Known Answer Tests

5.2 Distinguishing From Random

5.3 PRNG Test Suites

5.4 Entropy Measurements

5.5 Min Entropy Estimation

5.6 Model Equivalence Testing

5.7 Statistical Prerequisite Testing

5.8 The problem Distinguishing Entropy and Pseudo-randomness

5.9 PRNG Tests: DieHarder, NIST SP800-22,TestU01, China ICS 35.040

5.10 Entropy Measurements

5.11 Min Entropy Measurements

5.12 Modeling to Test a Source

5.13 Statistical Prerequisites

5.14 Testing for bias .

5.15 results that are âAŸtoo goodâAZ (E.G. Chi-square == 0.5)

5.16 Distinguishing Correlation from Bias

5.17 Testing for Stationary properties

5.18 FFT analysis

5.19 Online Testing

5.20 Working From the Source RNG

5.21 Tools

5.22 Summary

6 Entropy Extraction or Distillation

6.1 A simple extractor, the XOR gate

6.2 A simple way of improving the distribution of random numbers that have known missing

values using XOR

7 Quantifying Entropy

7.1 Rényi Entropy

7.2 Distance From Uniform



Topics to put somewhere in the book- in existing chapters and new chapters



8.1 XOR as a 2 bit extractor

8.2 Properties of real random numbers

8.3 Binomial distributions

8.4 Normal distributions

8.4.1 Dice, more dice

8.4.2 Central limit theorem

8.5 Seeing patterns

8.6 Regression to the mean

8.7 Lack of correlation, bias, algorithmic connections, predictability

8.8 What’s a True random number?

8.9 Random numbers in cryptography

8.10 Things they help with liveness, unpredictability, resistance to attacks

8.11 Examples of use

8.11.1 Salting Passwords .

8.11.2 802.11i exchange

8.11.3 PKMv2 exchange

8.11.4 Making Keys

8.12 Examples of RNG crypto failures

8.12.1 Sony PS3 attack

8.12.2 MiFare Classic

8.12.3 Online Poker

8.12.4 Debian OpenSSL Fiasco

8.12.5 Linux Boot Time Entropy

8.13 Humans and random numbers

8.14 Result of asking people for a random number

8.14.1 Normal People

8.14.2 Crypto People

8.15 Mental Random Number Tricks

8.15.1 How to think of a really random number

8.16 PRNGs

8.17 extractors

8.17.1 CBC MAC

8.17.2 BIW

8.17.3 Von Neumann

8.18 Extractor Theory

8.19 Random Number Standards

8.19.1 SP800-90A B C .

8.19.2 Ansi X9.82

8.20 PRNG Algorithms

8.20.1 SP800-90A CTR DRBG

8.20.2 SP800-90A SHA DRBG

8.20.3 XOR Construction

8.20.4 Oversampling Construction

8.21 Yarrow

8.22 Whirlpool

8.23 Linux Kernel random service

8.24 Appendices

8.25 Resources

8.25.1 SW Sources

8.25.2 Online random number sources

8.26 Example Algorithm Vectors

8.26.1 SP800-90A CTR DRBG 128 & 256

8.26.2 SP800-90A Hash DRBG SHA-1 & SHA 256

8.26.3 AES-CBC-MAC Conditioner 128

8.26.4 AES-CBC-MAC Conditioner

8.27 SP800-90 LZ Tests Issues