# How to compute the dataset size required by dieharder tests?

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. • I think it uses 32-bits samples so the input size needs to be$4 bytes \times tsamples \times psamples$. May 20 at 8:56 • 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$. May 20 at 8:59 • 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. – fgrieu May 20 at 9:31 ## 3 Answers 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. 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. 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). • Should compact the table and add the equivalent in MB in a column. May 22 at 0:29 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. • 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. – fgrieu May 20 at 15:00 • Ah, OK, good. Thanks @fgrieu. I'll edit my answer to point to your comment. – Mars May 20 at 15:35 • 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? Jun 4 at 1:54
• Thanks @PaulUszak. The way that I put it was incorrect. I've now rewritten that part of the answer.
– Mars
Jun 7 at 1:15