Our test recommendation
The following code generates a 25.6 MB file from Python’s Mersenne Twister, but there’s a new twist! Every 256th byte is 42 so the badness is quite subtle. We used this for testing our fast and slow IID tests.
They both failed to detect the rogue 42s. It is a very subtle defect. The following following is the NIST test run finding the 42s:-
import random
with open('/tmp/badfile.bin', 'wb') as f:
for i in range(100_000):
for j in range(256):
r = random.getrandbits(8)
f.write(r.to_bytes(1, byteorder='big', signed=False))
r = 42
f.write(r.to_bytes(1, byteorder='big', signed=False))nist-iid-tests/cpp/ea_iid -v /tmp/badfile.bin
Opening file: '/tmp/badfile.bin'
Loaded 25700000 samples of 256 distinct 8-bit-wide symbols
Number of Binary samples: 205600000
Calculating baseline statistics...
Raw Mean: 127.161515
Median: 127.000000
Binary: false
Literal MCV Estimate: mode = 200374, p-hat = 0.0077966536964980543, p_u = 0.0078413431447085739
Bitstring MCV Estimate: mode = 102894942, p-hat = 0.50046178015564202, p_u = 0.50055160063005621
H_original: 6.994683
H_bitstring: 0.998409
min(H_original, 8 X H_bitstring): 6.994683
Chi square independence
score = 65076.192898
degrees of freedom = 65280
p-value = 0.713210
Chi square goodness of fit
score = 2279.149983
degrees of freedom = 2295
p-value = 0.588872
** Passed chi square tests
LiteralLongest Repeated Substring results
P_col: 0.00392148
Length of LRS: 6
Pr(X >= 1): 0.6991
** Passed length of longest repeated substring test
Beginning initial tests...
Initial test results
excursion: 192089
numDirectionalRuns: 1.71339e+07
lenDirectionalRuns: 9
numIncreasesDecreases: 1.28998e+07
numRunsMedian: 1.28495e+07
lenRunsMedian: 23
avgCollision: 20.745
maxCollision: 77
periodicity(1): 99912
periodicity(2): 100529
periodicity(8): 101335
periodicity(16): 99921
periodicity(32): 100602
covariance(1): 4.1559e+11
covariance(2): 4.15587e+11
covariance(8): 4.1559e+11
covariance(16): 4.15585e+11
covariance(32): 4.15579e+11
compression: 2.74362e+07
statistic C[i][0] C[i][1] C[i][2]
----------------------------------------------------
excursion 73 0 6
numDirectionalRuns 6 0 26
lenDirectionalRuns 23 6 0
numIncreasesDecreases 8 0 6
numRunsMedian 6 0 9
lenRunsMedian 23 5 1
avgCollision* 0 0 10000 <<<<
maxCollision 310 3 3
periodicity(1) 741 0 6
periodicity(2) 12 0 6
periodicity(8) 6 0 61
periodicity(16) 1919 0 6
periodicity(32) 19 0 6
covariance(1) 6 0 12
covariance(2) 6 0 14
covariance(8) 6 0 8
covariance(16) 6 0 6
covariance(32) 6 0 13
compression 6 0 15
(* denotes failed test)
** Failed IID permutation tests Surprisingly for such a simple program, ent also caught the recurring 42 in the Chi squared test, although it’s not a pure IID testing suite of course. But if you had passed IID testing, your next step would have been a randomness test and for smallish sample sizes (approx. 500 kB) ent is thee go-to program.
ent /tmp/badfile.bin
Entropy = 7.997822 bits per byte.
Optimum compression would reduce the size
of this 25700000 byte file by 0 percent.
Chi square distribution for 25700000 samples is 100190.22, and randomly
would exceed this value less than 0.01 percent of the times.
Arithmetic mean value of data bytes is 127.1615 (127.5 = random).
Monte Carlo value for Pi is 3.148333319 (error 0.21 percent).
Serial correlation coefficient is 0.000139 (totally uncorrelated = 0.0).Grudgingly we have to admit that the NIST IID test is more powerful than either of our tests :-( For interest, if you have a good and proper IID file, the NIST test is pretty quick. For example, we tested 10 MB of /dev/urandom product, and it took less than 2 minutes. It’s only dog slow when the samples are very skewed (it happens randomly as randomness is pesky), or not IID.
We therefore recommend using the NIST ea_iid test. When passed, it also directly outputs the minimum entropy. Handy. The test recommends 1,000,000 bytes(samples) but that should be attainable by most DIY entropists. 10,000,000 bytes is indicated for our fast test, but our slow test has no lower size bound.