Newsgroups: sci.crypt
Path: illuminati.io.com!uunet!gatech!howland.reston.ans.net!news.sprintlink.
+     net!news.dorsai.org!stevalln
From: stevalln@news.dorsai.org (Steve Allen)

Subject: Re: How random is "random data"?
Message-ID: 
Sender: news@dorsai.org (Keeper of the News)
Organization: The Dorsai Embassy - New York
X-Newsreader: TIN [version 1.2 PL2]
References: 
Date: Sat, 10 Dec 1994 19:08:08 GMT
Lines: 37

rutger@euronet.nl writes

>- How can I check how random "random data" is?
>  I could of course count frequencies, but an array
>  filled with the bytes 00..FF (ascending) would then
>  be considered random, as there isn't any preference.

   Consider throwing a die until you get a six. The odds of getting
it on the first throw are 1/6. The odds of getting it on the second
throw are 5/6*1/6. On the third throw, 5/6*5/6*1/6, and so on.

   Rolling a die and generating truly random numbers share 3
properties:
 1) Only one number is generated at a time (this is important
theoretically).
 2) At any time t+s, the odds are the same as at time t.
 3) At any time, the process is independent of all that has happened
before.
   For any process that has these properties, the distribution of
times between successive occurences of the same value is exponential.

   You can test the exponentiality of your random source's
inter-arrival times by taking the logs of those times and forming an
average. If that average matches well with the theoretical value,
you've got good randomness.
   See Ueli Maurer's "A Universal Statistical Test For Random Bit
Generators", Advances In Cryptology-- Crypto '90 (Springer-Verlag).
This test does exactly that: for your n-bit generator (n=1..16), it
takes the logs of inter-arrival times for all values 0..2^n-1, and
compares the average to a perfect reference. He claims, as I
understand it, that this test reveals *any* weakness in a RNG due
to memory (violates rule 3 above).

   I recently posted a C version of this test, for PC-DOS, to the net.
-Steve