Testing and Validating RNG Implementations

Random number generator testing faces a fundamental challenge: truly random sequences and pseudorandom sequences from a good PRNG look identical to statistical tests. No finite-length test can prove a sequence is random — statistics can only detect non-randomness with some confidence. Testing validates that an RNG does not have obvious biases or patterns, but cannot prove cryptographic security. Cryptographic RNG testing has two distinct goals: (1) statistical quality — verifying output distribution looks uniform and independent; (2) cryptographic strength — verifying the DRBG algorithm is implemented correctly and the security claims hold. These require different test approaches.

NIST SP 800-22 provides 15 statistical tests for evaluating bit sequences. Tests include: Frequency (monobit) test — proportion of 1s should be close to 0.5. Block frequency test — frequency of 1s in each m-bit block. Runs test — number of uninterrupted runs of identical bits. Longest run test — length of the longest run of 1s. Binary matrix rank test — rank of binary matrices formed from the sequence. Spectral test (DFT) — detect periodic patterns. Overlapping template matching — count occurrences of specific patterns. Maurer's universal statistical test — compress the sequence, measure how much shorter it gets. Each test produces a p-value; p < 0.01 suggests non-randomness. Tests run on 1 million to 1 billion bits.

TestU01 (L'Ecuyer and Simard, 2007) is a comprehensive battery of statistical tests widely used in the RNG community. SmallCrush: 10 tests, ~35 seconds, appropriate for quick checks. Crush: 144 tests, ~2 hours. BigCrush: 160 tests, ~24 hours. BigCrush tests catch subtle correlations that NIST SP 800-22 misses. Well-designed cryptographic DRBGs (HMAC_DRBG, CTR_DRBG) pass BigCrush trivially — their output is computationally indistinguishable from random to polynomial-time algorithms. Non-cryptographic PRNGs (Mersenne Twister, linear congruential generators) fail some BigCrush tests. BigCrush failure is a strong indicator the RNG should not be used for cryptographic purposes.

SP 800-90B and 90A specify health tests that DRBGs must perform continuously during operation. Continuous RNG Test (CRNGT): each generated block is compared to the previous block — if they are equal (stuck RNG), the DRBG must enter an error state and stop generating. Repetition Count Test: if consecutive samples have the same value repeated more times than statistically expected given the entropy estimate, fail. Adaptive Proportion Test: if the most frequent value occurs more than a threshold number of times in a window, fail. These health tests detect entropy source failures (stuck sensor, HWRNG hardware fault) before they silently compromise cryptographic key generation.

PractRand is a modern RNG testing tool designed for online (streaming) evaluation, analyzing the sequence as it is generated rather than requiring a predetermined length. It applies tests including gap tests, bit distribution tests, and spectral tests with adaptive precision. PractRand is particularly effective at detecting RNGs that produce good short sequences but reveal patterns over billions of bits. Cryptographic DRBGs produce output that PractRand cannot distinguish from random regardless of length — this is the operational definition of computational indistinguishability. PractRand is also used to evaluate entropy sources (testing /dev/urandom output, RDRAND output) to detect hardware failures or systematic biases.

The Cryptographic Algorithm Validation Program (CAVP) provides official test vectors for SP 800-90A DRBGs. CAVP testing involves submitting an implementation to NIST's automated test system with known-answer test (KAT) vectors: given a specific entropy input, nonce, personalization string, and additional_input, the implementation must produce the exact expected output bits. CAVP does not test statistical properties — it tests algorithmic correctness. FIPS 140-3 certification requires CAVP validation for all cryptographic algorithms used within the module boundary. CAVP test vectors are publicly available from NIST's ACVP (Automated Crypto Validation Protocol) server and are integrated into OpenSSL, mbedTLS, and BoringSSL test suites.

Before a DRBG can be initialized securely, its entropy source must be validated. SP 800-90B defines: (1) Entropy estimate — measure the actual entropy per bit using statistical tests (min-entropy estimation). (2) Startup tests — verify the entropy source produces valid output before first use. (3) On-demand tests — optional tests triggered by the application. (4) Noise source health tests — detect hardware degradation. Common entropy sources and their estimated entropy per bit: CPU RDRAND/RDSEED (~1 bit/bit, hardware certified); /dev/urandom (mixes multiple sources, entropy estimate conservative); ring oscillator TRNG (0.5-0.9 bits/bit depending on design); ADC noise (0.1-0.5 bits/bit). SP 800-90B validation requires laboratory testing with specialized equipment.

Virtual environments introduce specific RNG testing challenges. VMs may see low-entropy conditions at startup (no hardware events) or after snapshot restoration (state reset). Docker containers share the host kernel RNG — a container cannot directly test the underlying entropy quality. Tests for VM deployments: (1) Measure time to /dev/random read completion — long waits indicate insufficient entropy. (2) Test for duplicate UUIDs or keys generated in parallel VM instances (a real failure mode documented in cloud deployments). (3) Verify VIRTIO-RNG (virtio_rng.ko) is loaded in VMs — this provides host-to-guest entropy injection. (4) Audit application startup sequence: does key generation happen before sufficient entropy is available?

Testing RNG fork safety prevents a subtle vulnerability: when a process forks, both parent and child share the same DRBG state, causing them to generate identical sequences. Detection: spawn N child processes, generate a UUID in each, verify all UUIDs are unique. If any two match, the RNG is not fork-safe. OpenSSL fixed a fork-safety bug in 2020 (CVE-2020-1971 did not directly involve DRBG but the pattern is similar). Current OpenSSL uses a PID-based seed update: if the PID has changed since the last call (indicating a fork), the DRBG is automatically reseeded. Testing this: run the test before and after a fork, confirm the reseeding occurred by verifying distinct outputs.

A practical audit checklist for RNG implementations: (1) Is the RNG initialized from the OS (getrandom, BCryptGenRandom) rather than time-based seeds? (2) Is the DRBG type a NIST SP 800-90A approved mechanism (Hash, HMAC, CTR)? (3) Is the seed length sufficient for the claimed security strength? (4) Is reseeding triggered periodically or after a fixed number of generate calls? (5) Does the implementation handle fork safety (reseeding after fork)? (6) Are health tests enabled and do they halt the system on failure? (7) Is state zeroized on shutdown? (8) Are CAVP test vectors run in CI/CD? (9) Are entropy estimates documented and validated? (10) For FIPS requirements: is the module FIPS 140-3 certified?

Historical RNG failures demonstrate the stakes. Debian OpenSSL (2006-2008): a patch accidentally removed two lines of entropy collection code, reducing the seed pool to a 15-bit PID space — only 32,767 possible SSH keys were generated for the entire Debian user base. All Debian-generated SSH host keys and user keys needed replacement. Android Bitcoin wallets (2013): Android's SecureRandom used a Java-level seeding that failed on some devices, causing duplicate k values in ECDSA signatures — which directly revealed private keys. Sony PS3 (2010): used a constant nonce in their ECDSA firmware signing, allowing private key extraction from two signatures (same k across different messages reveals the key via simple algebra).

Which of the following tests detects that a DRBG might be generating stuck output (same value repeatedly)?

Statistical tests (NIST SP 800-22, TestU01 BigCrush, PractRand) verify output quality but cannot prove cryptographic security. CAVP known-answer tests verify algorithmic correctness of SP 800-90A implementations. SP 800-90B entropy source tests (min-entropy estimation, health tests) validate the seed input. Continuous RNG Test (CRNGT) detects stuck-at output in real time. VM and container deployments require entropy injection (VIRTIO-RNG) and startup entropy checks. Fork-safety testing verifies child processes do not inherit parent DRBG state. Real-world failures (Debian, Android) demonstrate that RNG bugs lead directly to cryptographic key compromise. Audit checklists formalize these checks for production deployments.