# Presentation: 145839

## Slide 1

## Random Number Generation & Testing

**Random Number Generation & Testing**
**Juan Soto**
- soto@nist.gov
- 301/975-4641

**Notes:**
This morning we will be addressing the subject of Random Number Generation & Testing at 
NIST.

## The RNG Team

*Statistics Department*, **UMBC**
- Andrew Rukhin
*Computer Security Division*, **NIST**
- Miles Smid, Elaine Barker, Jim Nechvatal,   Jim Dray, San Vo, and Juan Soto
*Statistical Engineering Division*, **NIST**
- Stefan Leigh, Mark Vangel, David Banks, Mark Levenson, Allen Heckert

**Notes:**
Who is involved? The RNG Team consists of statisticians, mathematicians and computer scientists from the University of Maryland, the Computer Security Division and Statistical Engineering Division at NIST.

## Outline

- Introduction
- Overview of the NIST test suite
- Empirical Testing
- Future work
- Summary

**Notes:**
We will begin by providing a flavor for the subject by introducing a simple sequence to help motivate some terms that are used throughout the statistical tests.

We will describe the statistical tests in simple terms and then describe two numerical experiments conducted in our labs.  Finally we will highlight our future objectives and our accomplishments.

## Introduction

**Random Number Generation**
- Von Neumann is often quoted as having stated: “Anyone who considers arithmetic methods of producing random digits is, of course, in a state of sin.”
**Testing RNGs**
- He also stated, “...that in his experience it was more trouble to test random sequences than to manufacture them.”

**Notes:**
Before we proceed I’d like to make reference to some quotations made by John von Neumann.  Since we have primarily focused on testing PRNG its appropriate that we cite a well known
quote...”Anyone who considers arithmetic methods of producing random digits, of course, in a state of sin.  Alluding to the deterministic nature of computing.
Also, I’d like to focus on another quotation that may not be as prevalent.  He also stated, “... that in his experience it was more trouble to test random sequences that to manufacture them.”

## NIST Goals

- A set of statistical tests suitable in the assessment of the randomness of (P)RNGs.
- Provide supporting documentation.
- Inclusion of the tests in the **Cryptographic Module Validation** **Program?**
- Development of a **Special Publication**?

**Notes:**
In the next few slides we will describe our tests.  
The Monobits test assesses the distribution of bits.
The Block Frequency Test assesses the distribution of m-bit blocks.

The Spectral Test based on the discrete Fourier transform assesses the spectral frequency of a bitstring.  It is sensitive to periodicity in the sequence.

## Work In Progress

**The development of several documents:**
***“******A Statistical Test Suite for the Validation of Cryptographic RNGs” ***including test strategy and test interpretation.
***“******The NIST Statistical Test Suite User’s Guide Version 1.0”***
**A reference implementation in ANSI C. **

**Notes:**
In the next few slides we will describe our tests.  
The Monobits test assesses the distribution of bits.
The Block Frequency Test assesses the distribution of m-bit blocks.

The Spectral Test based on the discrete Fourier transform assesses the spectral frequency of a bitstring.  It is sensitive to periodicity in the sequence.

## Example:  A Finite Length Binary Sequence

**01010110111010100110101001101011101001010010100101010****   **
**  ****Bits**				**0s** = 26	**1s** = 27
**  ****Templates****	****   ****	****	****00s** = 5      	**01s** = 20       				     	   	**10s** = 20    	**11s** = 7
**  ****Runs** = 41		          	0, 1, 0, 1, 0, 11, 0, 111, 0, 1, ...** **
**  ****Cycles** = 5**	****	****	**01, 01, 01, 10, 111010.....010
**  ****Words** = 18		0, 1, 01, 011, 0111, 010, ...
**  ****Linear Complexity**      	< **27**, 1+D3+D8+D10+D17+D19+D22+   				         D23 +D24+D25+ D26 >

**Notes:**
We begin with a simple example.  We see here a short binary sequence.  Characteristics have to be defined in order to evaluate a finite sequence for randomness.  These characteristics are commonly referred to as test statistics.  Here we see a sample of test statistics:  bits, templates, runs, cycles, words, and linear complexity.

## Overview of the NIST Test Suite

**Frequency (Monobits)** Test
- Assess the distribution of 0s and 1s.
**Block Frequency** Test
- Assess the distribution of m-bit blocks.
**Spectral** (**DFT**) Test
- Assess the spectral frequency of a bitstring.

**Notes:**
In the next few slides we will describe our tests.  
The Monobits test assesses the distribution of bits.
The Block Frequency Test assesses the distribution of m-bit blocks.

The Spectral Test based on the discrete Fourier transform assesses the spectral frequency of a bitstring.  It is sensitive to periodicity in the sequence.

## Spectral Plot

**Notes:**
This graph depicts the spectral frequency of a Blum-Blum-Shub sequence with a deliberately induced bias. As we can observe there is periodicity in this sequence as revealed by the long peaks.

## Overview of the NIST Test Suite

**Runs** Test
- Assess the expected total number of runs.
**Long Runs** Test
- Assess the distribution of runs of ones; runs should not exceed log2 n.
**Marsaglia’s Rank** Test
- Assess the distribution of the rank for 32x32 binary matrices.

**Notes:**
The Runs test is a common test with many different variants.   In our case we expect that the total number of runs should be be about half  of the sequence length.  If not, then a sequence fails this test.

The Long Runs test examines the long runs of ones in a sequence.  

