2
$\begingroup$

I'm currently testing the randomness of using SHA-256 in Hash_DRBG mechanism based on this research. The parameters used in the testing are the default parameters, except for when the PRNG fails a certain test, the p-sample is doubled in a subsequent test. The result is as follows.

Test n-tuple p-samples p-value Assessment
diehard_birthdays 0 100 0.43249977 PASSED
diehard_operm5 0 100 0.60606614 PASSED
diehard_rank_32x32 0 100 0.72622055 PASSED
diehard_rank_6x8 0 100 0.24741913 PASSED
diehard_bitstream 0 100 0.93753414 PASSED
diehard_count_1s_stream 0 100 0.76684762 PASSED
diehard_count_1s_byte 0 100 0.97873412 PASSED
diehard_parking_lot 0 100 0.16111731 PASSED
diehard_2dsphere 2 100 0.49536684 PASSED
diehard_3dsphere 3 100 0.23973302 PASSED
diehard_squeeze 0 100 0.67110118 PASSED
diehard_runs 0 100 0.99444050 PASSED
diehard_runs 0 100 0.70217813 PASSED
diehard_craps 0 100 0.56128192 PASSED
diehard_craps 0 100 0.57819208 PASSED
marsaglia_tsang_gcd 0 100 0.92075700 PASSED
marsaglia_tsang_gcd 0 100 0.99119972 PASSED
sts_monobit 1 100 0.09297486 PASSED
sts_runs 2 100 0.79081331 PASSED
sts_serial 1 100 0.89838273 PASSED
sts_serial 2 100 0.78716413 PASSED
sts_serial 3 100 0.92203605 PASSED
sts_serial 3 100 0.65570434 PASSED
sts_serial 4 100 0.19614051 PASSED
sts_serial 4 100 0.57925551 PASSED
sts_serial 5 100 0.23663729 PASSED
sts_serial 5 100 0.90170006 PASSED
sts_serial 6 100 0.64931499 PASSED
sts_serial 6 100 0.69010358 PASSED
sts_serial 7 100 0.42388924 PASSED
sts_serial 7 100 0.99347778 PASSED
sts_serial 8 100 0.74742090 PASSED
sts_serial 8 100 0.44604533 PASSED
sts_serial 9 100 0.57977435 PASSED
sts_serial 9 100 0.13159624 PASSED
sts_serial 10 100 0.38560171 PASSED
sts_serial 10 100 0.95434782 PASSED
sts_serial 11 100 0.57229876 PASSED
sts_serial 11 100 0.15792463 PASSED
sts_serial 12 100 0.92706928 PASSED
sts_serial 12 100 0.98019070 PASSED
sts_serial 13 100 0.84666522 PASSED
sts_serial 13 100 0.93312452 PASSED
sts_serial 14 100 0.55365506 PASSED
sts_serial 14 100 0.79327463 PASSED
sts_serial 15 100 0.23782749 PASSED
sts_serial 15 100 0.22002745 PASSED
sts_serial 16 100 0.66132471 PASSED
sts_serial 16 100 0.77182523 PASSED
rgb_bitdist 1 100 0.64747038 PASSED
rgb_bitdist 2 100 0.51877252 PASSED
rgb_bitdist 3 100 0.41006132 PASSED
rgb_bitdist 4 100 0.40851961 PASSED
rgb_bitdist 5 100 0.59300019 PASSED
rgb_bitdist 6 100 0.28861909 PASSED
rgb_bitdist 7 100 0.00372080 WEAK
rgb_bitdist 7 200 0.15287515 PASSED
rgb_bitdist 8 100 0.85025803 PASSED
rgb_bitdist 9 100 0.43605146 PASSED
rgb_bitdist 10 100 0.83149474 PASSED
rgb_bitdist 11 100 0.39785076 PASSED
rgb_bitdist 12 100 0.91967414 PASSED
rgb_minimum_distance 2 1000 0.17766404 PASSED
rgb_minimum_distance 3 1000 0.79247782 PASSED
rgb_minimum_distance 4 1000 0.51699768 PASSED
rgb_minimum_distance 5 1000 0.24978643 PASSED
rgb_permutations 2 100 0.34186729 PASSED
rgb_permutations 3 100 0.17690627 PASSED
rgb_permutations 4 100 0.32725247 PASSED
rgb_permutations 5 100 0.85283344 PASSED
rgb_lagged_sum 0 100 0.35023504 PASSED
rgb_lagged_sum 1 100 0.73612544 PASSED
rgb_lagged_sum 2 100 0.19885141 PASSED
rgb_lagged_sum 3 100 0.88639389 PASSED
rgb_lagged_sum 4 100 0.71678053 PASSED
rgb_lagged_sum 5 100 0.69452785 PASSED
rgb_lagged_sum 6 100 0.87311557 PASSED
rgb_lagged_sum 7 100 0.57060025 PASSED
rgb_lagged_sum 8 100 0.58427119 PASSED
rgb_lagged_sum 9 100 0.18178947 PASSED
rgb_lagged_sum 10 100 0.24707067 PASSED
rgb_lagged_sum 11 100 0.42055800 PASSED
rgb_lagged_sum 12 100 0.29616065 PASSED
rgb_lagged_sum 13 100 0.29282504 PASSED
rgb_lagged_sum 14 100 0.10482720 PASSED
rgb_lagged_sum 15 100 0.21482880 PASSED
rgb_lagged_sum 16 100 0.30997101 PASSED
rgb_lagged_sum 17 100 0.63437543 PASSED
rgb_lagged_sum 18 100 0.15671220 PASSED
rgb_lagged_sum 19 100 0.31534388 PASSED
rgb_lagged_sum 20 100 0.73111917 PASSED
rgb_lagged_sum 21 100 0.52711913 PASSED
rgb_lagged_sum 22 100 0.45640958 PASSED
rgb_lagged_sum 23 100 0.84830587 PASSED
rgb_lagged_sum 24 100 0.13624445 PASSED
rgb_lagged_sum 25 100 0.74267452 PASSED
rgb_lagged_sum 26 100 0.99706185 WEAK
rgb_lagged_sum 26 200 0.80227931 PASSED
rgb_lagged_sum 27 100 0.06701886 PASSED
rgb_lagged_sum 28 100 0.98841011 PASSED
rgb_lagged_sum 29 100 0.44516079 PASSED
rgb_lagged_sum 30 100 0.19377513 PASSED
rgb_lagged_sum 31 100 0.70575626 PASSED
rgb_lagged_sum 32 100 0.82280212 PASSED
rgb_kstest_test 0 1000 0.04551584 PASSED
dab_bytedistrib 0 1 0.39520224 PASSED
dab_dct 256 1 0.59555375 PASSED
dab_filltree 32 1 0.34799918 PASSED
dab_filltree 32 1 0.72922031 PASSED
dab_filltree2 0 1 0.74629061 PASSED
dab_filltree2 1 1 0.72988477 PASSED
dab_monobit2 12 1 0.09431643 PASSED

