Randomness testing

We have been asked by a customer if we have any tests that demonstrate 
the randomness of the SSLeay random number generator (augmented by some
sound-card random number seeding that we wrote).

I'd like to find some standard implementation for testing randomness, but 
Schneier offers no help (other than a reference to Knuth Vol 2), and I
don't know where else to turn.

I realise that cryptographic randomness requires unpredictability, and
this quality depends upon closed-world assumptions about unknown individuals'
predictive powers, but we have to live with that.

-- 
Clifford Heath                    http://www.osa.com.au/~cjh
Open Software Associates Limited       mailto:cjh@osa.com.au
29 Ringwood Street / PO Box 4414       Phone  +613 9871 1694
Ringwood VIC 3134      AUSTRALIA       Fax    +613 9871 1711
------------------------------------------------------------
Deploy Applications across the net, see http://www.osa.com

Try Diehard at    http://stat.fsu.edu/~geo/diehard.html

Clifford Heath wrote:

> We have been asked by a customer if we have any tests that demonstrate
> the randomness of the SSLeay random number generator (augmented by some
> sound-card random number seeding that we wrote).
>
> I'd like to find some standard implementation for testing randomness, but
> Schneier offers no help (other than a reference to Knuth Vol 2), and I
> don't know where else to turn.
>
> I realise that cryptographic randomness requires unpredictability, and
> this quality depends upon closed-world assumptions about unknown individuals'
> predictive powers, but we have to live with that.
>
> --
> Clifford Heath                    http://www.osa.com.au/~cjh
> Open Software Associates Limited       mailto:cjh@osa.com.au
> 29 Ringwood Street / PO Box 4414       Phone  +613 9871 1694
> Ringwood VIC 3134      AUSTRALIA       Fax    +613 9871 1711
> ------------------------------------------------------------
> Deploy Applications across the net, see http://www.osa.com

Clifford Heath wrote:
> 
> We have been asked by a customer if we have any tests that demonstrate
> the randomness of the SSLeay random number generator (augmented by some
> sound-card random number seeding that we wrote).
> 
> I'd like to find some standard implementation for testing randomness, but
> Schneier offers no help (other than a reference to Knuth Vol 2), and I
> don't know where else to turn.

I suggest that you do at least Maurer's test which is described
in A. J. Menezes et al. Handbook of Applied Cryptography. The
test is not difficult to code. You could also look at my code in
http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper1 in Fortran.

M. K. Shen

On Fri, 2 Oct 1998, Clifford Heath wrote:

> We have been asked by a customer if we have any tests that demonstrate 
> the randomness of the SSLeay random number generator (augmented by some
> sound-card random number seeding that we wrote).
> 
> I'd like to find some standard implementation for testing randomness, but 
> Schneier offers no help (other than a reference to Knuth Vol 2), and I
> don't know where else to turn.
> 
> I realise that cryptographic randomness requires unpredictability, and
> this quality depends upon closed-world assumptions about unknown individuals'
> predictive powers, but we have to live with that.
> 

You mean you don't have a copy of Knuth, Vol 2.  For shame!

I'm too lazy to look it up for you, but I believe the two tests
are called the Run test and the Chi-square method.

(trying to remember from my own dusty compSci memories)

jim

Jim Burnes wrote:
> 
> You mean you don't have a copy of Knuth, Vol 2.  For shame!

I suppose Heath meant that there is no codes ready for him to use as
those given in Schneier's book. Some tests in Knuth are in fact not
very trivial to code.

M. K. Shen

One very easy test is to compress the produced random number binary files
with various compression algorithms or programs. If the data is truly 
random, it should not be possible to achieve any compression. At least
not if you include the compression program data size in the calculation.

Well, I'm not sure whether this is such a good practical test or not.(?)

++ J

On Fri, 2 Oct 1998, Clifford Heath wrote:

> We have been asked by a customer if we have any tests that demonstrate 
> the randomness of the SSLeay random number generator (augmented by some
> sound-card random number seeding that we wrote).
> 
> I'd like to find some standard implementation for testing randomness, but 
> Schneier offers no help (other than a reference to Knuth Vol 2), and I
> don't know where else to turn.
> 
> I realise that cryptographic randomness requires unpredictability, and
> this quality depends upon closed-world assumptions about unknown individuals'
> predictive powers, but we have to live with that.
> 
> -- 
> Clifford Heath                    http://www.osa.com.au/~cjh
> Open Software Associates Limited       mailto:cjh@osa.com.au
> 29 Ringwood Street / PO Box 4414       Phone  +613 9871 1694
> Ringwood VIC 3134      AUSTRALIA       Fax    +613 9871 1711
> ------------------------------------------------------------
> Deploy Applications across the net, see http://www.osa.com
> 
>

