2
$\begingroup$

The dieharder tests give a clear PASSED, WEAK, etc and I'm wondering what those thresholds might be for the ent tests. While I'm sure a subjective and holistic reading of results is also helpful (especially for someone who knows a lot about RNGs and their tests), are there values that could be considered passing?

I know, for example, that the Monte Carlo Pi test should ideally be 3.143580574, but would a 4 be considered passing?

Edit: the question is better worded as failing the tests, rather than passing (see answer below).

$\endgroup$
2
$\begingroup$

Failing ENT output is a little like the length of string; elusive. So I offer an anti-answer. The following is the output from running the code below and shows a random sequence passing ENT. You'll have to use some judement to weigh output diverging from this reference test.

The code executed for 1 MB, 10MB, 100MB, 1GB and 2GB random files using a decent cryptographic PRNG:-

public class SHA1 {

public static void main(String[] args) throws Exception {
    try (DataOutputStream dos = new DataOutputStream(
            new BufferedOutputStream(
                    new FileOutputStream(
                            new File("c:\\scratch\\SHA1-1GB.bin"))))) {
        SecureRandom sr = new SecureRandom(new byte[]{42});
        byte[] data = new byte[1_000_000];


        for (long i = 0; i < 1000; i++) {
            System.out.println(i);
            sr.nextBytes(data);
            dos.write(data);
        }
    }
}
}

C:\scratch>ent sha1-1mb.bin Entropy = 7.999807 bits per byte.

Optimum compression would reduce the size of this 1000000 byte file by 0 percent.

Chi square distribution for 1000000 samples is 268.02, and randomly would exceed this value 27.54 percent of the times.

Arithmetic mean value of data bytes is 127.6351 (127.5 = random). Monte Carlo value for Pi is 3.135252541 (error 0.20 percent). Serial correlation coefficient is -0.001522 (totally uncorrelated = 0.0).

C:\scratch>ent sha1-10mb.bin Entropy = 7.999982 bits per byte.

Optimum compression would reduce the size of this 10000000 byte file by 0 percent.

Chi square distribution for 10000000 samples is 251.25, and randomly would exceed this value 55.46 percent of the times.

Arithmetic mean value of data bytes is 127.5007 (127.5 = random). Monte Carlo value for Pi is 3.140763656 (error 0.03 percent). Serial correlation coefficient is 0.000043 (totally uncorrelated = 0.0).

C:\scratch>ent sha1-100mb.bin Entropy = 7.999998 bits per byte.

Optimum compression would reduce the size of this 100000000 byte file by 0 percent.

Chi square distribution for 100000000 samples is 241.51, and randomly would exceed this value 71.86 percent of the times.

Arithmetic mean value of data bytes is 127.4998 (127.5 = random). Monte Carlo value for Pi is 3.141108366 (error 0.02 percent). Serial correlation coefficient is -0.000179 (totally uncorrelated = 0.0).

C:\scratch>ent sha1-1gb.bin Entropy = 8.000000 bits per byte.

Optimum compression would reduce the size of this 1000000000 byte file by 0 percent.

Chi square distribution for 1000000000 samples is 234.14, and randomly would exceed this value 82.14 percent of the times.

Arithmetic mean value of data bytes is 127.5055 (127.5 = random). Monte Carlo value for Pi is 3.141422821 (error 0.01 percent). Serial correlation coefficient is 0.000024 (totally uncorrelated = 0.0).

C:\scratch>ent sha1-2gb.bin Entropy = 8.000000 bits per byte.

Optimum compression would reduce the size of this 2000000000 byte file by 0 percent.

Chi square distribution for 2000000000 samples is 231.40, and randomly would exceed this value 85.30 percent of the times.

Arithmetic mean value of data bytes is 127.5032 (127.5 = random). Monte Carlo value for Pi is 3.141451323 (error 0.00 percent). Serial correlation coefficient is 0.000034 (totally uncorrelated = 0.0).

Chi & pi values

You will see both the pi approximation and chi squared values converging. For another truly random sample (pi out to 2.5 trillion places), chi is 12 as all digits become fairly equally distributed.

(Apologies for the formatting spaghetti)

$\endgroup$
0
$\begingroup$

Answered (I think pretty well) by this Reddit thread:

All tests of RNGs are based on a "null hypothesis", meaning if they fail, they show the RNG may be flawed. But if they pass, it does not mean it is good. Therefore, the question should be re-worded as "what values constitute failing the ENT tests".

  • Entropy: compressibility > 10% is probably a pretty bad fail
  • Chi-squared: anything < 10% or > 90% is suspect
  • Mean: if test source is long enough this value shouldn't be off by much; more than 10% off from 127.5 would be suspect (ie: > 140.25 or < 114.75)
  • Monte Carlo pi: the longer the source, the closer this test should get to pi (converging at roughly O(1/sqrt(n)) where n is the number of samples, even if the source is not random at all! No good formula/suggestion for this one yet.
  • Serial correlation: no value for serial correlation yet – anyone?
$\endgroup$
  • 3
    $\begingroup$ No, even if a single iteration of a generator fails a test, that does not prove it is not pseudorandom. The test must fail with non-negligible probability when the probability is taken over all possible outputs. (More precisely, with probability non-negligibly different from the probability that the same test fails on a truly random string of the same length.) $\endgroup$ – fkraiem Jul 19 '15 at 12:52
  • $\begingroup$ Sorry: I understand the first sentence but you lost me on the second! $\endgroup$ – JeffThompson Jul 19 '15 at 12:56
  • 1
    $\begingroup$ Well, even if your generator is good (or, for that matter, even with a source of true randomness), you could get very unlucky and get a string where all bits are $1$, so the condition for pseudorandomness is more subtle than just take one string and apply some tests to it. $\endgroup$ – fkraiem Jul 19 '15 at 12:58
  • $\begingroup$ Ah, so failing doesn't prove the RNG is flawed, but is suspect? $\endgroup$ – JeffThompson Jul 19 '15 at 13:07
  • 3
    $\begingroup$ Yes. In order to show that a generator is or is not secure, you must consider the probability that a test succeeds (or not) on the output of the generator for a randomly chosen seed, as opposed to the fact that it suceeds (or not) on the output of the generator for some specific seed. (And then you must compare it with the probability that the test suceeds (or not) on a truly random string of the same length as the output of the generator.) $\endgroup$ – fkraiem Jul 19 '15 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.