RNG failing Restart Tests by NIST SP800-22?

The test that fails seems to be the one in 3.1.4 (Restart Tests) of NIST SP 800-90B (2^nd Draft), specifically 3.1.4.3 (Sanity Check - Most Common Value in the Rows and Columns), failing at

546     If F is greater than U, the test fails.

It can not be concluded that a generator that fails this has no entropy at all. It could well be that it has some imperfection, but still outputs a fair amount of entropy, leaving it perfectly usable to seed a CSPRNG.

CAUTION: this test requires 1000 samples obtained by re-starting the source and collecting 1000 symbols. If the question's 10⁶ bytes are generated by the hardware RNG without restarting it, then the test is abused (if it had succeeded that would be meaningless). But such abuse can not be why the test fails.

It is a common event that Output of RNG fails some Randomness Rest. That can occur for any combination of four causes:

1. Goof in use of Randomness Rest (or collecting Output of RNG, but here that's unlikely given that other tests have passed); like, the format, size.. of Output of RNG is not as expected by Randomness Rest with the parameters used. The possibilities are endless. This is diagnosed as for 3.

2. Bad luck. All useful randomness tests are expected to have some rate of false alarm, with a certain probability: the P-value, which any good test documents. Here my reading is that it is 1%. Assuming this, and if possible, re-run Randomness Rest with the same parameters, and a few fresh Output of RNG. If the next two tests fail, we can exclude bad luck with high confidence. Otherwise (that is, if some succeed), we can suspect bad luck (or 1.), and we should use a form sequential analysis to decide. As a rough approximation: run another 997 tests, compute the number of tests out of 1000 that failed (which should be in the order of 10), reject bad luck with high confidence if that's more than 27 (still suspect some issue and investigate thoroughly if that's more than 15).

3. Goof in Randomness Test (either it's implementation, or definition if that's a draft or has otherwise has not stood intense scrutiny). The general method to detect this is to run randomness test against files generated by a simple (thus hopefully correct and acceptably fast) CSPRNG (one is given below). The proportion that fails should be about the documented P-value.

4. Defective RNG. Conclude this after having eliminated all the rest.

Here is a simple generator of pseudo-random sequence:

// Simple generator of cryptographically secure pseudorandom sequence. // The 64-bit block cipher TEA is used in CFB mode to encipher // plaintext consisting of the block number. #include <stdint.h> #include <inttypes.h> #include <stdio.h> // For a different sequence, change these arbitrary 32-bit constants, // used as key for the TEA block cipher. // Note: in David Wheeler and Roger Needham's TEA, each key has 3 other // equivalents, as the high-order bits of K0/K1 and K2/K3 cancel out. #define K0 0x7638d4f2 #define K1 0xabe32749 #define K2 0x56b81d0e #define K3 0x4ed51d62 // output size, multiple of 8 #define OUTPUT_SIZE 1000000 int main(void) { uint32_t j, n, s, y=0, z=0; for( j=0; j < (OUTPUT_SIZE+7)>>3; ++j ) { s = 0; n = 32; do { // 32 pairs of rounds s += 0x9e3779b9; y += ((z<<4)+K0) ^ (z+s) ^ ((z>>5)+K1); z += ((y<<4)+K2) ^ (y+s) ^ ((y>>5)+K3); } while (--n); z ^= j; // CFB; makes short cycles virtually impossible // portably format in lowercase hexadecimal printf("%08"PRIx32"%08"PRIx32, y, z); } return 0; } // Generates one million octets expressed as two million characters // in lower-case hexadecimal on standard output; when expressed in // ASCII as two million octets, their hash per SHA-256 is // d5b727ef6a9177c897b68085d60a7660f6f6b1dbf09cb7e91fe59da3a66d4e2d