# Presentation: 042323

## Empirical Statistical Testing Of  Cryptographic Pseudo Random NumberGenerators

- Juan Soto
- June 25, 1998

## General Overview

- Background Information
- Description of the NIST developed statistical tests
- Empirical Statistical Testing
- Closing Remarks
- Future Work
- References

## What is a PRNG?

- A *deterministic algorithm* which, given a truly random binary sequence of length* k*, outputs a binary sequence of length *l *>> *k* which appears to be random.

## A PRNG is said to pass:

- all *polynomial time statistical tests* if **no** **polynomial time** **algorithm can distinguish an output** **sequence **of the generator and a **truly random sequence**.
- the *next-bit test* if there is **no polynomial** **time algorithm** which, on input of the **first *****l *****bits** of an output sequence *s*, **can predict the (*****l*****+1)****st**** bit** of* s* with probability greater than 1/2.

## Background

**Fact **
- A PRNG** **passes the** next-bit test** iff it passes **all polynomial-time statistical tests.**
- What is a cryptographically secure PRNG?
**It is a PRNG which passes the next-bit test** (possibly under some plausible but unproved mathematical assumption such as the intractability of factoring integers).

## Cryptographic Schemes

- Many cryptographic algorithms and protocols require random numbers.
- Digital Signatures
- Message Authentication Codes
- Encryption Algorithms
- Zero-Knowledge Schemes

## Randomness is a key ingredient in cryptography.

**Where is it used?**
- Generating cryptographic keys
- Integral part of steps of cryptographic algorithms.
**Why is this important?**
- Security of the scheme depends on the quality of the PRNG.
- Any detectable patterns improves the likelihood for predictability.

## Pseudo-Random Number Generators

**ANSI X9.17 PRNG (ANSI X9.17)**
**FIPS 186 One Way Function Using DES (G-DES)**
**FIPS 186 One Way Function Using SHA-1 (G-SHA)**
*Blum-Blum-Shub (BBS)*
*Micali-Schnorr (MS)*
*Rivest-Shamir-Adleman (RSA)*
- _Polynomial Congruential Generators (LCG, QCG, CCG)_
- _Modular Exponentiation (ModExp)_
- _Exclusive OR (XOR)_

## Applied Science

**Applied Statistics**
- Probability Theory
- Hypothesis Testing		e.g. Frequentist, Bayesian
- Goodness-Of-Fit Tests	e.g. Chi2, Kolgomorov-Smirnov
**Applied Computer Science**
- Algorithms		e.g. Pattern Matching
- Data Structures		e.g. Binary Trees, BitFields
**Applied Mathematics**
- Special Functions		e.g. Error, Inc. Beta, Inc. Gamma
- Numerical Analysis	e.g. Optimization Methods

## Evaluation Approaches

**Qualitative**
- Visualization/Graphics
- Discrete Fourier Transform Plot
- Approximate Entropy Graphics
- Linear Complexity Profile
**Quantitative**
- Statistical Tests
**Probability Theory Based**	e.g.  monobits, templates
**Information Theoretic Based**	e.g.  entropy, compression
**Complexity Theory Based****	**e.g.  linear, maximum order

## Preliminary Definitions

**Input Parameters**
- _[shifted] sequence (bitstream)__	_{0,1}n || {-1,1}n || **Z** ||
- _sequence length_ (n)
- _block length_ (m)
**Rank of a binary matrix**
- The number of non-zero rows in a row-reduced matrix.
**Entropy**
- H(X) = -     pi log pi
**Runs**
- Subsequences of a sequence *s *consisting of consecutive 0’s or 1’s.

## Preliminary Definitions

**Template**
- overlapping
- non-overlapping
*non-periodic*
- e.g. {0001,0011,0111,1000,1100,1110}
**Random Walk (Random Excursion)**
- A succession of *walks* along line segments in which the direction (and possibly the length) of each walk is determined in a random way.

## The NIST Statistical Test Suite

**Frequency**
**Cumulative Sum**
**Runs**
**Longest Runs Of Ones**
**Rank**
**Spectral**
**Template Matchings**

