FIPS 140-1 random generator test.

diff --git a/fipstest.c b/fipstest.c
new file mode 100644 (file)
index 0000000..cdfcc05
--- /dev/null
+++ b/fipstest.c
@@ -0,0 +1,205 @@
+/* -*-c-*-
+ *
+ * $Id: fipstest.c,v 1.1 2000/06/17 10:55:38 mdw Exp $
+ *
+ * FIPS 140-1 randomness tests
+ *
+ * (c) 2000 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------* 
+ *
+ * This file is part of Catacomb.
+ *
+ * Catacomb is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Library General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ * 
+ * Catacomb is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Library General Public License for more details.
+ * 
+ * You should have received a copy of the GNU Library General Public
+ * License along with Catacomb; if not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+ * MA 02111-1307, USA.
+ */
+
+/*----- Revision history --------------------------------------------------* 
+ *
+ * $Log: fipstest.c,v $
+ * Revision 1.1  2000/06/17 10:55:38  mdw
+ * FIPS 140-1 random generator test.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <mLib/bits.h>
+
+#include "fipstest.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @monobit@ --- *
+ *
+ * Arguments:  @const octet *p@ = pointer to buffer
+ *
+ * Returns:    Zero if OK, @FIPSTEST_MONOBIT@ on failure.
+ *
+ * Use:                Performs the monobit test on a buffer of data.  If %$n_1$% is
+ *             the number of 1 bits in the buffer, then the monobit test is
+ *             passed when %$9654 < n_1 < 10346$%.
+ */
+
+static unsigned monobit(const octet *p)
+{
+  unsigned n1 = 0;
+  unsigned i, j;
+
+  for (i = 0; i < FIPSTEST_BUFSZ; i++) {
+    octet x = p[i];
+    for (j = 0; j < 8; j++) {
+      if (x & 1)
+       n1++;
+      x >>= 1;
+    }
+  }
+
+  if (9654 >= n1 || n1 >= 10346)
+    return (FIPSTEST_MONOBIT);
+  return (0);
+}
+
+/* --- @poker@ --- *
+ *
+ * Arguments:  @const octet *p@ = pointer to buffer
+ *
+ * Returns:    Zero if OK, @FIPSTEST_POKER@ on failure.
+ *
+ * Use:                Performs the poker test on a buffer of data.  The buffer is
+ *             divided into 4-bit nibbles %$x_i$%.  If
+ *             %$f(x) = \sum_{x_i = x} 1$% is the frequency of each nibble,
+ *             then the test is passed if
+ *             %$1.03 < 16/5000 \sum_i f(i)^2 - 5000 < 57.4$%.
+ */
+
+static unsigned poker(const octet *p)
+{
+  unsigned long f[16] = { 0 };
+  unsigned i;
+  unsigned long q = 0;
+
+  /* --- Compute the frequencies --- */
+
+  for (i = 0; i < FIPSTEST_BUFSZ; i++) {
+    octet x = p[i];
+    f[x & 0xf]++;
+    f[(x >> 4) & 0xf]++;
+  }
+
+  /* --- Now do the comparison --- *
+   *
+   * This can be simplified.  Multiply through the inequality by 5000 and
+   * we get %$5150 < 16 \sum_i f(i)^2 - 5000^2 < 287000$%.
+   */
+
+  for (i = 0; i < 16; i++)
+    q += f[i] * f[i];
+  q <<= 4;
+  q -= 5000 * 5000;
+
+  if (5150 >= q || q >= 287000)
+    return (FIPSTEST_POKER);
+  return (0);
+}
+
+/* --- @runs@ --- *
+ *
+ * Arguments:  @const octet *p@ = pointer to buffer
+ *
+ * Returns:    Zero for success, @FIPSTEST_RUNS@ or @FIPSTEST_LONGRUNS@ on
+ *             failure.
+ *
+ * Use:                Performs the runs and long runs tests.  The frequency of each
+ *             `run', or sequence of equal bits, is counted and tested.
+ */
+
+static unsigned runs(const octet *p)
+{
+  unsigned rc = 0;
+  unsigned i, j;
+  unsigned r = 0;
+  unsigned bb = 0;
+  unsigned f[2][6] = { 0 };
+
+  /* --- Count the run lengths --- */
+
+  for (i = 0; i < FIPSTEST_BUFSZ; i++) {
+    octet x = p[i];
+    for (j = 0; j < 8; j++) {
+      unsigned b = x & 1;
+      x >>= 1;
+      if (b == bb)
+       r++;
+      else {
+       if (r) {
+         if (r >= 34)
+           rc |= FIPSTEST_LONGRUNS;
+         if (r > 6)
+           r = 6;
+         f[bb][r - 1]++;
+       }
+       r = 1;
+       bb = b;
+      }
+    }
+  }
+  
+  if (r >= 34)
+    rc |= FIPSTEST_LONGRUNS;
+  if (r > 6)
+    r = 6;
+  f[bb][r - 1]++;
+
+  /* --- Check the results --- */
+
+  if (2267 > f[0][0] || f[0][0] > 2733 ||
+      2267 > f[1][0] || f[1][0] > 2733 ||
+      1079 > f[0][1] || f[0][1] > 1421 ||
+      1079 > f[1][1] || f[1][1] > 1421 ||
+       502 > f[0][2] || f[0][2] >  748 ||
+       502 > f[1][2] || f[1][2] >  748 ||
+       223 > f[0][3] || f[0][3] >  402 ||
+       223 > f[1][3] || f[1][3] >  402 ||
+        90 > f[0][4] || f[0][4] >  223 ||
+        90 > f[1][4] || f[1][4] >  223 ||
+        90 > f[0][5] || f[0][5] >  223 ||
+        90 > f[1][5] || f[1][5] >  223)
+    rc |= FIPSTEST_RUNS;
+
+  return (rc);      
+}
+
+/* --- @fipstest@ --- *
+ *
+ * Arguments:  @const octet *p@ = pointer to a buffer of @FIPSTEST_BUFSZ@
+ *                     bytes
+ *
+ * Returns:    Zero if OK, or a bitmask of failed tests.
+ *
+ * Use:                Performs the FIPS 140-1 randomness tests on a block of data.
+ */
+
+unsigned fipstest(const octet *p)
+{
+  unsigned rc = 0;
+  rc |= monobit(p);
+  rc |= poker(p);
+  rc |= runs(p);
+  return (rc);
+}
+
+/*----- That's all, folks -------------------------------------------------*/

