Linux-style kernel PRNGs and the FIPS140-2 test

[Thor Lancelot Simon]

Many operating systems use "Linux-style" (environmental noise
stirred with a hash function) generators to provide "random"
and pseudorandom data on /dev/random and /dev/urandom
respectively.  A few modify the general Linux design by adding an
output buffer which is not stirred so that bits which have already
been output are not stirred into the pool of "new" "random" data
(IMO, not doing this is insane, but that's a different subject).

The enclosed implementation of the FIPS140-1/2 statistical test
appears to show that such generators fail the "runs" test quite
regularly.  Interestingly, the Linux generator seems to do better
the longer you let it run (which, perhaps, suggests that quite a
bit of data should be run through it at boot time and discarded)
but other, related generators do not.

The usual failure mode is "too many runs of 1 1s".  Using MD5
instead of SHA1 as the mixing function, the Linux generator
also displays "too many runs of 1 0s".  I have not yet seen
other failure modes from these generators.

To reproduce my results, just compile the enclosed and do
"a.out < /dev/urandom" on your platform of choice.

Thor
-------------- next part --------------
/*
This software is free for commercial and non-commercial use
subject to the following conditions.

Copyright remains vested in QUALCOMM Incorporated, and Copyright
notices in the code are not to be removed.  If this package is used in
a product, QUALCOMM should be given attribution as the author this
software.  This can be in the form of a textual message at program
startup or in documentation (online or textual) provided with the
package.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

1. Redistributions of source code must retain the copyright notice,
   this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the
   distribution.

3. All advertising materials mentioning features or use of this
   software must display the following acknowledgement:  This product
   includes software developed by QUALCOMM Incorporated.

THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
POSSIBILITY OF SUCH DAMAGE.

The license and distribution terms for any publically available version
or derivative of this code cannot be changed, that is, this code cannot
simply be copied and put under another distribution license including
the GNU Public License.
*/

/* Run FIPS 140 statistical tests on a file */
/* written by Greg Rose, Copyright C 2000 QUALCOMM Incorporated */

/* FIPS 140-2 significantly tightens the bounds. */
#define VER2 1	/* undefine to get FIPS 140-1 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char	*myname;
int	bitnum = 0;

typedef unsigned char	uchar;

#define NBITS 20000
uchar	b[NBITS/8];
int	poker[16];
int	runs[2][7];
int	nerrs;
int	verbose = 0;

#ifdef	VER2
int	minrun[7] = { 0, 2343, 1135, 542, 251, 111, 111 };
int	maxrun[7] = { 0, 2567, 1365, 708, 373, 201, 201 };
#define LONGRUN	26
#define MINONES 9725
#define MAXONES 10275
#define MINPOKE 2.16
#define MAXPOKE 46.17
#else	/* VER2 */
int	minrun[7] = { 0, 2267, 1079, 502, 223, 90, 90 };
int	maxrun[7] = { 0, 2733, 1421, 748, 402, 233, 233 };
#define LONGRUN	34
#define MINONES 9654
#define MAXONES 10346
#define MINPOKE 1.03
#define MAXPOKE 57.4
#endif /* VER2 */

/* Population count of 1's in a byte */
unsigned char Popcount[] = {
 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

/* end of run */
void
endrun(int last, int run)
{
    if (run >= LONGRUN) {
	printf("Sample fails long run test: Run of %d %ds found\n", 
	    run, last);
	++nerrs;
    }
    if (run > 6)
	run = 6;
    ++runs[last][run];
}

int
main(int ac, char **av)
{
    FILE		*f;
    register int	i;
    register uchar	*p;
    register int	c;
    double		X;
    register int	last;
    int			run;

    myname = av[0];
    if (ac >= 2 && strcmp(av[1], "-v") == 0) {
	verbose = 1;
	++av; --ac;
    }
    if (ac > 2) {
	fprintf(stderr, "usage: %s [-v] [file]\n", myname);
	return 1;
    }

    if (ac == 1 || strcmp(av[1], "-") == 0) {
	f = stdin;
    } else if ((f = fopen(av[1], "rb")) == NULL) {
	perror(av[1]);
	return 255;
    }

    /* test is defined on 20,000 bits. Read 'em. */
    if (fread(b, 1, sizeof b, f) != sizeof b) {
	fprintf(stderr,
	    "Insufficient input for test; %d bits (%d bytes) required\n",
	    NBITS, NBITS / 8);
	return 255;
    }

    /* monobit test */
    for (p = b, c = 0; p < &b[sizeof b]; ++p)
	c += Popcount[*p];
    if (verbose) printf("%d ones\n", c);
    if (c <= MINONES || MAXONES <= c) {
	printf("Sample fails monobit test: %d ones\n", c);
	++nerrs;
    }
    
    /* poker test */
    for (p = b; p < &b[sizeof b]; ++p) {
	++poker[*p & 0xF];
	++poker[(*p >> 4) & 0xF];
    }
    for (X = i = 0; i < 16; ++i) {
	X += (double)poker[i] * poker[i];
	if (verbose) printf("Poker test: %d 0x%Xs\n", poker[i], i);
    }
    X = 16.0 * X / 5000.0 - 5000.0;
    if (verbose) printf("Poker test ChiSquared parameter = %g\n", X);
    if (X <= MINPOKE || MAXPOKE <= X) {
	printf("Sample fails poker test: parameter X = %g\n", X);
	++nerrs;
    }

    /* runs test */
    last = b[0] & 1;
    run = 0;
    for (p = b; p < &b[sizeof b]; ++p) {
	c = *p;
	for (i = 0; i < 8; ++i) {
	    if ((c & 1) != last) {
		endrun(last, run);
		run = 0;
		last = c & 1;
	    }
	    ++run;
	    c >>= 1;
	}
    }
    endrun(last, run);

    for (run = 1; run <= 6; ++run) {
	for (last = 0; last <= 1; ++last) {
	    if (verbose)
		printf("%d runs of %d %ds\n", runs[last][run], run, last);
	    if (runs[last][run] < minrun[run]) {
		printf("Sample fails runs test: too few runs of %d %ds\n",
		    run, last);
		++nerrs;
	    }
	    else if (runs[last][run] > maxrun[run]) {
		printf("Sample fails runs test: too many runs of %d %ds\n",
		    run, last);
		++nerrs;
	    }
	}
    }

    /* error code non-zero if problems found */
    if (verbose && nerrs)
	printf("%d errors found\n", nerrs);
    return nerrs <= 255 ? nerrs : 255;
}