1 /* $NetBSD: rngtest.c,v 1.2 2011/11/25 12:45:00 joerg Exp $ */ 2 3 /*- 4 * Copyright (c) 2011 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Thor Lancelot Simon. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 /* fips140.c 1.5 (Qualcomm) 02/09/02 */ 33 /* 34 This software is free for commercial and non-commercial use 35 subject to the following conditions. 36 37 Copyright remains vested in QUALCOMM Incorporated, and Copyright 38 notices in the code are not to be removed. If this package is used in 39 a product, QUALCOMM should be given attribution as the author this 40 software. This can be in the form of a textual message at program 41 startup or in documentation (online or textual) provided with the 42 package. 43 44 Redistribution and use in source and binary forms, with or without 45 modification, are permitted provided that the following conditions are 46 met: 47 48 1. Redistributions of source code must retain the copyright notice, 49 this list of conditions and the following disclaimer. 50 51 2. Redistributions in binary form must reproduce the above copyright 52 notice, this list of conditions and the following disclaimer in the 53 documentation and/or other materials provided with the 54 distribution. 55 56 3. All advertising materials mentioning features or use of this 57 software must display the following acknowledgement: This product 58 includes software developed by QUALCOMM Incorporated. 59 60 THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED 61 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 62 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 63 IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 64 INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 65 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 66 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 67 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 68 STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 69 IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 70 POSSIBILITY OF SUCH DAMAGE. 71 72 The license and distribution terms for any publically available version 73 or derivative of this code cannot be changed, that is, this code cannot 74 simply be copied and put under another distribution license including 75 the GNU Public License. 76 */ 77 78 /* Run FIPS 140 statistical tests on a file */ 79 80 /* written by Greg Rose, Copyright C 2000 QUALCOMM Incorporated */ 81 82 /* 83 * Modified for in-kernel use (API adjustments, conversion from 84 * floating to fixed-point chi-sq computation) by Thor Lancelot 85 * Simon. 86 * 87 * A comment on appropriate use of this test and the infamous FIPS 140 88 * "continuous output test" (COT): Both tests are very appropriate for 89 * software interfaces to hardware implementations, and will quickly tell 90 * you if any number of very bad things have happened to your RNG: perhaps 91 * it has come disconnected from the rest of the system, somehow, and you 92 * are getting only unconditioned bus noise (read: clock edges from the 93 * loudest thing in your system). Perhaps it has ceased to latch a shift 94 * register and is feeding you the same data over and over again. Perhaps 95 * it is not really random at all but was sold to you as such. Perhaps it 96 * is not actually *there* (Intel chipset RNG anyone?) but claims to be, 97 * and is feeding you 01010101 on every register read. 98 * 99 * However, when applied to software RNGs, the situation is quite different. 100 * Most software RNGs use a modern hash function or cipher as an output 101 * stage. The resulting bitstream assuredly *should* pass both the 102 * "continuous output" (no two consecutive samples identical) and 103 * statistical tests: if it does not, the cryptographic primitive or its 104 * implementation is terribly broken. 105 * 106 * There is still value to this test: it will tell you if you inadvertently 107 * terribly break your implementation of the software RNG. Which is a thing 108 * that has in fact happened from time to time, even to the careful (or 109 * paranoid). But it will not tell you if there is a problem with the 110 * _input_ to that final cryptographic primitive -- the bits that are hashed 111 * or the key to the cipher -- and if an adversary can find one, you're 112 * still toast. 113 * 114 * The situation is -- sadly -- similar with hardware RNGs that are 115 * certified to one of the standards such as X9.31 or SP800-90. In these 116 * cases the hardware vendor has hidden the actual random bitstream behind 117 * a hardware cipher/hash implementation that should, indeed, produce good 118 * quality random numbers that pass will pass this test -- whether the 119 * underlying bitstream is trustworthy or not. 120 * 121 * However, this test (and the COT) will still probably tell you if the 122 * thing fell off the bus, etc. Which is a thing that has in fact 123 * happened from time to time, even to the fully certified... 124 * 125 * This module does not (yet?) implement the Continuous Output Test. When 126 * I call that test "infamous", it's because it obviously reduces the 127 * backtracking resistance of any implementation that includes it -- the 128 * implementation has to store the entire previous RNG output in order to 129 * perform the required comparison; not just periodically but all the time 130 * when operating at all. Nonetheless, it has obvious value for 131 * hardware implementations where it will quickly and surely detect a 132 * severe failure; but as of this writing several of the latest comments 133 * on SP800-90 recommend removing any requirement for the COT and my 134 * personal tendency is to agree. It's easy to add if you really need it. 135 * 136 */ 137 138 #include <sys/types.h> 139 #include <sys/systm.h> 140 #include <sys/rngtest.h> 141 142 #include <lib/libkern/libkern.h> 143 144 #include <sys/cdefs.h> 145 __KERNEL_RCSID(0, "$NetBSD: rngtest.c,v 1.2 2011/11/25 12:45:00 joerg Exp $"); 146 147 #ifndef _KERNEL 148 static inline int 149 printf(const char * __restrict format, ...) 150 { 151 return 0; /* XXX no standard way to do output in libkern? */ 152 } 153 #endif 154 155 int bitnum = 0; 156 157 const int minrun[7] = {0, 2315, 1114, 527, 240, 103, 103}; 158 const int maxrun[7] = {0, 2685, 1386, 723, 384, 209, 209}; 159 #define LONGRUN 26 160 #define MINONES 9725 161 #define MAXONES 10275 162 #define MINPOKE 2.16 163 #define MAXPOKE 46.17 164 #define PRECISION 100000 165 166 const int longrun = LONGRUN; 167 const int minones = MINONES; 168 const int maxones = MAXONES; 169 const long long minpoke = (MINPOKE * PRECISION); 170 const long long maxpoke = (MAXPOKE * PRECISION); 171 172 /* Population count of 1's in a byte */ 173 const unsigned char Popcount[] = { 174 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 175 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 176 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 177 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 178 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 179 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 180 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 181 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 182 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 183 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 184 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 185 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 186 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 187 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 188 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 189 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 190 }; 191 192 /* end of run */ 193 static void 194 endrun(rngtest_t *const rc, const int last, int run) 195 { 196 if (run >= longrun) { 197 printf("Kernel RNG \"%s\" long run test FAILURE: " 198 "Run of %d %ds found\n", rc->rt_name, run, last); 199 ++rc->rt_nerrs; 200 } 201 if (run > 6) 202 run = 6; 203 ++rc->rt_runs[last][run]; 204 } 205 206 int 207 rngtest(rngtest_t *const rc) 208 { 209 int i; 210 uint8_t *p; 211 int c; 212 long long X; 213 int last; 214 int run; 215 216 /* Enforce sanity for most members of the context */ 217 memset(rc->rt_poker, 0, sizeof(rc->rt_poker)); 218 memset(rc->rt_runs, 0, sizeof(rc->rt_runs)); 219 rc->rt_nerrs = 0; 220 rc->rt_name[sizeof(rc->rt_name) - 1] = '\0'; 221 222 /* monobit test */ 223 for (p = rc->rt_b, c = 0; p < &rc->rt_b[sizeof rc->rt_b]; ++p) 224 c += Popcount[*p]; 225 if (c <= minones || maxones <= c) { 226 printf("Kernel RNG \"%s\" monobit test FAILURE: %d ones\n", 227 rc->rt_name, c); 228 ++rc->rt_nerrs; 229 } 230 /* poker test */ 231 for (p = rc->rt_b; p < &rc->rt_b[sizeof rc->rt_b]; ++p) { 232 ++rc->rt_poker[*p & 0xF]; 233 ++rc->rt_poker[(*p >> 4) & 0xF]; 234 } 235 for (X = i = 0; i < 16; ++i) { 236 X += rc->rt_poker[i] * rc->rt_poker[i]; 237 } 238 X *= PRECISION; 239 X = 16 * X / 5000 - 5000 * PRECISION; 240 if (X <= minpoke || maxpoke <= X) { 241 printf("Kernel RNG \"%s\" poker test failure: " 242 "parameter X = %lld.%lld\n", rc->rt_name, 243 (X / PRECISION), (X % PRECISION)); 244 ++rc->rt_nerrs; 245 } 246 /* runs test */ 247 last = (rc->rt_b[0] >> 7) & 1; 248 run = 0; 249 for (p = rc->rt_b; p < &rc->rt_b[sizeof rc->rt_b]; ++p) { 250 c = *p; 251 for (i = 7; i >= 0; --i) { 252 if (((c >> i) & 1) != last) { 253 endrun(rc, last, run); 254 run = 0; 255 last = (c >> i) & 1; 256 } 257 ++run; 258 } 259 } 260 endrun(rc, last, run); 261 262 for (run = 1; run <= 6; ++run) { 263 for (last = 0; last <= 1; ++last) { 264 if (rc->rt_runs[last][run] <= minrun[run]) { 265 printf("Kernel RNG \"%s\" runs test FAILURE: " 266 "too few runs of %d %ds (%d < %d)\n", 267 rc->rt_name, run, last, 268 rc->rt_runs[last][run], minrun[run]); 269 ++rc->rt_nerrs; 270 } else if (rc->rt_runs[last][run] >= maxrun[run]) { 271 printf("Kernel RNG \"%s\" runs test FAILURE: " 272 "too many runs of %d %ds (%d > %d)\n", 273 rc->rt_name, run, last, 274 rc->rt_runs[last][run], maxrun[run]); 275 ++rc->rt_nerrs; 276 } 277 } 278 } 279 memset(rc->rt_b, 0, sizeof(rc->rt_b)); 280 return rc->rt_nerrs; 281 } 282