| 1 | /* $OpenBSD$ */ |
| 2 | |
| 3 | /* |
| 4 | * OCF/Linux port done by David McCullough <david_mccullough@securecomputing.com> |
| 5 | * Copyright (C) 2006-2007 David McCullough |
| 6 | * Copyright (C) 2004-2005 Intel Corporation. |
| 7 | * The license and original author are listed below. |
| 8 | * |
| 9 | * Copyright (c) 2002 Jason L. Wright (jason@thought.net) |
| 10 | * All rights reserved. |
| 11 | * |
| 12 | * Redistribution and use in source and binary forms, with or without |
| 13 | * modification, are permitted provided that the following conditions |
| 14 | * are met: |
| 15 | * 1. Redistributions of source code must retain the above copyright |
| 16 | * notice, this list of conditions and the following disclaimer. |
| 17 | * 2. Redistributions in binary form must reproduce the above copyright |
| 18 | * notice, this list of conditions and the following disclaimer in the |
| 19 | * documentation and/or other materials provided with the distribution. |
| 20 | * 3. All advertising materials mentioning features or use of this software |
| 21 | * must display the following acknowledgement: |
| 22 | * This product includes software developed by Jason L. Wright |
| 23 | * 4. The name of the author may not be used to endorse or promote products |
| 24 | * derived from this software without specific prior written permission. |
| 25 | * |
| 26 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
| 27 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED |
| 28 | * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
| 29 | * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, |
| 30 | * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES |
| 31 | * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR |
| 32 | * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| 33 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
| 34 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN |
| 35 | * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
| 36 | * POSSIBILITY OF SUCH DAMAGE. |
| 37 | */ |
| 38 | |
| 39 | #ifndef AUTOCONF_INCLUDED |
| 40 | #include <linux/config.h> |
| 41 | #endif |
| 42 | #include <linux/module.h> |
| 43 | #include <linux/list.h> |
| 44 | #include <linux/wait.h> |
| 45 | #include <linux/time.h> |
| 46 | #include <linux/version.h> |
| 47 | #include <linux/unistd.h> |
| 48 | #include <linux/kernel.h> |
| 49 | #include <linux/string.h> |
| 50 | #include <linux/time.h> |
| 51 | #include <cryptodev.h> |
| 52 | #include "rndtest.h" |
| 53 | |
| 54 | static struct rndtest_stats rndstats; |
| 55 | |
| 56 | static void rndtest_test(struct rndtest_state *); |
| 57 | |
| 58 | /* The tests themselves */ |
| 59 | static int rndtest_monobit(struct rndtest_state *); |
| 60 | static int rndtest_runs(struct rndtest_state *); |
| 61 | static int rndtest_longruns(struct rndtest_state *); |
| 62 | static int rndtest_chi_4(struct rndtest_state *); |
| 63 | |
| 64 | static int rndtest_runs_check(struct rndtest_state *, int, int *); |
| 65 | static void rndtest_runs_record(struct rndtest_state *, int, int *); |
| 66 | |
| 67 | static const struct rndtest_testfunc { |
| 68 | int (*test)(struct rndtest_state *); |
| 69 | } rndtest_funcs[] = { |
| 70 | { rndtest_monobit }, |
| 71 | { rndtest_runs }, |
| 72 | { rndtest_chi_4 }, |
| 73 | { rndtest_longruns }, |
| 74 | }; |
| 75 | |
| 76 | #define RNDTEST_NTESTS (sizeof(rndtest_funcs)/sizeof(rndtest_funcs[0])) |
| 77 | |
| 78 | static void |
| 79 | rndtest_test(struct rndtest_state *rsp) |
| 80 | { |
| 81 | int i, rv = 0; |
| 82 | |
| 83 | rndstats.rst_tests++; |
| 84 | for (i = 0; i < RNDTEST_NTESTS; i++) |
| 85 | rv |= (*rndtest_funcs[i].test)(rsp); |
| 86 | rsp->rs_discard = (rv != 0); |
| 87 | } |
| 88 | |
| 89 | |
| 90 | extern int crypto_debug; |
| 91 | #define rndtest_verbose 2 |
| 92 | #define rndtest_report(rsp, failure, fmt, a...) \ |
| 93 | { if (failure || crypto_debug) { printk("rng_test: " fmt "\n", a); } else; } |
| 94 | |
| 95 | #define RNDTEST_MONOBIT_MINONES 9725 |
| 96 | #define RNDTEST_MONOBIT_MAXONES 10275 |
| 97 | |
| 98 | static int |
| 99 | rndtest_monobit(struct rndtest_state *rsp) |
| 100 | { |
| 101 | int i, ones = 0, j; |
| 102 | u_int8_t r; |
| 103 | |
| 104 | for (i = 0; i < RNDTEST_NBYTES; i++) { |
| 105 | r = rsp->rs_buf[i]; |
| 106 | for (j = 0; j < 8; j++, r <<= 1) |
| 107 | if (r & 0x80) |
| 108 | ones++; |
| 109 | } |
| 110 | if (ones > RNDTEST_MONOBIT_MINONES && |
| 111 | ones < RNDTEST_MONOBIT_MAXONES) { |
| 112 | if (rndtest_verbose > 1) |
| 113 | rndtest_report(rsp, 0, "monobit pass (%d < %d < %d)", |
| 114 | RNDTEST_MONOBIT_MINONES, ones, |
| 115 | RNDTEST_MONOBIT_MAXONES); |
| 116 | return (0); |
| 117 | } else { |
| 118 | if (rndtest_verbose) |
| 119 | rndtest_report(rsp, 1, |
| 120 | "monobit failed (%d ones)", ones); |
| 121 | rndstats.rst_monobit++; |
| 122 | return (-1); |
| 123 | } |
| 124 | } |
| 125 | |
| 126 | #define RNDTEST_RUNS_NINTERVAL 6 |
| 127 | |
| 128 | static const struct rndtest_runs_tabs { |
| 129 | u_int16_t min, max; |
| 130 | } rndtest_runs_tab[] = { |
| 131 | { 2343, 2657 }, |
| 132 | { 1135, 1365 }, |
| 133 | { 542, 708 }, |
| 134 | { 251, 373 }, |
| 135 | { 111, 201 }, |
| 136 | { 111, 201 }, |
| 137 | }; |
| 138 | |
| 139 | static int |
| 140 | rndtest_runs(struct rndtest_state *rsp) |
| 141 | { |
| 142 | int i, j, ones, zeros, rv = 0; |
| 143 | int onei[RNDTEST_RUNS_NINTERVAL], zeroi[RNDTEST_RUNS_NINTERVAL]; |
| 144 | u_int8_t c; |
| 145 | |
| 146 | bzero(onei, sizeof(onei)); |
| 147 | bzero(zeroi, sizeof(zeroi)); |
| 148 | ones = zeros = 0; |
| 149 | for (i = 0; i < RNDTEST_NBYTES; i++) { |
| 150 | c = rsp->rs_buf[i]; |
| 151 | for (j = 0; j < 8; j++, c <<= 1) { |
| 152 | if (c & 0x80) { |
| 153 | ones++; |
| 154 | rndtest_runs_record(rsp, zeros, zeroi); |
| 155 | zeros = 0; |
| 156 | } else { |
| 157 | zeros++; |
| 158 | rndtest_runs_record(rsp, ones, onei); |
| 159 | ones = 0; |
| 160 | } |
| 161 | } |
| 162 | } |
| 163 | rndtest_runs_record(rsp, ones, onei); |
| 164 | rndtest_runs_record(rsp, zeros, zeroi); |
| 165 | |
| 166 | rv |= rndtest_runs_check(rsp, 0, zeroi); |
| 167 | rv |= rndtest_runs_check(rsp, 1, onei); |
| 168 | |
| 169 | if (rv) |
| 170 | rndstats.rst_runs++; |
| 171 | |
| 172 | return (rv); |
| 173 | } |
| 174 | |
| 175 | static void |
| 176 | rndtest_runs_record(struct rndtest_state *rsp, int len, int *intrv) |
| 177 | { |
| 178 | if (len == 0) |
| 179 | return; |
| 180 | if (len > RNDTEST_RUNS_NINTERVAL) |
| 181 | len = RNDTEST_RUNS_NINTERVAL; |
| 182 | len -= 1; |
| 183 | intrv[len]++; |
| 184 | } |
| 185 | |
| 186 | static int |
| 187 | rndtest_runs_check(struct rndtest_state *rsp, int val, int *src) |
| 188 | { |
| 189 | int i, rv = 0; |
| 190 | |
| 191 | for (i = 0; i < RNDTEST_RUNS_NINTERVAL; i++) { |
| 192 | if (src[i] < rndtest_runs_tab[i].min || |
| 193 | src[i] > rndtest_runs_tab[i].max) { |
| 194 | rndtest_report(rsp, 1, |
| 195 | "%s interval %d failed (%d, %d-%d)", |
| 196 | val ? "ones" : "zeros", |
| 197 | i + 1, src[i], rndtest_runs_tab[i].min, |
| 198 | rndtest_runs_tab[i].max); |
| 199 | rv = -1; |
| 200 | } else { |
| 201 | rndtest_report(rsp, 0, |
| 202 | "runs pass %s interval %d (%d < %d < %d)", |
| 203 | val ? "ones" : "zeros", |
| 204 | i + 1, rndtest_runs_tab[i].min, src[i], |
| 205 | rndtest_runs_tab[i].max); |
| 206 | } |
| 207 | } |
| 208 | return (rv); |
| 209 | } |
| 210 | |
| 211 | static int |
| 212 | rndtest_longruns(struct rndtest_state *rsp) |
| 213 | { |
| 214 | int i, j, ones = 0, zeros = 0, maxones = 0, maxzeros = 0; |
| 215 | u_int8_t c; |
| 216 | |
| 217 | for (i = 0; i < RNDTEST_NBYTES; i++) { |
| 218 | c = rsp->rs_buf[i]; |
| 219 | for (j = 0; j < 8; j++, c <<= 1) { |
| 220 | if (c & 0x80) { |
| 221 | zeros = 0; |
| 222 | ones++; |
| 223 | if (ones > maxones) |
| 224 | maxones = ones; |
| 225 | } else { |
| 226 | ones = 0; |
| 227 | zeros++; |
| 228 | if (zeros > maxzeros) |
| 229 | maxzeros = zeros; |
| 230 | } |
| 231 | } |
| 232 | } |
| 233 | |
| 234 | if (maxones < 26 && maxzeros < 26) { |
| 235 | rndtest_report(rsp, 0, "longruns pass (%d ones, %d zeros)", |
| 236 | maxones, maxzeros); |
| 237 | return (0); |
| 238 | } else { |
| 239 | rndtest_report(rsp, 1, "longruns fail (%d ones, %d zeros)", |
| 240 | maxones, maxzeros); |
| 241 | rndstats.rst_longruns++; |
| 242 | return (-1); |
| 243 | } |
| 244 | } |
| 245 | |
| 246 | /* |
| 247 | * chi^2 test over 4 bits: (this is called the poker test in FIPS 140-2, |
| 248 | * but it is really the chi^2 test over 4 bits (the poker test as described |
| 249 | * by Knuth vol 2 is something different, and I take him as authoritative |
| 250 | * on nomenclature over NIST). |
| 251 | */ |
| 252 | #define RNDTEST_CHI4_K 16 |
| 253 | #define RNDTEST_CHI4_K_MASK (RNDTEST_CHI4_K - 1) |
| 254 | |
| 255 | /* |
| 256 | * The unnormalized values are used so that we don't have to worry about |
| 257 | * fractional precision. The "real" value is found by: |
| 258 | * (V - 1562500) * (16 / 5000) = Vn (where V is the unnormalized value) |
| 259 | */ |
| 260 | #define RNDTEST_CHI4_VMIN 1563181 /* 2.1792 */ |
| 261 | #define RNDTEST_CHI4_VMAX 1576929 /* 46.1728 */ |
| 262 | |
| 263 | static int |
| 264 | rndtest_chi_4(struct rndtest_state *rsp) |
| 265 | { |
| 266 | unsigned int freq[RNDTEST_CHI4_K], i, sum; |
| 267 | |
| 268 | for (i = 0; i < RNDTEST_CHI4_K; i++) |
| 269 | freq[i] = 0; |
| 270 | |
| 271 | /* Get number of occurances of each 4 bit pattern */ |
| 272 | for (i = 0; i < RNDTEST_NBYTES; i++) { |
| 273 | freq[(rsp->rs_buf[i] >> 4) & RNDTEST_CHI4_K_MASK]++; |
| 274 | freq[(rsp->rs_buf[i] >> 0) & RNDTEST_CHI4_K_MASK]++; |
| 275 | } |
| 276 | |
| 277 | for (i = 0, sum = 0; i < RNDTEST_CHI4_K; i++) |
| 278 | sum += freq[i] * freq[i]; |
| 279 | |
| 280 | if (sum >= 1563181 && sum <= 1576929) { |
| 281 | rndtest_report(rsp, 0, "chi^2(4): pass (sum %u)", sum); |
| 282 | return (0); |
| 283 | } else { |
| 284 | rndtest_report(rsp, 1, "chi^2(4): failed (sum %u)", sum); |
| 285 | rndstats.rst_chi++; |
| 286 | return (-1); |
| 287 | } |
| 288 | } |
| 289 | |
| 290 | int |
| 291 | rndtest_buf(unsigned char *buf) |
| 292 | { |
| 293 | struct rndtest_state rsp; |
| 294 | |
| 295 | memset(&rsp, 0, sizeof(rsp)); |
| 296 | rsp.rs_buf = buf; |
| 297 | rndtest_test(&rsp); |
| 298 | return(rsp.rs_discard); |
| 299 | } |
| 300 | |
| 301 | |
