fips.c

   1 /*
   2  * fips.c -- Performs FIPS 140-1/140-2 RNG tests
   3  *
   4  * Copyright (C) 2001 Philipp Rumpf
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19  */
  20
  21 #define _GNU_SOURCE
  22
  23 #ifndef HAVE_CONFIG_H
  24 #error Invalid or missing autoconf build environment
  25 #endif
  26
  27 #include "rng-tools-config.h"
  28
  29 #include <unistd.h>
  30 #include <string.h>
  31
  32 #include "fips.h"
  33
  34 /*
  35  * Names for the FIPS tests, and bitmask
  36  */
  37 const char *fips_test_names[N_FIPS_TESTS] = {
  38         "FIPS 140-2(2001-10-10) Monobit",
  39         "FIPS 140-2(2001-10-10) Poker",
  40         "FIPS 140-2(2001-10-10) Runs",
  41         "FIPS 140-2(2001-10-10) Long run",
  42         "FIPS 140-2(2001-10-10) Continuous run"
  43 };
  44 const unsigned int fips_test_mask[N_FIPS_TESTS] = {
  45         FIPS_RNG_MONOBIT, FIPS_RNG_POKER, FIPS_RNG_RUNS,
  46         FIPS_RNG_LONGRUN, FIPS_RNG_CONTINUOUS_RUN
  47 };
  48
  49
  50 /* These are the startup tests suggested by the FIPS 140-1 spec section
  51 *  4.11.1 (http://csrc.nist.gov/fips/fips1401.htm), and updated by FIPS
  52 *  140-2 4.9, errata of 2001-10-10.  FIPS 140-2, errata of 2002-12-03
  53 *  removed all requirements for non-deterministic RNGs, and thus most of
  54 *  the tests we need are not mentioned in FIPS 140-2 anymore.  We also
  55 *  implement FIPS 140-1 4.11.2/FIPS 140-2 4.9 Continuous Run test.
  56 *
  57 *  The Monobit, Poker, Runs, and Long Runs tests are implemented below.
  58 *  This test must be run at periodic intervals to verify data is
  59 *  sufficiently random.  If the tests are failed the RNG module shall
  60 *  no longer submit data to the entropy pool, but the tests shall
  61 *  continue to run at the given interval.  If at a later time the RNG
  62 *  passes all tests it shall be re-enabled for the next period.
  63 *
  64 *  The reason for this is that it is not unlikely that at some time
  65 *  during normal operation one of the tests will fail.  This does not
  66 *  necessarily mean the RNG is not operating properly, it is just a
  67 *  statistically rare event.  In that case we don't want to forever
  68 *  disable the RNG, we will just leave it disabled for the period of
  69 *  time until the tests are rerun and passed.
  70 *
  71 *  For the continuous run test, we need to check all bits of data, so
  72 *  "periodic" above shall be read as "for every back-to-back block of
  73 *  20000 bits".  We verify 32 bits to accomodate the AMD TRNG, and
  74 *  to reduce false positives with other TRNGs.
  75 */
  76
  77
  78 /*
  79  * fips_test_store - store 8 bits of entropy in FIPS
  80  *                       internal test data pool
  81  */
  82 static void fips_test_store(fips_ctx_t *ctx, unsigned int rng_data)
  83 {
  84         int j;
  85
  86         ctx->poker[rng_data >> 4]++;
  87         ctx->poker[rng_data & 15]++;
  88
  89         /* Note in the loop below rlength is always one less than the actual
  90            run length. This makes things easier. */
  91         for (j = 7; j >= 0; j--) {
  92                 ctx->ones += ctx->current_bit = ((rng_data >> j) & 1);
  93                 if (ctx->current_bit != ctx->last_bit) {
  94                         /* If runlength is 1-6 count it in correct bucket. 0's go in
  95                            runs[0-5] 1's go in runs[6-11] hence the 6*current_bit below */
  96                         if (ctx->rlength < 5) {
  97                                 ctx->runs[ctx->rlength +
  98                                      (6 * ctx->current_bit)]++;
  99                         } else {
 100                                 ctx->runs[5 + (6 * ctx->current_bit)]++;
 101                         }
 102
 103                         /* Check if we just failed longrun test */
 104                         if (ctx->rlength >= 25)
 105                                 ctx->longrun = 1;
 106                         ctx->rlength = 0;
 107                         /* flip the current run type */
 108                         ctx->last_bit = ctx->current_bit;
 109                 } else {
 110                         ctx->rlength++;
 111                 }
 112         }
 113 }
 114
 115 int fips_run_rng_test (fips_ctx_t *ctx, const void *buf)
 116 {
 117         int i, j;
 118         int rng_test = 0;
 119         unsigned char *rngdatabuf;
 120
 121         if (!ctx) return -1;
 122         if (!buf) return -1;
 123         rngdatabuf = (unsigned char *)buf;
 124
 125         for (i=0; i<FIPS_RNG_BUFFER_SIZE; i += 4) {
 126                 int new32 = rngdatabuf[i] |
 127                             ( rngdatabuf[i+1] << 8 ) |
 128                             ( rngdatabuf[i+2] << 16 ) |
 129                             ( rngdatabuf[i+3] << 24 );
 130                 if (new32 == ctx->last32) rng_test |= FIPS_RNG_CONTINUOUS_RUN;
 131                 ctx->last32 = new32;
 132                 fips_test_store(ctx, rngdatabuf[i]);
 133                 fips_test_store(ctx, rngdatabuf[i+1]);
 134                 fips_test_store(ctx, rngdatabuf[i+2]);
 135                 fips_test_store(ctx, rngdatabuf[i+3]);
 136         }
 137
 138         /* add in the last (possibly incomplete) run */
 139         if (ctx->rlength < 5)
 140                 ctx->runs[ctx->rlength + (6 * ctx->current_bit)]++;
 141         else {
 142                 ctx->runs[5 + (6 * ctx->current_bit)]++;
 143                 if (ctx->rlength >= 25)
 144                         rng_test |= FIPS_RNG_LONGRUN;
 145         }
 146
 147         if (ctx->longrun) {
 148                 rng_test |= FIPS_RNG_LONGRUN;
 149                 ctx->longrun = 0;
 150         }
 151
 152         /* Ones test */
 153         if ((ctx->ones >= 10275) || (ctx->ones <= 9725))
 154                 rng_test |= FIPS_RNG_MONOBIT;
 155         /* Poker calcs */
 156         for (i = 0, j = 0; i < 16; i++)
 157                 j += ctx->poker[i] * ctx->poker[i];
 158         /* 16/5000*1563176-5000 = 2.1632  */
 159         /* 16/5000*1576928-5000 = 46.1696 */
 160         if ((j > 1576928) || (j < 1563176))
 161                 rng_test |= FIPS_RNG_POKER;
 162
 163         if ((ctx->runs[0] < 2315) || (ctx->runs[0] > 2685) ||
 164             (ctx->runs[1] < 1114) || (ctx->runs[1] > 1386) ||
 165             (ctx->runs[2] < 527) || (ctx->runs[2] > 723) ||
 166             (ctx->runs[3] < 240) || (ctx->runs[3] > 384) ||
 167             (ctx->runs[4] < 103) || (ctx->runs[4] > 209) ||
 168             (ctx->runs[5] < 103) || (ctx->runs[5] > 209) ||
 169             (ctx->runs[6] < 2315) || (ctx->runs[6] > 2685) ||
 170             (ctx->runs[7] < 1114) || (ctx->runs[7] > 1386) ||
 171             (ctx->runs[8] < 527) || (ctx->runs[8] > 723) ||
 172             (ctx->runs[9] < 240) || (ctx->runs[9] > 384) ||
 173             (ctx->runs[10] < 103) || (ctx->runs[10] > 209) ||
 174             (ctx->runs[11] < 103) || (ctx->runs[11] > 209)) {
 175                 rng_test |= FIPS_RNG_RUNS;
 176         }
 177
 178         /* finally, clear out FIPS variables for start of next run */
 179         memset (ctx->poker, 0, sizeof (ctx->poker));
 180         memset (ctx->runs, 0, sizeof (ctx->runs));
 181         ctx->ones = 0;
 182         ctx->rlength = -1;
 183         ctx->current_bit = 0;
 184
 185         return rng_test;
 186 }
 187
 188 void fips_init(fips_ctx_t *ctx, unsigned int last32)
 189 {
 190         if (ctx) {
 191                 memset (ctx->poker, 0, sizeof (ctx->poker));
 192                 memset (ctx->runs, 0, sizeof (ctx->runs));
 193                 ctx->longrun = 0;
 194                 ctx->ones = 0;
 195                 ctx->rlength = -1;
 196                 ctx->current_bit = 0;
 197                 ctx->last_bit = 0;
 198                 ctx->last32 = last32;
 199         }
 200 }
 201