/* @(#)fips140.c 1.5 (Qualcomm) 02/09/02 */ /* 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 V1 1 #define V2wrong 2 #define V2 3 #define VER V2 /* Version 1.2 -- Bill Chauncey pointed out some * typos and consistency problems. * Version 1.3 -- Bill Chauncey and his colleages pointed out to NIST that * the bounds in the runs test were incorrect. * They issued an update 2001-oct-10. * Version 1.4 -- added self test and timing capability */ #include #include #include 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; #if VER == V2 int MINRUN[7] = { 0, 2315, 1114, 527, 240, 103, 103 }; int MAXRUN[7] = { 0, 2685, 1386, 723, 384, 209, 209 }; #define LONGRUN 26 #define MINONES 9725 #define MAXONES 10275 #define MINPOKE 2.16 #define MAXPOKE 46.17 #else #if VER == V2wrong int MINRUN[7] = { 0, 2343, 1135, 542, 251, 111, 111 }; int MAXRUN[7] = { 0, 2657, 1365, 708, 373, 201, 201 }; #define LONGRUN 26 #define MINONES 9725 #define MAXONES 10275 #define MINPOKE 2.16 #define MAXPOKE 46.17 #else #if VER == V1 int MINRUN[7] = { 0, 2267, 1079, 502, 223, 90, 90 }; int MAXRUN[7] = { 0, 2733, 1421, 748, 402, 223, 223 }; #define LONGRUN 34 #define MINONES 9654 #define MAXONES 10346 #define MINPOKE 1.03 #define MAXPOKE 57.4 #else #error version VER is incorrect or unset #endif #endif #endif int *minrun = MINRUN; int *maxrun = MAXRUN; int longrun = LONGRUN; int minones = MINONES; int maxones = MAXONES; double minpoke = MINPOKE; double maxpoke = MAXPOKE; /* 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]; } void dofips() { register int i; register uchar *p; register int c; double X; register int last; int run; /* 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] >> 7) & 1; run = 0; for (p = b; p < &b[sizeof b]; ++p) { c = *p; for (i = 7; i >= 0; --i) { if (((c >> i) & 1) != last) { endrun(last, run); run = 0; last = (c >> i) & 1; } ++run; } } 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; } } } } /* fill buffer and bounds with self-test data */ void gentestdata() { int i; static int test_minrun[7] = {0, 2496, 1251, 620, 306, 151, 148 }; static int test_maxrun[7] = {0, 2530, 1256, 629, 318, 160, 161 }; for (i = 0; i < sizeof b; ++i) b[i] = i & 0xFF; minrun = test_minrun; maxrun = test_maxrun; longrun = 16; minones = 9931; maxones = 9933; minpoke = 2.3035; maxpoke = 2.3045; } /* Self test */ void dotest() { /* no test should fail */ gentestdata(); verbose = 1; dofips(); if (nerrs) { fprintf(stderr, "Self test failed! %d errors.\n", nerrs); exit(1); } } /* do timing */ void dotime() { register int i; #define TIMES 10000 gentestdata(); verbose = 0; for (i = 0; i < TIMES; ++i) { dofips(); /* reinitialise global counters */ bzero(poker, sizeof poker); bzero(runs, sizeof runs); } printf("%d iterations\n", TIMES); } int main(int ac, char **av) { FILE *f; myname = av[0]; if (ac == 2 && strcmp(av[1], "-test") == 0) { dotest(); return 0; } if (ac == 2 && strcmp(av[1], "-time") == 0) { dotime(); return 0; } if (ac >= 2 && strcmp(av[1], "-v") == 0) { verbose = 1; ++av; --ac; } if (ac > 2) { fprintf(stderr, "usage: %s [-v] [file]\n", myname); fprintf(stderr, " or: %s -time|-test\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; } dofips(); /* error code non-zero if problems found */ if (verbose && nerrs) printf("%d errors found\n", nerrs); return nerrs <= 255 ? nerrs : 255; }