**Universal Statistical**
**Approximate Entropy**
**Random Excursions**
**Moving Averages**
**Lempel-Ziv Compression**
**Linear Complexity**
**Bayes**

## Evaluation Procedure

- Compute the **test statistic**.
- Testing is carried out at the bit level.
- Compute its **p****value**.
- Probability of observing a test statistic at least as extreme as the value actually observed.
- Compare the **p****value** to **alpha**:
**SUCCESS** whenever **p****value** > alpha
**FAILURE** whenever **p****value** < alpha
- alpha is chosen *conservatively* in (0.001, 0.01]

## Frequency Test

**INPUT**
- bitstream, sequence length (n)
**PROCEDURE**
- Compute the frequency of ones (or zeroes).
- Compute the pvalue.
**DEFECT DETECTED**
- Larger than expected deviation from the theoretical distribution of zeroes and ones, i.e. either there are too many ones or there are too many zeroes.

## Cumulative Sum Test

**INPUT**
- bitstream, sequence length (n)
**PROCEDURE**
- Compute the maximum of the partial sums of the shifted bitstream values.
- Compute the pvalue.
**DEFECT DETECTED**
- Either too many ones or too many zeroes at early stages

## Runs Test

**INPUT**
- bitstream, sequence length (n)
**PROCEDURE**
- Compute the total number of runs of zeroes and ones in the bitstream.
- Compute the pvalue.
**DEFECT DETECTED**
- Large (small) test statistic indicates that the oscillation in the bitstream is too fast (too slow).

## Rank TestDue To Marsaglia (DIEHARD)

**INPUT**
- bitstream, sequence length (n), block length (M)
**PROCEDURE**
- Construct N matrices (MxM) from the bitstream.
- For each matrix, determine its rank.
- Compute a chi squared statistic based on the theoretical distribution of rank.
- Compute the pvalue.
**DEFECT DETECTED**
- Deviation of the rank distribution from a corresponding random sequence.

## Spectral Test

**INPUT**
- shifted sequence, sequence length (n)
**PROCEDURE**
- Apply the DFT on the shifted sequence and then determine its modulus.
- Pick the first n/2 elements (peaks) and count the number of peaks less than sqrt(3n).
- Compute the pvalue.
**DEFECT DETECTED**
- Detects periodic features in the bitstream.

## Template Matchings Test

**INPUT**
- bitstream, sequence length (n), block length (m), template (B)
**PROCEDURE**
- Compute the # of times B appears in the bitstream.
- Compute the pvalue.
**DEFECT DETECTED**
- Too many occurrences of a nonperiodic templates.
- Too many occurrences of m-runs of ones.

## Universal Statistical TestDue To Ueli Maurer

**INPUT**
- bitstream, sequence length, block length (L),                  initialization steps (Q), number of steps in the test  (K).
**PROCEDURE**
- Count the number of different templates in the sequence.
- Compute the pvalue.
**DEFECT DETECTED**
- Detects PRNGs which can be modeled by an ergodic stationary source with limited memory.
- Compressibility criterion (regularity).

## Approximate Entropy TestDue To Pincus & Singer (1997)

**INPUT**
- bitstream, block  length (m)
**PROCEDURE**
- Compute the bitstream block frequencies.
- Compute **ApEn** (a measure of the logarithmic frequency with which blocks of length m that are close together remain close together for blocks augmented by one position).
- Compute the pvalue.
**DEFECT DETECTED**
- Small values of ApEn(m) imply strong regularity.

## Random Excursions Test

**INPUT**
- shifted sequence, number of 0-cycles (J)
**PROCEDURE**
- For each state, x in [-9,-1] and [1,9] determine the frequency each state value was visited for each cycle.
- Let nuk(x) = the total number of visits to state x within the kth excursion.
- Compute a chi squared statistic and its respective pvalue.
**DEFECT DETECTED**
- Detects deviation from the distribution of the number of visits of the random walk to a certain state.

## Moving Averages Test

