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

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