FIPS 140-2 rng data tester for h/w crypto devices. This driver periodically

monitors the entropy data harvested by crypto drivers to verify it complies
with FIPS 140-2.  If data fails any test then the driver discards it and
commences continuous testing of harvested data until it is deemed ok.
Results are collected in a statistics block and, optionally, reported on
the console.  In normal use the overhead associated with this driver is
not noticeable.

Note that drivers must (currently) be compiled specially to enable use.

Obtained from:	original code by Jason L. Wright

2 files changed, 455 insertions, 0 deletions

diff --git a/sys/dev/rndtest/rndtest.c b/sys/dev/rndtest/rndtest.c
new file mode 100644
index 0000000..8c06b3a
--- /dev/null
+++ b/sys/dev/rndtest/rndtest.c
@@ -0,0 +1,395 @@
+/*	$FreeBSD$	*/
+/*	$OpenBSD$	*/
+
+/*
+ * Copyright (c) 2002 Jason L. Wright (jason@thought.net)
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by Jason L. Wright
+ * 4. The name of the author may not be used to endorse or promote products
+ *    derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <sys/param.h>
+#include <sys/systm.h>
+#include <sys/bus.h>
+#include <sys/callout.h>
+#include <sys/kernel.h>
+#include <sys/malloc.h>
+#include <sys/module.h>
+#include <sys/random.h>
+#include <sys/sysctl.h>
+#include <machine/stdarg.h>
+
+#include <dev/rndtest/rndtest.h>
+
+static	void rndtest_test(struct rndtest_state *);
+static	void rndtest_timeout(void *);
+
+/* The tests themselves */
+static	int rndtest_monobit(struct rndtest_state *);
+static	int rndtest_runs(struct rndtest_state *);
+static	int rndtest_longruns(struct rndtest_state *);
+static	int rndtest_chi_4(struct rndtest_state *);
+
+static	int rndtest_runs_check(struct rndtest_state *, int, int *);
+static	void rndtest_runs_record(struct rndtest_state *, int, int *);
+
+static const struct rndtest_testfunc {
+	int (*test)(struct rndtest_state *);
+} rndtest_funcs[] = {
+	{ rndtest_monobit },
+	{ rndtest_runs },
+	{ rndtest_chi_4 },
+	{ rndtest_longruns },
+};
+
+#define	RNDTEST_NTESTS	(sizeof(rndtest_funcs)/sizeof(rndtest_funcs[0]))
+
+SYSCTL_NODE(_kern, OID_AUTO, rndtest, CTLFLAG_RD, 0, "RNG test parameters");
+
+static	int rndtest_retest = 120;		/* interval in seconds */
+SYSCTL_INT(_kern_rndtest, OID_AUTO, reset, CTLFLAG_RW, &rndtest_retest,
+	    0, "retest interval (seconds)");
+static struct rndtest_stats rndstats;
+SYSCTL_STRUCT(_kern_rndtest, OID_AUTO, stats, CTLFLAG_RD, &rndstats,
+	    rndtest_stats, "RNG test statistics");
+static	int rndtest_verbose = 1;		/* report only failures */
+SYSCTL_INT(_kern_rndtest, OID_AUTO, verbose, CTLFLAG_RW, &rndtest_verbose,
+	    0, "display results on console");
+
+struct rndtest_state *
+rndtest_attach(device_t dev)
+{
+	struct rndtest_state *rsp;
+
+	rsp = malloc(sizeof (*rsp), M_DEVBUF, M_NOWAIT);
+	if (rsp != NULL) {
+		rsp->rs_begin = rsp->rs_buf;
+		rsp->rs_end = rsp->rs_buf + sizeof(rsp->rs_buf);
+		rsp->rs_current = rsp->rs_begin;
+		rsp->rs_discard = 1;
+		rsp->rs_collect = 1;
+		rsp->rs_parent = dev;
+		/* NB: 1 means the callout runs w/o Giant locked */
+		callout_init(&rsp->rs_to, 1);
+	} else
+		device_printf(dev, "rndtest_init: no memory for state block\n");
+	return (rsp);
+}
+
+void
+rndtest_detach(struct rndtest_state *rsp)
+{
+	callout_stop(&rsp->rs_to);
+	free(rsp, M_DEVBUF);
+}
+
+void
+rndtest_harvest(struct rndtest_state *rsp, void *buf, u_int len)
+{
+	/*
+	 * If enabled, collect data and run tests when we have enough.
+	 */
+	if (rsp->rs_collect) {
+		size_t i;
+		for (i = 0; i < len; i++) {
+			*rsp->rs_current = ((u_char *) buf)[i];
+			if (++rsp->rs_current == rsp->rs_end) {
+				rndtest_test(rsp);
+				rsp->rs_current = rsp->rs_begin;
+				/*
+				 * If tests passed, turn off collection and
+				 * schedule another test. Otherwise we keep
+				 * testing until the data looks ok.
+				 */
+				if (!rsp->rs_discard && rndtest_retest != 0) {
+					rsp->rs_collect = 0;
+					callout_reset(&rsp->rs_to,
+						hz * rndtest_retest,
+						rndtest_timeout, rsp);
+					break;
+				}
+			}
+		}
+	}
+	/*
+	 * Only stir entropy that passes muster into the pool.
+	 */
+	if (rsp->rs_discard)
+		rndstats.rst_discard += len;
+	else
+		random_harvest(buf, len, len*NBBY, 0, RANDOM_PURE);
+}
+
+static void
+rndtest_test(struct rndtest_state *rsp)
+{
+	int i, rv = 0;
+
+	rndstats.rst_tests++;
+	for (i = 0; i < RNDTEST_NTESTS; i++)
+		rv |= (*rndtest_funcs[i].test)(rsp);
+	rsp->rs_discard = (rv != 0);
+}
+
+static void
+rndtest_report(struct rndtest_state *rsp, int failure, const char *fmt, ...)
+{
+	char buf[80];
+	va_list ap;
+
+	if (rndtest_verbose == 0)
+		return;
+	if (!failure && rndtest_verbose == 1)	/* don't report successes */
+		return;
+	va_start(ap, fmt);
+	vsnprintf(buf, sizeof (buf), fmt, ap);
+	va_end(ap);
+	device_printf(rsp->rs_parent, "rndtest: %s\n", buf);
+}
+
+#define	RNDTEST_MONOBIT_MINONES	9725
+#define	RNDTEST_MONOBIT_MAXONES	10275
+
+static int
+rndtest_monobit(struct rndtest_state *rsp)
+{
+	int i, ones = 0, j;
+	u_int8_t r;
+
+	for (i = 0; i < RNDTEST_NBYTES; i++) {
+		r = rsp->rs_buf[i];
+		for (j = 0; j < 8; j++, r <<= 1)
+			if (r & 0x80)
+				ones++;
+	}
+	if (ones > RNDTEST_MONOBIT_MINONES &&
+	    ones < RNDTEST_MONOBIT_MAXONES) {
+		if (rndtest_verbose > 1)
+			rndtest_report(rsp, 0, "monobit pass (%d < %d < %d)",
+			    RNDTEST_MONOBIT_MINONES, ones,
+			    RNDTEST_MONOBIT_MAXONES);
+		return (0);
+	} else {
+		if (rndtest_verbose)
+			rndtest_report(rsp, 1,
+			    "monobit failed (%d ones)", ones);
+		rndstats.rst_monobit++;
+		return (-1);
+	}
+}
+
+#define	RNDTEST_RUNS_NINTERVAL	6
+
+static const struct rndtest_runs_tabs {
+	u_int16_t min, max;
+} rndtest_runs_tab[] = {
+	{ 2343, 2657 },
+	{ 1135, 1365 },
+	{ 542, 708 },
+	{ 251, 373 },
+	{ 111, 201 },
+	{ 111, 201 },
+};
+
+static int
+rndtest_runs(struct rndtest_state *rsp)
+{
+	int i, j, ones, zeros, rv = 0;
+	int onei[RNDTEST_RUNS_NINTERVAL], zeroi[RNDTEST_RUNS_NINTERVAL];
+	u_int8_t c;
+
+	bzero(onei, sizeof(onei));
+	bzero(zeroi, sizeof(zeroi));
+	ones = zeros = 0;
+	for (i = 0; i < RNDTEST_NBYTES; i++) {
+		c = rsp->rs_buf[i];
+		for (j = 0; j < 8; j++, c <<= 1) {
+			if (c & 0x80) {
+				ones++;
+				rndtest_runs_record(rsp, zeros, zeroi);
+				zeros = 0;
+			} else {
+				zeros++;
+				rndtest_runs_record(rsp, ones, onei);
+				ones = 0;
+			}
+		}
+	}
+	rndtest_runs_record(rsp, ones, onei);
+	rndtest_runs_record(rsp, zeros, zeroi);
+
+	rv |= rndtest_runs_check(rsp, 0, zeroi);
+	rv |= rndtest_runs_check(rsp, 1, onei);
+
+	if (rv)
+		rndstats.rst_runs++;
+
+	return (rv);
+}
+
+static void
+rndtest_runs_record(struct rndtest_state *rsp, int len, int *intrv)
+{
+	if (len == 0)
+		return;
+	if (len > RNDTEST_RUNS_NINTERVAL)
+		len = RNDTEST_RUNS_NINTERVAL;
+	len -= 1;
+	intrv[len]++;
+}
+
+static int
+rndtest_runs_check(struct rndtest_state *rsp, int val, int *src)
+{
+	int i, rv = 0;
+
+	for (i = 0; i < RNDTEST_RUNS_NINTERVAL; i++) {
+		if (src[i] < rndtest_runs_tab[i].min ||
+		    src[i] > rndtest_runs_tab[i].max) {
+			rndtest_report(rsp, 1,
+			    "%s interval %d failed (%d, %d-%d)",
+			    val ? "ones" : "zeros",
+			    i + 1, src[i], rndtest_runs_tab[i].min,
+			    rndtest_runs_tab[i].max);
+			rv = -1;
+		} else {
+			rndtest_report(rsp, 0,
+			    "runs pass %s interval %d (%d < %d < %d)",
+			    val ? "ones" : "zeros",
+			    i + 1, rndtest_runs_tab[i].min, src[i],
+			    rndtest_runs_tab[i].max);
+		}
+	}
+	return (rv);
+}
+
+static int
+rndtest_longruns(struct rndtest_state *rsp)
+{
+	int i, j, ones = 0, zeros = 0, maxones = 0, maxzeros = 0;
+	u_int8_t c;
+
+	for (i = 0; i < RNDTEST_NBYTES; i++) {
+		c = rsp->rs_buf[i];
+		for (j = 0; j < 8; j++, c <<= 1) {
+			if (c & 0x80) {
+				zeros = 0;
+				ones++;
+				if (ones > maxones)
+					maxones = ones;
+			} else {
+				ones = 0;
+				zeros++;
+				if (zeros > maxzeros)
+					maxzeros = zeros;
+			}
+		}
+	}
+
+	if (maxones < 26 && maxzeros < 26) {
+		rndtest_report(rsp, 0, "longruns pass (%d ones, %d zeros)",
+			maxones, maxzeros);
+		return (0);
+	} else {
+		rndtest_report(rsp, 1, "longruns fail (%d ones, %d zeros)",
+			maxones, maxzeros);
+		rndstats.rst_longruns++;
+		return (-1);
+	}
+}
+
+/*
+ * chi^2 test over 4 bits: (this is called the poker test in FIPS 140-2,
+ * but it is really the chi^2 test over 4 bits (the poker test as described
+ * by Knuth vol 2 is something different, and I take him as authoritative
+ * on nomenclature over NIST).
+ */
+#define	RNDTEST_CHI4_K	16
+#define	RNDTEST_CHI4_K_MASK	(RNDTEST_CHI4_K - 1)
+
+/*
+ * The unnormalized values are used so that we don't have to worry about
+ * fractional precision.  The "real" value is found by:
+ *	(V - 1562500) * (16 / 5000) = Vn   (where V is the unnormalized value)
+ */
+#define	RNDTEST_CHI4_VMIN	1563181		/* 2.1792 */
+#define	RNDTEST_CHI4_VMAX	1576929		/* 46.1728 */
+
+static int
+rndtest_chi_4(struct rndtest_state *rsp)
+{
+	unsigned int freq[RNDTEST_CHI4_K], i, sum;
+
+	for (i = 0; i < RNDTEST_CHI4_K; i++)
+		freq[i] = 0;
+
+	/* Get number of occurances of each 4 bit pattern */
+	for (i = 0; i < RNDTEST_NBYTES; i++) {
+		freq[(rsp->rs_buf[i] >> 4) & RNDTEST_CHI4_K_MASK]++;
+		freq[(rsp->rs_buf[i] >> 0) & RNDTEST_CHI4_K_MASK]++;
+	}
+
+	for (i = 0, sum = 0; i < RNDTEST_CHI4_K; i++)
+		sum += freq[i] * freq[i];
+
+	if (sum >= 1563181 && sum <= 1576929) {
+		rndtest_report(rsp, 0, "chi^2(4): pass (sum %u)", sum);
+		return (0);
+	} else {
+		rndtest_report(rsp, 1, "chi^2(4): failed (sum %u)", sum);
+		rndstats.rst_chi++;
+		return (-1);
+	}
+}
+
+static void
+rndtest_timeout(void *xrsp)
+{
+	struct rndtest_state *rsp = xrsp;
+
+	rsp->rs_collect = 1;
+}
+
+static int
+rndtest_modevent(module_t mod, int type, void *unused)
+{
+	switch (type) {
+	case MOD_LOAD:
+		return 0;
+	case MOD_UNLOAD:
+		return 0;
+	}
+	return EINVAL;
+}
+
+static moduledata_t rndtest_mod = {
+	"rndtest",
+	rndtest_modevent,
+	0
+};
+DECLARE_MODULE(rndtest, rndtest_mod, SI_SUB_DRIVERS, SI_ORDER_ANY);
+MODULE_VERSION(rndtest, 1);
diff --git a/sys/dev/rndtest/rndtest.h b/sys/dev/rndtest/rndtest.h
new file mode 100644
index 0000000..93b7eb8
--- /dev/null
+++ b/sys/dev/rndtest/rndtest.h
@@ -0,0 +1,60 @@
+/*	$FreeBSD$	*/
+/*	$OpenBSD$	*/
+
+/*
+ * Copyright (c) 2002 Jason L. Wright (jason@thought.net)
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by Jason L. Wright
+ * 4. The name of the author may not be used to endorse or promote products
+ *    derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+
+/* Some of the tests depend on these values */
+#define	RNDTEST_NBYTES	2500
+#define	RNDTEST_NBITS	(8 * RNDTEST_NBYTES)
+
+struct rndtest_state {
+	device_t	rs_parent;	/* associated device */
+	u_int8_t	*rs_end, *rs_begin, *rs_current;
+	struct callout	rs_to;
+	int		rs_collect;	/* collect and test data */
+	int		rs_discard;	/* discard/accept random data */
+	u_int8_t	rs_buf[RNDTEST_NBYTES];
+};
+
+struct rndtest_stats {
+	u_int32_t	rst_discard;	/* number of bytes discarded */
+	u_int32_t	rst_tests;	/* number of test runs */
+	u_int32_t	rst_monobit;	/* monobit test failures */
+	u_int32_t	rst_runs;	/* 0/1 runs failures */
+	u_int32_t	rst_longruns;	/* longruns failures */
+	u_int32_t	rst_chi;	/* chi^2 failures */
+};
+
+extern 	struct rndtest_state *rndtest_attach(device_t dev);
+extern	void rndtest_detach(struct rndtest_state *);
+extern	void rndtest_harvest(struct rndtest_state *arg, void * buf, u_int len);