The Rank test assesses the distribution of the rank for 32x32 binary matrices.

## Rank of Binary Matrices

_**The Rank of 32x32 Binary Matrices**_
- 28.88 % of binary matrices have rank = 32 57.76 % of binary matrices have rank = 31 13.36 % of binary matrices have rank  30

**Notes:**
Here we have two binary matrices.  The first consists of four linearly independent vectors and thus has full rank.  The second matrix consists of three linearly independent vectors; notice that the first and fourth row are the same and thus this is why the rank is equal to 3.  

Three facts about the rank 32x32 bit matrices:  Only 28.88% of binary matrices have full rank.  The majority have one less than full rank. The rest are grouped together is just one class. 

## Overview of the NIST Test Suite

**NonOverlapping Template Matching** Test
- Assess the frequency of m-bit nonperiodic patterns.
**Cumulative Sums** Test
- Assess that the sum of partial sequences isn’t too large or too small; indicative of too many 0s or 1s.
**Random Excursions** Test
- Assess the distribution of states within a cycle of a random walk.

**Notes:**
The nonoverlapping (non-periodic) template matching test examines the number of occurrences of a given nonperiodic template. 
An example of a non-periodic template is (0111) whereas a periodic template is (0101). 

The following two tests are based upon the concept of random walks.  The cusums tests assess the trajectory of random walks based on the maximum of the cumulative sums; whereas the random excursions tests assesses the distribution of states within a cycle. 

## Random Walk (1D) 

**-4   -3  -2   -1    0    1    2    3    4**

**Bitstring**

**Transformed**

**Summation**

**Notes:**
Think of a one-dimensional random walk as either moving to the left or to the right, for example, on the integer line.
Given a  binary sequence how do you determine a cycle? By definition a cycle is the path which returns to 0.   

## Overview of the NIST Test Suite

**Overlapping Template Matching** Test
- Assess the frequency of *m-bit* periodic templates.
**Serial** Test
- Assess the distribution of all 2m *m-bit* blocks.
**Approximate Entropy** Test
- Assess the entropy (regularity) of a bitstring; compares the frequency of all *m-bit* patterns against all (*m+1)-bit* patterns.

## Approximate Entropy Plot

**Notes:**
Pincus, Singer and Kalman demonstrated how to construct an ApEn plot for an arbitrary sequence.  The x-axis depicts the length of a binary sequence.  The y-axis depicts the deficit from maximal irregularity.  That is how far the sequence is from having “maximum entropy.”

Here we observe three plots for the binary expansion of E, Pi, and a SHA-1 sequence.
The further above the sequence the more regular and therefore the less random.

## Overview of The NIST Test Suite

**Maurer’s Universal Statistical** Test
- Assess the compressibility of a bitstring.
**Lempel-Ziv Complexity** Test
- Assess the compressibility of a bitstring.
**Linear Complexity** Test
- Assess the linear complexity of a bitstring; the shortest LFSR that can generate the bitstring.

**Notes:**
Maurer’s Universal Statistical test assesses the compressibility of a binary sequence for L-bit blocks.

The Lempel-Ziv complexity test  also assesses the compressibility of a binary sequence.  In this case based upon the number of unique words.

The Linear Complexity test determines the linear complexity of a finite sequence.

## Linear Complexity Profile

**Notes:**
A graph of the linear complexity profile for a XOR PRNG sequence.  The x-axis depicts the sequence length while they y-axis depicts its corresponding linear complexity.  The reference line n/2, where n is the sequence length represents where the ordinate value should lie.  
As we can see at 127 our graph no longer monotonically increases but rather reaches a steady state.

## Empirical Testing

**Good PRNGs**
- ANSI X9.17, G-SHA-1, G-DES
- Blum-Blum-Shub
**Block Cipher Algorithms** (AES)
- Correlation, CBC Mode
- Key (Plaintext) Avalanche
- Special Key (Plaintext) Inputs

**Notes:**
Two categories of  data have been evaluated.  Pseudo random number generators such as ANSI X9.17, G-SHA-1, and G-DES.

And several characteristics for 128-bit block cipher algorithms such as:  correlation, cipher block chaining mode, key and plaintext avalanche, and special key and plaintext inputs.

## Poor PRNGs

**XOR PRNG**
- Fails the linear complexity test, rank test and several other tests.  Failure due to the simplicity of the scheme.
**HPC Key Avalanche**
- Fails the monobits test, approximate entropy test and several others.  Failure due to the existence of equivalent keys.

**Notes:**
Two examples of poor pseudo-random number generators are the XOR PRNG and the HPC Key Avalanche dataset.

## Our Efforts

- Tests developed for cryptographic use.
- Full scientific documentation provided (each algorithm based on rigorous math).
- Sixteen statistical tests fully developed to date; over 200 if one considers alternate input parameters.

**Notes:**
Our objectives have been...

## Future Work

- Peer Review Process
- Testing Hardware RNG data
- Development of Additional Statistical Tests
- Moving Averages & Generalized OPSO test
- Block Cipher tests
- Inclusion of Assessment Tools
- Graphical Utilities & Goodness-of-Fit tests

**Notes:**
In the future we anticipate.

## Summary

- Statistical tests are very important in ensuring good quality (P)RNGs.
- Statistical tests are necessary but not sufficient to recommend a (P)RNG.
- A statistical test suite must be diverse.
- In the last two years, **NIST** has developed over 200 tests.

**Notes:**
In summary,