4
$\begingroup$

I am trying to use the dieharder random number test suite.

However, this suite requires massive amount of data (this paper claims 228GB for no rewinding for every test) for most of the tests. I'd like to understand how rewinding is implemented and to know how much data is required for each test. It seems related to the tsamples value but I cannot find an exact correlation.

For example, if I generate 400MiB of data using dd if=/dev/urandom of=random.dat bs=1M count=400, this produces the following (cropped) output:

$ dieharder -a -g 201 -f random.dat
#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
   rng_name    |           filename             |rands/second|
 file_input_raw|                      random.dat|  6.38e+07  |
#=============================================================================#
        test_name   |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
   diehard_birthdays|   0|       100|     100|0.70238534|  PASSED  
# The file file_input_raw was rewound 1 times
      diehard_operm5|   0|   1000000|     100|0.74169241|  PASSED  
# The file file_input_raw was rewound 2 times
  diehard_rank_32x32|   0|     40000|     100|0.03164866|  PASSED  
# The file file_input_raw was rewound 2 times
    diehard_rank_6x8|   0|    100000|     100|0.18168084|  PASSED  
# The file file_input_raw was rewound 3 times
   diehard_bitstream|   0|   2097152|     100|0.59056568|  PASSED  
# The file file_input_raw was rewound 5 times
        diehard_opso|   0|   2097152|     100|0.19175240|  PASSED  
# The file file_input_raw was rewound 6 times
        diehard_oqso|   0|   2097152|     100|0.67542036|  PASSED  
# The file file_input_raw was rewound 7 times
         diehard_dna|   0|   2097152|     100|0.04906220|  PASSED  
# The file file_input_raw was rewound 7 times
diehard_count_1s_str|   0|    256000|     100|0.80349572|  PASSED  
# The file file_input_raw was rewound 8 times
diehard_count_1s_byt|   0|    256000|     100|0.43003125|  PASSED  
# The file file_input_raw was rewound 8 times
 diehard_parking_lot|   0|     12000|     100|0.07270933|  PASSED  
# The file file_input_raw was rewound 8 times
    diehard_2dsphere|   2|      8000|     100|0.92548415|  PASSED  

I assume that dieharder just loops over the file, keeping its pointer position when jumping to the next test and that The file file_input_raw was rewound N times is just the total count that the pointer reached the end of the file.

$\endgroup$
3
  • $\begingroup$ I think it uses 32-bits samples so the input size needs to be $4 bytes \times tsamples \times psamples$. $\endgroup$
    – DurandA
    May 20 at 8:56
  • $\begingroup$ If I am correct, the total amount of rewinds is not important as long as each test has an input larger than $4 \times tsamples \times psamples$. $\endgroup$
    – DurandA
    May 20 at 8:59
  • 2
    $\begingroup$ That question may help, and at least my answer gives a value (2 GiB = 16 Gib) that seems to work in practice. I don't know why you try to use dieharder for, but if it's to test the output of a CSPRNG: passing the test is not useful indication that the CSPRNG is theoretically correct, much less that it is correctly seeded and practically secure. This extends to other crypto algorithms. And, independently: the best option might be to remove the tests that require more data than available. $\endgroup$
    – fgrieu
    May 20 at 9:31
4
$\begingroup$

I'll be so bold as to say that no one knows for sure how much data you really need. There is no guidance on the homepage, the manpage and this thread from Duke is equally unspecific. Anecdotal evidence suggests that a 'few' GB will return a sane PASS/FAIL answer, but there will still be rewinds. For a 4 GB /dev/urandom test:-

...snip
# The file file_input_raw was rewound 43 times
      rgb_lagged_sum|  27|   1000000|     100|0.75608263|  PASSED  
# The file file_input_raw was rewound 46 times
      rgb_lagged_sum|  28|   1000000|     100|0.88574962|  PASSED  
# The file file_input_raw was rewound 49 times
      rgb_lagged_sum|  29|   1000000|     100|0.69532845|  PASSED  
# The file file_input_raw was rewound 52 times
      rgb_lagged_sum|  30|   1000000|     100|0.93874399|  PASSED  
# The file file_input_raw was rewound 55 times
      rgb_lagged_sum|  31|   1000000|     100|0.59282678|  PASSED  
# The file file_input_raw was rewound 58 times
      rgb_lagged_sum|  32|   1000000|     100|0.88988310|  PASSED  

58 times!

In your case (input file), a rewind is just that; start again from the beginning. Eight rewinds is good. I've seen 1849 rewinds. Honestly I can't understand the reasoning behind that, as all it does is retest what's been tested.

