summaryrefslogtreecommitdiff
path: root/sys/lib
diff options
context:
space:
mode:
authortls <tls@NetBSD.org>2011-11-19 22:51:18 +0000
committertls <tls@NetBSD.org>2011-11-19 22:51:18 +0000
commit8e9334525367ba7642ed9b753a94935c07817c19 (patch)
tree1b53338e20cd060235386b574dbf34d8cf11d50f /sys/lib
parent836ffd606791f7517a3ff458821d8013500d001c (diff)
First step of random number subsystem rework described in
<20111022023242.BA26F14A158@mail.netbsd.org>. This change includes the following: An initial cleanup and minor reorganization of the entropy pool code in sys/dev/rnd.c and sys/dev/rndpool.c. Several bugs are fixed. Some effort is made to accumulate entropy more quickly at boot time. A generic interface, "rndsink", is added, for stream generators to request that they be re-keyed with good quality entropy from the pool as soon as it is available. The arc4random()/arc4randbytes() implementation in libkern is adjusted to use the rndsink interface for rekeying, which helps address the problem of low-quality keys at boot time. An implementation of the FIPS 140-2 statistical tests for random number generator quality is provided (libkern/rngtest.c). This is based on Greg Rose's implementation from Qualcomm. A new random stream generator, nist_ctr_drbg, is provided. It is based on an implementation of the NIST SP800-90 CTR_DRBG by Henric Jungheim. This generator users AES in a modified counter mode to generate a backtracking-resistant random stream. An abstraction layer, "cprng", is provided for in-kernel consumers of randomness. The arc4random/arc4randbytes API is deprecated for in-kernel use. It is replaced by "cprng_strong". The current cprng_fast implementation wraps the existing arc4random implementation. The current cprng_strong implementation wraps the new CTR_DRBG implementation. Both interfaces are rekeyed from the entropy pool automatically at intervals justifiable from best current cryptographic practice. In some quick tests, cprng_fast() is about the same speed as the old arc4randbytes(), and cprng_strong() is about 20% faster than rnd_extract_data(). Performance is expected to improve. The AES code in src/crypto/rijndael is no longer an optional kernel component, as it is required by cprng_strong, which is not an optional kernel component. The entropy pool output is subjected to the rngtest tests at startup time; if it fails, the system will reboot. There is approximately a 3/10000 chance of a false positive from these tests. Entropy pool _input_ from hardware random numbers is subjected to the rngtest tests at attach time, as well as the FIPS continuous-output test, to detect bad or stuck hardware RNGs; if any are detected, they are detached, but the system continues to run. A problem with rndctl(8) is fixed -- datastructures with pointers in arrays are no longer passed to userspace (this was not a security problem, but rather a major issue for compat32). A new kernel will require a new rndctl. The sysctl kern.arandom() and kern.urandom() nodes are hooked up to the new generators, but the /dev/*random pseudodevices are not, yet. Manual pages for the new kernel interfaces are forthcoming.
Diffstat (limited to 'sys/lib')
-rw-r--r--sys/lib/libkern/Makefile.libkern3
-rw-r--r--sys/lib/libkern/arc4random.c239
-rw-r--r--sys/lib/libkern/rngtest.c281
3 files changed, 449 insertions, 74 deletions
diff --git a/sys/lib/libkern/Makefile.libkern b/sys/lib/libkern/Makefile.libkern
index cc5adacff32..e15c16ca870 100644
--- a/sys/lib/libkern/Makefile.libkern
+++ b/sys/lib/libkern/Makefile.libkern
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile.libkern,v 1.14 2011/08/26 21:22:10 dyoung Exp $
+# $NetBSD: Makefile.libkern,v 1.15 2011/11/19 22:51:25 tls Exp $
#
# Variable definitions for libkern.
@@ -82,6 +82,7 @@ SRCS+= strtoul.c strtoll.c strtoull.c strtoumax.c
SRCS+= scanc.c skpc.c
SRCS+= random.c
+SRCS+= rngtest.c
SRCS+= memchr.c
SRCS+= strcat.c strcmp.c strcpy.c strlen.c
diff --git a/sys/lib/libkern/arc4random.c b/sys/lib/libkern/arc4random.c
index 5a0b846a9f3..566befabd14 100644
--- a/sys/lib/libkern/arc4random.c
+++ b/sys/lib/libkern/arc4random.c
@@ -1,7 +1,7 @@
-/* $NetBSD: arc4random.c,v 1.21 2010/01/18 20:54:54 joerg Exp $ */
+/* $NetBSD: arc4random.c,v 1.22 2011/11/19 22:51:25 tls Exp $ */
/*-
- * Copyright (c) 2002 The NetBSD Foundation, Inc.
+ * Copyright (c) 2002, 2011 The NetBSD Foundation, Inc.
* All rights reserved.
*
* This code is derived from software contributed to The NetBSD Foundation
@@ -57,15 +57,44 @@
#endif
#include <sys/systm.h>
+#ifdef _KERNEL
+#include <sys/mutex.h>
+#include <sys/rngtest.h>
+#else
+#define mutex_spin_enter(x) ;
+#define mutex_spin_exit(x) ;
+#define mutex_init(x, y, z) ;
+#endif
+
#include <lib/libkern/libkern.h>
#if NRND > 0
#include <sys/rnd.h>
+
+rndsink_t rs;
+
#endif
-#define ARC4_MAXRUNS 16384
-#define ARC4_RESEED_SECONDS 300
-#define ARC4_KEYBYTES 32 /* 256 bit key */
+/*
+ * The best known attack that distinguishes RC4 output from a random
+ * bitstream requires 2^25 bytes. (see Paul and Preneel, Analysis of
+ * Non-fortuitous Predictive States of the RC4 Keystream Generator.
+ * INDOCRYPT 2003, pp52 – 67).
+ *
+ * However, we discard the first 1024 bytes of output, avoiding the
+ * biases detected in this paper. The best current attack that
+ * can distinguish this "RC4[drop]" output seems to be Fleuhrer &
+ * McGrew's attack which requires 2^30.6 bytes of output:
+ * Fluhrer and McGrew, Statistical Analysis of the Alleged RC4
+ * Keystream Generator. FSE 2000, pp19 – 30
+ *
+ * We begin trying to rekey at 2^24 bytes, and forcibly rekey at 2^29 bytes
+ * even if the resulting key cannot be guaranteed to have full entropy.
+ */
+#define ARC4_MAXBYTES (16 * 1024 * 1024)
+#define ARC4_HARDMAX (512 * 1024 * 1024)
+#define ARC4_RESEED_SECONDS 300
+#define ARC4_KEYBYTES 16 /* 128 bit key */
#ifdef _STANDALONE
#define time_uptime 1 /* XXX ugly! */
@@ -73,11 +102,17 @@
static u_int8_t arc4_i, arc4_j;
static int arc4_initialized = 0;
-static int arc4_numruns = 0;
+static int arc4_numbytes = 0;
static u_int8_t arc4_sbox[256];
static time_t arc4_nextreseed;
+#ifdef _KERNEL
+kmutex_t arc4_mtx;
+#endif
+
static inline u_int8_t arc4_randbyte(void);
+static inline void arc4randbytes_unlocked(void *, size_t);
+
static inline void
arc4_swap(u_int8_t *a, u_int8_t *b)
@@ -93,62 +128,119 @@ arc4_swap(u_int8_t *a, u_int8_t *b)
* Stir our S-box.
*/
static void
-arc4_randrekey(void)
+arc4_randrekey(void *arg)
{
u_int8_t key[256];
- static int cur_keybytes;
- int n, byteswanted;
+ int n, ask_for_more = 0;
+#ifdef _KERNEL
+ rngtest_t rt;
+#endif
#if NRND > 0
+ static int callback_pending;
int r;
#endif
- if(!arc4_initialized)
- /* The first time through, we must take what we can get */
- byteswanted = 0;
- else
- /* Don't rekey with less entropy than we already have */
- byteswanted = cur_keybytes;
-
+ /*
+ * The first time through, we must take what we can get,
+ * so schedule ourselves for callback no matter what.
+ */
+ if (__predict_true(arc4_initialized)) {
+ mutex_spin_enter(&arc4_mtx);
+ }
#if NRND > 0 /* XXX without rnd, we will key from the stack, ouch! */
- r = rnd_extract_data(key, ARC4_KEYBYTES, RND_EXTRACT_GOOD);
-
- if (r < ARC4_KEYBYTES) {
- if (r >= byteswanted) {
- (void)rnd_extract_data(key + r,
- ARC4_KEYBYTES - r,
- RND_EXTRACT_ANY);
- } else {
- /* don't replace a good key with a bad one! */
- arc4_nextreseed = time_uptime + ARC4_RESEED_SECONDS;
- arc4_numruns = 0;
- /* we should just ask rnd(4) to rekey us when
- it can, but for now, we'll just try later. */
- return;
- }
+ else {
+ ask_for_more = 1;
+ r = rnd_extract_data(key, ARC4_KEYBYTES, RND_EXTRACT_ANY);
+ goto got_entropy;
}
- cur_keybytes = r;
-
- for (n = ARC4_KEYBYTES; n < sizeof(key); n++)
- key[n] = key[n % ARC4_KEYBYTES];
-#endif
- for (n = 0; n < 256; n++) {
- arc4_j = (arc4_j + arc4_sbox[n] + key[n]) % 256;
- arc4_swap(&arc4_sbox[n], &arc4_sbox[arc4_j]);
+ if (arg == NULL) {
+ if (callback_pending) {
+ if (arc4_numbytes > ARC4_HARDMAX) {
+ printf("arc4random: WARNING, hit 2^29 bytes, "
+ "forcibly rekeying.\n");
+ r = rnd_extract_data(key, ARC4_KEYBYTES,
+ RND_EXTRACT_ANY);
+ rndsink_detach(&rs);
+ callback_pending = 0;
+ goto got_entropy;
+ } else {
+ mutex_spin_exit(&arc4_mtx);
+ return;
+ }
+ }
+ r = rnd_extract_data(key, ARC4_KEYBYTES, RND_EXTRACT_GOOD);
+ if (r < ARC4_KEYBYTES) {
+ ask_for_more = 1;
+ }
+ } else {
+ ask_for_more = 0;
+ callback_pending = 0;
+ if (rs.len != ARC4_KEYBYTES) {
+ panic("arc4_randrekey: rekey callback bad length");
+ }
+ memcpy(key, rs.data, rs.len);
+ memset(rs.data, 0, rs.len);
}
- arc4_i = arc4_j;
-
- /* Reset for next reseed cycle. */
- arc4_nextreseed = time_uptime + ARC4_RESEED_SECONDS;
- arc4_numruns = 0;
+got_entropy:
+
+ if (!ask_for_more) {
+ callback_pending = 0;
+ } else if (!callback_pending) {
+ callback_pending = 1;
+ strlcpy(rs.name, "arc4random", sizeof(rs.name));
+ rs.cb = arc4_randrekey;
+ rs.arg = &rs;
+ rs.len = ARC4_KEYBYTES;
+ rndsink_attach(&rs);
+ }
+#endif
/*
- * Throw away the first N words of output, as suggested in the
- * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
- * by Fluher, Mantin, and Shamir. (N = 256 in our case.)
+ * If it's the first time, or we got a good key, actually rekey.
*/
- for (n = 0; n < 256 * 4; n++)
- arc4_randbyte();
+ if (!ask_for_more || !arc4_initialized) {
+ for (n = ARC4_KEYBYTES; n < sizeof(key); n++)
+ key[n] = key[n % ARC4_KEYBYTES];
+
+ for (n = 0; n < 256; n++) {
+ arc4_j = (arc4_j + arc4_sbox[n] + key[n]) % 256;
+ arc4_swap(&arc4_sbox[n], &arc4_sbox[arc4_j]);
+ }
+ arc4_i = arc4_j;
+
+ memset(key, 0, sizeof(key));
+ /*
+ * Throw away the first N words of output, as suggested in the
+ * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
+ * by Fluher, Mantin, and Shamir. (N = 256 in our case.)
+ */
+ for (n = 0; n < 256 * 4; n++)
+ arc4_randbyte();
+
+ /* Reset for next reseed cycle. */
+ arc4_nextreseed = time_uptime + ARC4_RESEED_SECONDS;
+ arc4_numbytes = 0;
+#ifdef _KERNEL
+#ifdef DIAGNOSTIC
+ /*
+ * Perform the FIPS 140-2 statistical RNG test; warn if our
+ * output has such poor quality as to fail the test.
+ */
+ arc4randbytes_unlocked(rt.rt_b, sizeof(rt.rt_b));
+ strlcpy(rt.rt_name, "arc4random", sizeof(rt.rt_name));
+ if (rngtest(&rt)) {
+ /* rngtest will scream to the console. */
+ arc4_nextreseed = time_uptime;
+ arc4_numbytes = ARC4_MAXBYTES;
+ /* XXX should keep old context around, *NOT* use new */
+ }
+#endif
+#endif
+ }
+ if (__predict_true(arc4_initialized)) {
+ mutex_spin_exit(&arc4_mtx);
+ }
}
/*
@@ -159,11 +251,12 @@ arc4_init(void)
{
int n;
+ mutex_init(&arc4_mtx, MUTEX_DEFAULT, IPL_VM);
arc4_i = arc4_j = 0;
for (n = 0; n < 256; n++)
arc4_sbox[n] = (u_int8_t) n;
- arc4_randrekey();
+ arc4_randrekey(NULL);
arc4_initialized = 1;
}
@@ -187,40 +280,40 @@ arc4_randbyte(void)
u_int32_t
arc4random(void)
{
- u_int32_t ret;
- int i;
+ int ret;
+ u_int8_t *retc;
- /* Initialize array if needed. */
- if (!arc4_initialized)
- arc4_init();
+ retc = (u_int8_t *)&ret;
- if ((++arc4_numruns > ARC4_MAXRUNS) ||
- (time_uptime > arc4_nextreseed)) {
- arc4_randrekey();
- }
+ arc4randbytes(retc, sizeof(u_int32_t));
+ return ret;
+}
- for (i = 0, ret = 0; i <= 24; ret |= arc4_randbyte() << i, i += 8)
+static inline void
+arc4randbytes_unlocked(void *p, size_t len)
+{
+ u_int8_t *buf = (u_int8_t *)p;
+ size_t i;
+
+ for (i = 0; i < len; buf[i] = arc4_randbyte(), i++)
continue;
- return ret;
}
void
arc4randbytes(void *p, size_t len)
{
- u_int8_t *buf;
- size_t i;
-
/* Initialize array if needed. */
- if (!arc4_initialized)
+ if (!arc4_initialized) {
arc4_init();
-
- buf = (u_int8_t *)p;
-
- for (i = 0; i < len; buf[i] = arc4_randbyte(), i++)
- continue;
- arc4_numruns += len / sizeof(u_int32_t);
- if ((arc4_numruns > ARC4_MAXRUNS) ||
+ /* avoid conditionalizing locking */
+ return arc4randbytes_unlocked(p, len);
+ }
+ mutex_spin_enter(&arc4_mtx);
+ arc4randbytes_unlocked(p, len);
+ arc4_numbytes += len;
+ mutex_spin_exit(&arc4_mtx);
+ if ((arc4_numbytes > ARC4_MAXBYTES) ||
(time_uptime > arc4_nextreseed)) {
- arc4_randrekey();
+ arc4_randrekey(NULL);
}
}
diff --git a/sys/lib/libkern/rngtest.c b/sys/lib/libkern/rngtest.c
new file mode 100644
index 00000000000..d423d40e39b
--- /dev/null
+++ b/sys/lib/libkern/rngtest.c
@@ -0,0 +1,281 @@
+/* $NetBSD: rngtest.c,v 1.1 2011/11/19 22:51:25 tls Exp $ */
+
+/*-
+ * Copyright (c) 2011 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to The NetBSD Foundation
+ * by Thor Lancelot Simon.
+ *
+ * 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
+ * ``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 FOUNDATION OR CONTRIBUTORS
+ * 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.
+ */
+
+/* fips140.c 1.5 (Qualcomm) 02/09/02 */
+/*
+This software is free for commercial and non-commercial use
+subject to the following conditions.
+
+Copyright remains vested in QUALCOMM Incorporated, and Copyright
+notices in the code are not to be removed. If this package is used in
+a product, QUALCOMM should be given attribution as the author this
+software. This can be in the form of a textual message at program
+startup or in documentation (online or textual) provided with the
+package.
+
+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 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 QUALCOMM Incorporated.
+
+THIS SOFTWARE IS PROVIDED ``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 OR CONTRIBUTORS 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.
+
+The license and distribution terms for any publically available version
+or derivative of this code cannot be changed, that is, this code cannot
+simply be copied and put under another distribution license including
+the GNU Public License.
+*/
+
+/* Run FIPS 140 statistical tests on a file */
+
+/* written by Greg Rose, Copyright C 2000 QUALCOMM Incorporated */
+
+/*
+ * Modified for in-kernel use (API adjustments, conversion from
+ * floating to fixed-point chi-sq computation) by Thor Lancelot
+ * Simon.
+ *
+ * A comment on appropriate use of this test and the infamous FIPS 140
+ * "continuous output test" (COT): Both tests are very appropriate for
+ * software interfaces to hardware implementations, and will quickly tell
+ * you if any number of very bad things have happened to your RNG: perhaps
+ * it has come disconnected from the rest of the system, somehow, and you
+ * are getting only unconditioned bus noise (read: clock edges from the
+ * loudest thing in your system). Perhaps it has ceased to latch a shift
+ * register and is feeding you the same data over and over again. Perhaps
+ * it is not really random at all but was sold to you as such. Perhaps it
+ * is not actually *there* (Intel chipset RNG anyone?) but claims to be,
+ * and is feeding you 01010101 on every register read.
+ *
+ * However, when applied to software RNGs, the situation is quite different.
+ * Most software RNGs use a modern hash function or cipher as an output
+ * stage. The resulting bitstream assuredly *should* pass both the
+ * "continuous output" (no two consecutive samples identical) and
+ * statistical tests: if it does not, the cryptographic primitive or its
+ * implementation is terribly broken.
+ *
+ * There is still value to this test: it will tell you if you inadvertently
+ * terribly break your implementation of the software RNG. Which is a thing
+ * that has in fact happened from time to time, even to the careful (or
+ * paranoid). But it will not tell you if there is a problem with the
+ * _input_ to that final cryptographic primitive -- the bits that are hashed
+ * or the key to the cipher -- and if an adversary can find one, you're
+ * still toast.
+ *
+ * The situation is -- sadly -- similar with hardware RNGs that are
+ * certified to one of the standards such as X9.31 or SP800-90. In these
+ * cases the hardware vendor has hidden the actual random bitstream behind
+ * a hardware cipher/hash implementation that should, indeed, produce good
+ * quality random numbers that pass will pass this test -- whether the
+ * underlying bitstream is trustworthy or not.
+ *
+ * However, this test (and the COT) will still probably tell you if the
+ * thing fell off the bus, etc. Which is a thing that has in fact
+ * happened from time to time, even to the fully certified...
+ *
+ * This module does not (yet?) implement the Continuous Output Test. When
+ * I call that test "infamous", it's because it obviously reduces the
+ * backtracking resistance of any implementation that includes it -- the
+ * implementation has to store the entire previous RNG output in order to
+ * perform the required comparison; not just periodically but all the time
+ * when operating at all. Nonetheless, it has obvious value for
+ * hardware implementations where it will quickly and surely detect a
+ * severe failure; but as of this writing several of the latest comments
+ * on SP800-90 recommend removing any requirement for the COT and my
+ * personal tendency is to agree. It's easy to add if you really need it.
+ *
+ */
+
+#include <sys/types.h>
+#include <sys/systm.h>
+#include <sys/rngtest.h>
+
+#include <lib/libkern/libkern.h>
+
+#include <sys/cdefs.h>
+__KERNEL_RCSID(0, "$NetBSD: rngtest.c,v 1.1 2011/11/19 22:51:25 tls Exp $");
+
+#ifndef _KERNEL
+static inline int
+printf(const char *restrict format, ...)
+{
+ return 0; /* XXX no standard way to do output in libkern? */
+}
+#endif
+
+int bitnum = 0;
+
+const int minrun[7] = {0, 2315, 1114, 527, 240, 103, 103};
+const int maxrun[7] = {0, 2685, 1386, 723, 384, 209, 209};
+#define LONGRUN 26
+#define MINONES 9725
+#define MAXONES 10275
+#define MINPOKE 2.16
+#define MAXPOKE 46.17
+#define PRECISION 100000
+
+const int longrun = LONGRUN;
+const int minones = MINONES;
+const int maxones = MAXONES;
+const long long minpoke = (MINPOKE * PRECISION);
+const long long maxpoke = (MAXPOKE * PRECISION);
+
+/* Population count of 1's in a byte */
+const unsigned char Popcount[] = {
+ 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+ 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
+};
+
+/* end of run */
+static void
+endrun(rngtest_t *const rc, const int last, int run)
+{
+ if (run >= longrun) {
+ printf("Kernel RNG \"%s\" long run test FAILURE: "
+ "Run of %d %ds found\n", rc->rt_name, run, last);
+ ++rc->rt_nerrs;
+ }
+ if (run > 6)
+ run = 6;
+ ++rc->rt_runs[last][run];
+}
+
+int
+rngtest(rngtest_t *const rc)
+{
+ int i;
+ uint8_t *p;
+ int c;
+ long long X;
+ int last;
+ int run;
+
+ /* Enforce sanity for most members of the context */
+ memset(rc->rt_poker, 0, sizeof(rc->rt_poker));
+ memset(rc->rt_runs, 0, sizeof(rc->rt_runs));
+ rc->rt_nerrs = 0;
+ rc->rt_name[sizeof(rc->rt_name) - 1] = '\0';
+
+ /* monobit test */
+ for (p = rc->rt_b, c = 0; p < &rc->rt_b[sizeof rc->rt_b]; ++p)
+ c += Popcount[*p];
+ if (c <= minones || maxones <= c) {
+ printf("Kernel RNG \"%s\" monobit test FAILURE: %d ones\n",
+ rc->rt_name, c);
+ ++rc->rt_nerrs;
+ }
+ /* poker test */
+ for (p = rc->rt_b; p < &rc->rt_b[sizeof rc->rt_b]; ++p) {
+ ++rc->rt_poker[*p & 0xF];
+ ++rc->rt_poker[(*p >> 4) & 0xF];
+ }
+ for (X = i = 0; i < 16; ++i) {
+ X += rc->rt_poker[i] * rc->rt_poker[i];
+ }
+ X *= PRECISION;
+ X = 16 * X / 5000 - 5000 * PRECISION;
+ if (X <= minpoke || maxpoke <= X) {
+ printf("Kernel RNG \"%s\" poker test failure: "
+ "parameter X = %lld.%lld\n", rc->rt_name,
+ (X / PRECISION), (X % PRECISION));
+ ++rc->rt_nerrs;
+ }
+ /* runs test */
+ last = (rc->rt_b[0] >> 7) & 1;
+ run = 0;
+ for (p = rc->rt_b; p < &rc->rt_b[sizeof rc->rt_b]; ++p) {
+ c = *p;
+ for (i = 7; i >= 0; --i) {
+ if (((c >> i) & 1) != last) {
+ endrun(rc, last, run);
+ run = 0;
+ last = (c >> i) & 1;
+ }
+ ++run;
+ }
+ }
+ endrun(rc, last, run);
+
+ for (run = 1; run <= 6; ++run) {
+ for (last = 0; last <= 1; ++last) {
+ if (rc->rt_runs[last][run] <= minrun[run]) {
+ printf("Kernel RNG \"%s\" runs test FAILURE: "
+ "too few runs of %d %ds (%d < %d)\n",
+ rc->rt_name, run, last,
+ rc->rt_runs[last][run], minrun[run]);
+ ++rc->rt_nerrs;
+ } else if (rc->rt_runs[last][run] >= maxrun[run]) {
+ printf("Kernel RNG \"%s\" runs test FAILURE: "
+ "too many runs of %d %ds (%d > %d)\n",
+ rc->rt_name, run, last,
+ rc->rt_runs[last][run], maxrun[run]);
+ ++rc->rt_nerrs;
+ }
+ }
+ }
+ memset(rc->rt_b, 0, sizeof(rc->rt_b));
+ return rc->rt_nerrs;
+}