mooltipass_trng.py

"""Looking for collisions in Mooltipass "TRNG" output.

The "TRNG" outputs 32 bit blocks whitened with Jenkins one at a time hash,
keeping no state between samples. Running ent or diehard on the output stream
produces a predictable "pass" result, since these tests do not take the 32 bit
block structure into account.

Excessive collisions found by the following test would disprove the null
hypothesis that each 32 bit sample from the "TRNG" is uniformly distributed.

> Total samples: 250000
> Expected repeats: 14.5514335175
> Actual repeats: 8
"""
import urllib2
SAMPLE_URL = 'https://raw.githubusercontent.com/limpkin/mooltipass/master/source_code/src/RNG/random.bin'
WGET = True
b = urllib2.urlopen(SAMPLE_URL) if WGET else file('random.bin','rb')
b = b.read()

# build dictionary of occurance counts per 32bit sample
d = {}
for n in range(0,len(b),4):
    s = b[n:n+4]
    d[s] = 1 if s not in d else d[s] + 1

# show stats
sample_count = len(b) / 4
sample_repeats = 0
for k in d:
    if d[k]>1:
        sample_repeats += 1
        print '  Sample {0} occurred {1} times at offset {2}.'.format(
            k.encode('hex'), d[k], hex(b.find(k)))
print 'Total samples:', sample_count

# compare to expected value
N = 2**32
n = sample_count
#                   xxxxxxxxxxx          chance of sample not colliding with 1
exp_val = n * (1 - (1 - (1.0/N))**(n-1))
#                   xxxxxxxxxxxxxxxxxxx  chance of 1 sample not colliding in n
#         ############################## exp. # of samples colliding
print 'Expected repeats:', exp_val
# Sanity check of calculation precision in Wolfram Alpha:
# http://www.wolframalpha.com/input/?i=250000+*+%281+-+%281-+%281%2F%282**32%29%29%29**%28250000-1%29%29
print 'Actual repeats:', sample_repeats