RNG quality verification

[Travis H.]

On 12/22/05, Philipp Gühring <pg at futureware.at> wrote:
> So if I extract the key, remove the first and the last bit, then I should have
> the pure random numbers that are being used. If I do that with lots of keys,
> I should have a good amount of random material for the usual statistical
> tests.

The only thing is, you cannot test in randomness, and it is an abuse
of statistics to make predictions about individual events -- they
describe populations.  The best thing you could do is combine them
with a truly random source that you control.  Of course then your
users may not trust you, so you have to do a cryptographically strong
combination such that control of one of the inputs doesn't translate
into control of the outputs.  For example, you cannot simply XOR them
or you could force the key to be anything of the same length by
choosing an appropriate stream.  Also, you could not do this with
small input spaces or else exhaustive search is trivial (try every
input until the output is what you want).

The best you could do is examine (reverse engineer) the RNGs in the
products, and whatever seeds them, and then create tests for their
nonrandom properties, and then see if the tests work.  This would,
however, not tell you anything you didn't already know once you had
examined the internals.  You might be able to find structure in their
outputs through blind application of general-purpose statistics, but
it will likely take a great deal more output, even with supposedly
sensitive statistics like double-sided Kolmogorov-Smirnof.

As a pathological example, my RNG may output the text of the King
James Bible, encrypted with AES-CBC using a counter as the key, and
uniquified across instances by using a processor serial number or
licence number as an IV.  Unless you knew this, you would be
hard-pressed to tell they were not random and in fact totally
predictable to anyone who knows the "secret".  If a general statistic
could distinguish this from a random stream, I think it would imply a
weakness in AES-CBC.  The tests would likely fail until enough output
was generated that it started to repeat itself.  On the other hand, I
could decrypt it with a counter and see what pops out, and all I'd
have to do is distringuish the KJV from a random stream.

I'd look at seeding techniques first, as that's an easy win. 
Predictable seed -> predictable output.  If that bootstrap is wrong,
you can treat everything else as an oracle and still get a good
distinguisher.
--
http://www.lightconsulting.com/~travis/
"You are free... to do as we tell you!" -><-
GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com