At 09:11 PM 8/17/99 -0700, Nick Szabo wrote:
>>how it was prepared. There simply *cannot* be an all-purpose statistical
>>test.
>
>Quite so. I'd like to see what Maurer's "universal" test
>says about the entropy of completely predictable sequences
>like the following:
>
>(1) pi
>(2) Champernowne's number (0.12345678901011121314151617181920...)
>
Look, no test can distinguish between an arbitrarily
large-state PRNG and a 'real' RNG. Pi's digits will
appear fully entropic, under MUST, Diehard, etc. Even
though its Kolomogorov/Chaitin-complexity is simple (ie, the program that
computes Pi is short). Pi is not random,
though its digits (and all N-tuples of digits, etc.) are evenly
distributed. This *is* a profound point.
Dunno about C's number, suspect its the same.
Maurer, BTW, points out that his test is only
useful if you know you have a real random bitstream
generator. (Any faults in this exposition are my own.
I have never met or corresponded with Maurer, in fact.)
But if you cut through the philosophical boolsheet,
and elegant computation-theory definitions of complexity,
you are left with a problem: how to measure the entropy
of a sample of a source, e.g., /dev/random's input. And it comes down to F
log F no matter what algorithm you use to approximate it.
The only philosophy you need is this: the Adversary doesn't
know the internal (e.g., atomic) state of your hardware.
Therefore, the measured state is unpredictable; but it probably isn't
uniformly distributed. So you distill it. Until
you've got fully independent bits. And you hash and stir
it when you read it, for 'security in depth', ie, extra
layers of protection.
.........
Again, the question is, what is the alternative?
I'm willing to discuss e.g., a function of raw vs. gzip-compressed file
size as a measure of entropy. I think
my major point is, measure it as best you can.
I stumbled upon MUST; its a measure, so easier to handle
than a multidimensional spectrum like Diehard; more informative
than FIPS-140 binary tests. I am open
to suggestions as to how to quantitatively evaluate
RNGs, for /dev/r or otherwise.
Cheers,
David Honig
