NIST SP800-22 Test Protocol
How Eormen tests 1 GiB entropy blocks against the US government’s official randomness standard: all 15 tests explained, with the implementation details for testing at 1 GiB scale.
Overview
This document covers the comprehensive statistical test results from the NIST SP800-22 Rev. 1a randomness test suite, as applied to 1 GiB blocks of entropy data generated by Eormen entropy systems. These results provide rigorous mathematical validation of the randomness quality of the entropy blocks.
What is NIST SP800-22 Testing?
The NIST Special Publication 800-22 Revision 1a represents the internationally recognised standard for evaluating random number generators used in cryptographic applications. Developed by the U.S. National Institute of Standards and Technology, this test suite employs 15 distinct statistical tests to examine different aspects of randomness.
For cryptographic applications, true randomness is essential. Any patterns or biases in random data can create vulnerabilities that compromise security. The NIST test suite provides mathematical assurance that the entropy data exhibits the statistical properties expected from truly random sequences.
Testing 1 GiB Blocks: The Challenge and Solution
Standard NIST test implementations typically process small files (a few megabytes at most) by loading entire sequences into memory. Testing 1 GiB blocks (containing over 8.5 billion bits) required significant engineering enhancements whilst maintaining absolute compliance with NIST mathematical specifications.
Key Enhancements Implemented
- Memory-efficient processing: All tests were enhanced to process data in streaming chunks (typically 1 MiB at a time), enabling analysis of the full 1 GiB blocks without requiring excessive RAM.
- Computational optimisation: Advanced vectorised operations and optimised algorithms reduced processing time from potentially days to manageable timeframes whilst maintaining mathematical rigour.
- Complete data analysis: Unlike some implementations that sample portions of large files, these tests analyse the complete 1 GiB block, ensuring comprehensive validation.
- Preserved mathematical integrity: All NIST-specified formulas, thresholds, and statistical methods remain exactly as published, ensuring results are directly comparable to standard implementations.
File Structure and Metadata
EORM entropy blocks contain:
- 1,073,741,824 bytes (1 GiB) of entropy data
- 64 bytes of metadata appended after the data
| Metadata field | Byte offset | Size | Description |
|---|---|---|---|
| Nonce | 0–15 | 16 bytes | Unique identifier for this generation session |
| Timestamp | 16–23 | 8 bytes (little-endian) | Generation time |
| Filename | 24–55 | 32 bytes (UTF-8) | Original filename |
| File size | 56–63 | 8 bytes (little-endian) | Total file size |
Understanding the Test Results
The JSON results file contains four main sections:
1. Test Identification
- nonce: 16-byte unique identifier extracted from the EORM block metadata.
- data_only_sha256: SHA-256 hash of the 1 GiB entropy data (excludes metadata).
- complete_file_sha256: SHA-256 hash of the entire file (data + metadata).
- metadata_only_sha256: SHA-256 hash of the 64-byte metadata section.
- generation_timestamp_utc: When the entropy block was created.
- data_size_bytes: Confirms exactly 1,073,741,824 bytes (1 GiB) were tested.
2. Test Configuration
- specification: Confirms NIST SP800-22 Rev. 1a compliance.
- significance_level: 0.01 (standard 99% confidence level).
- pass_criteria: Tests pass when p_value ≥ 0.01.
3. Individual Test Results
Each of the 15 tests provides the result (PASSED or FAILED), the p-value (statistical probability; higher values indicate better randomness), a plain-English assessment of what the test found, and the specific metrics measured.
4. Test Suite Summary
The overall result shows PASSED only if all 15 tests pass, with the percentage of tests passed and a professional assessment of randomness quality.
The 15 NIST Tests
All 15 tests run on the full 1 GiB block. Select any test to see how it was run and what a passing result means.
- What it measures
- Whether the data contains approximately equal numbers of 0s and 1s.
- How Eormen tested 1 GiB
- Processed the entire file in chunks, maintaining running counts without loading all 8.5 billion bits into memory simultaneously.
- What PASSED means
- The entropy has the expected 50/50 bit balance of random data.
- What it measures
- Whether the proportion of 1s remains consistent across different sections of the data.
- How Eormen tested 1 GiB
- Divided the data into optimal-sized blocks (10,000 bits each for 1 GiB files) and verified frequency consistency across all blocks.
- What PASSED means
- No sections of the data show unusual concentrations of 0s or 1s.
- What it measures
- Whether sequences of consecutive identical bits (runs) occur as frequently as expected in random data.
- How Eormen tested 1 GiB
- Tracked runs across chunk boundaries to ensure accurate counting throughout the entire file.
- What PASSED means
- The data transitions between 0s and 1s at the expected rate for random sequences.
- What it measures
- Whether the longest sequences of consecutive 1s match expectations for random data.
- How Eormen tested 1 GiB
- Analysed blocks of 10,000 bits each, categorising longest runs without storing block contents.
- What PASSED means
- No unexpectedly long sequences of 1s that might indicate patterns.
- What it measures
- Whether binary matrices formed from the data have the expected mathematical properties of random matrices.
- How Eormen tested 1 GiB
- Constructed and analysed thousands of 32×32 bit matrices using streaming techniques.
- What PASSED means
- The data’s mathematical structure matches that of random sequences.
- What it measures
- Whether the data contains periodic patterns when analysed in the frequency domain.
- How Eormen tested 1 GiB
- Applied spectral analysis to the first million bits (sufficient for detecting periodic features per NIST guidelines).
- What PASSED means
- No hidden repeating patterns detected in the entropy.
- What it measures
- Whether specific bit patterns occur with the expected frequency.
- How Eormen tested 1 GiB
- Searched for a randomly selected 9-bit pattern across million-bit blocks using efficient pattern matching.
- What PASSED means
- Pattern occurrences match random distribution expectations.
- What it measures
- How often a specific pattern (nine consecutive 1s) appears when searching with overlaps.
- How Eormen tested 1 GiB
- Scanned 968 blocks of 1,032 bits each for the test pattern using memory-efficient algorithms.
- What PASSED means
- The test pattern appears with appropriate frequency for random data.
- What it measures
- Whether the data can be compressed, as truly random data should be incompressible.
- How Eormen tested 1 GiB
- Analysed pattern recurrence distances using sophisticated streaming algorithms that handle millions of patterns efficiently.
- What PASSED means
- The entropy cannot be significantly compressed, confirming randomness.
- What it measures
- Whether bit sequences have appropriate algorithmic complexity.
- How Eormen tested 1 GiB
- Applied the Berlekamp-Massey algorithm to 2,000 blocks of 500 bits each, computing linear complexity distributions.
- What PASSED means
- The data exhibits the complex structure expected from random sequences.
- What it measures
- Whether all possible bit patterns of given lengths occur with equal frequency.
- How Eormen tested 1 GiB
- Tracked frequencies of all 16-bit patterns (65,536 possibilities) across 100 million bits using sparse storage techniques.
- What PASSED means
- No bit patterns appear significantly more or less than expected.
- What it measures
- The rate of entropy generation by comparing pattern frequencies at different lengths.
- How Eormen tested 1 GiB
- Compared 10-bit and 11-bit pattern frequencies across 10 million bits using unified tracking systems.
- What PASSED means
- The entropy generation rate is consistent with true randomness.
- What it measures
- Whether the running sum of the data (treating 0 as −1 and 1 as +1) stays within expected bounds.
- How Eormen tested 1 GiB
- Performed both forward and backward cumulative sum calculations, with the backward test using the last 100 million bits.
- What PASSED means
- No systematic bias causing drift in cumulative values.
- What it measures
- How often the cumulative sum visits specific values during “excursions” from zero.
- How Eormen tested 1 GiB
- Identified and analysed all complete cycles in the cumulative sum using streaming detection.
- What PASSED means
- State visits within cycles match random walk theory.
- What it measures
- The total number of times specific cumulative sum values are reached.
- How Eormen tested 1 GiB
- Tracked visits to 18 different states throughout the entire file using memory-efficient counting.
- What PASSED means
- Overall state visit frequencies align with theoretical predictions.
Interpreting the Results
Understanding P-Values
- P-value ≥ 0.01: Test PASSED (99% confidence the data is random).
- P-value < 0.01: Test FAILED (statistical evidence of non-randomness).
- Higher p-values indicate stronger randomness properties.
Overall Assessment
- All Tests PASSED: The entropy block exhibits excellent randomness suitable for cryptographic use.
- Any Test FAILED: Indicates potential weaknesses that should be investigated.
Common Questions
Why test the full 1 GiB when smaller samples might suffice?
Complete testing ensures no patterns exist at any scale within the entropy blocks, providing maximum assurance for critical applications.
Can these results be compared to standard NIST test results?
Yes. Despite Eormen's enhancements for large files, all mathematical specifications remain identical to standard NIST SP800-22 implementations. Results are directly comparable.
File Authenticity
The results file includes cryptographic verification using a three-tier hashing system:
- Data-only SHA-256: Verifies the entropy data independently. Remains constant for reproductions.
- Complete file SHA-256: Verifies the entire file has not been modified.
- Metadata-only SHA-256: Verifies the metadata section.
- Nonce: Links results to the specific EORM generation session.
- Timestamp: Unix timestamp confirming when the entropy was generated.
This three-tier approach ensures both data integrity and proper attribution to the original generation session. The data-only hash remains constant for reproductions, whilst the complete file hash verifies the entire file has not been modified.