The PRNG, understandably with such a low p-value, fails at the rgb_bitdist with 7 n-tuple. However it also fails rgb_lagged_sum with p-value at 0.99706185. If i understand correctly, that p-value is the result of the final Kolmogorov-Smirnov test. What does this result indicates?

$\endgroup$
2
  • 2
    $\begingroup$ A most common cause of failure or near failure in Dieharder is too short input. Quoting the manual: "Note well that file input rands are delivered to the tests on demand, but if the test needs more than are available it simply rewinds the file and cycles through it again, and again, and again as needed. Obviously this significantly reduces the sample space and can lead to completely incorrect results for the p-value histograms unless there are enough rands to run EACH test without repetition (it is harmless to reuse the sequence for different tests). Let the user beware!." $\endgroup$
    – fgrieu
    Commented Jan 16 at 8:03
  • $\begingroup$ Thank you, @fgrieu. I understand how the input length could be a problem, but I don't understand why the assessment comes out as "WEAK" when the p-value is very high. How the generator didn't pass the test despite the p-value observed, rather than why the generator didn't pass per se. $\endgroup$
    – vnwrywn
    Commented Jan 17 at 8:58

1 Answer 1

2
$\begingroup$

As explained in the "P-values and the Null Hypothesis" section of the manual, p-values are expected to be uniformly distributed on [0,1]. Dieharder makes the very reasonable choice to flag as suspicious p-values that are very close to 0 or to 1.

That's much like when testing for the number of one bits in 1,000,000 outputs of a RNG, getting 500,001 is somewhat suspicious (there is less than one chance out of 417 to be at most 1 off the expected 500,000), more so than getting 501,452 (there is more than one chance out of 271 to be at least 1,452 off).

Here, a p-value $0.99706185$ or higher should occur with probability one out of $\displaystyle\frac1{1-0.99706185}\approx340$, which is quite unexpected for one given test, hence the WEAK. However, given the number of tests, one or two WEAK is not alarming.

Invariably, when a standard statistical test is applied to the output of a correctly implemented, at least half-decent, Cryptographically Secure Pseudo-Random Number Generator (including Hash_DRBG), and the test finds an issue, that's a false positive, or a methodology error in applying the test.

Statistical tests applied to CSPRNGs can only catch some gross mistakes (in the implementation of the CSPRNG, or in applying the test). Performing such tests is an exercise in testing, and illustrating experimentally that CSPRNGs pass all tests of randomness. They are not a valid argument of security.

Statistical tests on the output of a RNG do not have access to the structure of the RNG, when (since Kerckhoffs) access to that structure is an hypothesis in evaluating the security of a CSPRNG. Thus such statistical tests can't be valid arguments of security.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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