And that could be good or bad as is illustrated with the following walk over a random source. If you test and rewind the contents of box A you might expect a pass. Conversely if you test and rewind box B, monobit and runs tests are likely to fail due to the large 3:1 bias in the x axis. Repetitive rewinding clearly can't help the p values, so perhaps we need a larger sample size such as box C.

walk

All we know for certain is that Dieharder uses a lot. Your paper and my research shows that a free run of Dieharder (with no rewinds) needs approximately 225 - 250 GB! Notice that $58 \times 4 \text{GB}= 232 \text{GB}$.

There are other tests though. A more common test in the TRNG scientific literature is NIST's Statistical Test Suite, (SP 800-22). It's sample requirements are much more predictable.

And now a warning. You have to resist manipulating any randomness tests in order to get a PASS. Tweaking test parameters or selectively choosing individual tests to produce your expected result is dangerous, as a random sample is random no matter how you test it. From the manpage:-

...where a file that is too small will "rewind" and render the test results where a rewind occurs suspect.

$\endgroup$
1
$\begingroup$

In order to get a precise, hopefully definitive answer we can count the number of rewinds for each test. I generated a 1KiB file that was used as an input.

After some source code investigation, dieharder treats input files as a stream that is consumed indefinitely so every new test resumes the stream at the same place where the previous test stopped. Interestingly, dieharder has is an -s strategy flag:

if strategy is the (default) 0, dieharder reseeds (or rewinds) once at the beginning when the random number generator is selected and then never again. If strategy is nonzero, the generator is reseeded or rewound at the beginning of EACH TEST. If [...] a file is used, this means every test is applied to the same sequence (which is useful for validation and testing of dieharder, but not a good way to test rngs).

So running dieharder -a -g 201 -s 1 -f kibibyte.dat (full output) produces the following data:

test_name ntup tsamples psamples rewinds for 1 KiB remarks
diehard_birthdays 0 100 100 15000
diehard_operm5 0 1000000 100 390626
diehard_rank_32x32 0 40000 100 500000
diehard_rank_6x8 0 100000 100 234375
diehard_bitstream 0 2097152 100 102400
diehard_opso 0 2097152 100 819200
diehard_oqso 0 2097152 100 546134
diehard_dna 0 2097152 100 256004
diehard_count_1s_str 0 256000 100 25000
diehard_count_1s_byt 0 256000 100 500000
diehard_parking_lot 0 12000 100 9375
diehard_2dsphere 2 8000 100 6250
diehard_3dsphere 3 4000 100 4687
diehard_squeeze 0 100000 100 909090
diehard_sums 0 100 100 77
diehard_runs 0 100000 100 39062 test ran 2x
diehard_craps 0 200000 100 526315 test ran 2x
marsaglia_tsang_gcd 0 10000000 100 7812500 test ran 2x
sts_monobit 1 100000 100 39062
sts_runs 2 100000 100 39062
sts_serial 1-16 100000 100 39062
rgb_bitdist 1 100000 100 78125
rgb_bitdist 2 100000 100 156250
rgb_bitdist 3 100000 100 234375
rgb_bitdist 4 100000 100 312500
rgb_bitdist 5 100000 100 390625
rgb_bitdist 6 100000 100 468750
rgb_bitdist 7 100000 100 546875
rgb_bitdist 8 100000 100 625000
rgb_bitdist 9 100000 100 703125
rgb_bitdist 10 100000 100 781250
rgb_bitdist 11 100000 100 859375
rgb_bitdist 12 100000 100 937500
rgb_minimum_distance 2 10000 1000 78125
rgb_minimum_distance 3 10000 1000 117187
rgb_minimum_distance 4 10000 1000 156250
rgb_minimum_distance 5 10000 1000 195312
rgb_permutations 2 100000 100 78125
rgb_permutations 3 100000 100 117187
rgb_permutations 4 100000 100 156250
rgb_permutations 5 100000 100 195312
rgb_lagged_sum 0 1000000 100 390625
rgb_lagged_sum 1 1000000 100 781250
rgb_lagged_sum 2 1000000 100 1171875
rgb_lagged_sum 3 1000000 100 1562500
rgb_lagged_sum 4 1000000 100 1953125
rgb_lagged_sum 5 1000000 100 2343750
rgb_lagged_sum 6 1000000 100 2734375
rgb_lagged_sum 7 1000000 100 3125000
rgb_lagged_sum 8 1000000 100 3515625
rgb_lagged_sum 9 1000000 100 3906250
rgb_lagged_sum 10 1000000 100 4296875
rgb_lagged_sum 11 1000000 100 4687500
rgb_lagged_sum 12 1000000 100 5078125
rgb_lagged_sum 13 1000000 100 5468750
rgb_lagged_sum 14 1000000 100 5859375
rgb_lagged_sum 15 1000000 100 6250000
rgb_lagged_sum 16 1000000 100 6640625
rgb_lagged_sum 17 1000000 100 7031250
rgb_lagged_sum 18 1000000 100 7421875
rgb_lagged_sum 19 1000000 100 7812500
rgb_lagged_sum 20 1000000 100 8203125
rgb_lagged_sum 21 1000000 100 8593750
rgb_lagged_sum 22 1000000 100 8984375
rgb_lagged_sum 23 1000000 100 9375000
rgb_lagged_sum 24 1000000 100 9765625
rgb_lagged_sum 25 1000000 100 10156250
rgb_lagged_sum 26 1000000 100 10546875
rgb_lagged_sum 27 1000000 100 10937500
rgb_lagged_sum 28 1000000 100 11328125
rgb_lagged_sum 29 1000000 100 11718750
rgb_lagged_sum 30 1000000 100 12109375
rgb_lagged_sum 31 1000000 100 12500000
rgb_lagged_sum 32 1000000 100 12890625
rgb_kstest_test 0 10000 1000 39062
dab_bytedistrib 0 51200000 1 600000
dab_dct 256 50000 1 50000
dab_filltree 32 15000000 1 422619 test ran 2x
dab_filltree2 0-1 5000000 1 113636
dab_monobit2 12 65000000 1 253906

