NIST SP 800-22 Randomness Test Suite

US Federal Standard: NIST SP 800-22 Rev. 1a is the mandatory randomness test suite for FIPS 140-2/3 cryptographic module validation and NSA Suite B compliance. Evaluates bit sequences across 15 independent statistical dimensions.

NIST SP 800-22 Rev. 1a Test Battery

All 15 tests evaluate a null hypothesis that the input sequence is produced by a truly random process. A test fails when its p-value falls below the significance level $\alpha = 0.01$:

§	Test Name	Pass Criteria	Description
2.1	Frequency (Monobit)	$p \ge 0.01$	Proportion of zeros and ones across the entire sequence.
2.2	Block Frequency	$p \ge 0.01$ ($m=128$)	Proportion of ones within $M$-bit non-overlapping blocks.
2.3	Runs	$p \ge 0.01$	Total number of uninterrupted identical bit sequences.
2.4	Longest Run of Ones	$p \ge 0.01$	Longest run of consecutive ones within an $M$-bit block.
2.5	Binary Matrix Rank	$p \ge 0.01$ (32×32)	Linear independence of sub-matrices of the sequence (planned).
2.6	DFT / Spectral	$p \ge 0.01$	Periodic structure detected via discrete Fourier transform (planned).
2.7	Non-overlapping Template	$p \ge 0.01$	Occurrences of pre-specified aperiodic patterns (planned).
2.8	Overlapping Template	$p \ge 0.01$	Occurrences of overlapping runs of ones (planned).
2.9	Maurer’s Universal	$p \ge 0.01$	Compressibility proxy via universal statistical test (planned).
2.10	Linear Complexity	$p \ge 0.01$	Length of the LFSR producing the sequence (planned).
2.11	Serial Test	$p \ge 0.01$ ($m=16$)	Frequency of all possible overlapping $m$-bit patterns (planned).
2.12	Approximate Entropy	$p \ge 0.01$ ($m=10$)	Compares frequencies of overlapping $m$ and $(m+1)$-bit blocks (planned).
2.13	Cumulative Sums	$p \ge 0.01$	Maximum excursion of a random walk derived from the sequence (planned).
2.14	Random Excursions	$p \ge 0.01$ (8 states)	Number of cycles visiting each of 8 states in a random walk (planned).
2.15	Random Excursions Variant	$p \ge 0.01$ (18 states)	Total visits to 18 states during a random walk (planned).

[!NOTE]
§2.1–§2.4 are fully implemented. §2.5–§2.15 are specification stubs shown as NOT IMPLEMENTED in the dashboard — they will be enabled in future releases.

Minimum Sequence Length

NIST recommends a minimum of 1,000,000 bits (125,000 bytes) per sequence for reliable p-value estimation. Shorter sequences may produce INSUFFICIENT DATA for some tests.

When to Use NIST SP 800-22

FIPS 140-2 / 140-3 Cryptographic Module Validation: Required randomness testing for NSA/NIST cryptographic module certification. The SP 800-22 battery is the US government standard applied to AES key generators, DRBG implementations, and entropy sources in validated modules.
DRBG Seed Material Validation: Verifying that raw entropy harvested from hardware sources (thermal noise, ring oscillators, quantum RNG) passes all 15 NIST criteria before being used to seed NIST-approved DRBGs (AES-CTR-DRBG, Hash-DRBG, HMAC-DRBG per SP 800-90A).
Stream Cipher & Block Cipher Output Analysis: Testing the output distribution of ChaCha20, Salsa20, AES-CTR, or any keystream generator to verify pseudorandom uniformity under different key/nonce combinations.
Research & Academic Benchmarking: Standard reference battery for comparing novel RNG algorithms in publications targeting IEEE/IACR venues.

Interpretation Tip: A single p-value below 0.01 does not conclusively prove non-randomness — approximately 1% of tests will fail by chance for a truly random sequence. NIST recommends testing multiple independent sequences (at least 55 sequences of 1 Mbit) and examining the proportion of failing tests.

Sequence Length Warning: NIST SP 800-22 was designed for sequences of exactly 1,000,000 bits. Tests §2.5–§2.15 in particular require long sequences for reliable chi-square approximations. Short files will produce misleading p-values.