diff options
| author | tls <tls@NetBSD.org> | 2011-11-19 22:51:18 +0000 |
|---|---|---|
| committer | tls <tls@NetBSD.org> | 2011-11-19 22:51:18 +0000 |
| commit | 8e9334525367ba7642ed9b753a94935c07817c19 (patch) | |
| tree | 1b53338e20cd060235386b574dbf34d8cf11d50f /sys/lib | |
| parent | 836ffd606791f7517a3ff458821d8013500d001c (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.libkern | 3 | ||||
| -rw-r--r-- | sys/lib/libkern/arc4random.c | 239 | ||||
| -rw-r--r-- | sys/lib/libkern/rngtest.c | 281 |
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; +} |