**INPUT**
- bitstream, average threshold (x)
**PROCEDURE**
- Determine the block length and label each block in the bitstream  (1, 2, 3, ...)
- Let tau index the 1st block whose average of ones exceeds x.
- Compute the pvalue.
**DEFECT DETECTED**
- Large values of the test statistic indicates that there are relatively fewer ones than zeroes in the beginning.

## Lempel-Ziv Compression Test

**INPUT**
- bitstream
**PROCEDURE**
- Measures the rate at which new patterns appear in a sequence.
- Construct a dictionary from the bitstream.
- Add a new word into the dictionary that has never appeared there before.
- Count the number of words in the dictionary.
- Compute the pvalue.
**DEFECT DETECTED**
- More compressed than a truly random sequence.

## Linear Complexity Test

**INPUT**
- bitstream
**PROCEDURE**
- Compute the connection polynomial for the bitstream.
- The length of the shortest LFSR that generates a binary sequence* S* with* n* terms.
- Compute the pvalue.
**DEFECT DETECTED**
- The sequence is not complex enough to be considered random.

## Bayes Test

**INPUT:  ****	**bitstream, sequence length (n), block length (m)

**PROCEDURE:**  (1) Determine the bitstream _block frequencies,_                     		(2) Compute the Bayes Factor, **F****m****(*****k*****)**:

**RETURN:**  **1/max****k**** F****m****(k) ~ probability that the sequence is random.**

## Numerical Experiments

- PRNGs for which:
- flaws **were not** detected
- ANSI X9.17, G-DES, G-SHA, BBS, MS, LCG, QCG2
- flaws** were detected**
- QCG-1, CCG, XOR, ModExp, Lovasz
- Statistically significant results detected at the 0.01 significance level.

## Remarks

**Existing Packages For PRNG Evaluation**
**G. Marsaglia’s **_**DIEHARD**_** Battery of Tests**
**P. L’Ecuyer **_**TestU01**_** (circa 2000)**
**Knuth’s Statistical Tests**
**QUT’s **_**Crypt-X **_**Package**
**Parameter Sizes**
**Sequence Length****	****~ O(10****5****) - O(10****?****)**
**Block Length ****	****	****~ O(log****2**** n)**

## Closing Remarks

**Design of statistical tests for PRNGs is difficult.**
**Care should be taken to ensure that results are as accurate as they can be; highly dependent on the numerical algorithms.**
**The need exists to continuously develop new statistical tests to ensure higher quality PRNGs.**
**Designers of statistical tests must decouple the evaluation procedure from the PRNG under study.**

## Closing Remarks

**Standards described PRNG have so far not demonstrated any statistically significant results.**
**The NIST STS is applicable to both SW/HW PRNGs.**
**The number of statistical tests in our test suite varies.**
**Generalization to higher dimensional spaces for the random walks tests is a possibility.**
**Corpora of knowledge has applications to empirical statistical testing of encryption algorithms.**

## Future Work 

**Port Code To PC Environment**
**Software Testing**
**Algorithmic/Statistical Correctness**
**Computational Limits/Parameter Options**
**Completion of the NIST STS User’s Guide: Version 1.0**
**Implementation of a GUI front-end.**
**Inclusion Of Additional Tests & Improvements:**
**Moving Averages Test**
**Maximum Order Complexity Test**
**Length of the shortest FSR that can generate the sequence.**

## References

**Handbook of Applied Cryptography**, Alfred Menezes, et. al., 1997
**The Art of Computer Programming, Seminumerical Algorithms**, vol. 2, D. Knuth, Addison Wesley, Reading, Massachusetts, 1973.
**Cryptographic Pseudo-random Number in Simulation**,                  N. Macalaren, Fast Software Encryption Conference, 1993.
**“****Suggestions For Random Number Generation In Software,”       **T. Matthews, 1995 (http://www.rsa.com/rsa/developers/random.htm)
**“****Software Generation of Practically Strong Random Numbers,”  **P. Guttman, Computer Science Dept., University of Auckland, 1998.
**“****Using and Creating Cryptographic-Quality Random Numbers,” **J. Callas, 6/96 (http://www.merrymeet.com/jon/usingrandom.html)