RNG failing Restart Tests by NIST SP800-22? I have data sample of 1,000,000 bytes generated by a hardware RNG. The device is certified by ENT test suite, NIST SP800-22, DIE HARDER and TestU01.

I have tested my sample by SP800-90B_EntropyAssessment (github.com/usnistgov/SP800-90B_EntropyAssessment). Minimum Entropy Estimate is 7.88237 after which I run Restart Tests. 

My sample fails at Restart Testing and the program displays 


  Validation Failed, No Entropy Estimate Awarded. 


“Analysis and Improvement of Entropy Estimators in NIST SP 800-90B“ (PDF) says 


  Randomness has three features: unpredictability, unbiasedness and non-repeatability and and the non-repeatability is validated by restart tests. 


I want to know if my RNG is failing Restart Tests, does it mean it offers no entropy at all?
The test that fails seems to be the one in 3.1.4 (Restart Tests) of NIST SP&nbsp;800-90B (2nd Draft), specifically 3.1.4.3 (Sanity Check - Most Common Value in the Rows and Columns), failing at


  546 &nbsp; &nbsp; 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 106 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:


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.
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).
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.
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 &lt;stdint.h&gt;
#include &lt;inttypes.h&gt;
#include &lt;stdio.h&gt;

// 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 &lt; (OUTPUT_SIZE+7)&gt;&gt;3; ++j ) {
        s = 0;
        n = 32; do { // 32 pairs of rounds
            s += 0x9e3779b9;
            y += ((z&lt;&lt;4)+K0) ^ (z+s) ^ ((z&gt;&gt;5)+K1);
            z += ((y&lt;&lt;4)+K2) ^ (y+s) ^ ((y&gt;&gt;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