diff --git a/fipstest.h b/fipstest.h
new file mode 100644 (file)
index 0000000..c267876
--- /dev/null
+++ b/fipstest.h
@@ -0,0 +1,81 @@
+/* -*-c-*-
+ *
+ * $Id: fipstest.h,v 1.1 2000/06/17 10:55:38 mdw Exp $
+ *
+ * FIPS 140-1 randomness tests
+ *
+ * (c) 2000 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------* 
+ *
+ * This file is part of Catacomb.
+ *
+ * Catacomb is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Library General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ * 
+ * Catacomb is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Library General Public License for more details.
+ * 
+ * You should have received a copy of the GNU Library General Public
+ * License along with Catacomb; if not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+ * MA 02111-1307, USA.
+ */
+
+/*----- Revision history --------------------------------------------------* 
+ *
+ * $Log: fipstest.h,v $
+ * Revision 1.1  2000/06/17 10:55:38  mdw
+ * FIPS 140-1 random generator test.
+ *
+ */
+
+#ifndef CATACOMB_FIPSTEST_H
+#define CATACOMB_FIPSTEST_H
+
+#ifdef __cplusplus
+  extern "C" {
+#endif
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <mLib/bits.h>
+
+/*----- Magic numbers -----------------------------------------------------*/
+
+#define FIPSTEST_BUFSZ 2500
+
+enum {
+  FIPSTEST_OK = 0,
+  FIPSTEST_MONOBIT = 1,
+  FIPSTEST_POKER = 2,
+  FIPSTEST_RUNS = 4,
+  FIPSTEST_LONGRUNS = 8
+};
+
+/*----- Functions provided ------------------------------------------------*/
+
+/* --- @fipstest@ --- *
+ *
+ * Arguments:  @const octet *p@ = pointer to a buffer of @FIPSTEST_BUFSZ@
+ *                     bytes
+ *
+ * Returns:    Zero if OK, or a bitmask of failed tests.
+ *
+ * Use:                Performs the FIPS 140-1 randomness tests on a block of data.
+ */
+
+extern unsigned fipstest(const octet */*p*/);
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+  }
+#endif
+
+#endif