At 03:36 PM 10/2/98 +1000, Clifford Heath wrote:
>We have been asked by a customer if we have any tests that demonstrate 
>the randomness of the SSLeay random number generator (augmented by some
>sound-card random number seeding that we wrote).
>
>I'd like to find some standard implementation for testing randomness, but 
>Schneier offers no help (other than a reference to Knuth Vol 2), and I
>don't know where else to turn.
>
>I realise that cryptographic randomness requires unpredictability, and
>this quality depends upon closed-world assumptions about unknown individuals'
>predictive powers, but we have to live with that.

* Marsaglia's DIEHARD suite, also see DIEHARDC
* I posted code for Maurer's Universal statistical test a week or so
ago; I find this discriminates between a cipher output and real noise...
* Find the RAND corp paper on random numbers 
* See FIPS 140

At 11:13 AM 10/2/98 +0100, Mok-Kong Shen wrote:
>Clifford Heath wrote:
>> 
>I suggest that you do at least Maurer's test which is described
>in A. J. Menezes et al. Handbook of Applied Cryptography. The
>test is not difficult to code. You could also look at my code in
>http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper1 in Fortran.
>
>M. K. Shen
>



/*
UELI.c

1 Oct 98

This implements Ueli M Maurer's
"Universal Statistical Test for Random Bit Generators"
using L=16

Accepts a filename on the command line;
writes its results, with other info, to stdout.

Handles input file exhaustion gracefully.

Ref: J. Cryptology v 5 no 2, 1992 pp 89-105
also on the web somewhere, which is where I found it.

-David Honig
honig@sprynet.com


Built with Wedit 2.3, lcc-win32
http://www.cs.virginia.edu/~lcc-win32


26 Sept CP Release
Version Notes:

	This version does L=16.  It evolved from an L=8 prototype
	which I ported from the Pascal in the above reference.

	I made the memory usage reasonable
	by replacing Maurer's "block" array
	with the 'streaming' fgetc() call.


Usage:
	UELI filename
	outputs to stdout

*/

#define L 16		// bits per block
#define V (1<<L)	// number of possible blocks
#define Q (10*V)    // at LEAST 10 * V, to assure each block seen
#define K (100*Q)   // at LEAST 100 * Q, as large as possible
#define MAXSAMP (Q + K)

#include <stdio.h>
#include <math.h>


int main( int argc, char **argv )
{
FILE *fptr;
int i;
int b, c;
int table[V];
float sum=0.0;
int run;

// Human Interface
printf("UELI 26 Sep 98\nL=%d %d %d \n", L, V, MAXSAMP);
if (argc <2)
	{printf("Usage: UELI filename\n"); exit(-1); }
else
	printf("Measuring file %s\n", argv[1]);

// FILE IO
fptr=fopen(argv[1],"rb");
if (fptr == NULL) {printf("Can't find %s\n", argv[1]); exit(-1); }

// INIT
for (i=0; i<V; i++) table[i]=0;
for (i=0; i<Q; i++)	{
	b= fgetc(fptr)<<8 | fgetc(fptr);
	table[ b ]=i;
}

printf("Init done\n");

// COMPUTE
run=1;
for (i=Q;  run && i<Q+K; i++)
	{
	// COMPOSE A 16-bit quantity
	b=fgetc(fptr); if (b<0) run=0;
	c=fgetc(fptr); if (c<0) run=0;
	if (run) { b = b<<8 | c;
			sum += log( (double) ( i-table[b] ) ) ;
			table[ b ]=i;
		}
	}

	if (!run) printf("Premature end of file; read %d blocks.\n", i-Q);
	sum = (sum/( (double) (i-Q) ) ) /  log(2.0);    // i should be K if enough
samples
	printf("%s fTU= %f\n\n", argv[1], sum);
	printf("Expected value for L=16 is 15.167379 \n");

	// Add further interpretation/thresholding of the number of sigmas from
expected,
	// and include the fudge factors explained in the paper.




} // end