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

   1 /* -*-c-*-
   2  *
   3  * $Id: fipstest.c,v 1.4 2004/04/08 01:36:15 mdw Exp $
   4  *
   5  * FIPS140 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 /*----- Header files ------------------------------------------------------*/
  31
  32 #include <mLib/bits.h>
  33
  34 #include "fipstest.h"
  35
  36 /*----- Main code ---------------------------------------------------------*/
  37
  38 /* --- @monobit@ --- *
  39  *
  40  * Arguments:   @const octet *p@ = pointer to buffer
  41  *
  42  * Returns:     Zero if OK, @FIPSTEST_MONOBIT@ on failure.
  43  *
  44  * Use:         Performs the monobit test on a buffer of data.  If %$n_1$% is
  45  *              the number of 1 bits in the buffer, then the monobit test is
  46  *              passed when %$9654 < n_1 < 10346$%.
  47  */
  48
  49 static unsigned monobit(const octet *p)
  50 {
  51   unsigned n1 = 0;
  52   unsigned i, j;
  53
  54   for (i = 0; i < FIPSTEST_BUFSZ; i++) {
  55     octet x = p[i];
  56     for (j = 0; j < 8; j++) {
  57       if (x & 1)
  58         n1++;
  59       x >>= 1;
  60     }
  61   }
  62
  63   if (9725 >= n1 || n1 >= 10275)
  64     return (FIPSTEST_MONOBIT);
  65   return (0);
  66 }
  67
  68 /* --- @poker@ --- *
  69  *
  70  * Arguments:   @const octet *p@ = pointer to buffer
  71  *
  72  * Returns:     Zero if OK, @FIPSTEST_POKER@ on failure.
  73  *
  74  * Use:         Performs the poker test on a buffer of data.  The buffer is
  75  *              divided into 4-bit nibbles %$x_i$%.  If
  76  *              %$f(x) = \sum_{x_i = x} 1$% is the frequency of each nibble,
  77  *              then the test is passed if
  78  *              %$2.16 < 16/5000 \sum_i f(i)^2 - 5000 < 46.17$%.
  79  */
  80
  81 static unsigned poker(const octet *p)
  82 {
  83   unsigned long f[16] = { 0 };
  84   unsigned i;
  85   unsigned long q = 0;
  86
  87   /* --- Compute the frequencies --- */
  88
  89   for (i = 0; i < FIPSTEST_BUFSZ; i++) {
  90     octet x = p[i];
  91     f[x & 0xf]++;
  92     f[(x >> 4) & 0xf]++;
  93   }
  94
  95   /* --- Now do the comparison --- *
  96    *
  97    * This can be simplified.  Multiply through the inequality by 5000 and
  98    * we get %$5150 < 16 \sum_i f(i)^2 - 5000^2 < 287000$%.
  99    */
 100
 101   for (i = 0; i < 16; i++)
 102     q += f[i] * f[i];
 103   q <<= 4;
 104   q -= 5000ul * 5000ul;
 105
 106   if (10800 >= q || q >= 230850)
 107     return (FIPSTEST_POKER);
 108   return (0);
 109 }
 110
 111 /* --- @runs@ --- *
 112  *
 113  * Arguments:   @const octet *p@ = pointer to buffer
 114  *
 115  * Returns:     Zero for success, @FIPSTEST_RUNS@ or @FIPSTEST_LONGRUNS@ on
 116  *              failure.
 117  *
 118  * Use:         Performs the runs and long runs tests.  The frequency of each
 119  *              `run', or sequence of equal bits, is counted and tested.
 120  */
 121
 122 static unsigned runs(const octet *p)
 123 {
 124   unsigned rc = 0;
 125   unsigned i, j;
 126   unsigned r = 0;
 127   unsigned bb = 0;
 128   unsigned f[2][6] = { { 0 } };
 129
 130   /* --- Count the run lengths --- */
 131
 132   for (i = 0; i < FIPSTEST_BUFSZ; i++) {
 133     octet x = p[i];
 134     for (j = 0; j < 8; j++) {
 135       unsigned b = x & 1;
 136       x >>= 1;
 137       if (b == bb)
 138         r++;
 139       else {
 140         if (r) {
 141           if (r >= 34)
 142             rc |= FIPSTEST_LONGRUNS;
 143           if (r > 6)
 144             r = 6;
 145           f[bb][r - 1]++;
 146         }
 147         r = 1;
 148         bb = b;
 149       }
 150     }
 151   }
 152
 153   if (r >= 26)
 154     rc |= FIPSTEST_LONGRUNS;
 155   if (r > 6)
 156     r = 6;
 157   f[bb][r - 1]++;
 158
 159   /* --- Check the results --- */
 160
 161   if (2343 > f[0][0] || f[0][0] > 2657 || 2343 > f[1][0] || f[1][0] > 2657 ||
 162       1135 > f[0][1] || f[0][1] > 1365 || 1135 > f[1][1] || f[1][1] > 1365 ||
 163        542 > f[0][2] || f[0][2] >  708 ||  542 > f[1][2] || f[1][2] >  708 ||
 164        251 > f[0][3] || f[0][3] >  373 ||  251 > f[1][3] || f[1][3] >  373 ||
 165        111 > f[0][4] || f[0][4] >  201 ||  111 > f[1][4] || f[1][4] >  201 ||
 166        111 > f[0][5] || f[0][5] >  201 ||  111 > f[1][5] || f[1][5] >  201)
 167     rc |= FIPSTEST_RUNS;
 168
 169   return (rc);
 170 }
 171
 172 /* --- @fipstest@ --- *
 173  *
 174  * Arguments:   @const octet *p@ = pointer to a buffer of @FIPSTEST_BUFSZ@
 175  *                      bytes
 176  *
 177  * Returns:     Zero if OK, or a bitmask of failed tests.
 178  *
 179  * Use:         Performs the FIPS140 randomness tests on a block of data.
 180  */
 181
 182 unsigned fipstest(const octet *p)
 183 {
 184   unsigned rc = 0;
 185   rc |= monobit(p);
 186   rc |= poker(p);
 187   rc |= runs(p);
 188   return (rc);
 189 }
 190
 191 /*----- That's all, folks -------------------------------------------------*/