# Presentation: 361595

## Empirical Statistical Testing Of Cryptographic PRNGs

**Juan Soto**
*National Institute Of Standards & Technology*
**soto@nist.gov**

## Existing Packages

*Stanford University*, Donald Knuth** **
**Classical Tests**
*Florida State University*, George Marsaglia
**DIEHARD**
*Queensland University of Technology*, Helen Gustafson, Edward Dawson, William Caelli and Lauren Nielsen
**Crypt-X**
*University of Montreal*, Pierre L’Ecuyer
**TestU01 (?)**

## Project Goals

- The development of a computer package suitable in the assessment of binary stream randomness.
- Applicable to binary streams produced by both hardware and software based PRNGs.
- Warning:
- No set of statistical tests can certify a generator as appropriate for usage in a particular application.
- Statistical testing cannot serve as a substitute for cryptanalysis.

## Research Team

**The NIST RNG TWG**
**Computer Security Division**
- Miles Smid, James Nechvatal, James Dray, San Vo, Juan Soto
**Statistical Engineering Division**
- Andrew Rukhin, David Banks, Stefan Leigh, Mark Vangel, Mark Levenson

## NIST Test Suite Strengths

- Diverse research team.
- Full scientific documentation provided (each algorithm based on rigorous math).
- More advanced statistical tests.
- Uniform reporting standard (p-value).

## Pseudorandom 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)***
_**Polynomial Congruential (LCG,QCG,CCG)**_
_**Modular Exponentiation (MODEXP)**_
_**Exclusive OR (XOR)**_

## NIST Statistical Test Suite

**Frequency**
**Block Frequency**
**Cusum **
**Runs**
**Longest Run Of Ones**
**Marsaglia’s Rank*******
**Spectral (DFT)**

**Template Matchings**
**Maurer’s Universal*******
**Approximate Entropy**
**Random Excursions**
**Moving Averages**
**Lempel Ziv Complexity**
**Linear Complexity*******

## Evaluation Approaches

**Analytical**
- Probability Theory
- Information Theory
- Complexity Theory
**Graphical **
- Approximate Entropy
- Spectral Graph
- Cycle Structure

## Evaluation Procedure

**Null Hypothesis.**
- Binary stream is random.
**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 ********.**
**Success** whenever P-value  .  **Failure** otherwise.
-  is chosen *conservatively* in (0.001, 0.01].

## Numerical Experiments

**Experiment Parameters**
- 1,000,000 bits/sequence.
- 300 binary sequences/generator.
**PRNGs for which:**
- flaws** **were not** **detected
- ANSI X9.17, G-DES, G-SHA, BBS, MS, LCG, QCG2
- flaws were detected** **
- QCG1, CCG, XOR, MODEXP
- Statistically significant results detected at the 0.01 level.

## Pass Rates at 1% Significance Level

## Pass Rates at 1% Significance Level

## Depicts the cycle 

- Depicts the cycle
- structure for 3600
- binary sequences
- among 12 PRNGs.
- Clear discriminant
- among classes of
- generators.

## Status

- Spring 1998:
- Release documentation & reference implementation for peer review.
- Summer 1999:
- Release the statistical test suite and associated documents to the public.

** ****http://www.nist.gov/div893/staff/soto/sts.html**

** ****FOR MORE INFO...**

## Closing Remarks

- Benefits Of Statistical Testing
- Helps to distinguish between bad PRNGs and good PRNGs.
- Helps to ensure that the implementation of good PRNGs is in fact producing random looking binary sequences.
- Helps to evaluate other cryptographic primitives, such as encryption algorithms.

## References

*“**A computer package for measuring strength of encryption algorithms,”*** **H. Gustafson, E. Dawson, L. Nielsen, and W. Caelli, Computers & Security, 13 (1994), pages 687-697.
*Handbook of Applied Cryptography*, A. Menezes, P. van Oorschot, S. Vanstone, 1997.
*The Art of Computer Programming, Seminumerical Algorithms, Vol. 2*, Third Edition, D. Knuth, 1998.