chiark - git - mdw - catacomb/blob - fipstest.c

   1 /* -*-c-*-
   2  *
   3  * $Id: fipstest.c,v 1.2 2000/06/17 12:21:39 mdw Exp $
   4  *
   5  * FIPS 140-1 randomness tests
   6  *
   7  * (c) 2000 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: fipstest.c,v $
  33  * Revision 1.2  2000/06/17 12:21:39  mdw
  34  * Add braces to shut compiler up.  Reformat code slightly.
  35  *
  36  * Revision 1.1  2000/06/17 10:55:38  mdw
  37  * FIPS 140-1 random generator test.
  38  *
  39  */
  40
  41 /*----- Header files ------------------------------------------------------*/
  42
  43 #include <mLib/bits.h>
  44
  45 #include "fipstest.h"
  46
  47 /*----- Main code ---------------------------------------------------------*/
  48
  49 /* --- @monobit@ --- *
  50  *
  51  * Arguments:   @const octet *p@ = pointer to buffer
  52  *
  53  * Returns:     Zero if OK, @FIPSTEST_MONOBIT@ on failure.
  54  *
  55  * Use:         Performs the monobit test on a buffer of data.  If %$n_1$% is
  56  *              the number of 1 bits in the buffer, then the monobit test is
  57  *              passed when %$9654 < n_1 < 10346$%.
  58  */
  59
  60 static unsigned monobit(const octet *p)
  61 {
  62   unsigned n1 = 0;
  63   unsigned i, j;
  64
  65   for (i = 0; i < FIPSTEST_BUFSZ; i++) {
  66     octet x = p[i];
  67     for (j = 0; j < 8; j++) {
  68       if (x & 1)
  69         n1++;
  70       x >>= 1;
  71     }
  72   }
  73
  74   if (9654 >= n1 || n1 >= 10346)
  75     return (FIPSTEST_MONOBIT);
  76   return (0);
  77 }
  78
  79 /* --- @poker@ --- *
  80  *
  81  * Arguments:   @const octet *p@ = pointer to buffer
  82  *
  83  * Returns:     Zero if OK, @FIPSTEST_POKER@ on failure.
  84  *
  85  * Use:         Performs the poker test on a buffer of data.  The buffer is
  86  *              divided into 4-bit nibbles %$x_i$%.  If
  87  *              %$f(x) = \sum_{x_i = x} 1$% is the frequency of each nibble,
  88  *              then the test is passed if
  89  *              %$1.03 < 16/5000 \sum_i f(i)^2 - 5000 < 57.4$%.
  90  */
  91
  92 static unsigned poker(const octet *p)
  93 {
  94   unsigned long f[16] = { 0 };
  95   unsigned i;
  96   unsigned long q = 0;
  97
  98   /* --- Compute the frequencies --- */
  99
 100   for (i = 0; i < FIPSTEST_BUFSZ; i++) {
 101     octet x = p[i];
 102     f[x & 0xf]++;
 103     f[(x >> 4) & 0xf]++;
 104   }
 105
 106   /* --- Now do the comparison --- *
 107    *
 108    * This can be simplified.  Multiply through the inequality by 5000 and
 109    * we get %$5150 < 16 \sum_i f(i)^2 - 5000^2 < 287000$%.
 110    */
 111
 112   for (i = 0; i < 16; i++)
 113     q += f[i] * f[i];
 114   q <<= 4;
 115   q -= 5000 * 5000;
 116
 117   if (5150 >= q || q >= 287000)
 118     return (FIPSTEST_POKER);
 119   return (0);
 120 }
 121
 122 /* --- @runs@ --- *
 123  *
 124  * Arguments:   @const octet *p@ = pointer to buffer
 125  *
 126  * Returns:     Zero for success, @FIPSTEST_RUNS@ or @FIPSTEST_LONGRUNS@ on
 127  *              failure.
 128  *
 129  * Use:         Performs the runs and long runs tests.  The frequency of each
 130  *              `run', or sequence of equal bits, is counted and tested.
 131  */
 132
 133 static unsigned runs(const octet *p)
 134 {
 135   unsigned rc = 0;
 136   unsigned i, j;
 137   unsigned r = 0;
 138   unsigned bb = 0;
 139   unsigned f[2][6] = { { 0 } };
 140
 141   /* --- Count the run lengths --- */
 142
 143   for (i = 0; i < FIPSTEST_BUFSZ; i++) {
 144     octet x = p[i];
 145     for (j = 0; j < 8; j++) {
 146       unsigned b = x & 1;
 147       x >>= 1;
 148       if (b == bb)
 149         r++;
 150       else {
 151         if (r) {
 152           if (r >= 34)
 153             rc |= FIPSTEST_LONGRUNS;
 154           if (r > 6)
 155             r = 6;
 156           f[bb][r - 1]++;
 157         }
 158         r = 1;
 159         bb = b;
 160       }
 161     }
 162   }
 163
 164   if (r >= 34)
 165     rc |= FIPSTEST_LONGRUNS;
 166   if (r > 6)
 167     r = 6;
 168   f[bb][r - 1]++;
 169
 170   /* --- Check the results --- */
 171
 172   if (2267 > f[0][0] || f[0][0] > 2733 || 2267 > f[1][0] || f[1][0] > 2733 ||
 173       1079 > f[0][1] || f[0][1] > 1421 || 1079 > f[1][1] || f[1][1] > 1421 ||
 174        502 > f[0][2] || f[0][2] >  748 ||  502 > f[1][2] || f[1][2] >  748 ||
 175        223 > f[0][3] || f[0][3] >  402 ||  223 > f[1][3] || f[1][3] >  402 ||
 176         90 > f[0][4] || f[0][4] >  223 ||   90 > f[1][4] || f[1][4] >  223 ||
 177         90 > f[0][5] || f[0][5] >  223 ||   90 > f[1][5] || f[1][5] >  223)
 178     rc |= FIPSTEST_RUNS;
 179
 180   return (rc);
 181 }
 182
 183 /* --- @fipstest@ --- *
 184  *
 185  * Arguments:   @const octet *p@ = pointer to a buffer of @FIPSTEST_BUFSZ@
 186  *                      bytes
 187  *
 188  * Returns:     Zero if OK, or a bitmask of failed tests.
 189  *
 190  * Use:         Performs the FIPS 140-1 randomness tests on a block of data.
 191  */
 192
 193 unsigned fipstest(const octet *p)
 194 {
 195   unsigned rc = 0;
 196   rc |= monobit(p);
 197   rc |= poker(p);
 198   rc |= runs(p);
 199   return (rc);
 200 }
 201
 202 /*----- That's all, folks -------------------------------------------------*/