# 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.

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?

• Run ent and see what that says. Nothing has no entropy at all. I don't like any randomness test where you have to configure the type of randomness you're looking for... – Paul Uszak Oct 20 '17 at 11:22
• @PaulUszak Huh? OP writes “The device is certified by ENT test suite, NIST SP800-22, DIE HARDER and TestU01.” (emphasis mine), which covers your tip Run ent and see what that says. As for entropy, OP already got a result of “Minimum Entropy Estimate is 7.88237 This question is about the restart tests OP did after that – which fail, and confuses OP who isn’t sure if that “Minimum Entropy Estimate” is indeed correct or if he's doing the restart testing in a wrong way. – e-sushi Oct 20 '17 at 13:28
• @e-sushi We're not talking about the device though are we? We're talking about the test sample. ent will confirm said entropy. Never mind... – Paul Uszak Oct 20 '17 at 13:40
• Have you had any luck in passing the tests? I'm curious... – Paul Uszak Nov 25 '17 at 16:51
• @PaulUszak, I have generated two different datasets for my test. First dataset is the "Continuous Stream of 1,000,000 B" and second is "Restart Dataset". For the generation of Restart Dataset, I have used DevCon Utility to Restart my device. I generate 1000 B, then restart my device using Devcon, then generate 1000 B, so on. Using this method, I generate 1000 files, each of 1000 B with Devcon Restart in between each file. I run " independent and Identically distributed test" on Continuous Stream & Restart Test on Restart Dataset. – R. Sam Nov 27 '17 at 9:45

The test that fails seems to be the one in 3.1.4 (Restart Tests) of NIST SP 800-90B (2nd 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 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:

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

• 1) Are you correct in your CAUTION? You can't physically restart a TRNG 1000 times for a test can you? Is this the correct interpretation of restart? 2) Before tossing the device, it would be prudent to try another test suite. One that doesn't have so many configuration options. That explains my reference to ent as a randomness litmus test. – Paul Uszak Oct 20 '17 at 16:58
• @PaulUszak: 1) Yes. The Restart Test is an important test (countless fielded devices used to fail it; see e.g. this). I often reinitialize my TRNGs for such testing, with an automated script. That's a Smart Card, usually in a PC/SC reader, which supports power-off/power-on cycles by software. If I was making HSMs, I'd have to devise a way to power-cycle the PC including it; testing would be slow, but still feasible (there's >3000 minutes in a week-end). $\$ 2) Agreed: less options, less goofs. – fgrieu Oct 20 '17 at 17:11
• @fgrieu, now I understand that my Restart Dataset is not properly generated. I need to generate 1000 files, each of 1000 bytes by restarting hardware RNG in between each file. Can you share your automated script for generating files, if possible. I am using a USB based hardware RNG. – R. Sam Oct 22 '17 at 11:23
• @R.Sam: the reason why the test fails should have nothing to do with the fact that your Restart Dataset is not properly generated. My test script can't be shared and wouldn't help (it uses a non-standard command line PC/SC tool). To power off, that tool ends up using SCardDisconnect with SCARD_UNPOWER_CARD, then an appropriate delay. That's doable in python. An oscilloscope is useful to check that is honored by the Smart Card reader. – fgrieu Oct 22 '17 at 18:13
• @R.Sam It's simple. Generate 1MB from /dev/urandom using disc destroyer (dd) or download a binary version of pi from the internet. Both should pass any test. Substitute for your restart file and test. If it fails then it's your testing methodology /program. – Paul Uszak Oct 27 '17 at 20:52

It's easy to test the restart test. As I commented earlier, generate 1MB from /dev/urandom using disc destroyer (dd) or download a binary version of pi from the internet. 1000 concatenated blocks of 1000 random bytes should be indistinguishable from a single 1MB random sequence. Use that as the restart test file. If it fails, then it's definitely your test methodology.

Assuming that your methodology is sound, it's probably that your device just doesn't generate good entropy from power up. I would not be surprised as electronics take some time to warm up and settle. Capacitors need to be charged and voltage spikes have to diminish. A good device should wait for a period for this to happen prior to commencing output. But it might not, especially if it's a small USB thing made in a garage (as many appear to be). Take for example the SG100. It's a pile of rubbish with technical documentation that's full of errors and a schematic that looks as if my 11 year old drew it. The reason I mention this one, it that it runs casinos like Gala.

I wouldn't worry too much about the restart tests. If you look at governmental testing of large consumers of random numbers ie. casinos and lotteries, it's only the long run randomness that's enforced. If you look at the RNG certification for some casinos, they use custom statistics and DIEHARD anyway. They don't use NIST testing as it's not relevant for return to player ratios. The most important thing is that you know how your device behaves. If it takes 2 mins to warm up, so be it.

Test the test with pi and see...