The test which requires the largest amount of data is rgb_lagged_sum which requires 13.2 GB when ntup=32. Ignoring other instances of rgb_lagged_sum, the second and third test with largest input are marsaglia_tsang_gcd which requires 8GB and then rgb_bitdist which requires 960MB.

An interesting take on this is that rewinds do not influence the outcome above 13.2GB (but some tests will reuse the same sequence).

$\endgroup$
1
  • $\begingroup$ Should compact the table and add the equivalent in MB in a column. $\endgroup$
    – DurandA
    May 22 at 0:29
0
$\begingroup$

The TestU01 suite for testing pseudorandom number generators incorporates tests from DieHarder (all of them, I think). On pages 5 and 6 of the journal article on the TestU01 suite (see link near bottom of same page), L'Ecuyer and Simard explain that it makes sense to test until the p-values are incredibly small, or continue to remain relatively large. In the former case, the PRNG fails the test; in the latter case, it doesn't. If the p-values are small but not very small, one can re-test several times with disjoint generated sequences "until either failure becomes obvious or suspicion disappears" (p. 5). The same informal principle applies to the subset of TestU01 contained in DieHarder. TestU01 also includes a set of modules intended for the purpose of finding "prediction formulas for the sample size $n_0$ for which the test starts to reject an RNG decisively, as a function of its period length $\rho$" (p. 25).

Of course your random source has to be capable producing that much data without repeating itself, as your question reflects, but DieHarder and TestU01 were designed for modern pseudorandom number generating algorithms with very large periods, i.e. no rewinding--if I understand the terminology in the question--for many steps.

As @fgrieu's comment indicates, passing DieHarder or TestU01 doesn't tell you anything about cryptographic security, but I'm assuming that you're using DieHarder to test whether RNG output satisfies other, non-cryptographic, criteria for RNG quality.

@PaulUszak's answer suggests the NIST SP800-22 suite for cryptographic security properties. Please see @fgrieu's comment below as well. Johnston's book Random Number Generators—Principles and Practices contains an extended survey of SP800-22.

$\endgroup$
4
  • 2
    $\begingroup$ I don't agree that "the NIST SP800-22 suite (…) clearly is designed to test for cryptographic security". The closest I know to a stated design goal is "These tests may be useful as a first step in determining whether or not a generator is suitable for a particular cryptographic application". And it's not like the NIST always states their true design goals. Dual_EC_DRBG passes NIST SP800-22! What's clear is that passing the NIST SP800-22 suite, or any test based on the output of a CSPRNG or conditioned TRNG, is not a useful indication that it is practically secure. $\endgroup$
    – fgrieu
    May 20 at 15:00
  • 1
    $\begingroup$ Ah, OK, good. Thanks @fgrieu. I'll edit my answer to point to your comment. $\endgroup$
    – Mars
    May 20 at 15:35
  • $\begingroup$ Re: " On pages 5 and 6... ". How do you figure? Correctly determined p values are uniformly distributed as $\mathcal{U}(0,1)$. I can't see how they could stabilise. p has to vary randomly, irrespective of sample size, no? $\endgroup$
    – Paul Uszak
    Jun 4 at 1:54
  • 1
    $\begingroup$ Thanks @PaulUszak. The way that I put it was incorrect. I've now rewritten that part of the answer. $\endgroup$
    – Mars
    Jun 7 at 1:15

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.