1 /* 2 * stats.c 3 * 4 * statistical tests for randomness (FIPS 140-2, Section 4.9) 5 * 6 * David A. McGrew 7 * Cisco Systems, Inc. 8 */ 9 /* 10 * 11 * Copyright (c) 2001-2006, Cisco Systems, Inc. 12 * All rights reserved. 13 * 14 * Redistribution and use in source and binary forms, with or without 15 * modification, are permitted provided that the following conditions 16 * are met: 17 * 18 * Redistributions of source code must retain the above copyright 19 * notice, this list of conditions and the following disclaimer. 20 * 21 * Redistributions in binary form must reproduce the above 22 * copyright notice, this list of conditions and the following 23 * disclaimer in the documentation and/or other materials provided 24 * with the distribution. 25 * 26 * Neither the name of the Cisco Systems, Inc. nor the names of its 27 * contributors may be used to endorse or promote products derived 28 * from this software without specific prior written permission. 29 * 30 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 31 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 32 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 33 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 34 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 35 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 36 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 37 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 38 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 39 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 40 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 41 * OF THE POSSIBILITY OF SUCH DAMAGE. 42 * 43 */ 44 45 #include "stat.h" 46 47 debug_module_t mod_stat = { 48 0, /* debugging is off by default */ 49 (char *)"stat test" /* printable module name */ 50 }; 51 52 /* 53 * each test assumes that 20,000 bits (2500 octets) of data is 54 * provided as input 55 */ 56 57 #define STAT_TEST_DATA_LEN 2500 58 59 err_status_t 60 stat_test_monobit(uint8_t *data) { 61 uint8_t *data_end = data + STAT_TEST_DATA_LEN; 62 uint16_t ones_count; 63 64 ones_count = 0; 65 while (data < data_end) { 66 ones_count += octet_get_weight(*data); 67 data++; 68 } 69 70 debug_print(mod_stat, "bit count: %d", ones_count); 71 72 if ((ones_count < 9725) || (ones_count > 10275)) 73 return err_status_algo_fail; 74 75 return err_status_ok; 76 } 77 78 err_status_t 79 stat_test_poker(uint8_t *data) { 80 int i; 81 uint8_t *data_end = data + STAT_TEST_DATA_LEN; 82 double poker; 83 uint16_t f[16] = { 84 0, 0, 0, 0, 0, 0, 0, 0, 85 0, 0, 0, 0, 0, 0, 0, 0 86 }; 87 88 while (data < data_end) { 89 f[*data & 0x0f]++; /* increment freq. count for low nibble */ 90 f[(*data) >> 4]++; /* increment freq. count for high nibble */ 91 data++; 92 } 93 94 poker = 0.0; 95 for (i=0; i < 16; i++) 96 poker += (double) f[i] * f[i]; 97 98 poker *= (16.0 / 5000.0); 99 poker -= 5000.0; 100 101 debug_print(mod_stat, "poker test: %f\n", poker); 102 103 if ((poker < 2.16) || (poker > 46.17)) 104 return err_status_algo_fail; 105 106 return err_status_ok; 107 } 108 109 110 /* 111 * runs[i] holds the number of runs of size (i-1) 112 */ 113 114 err_status_t 115 stat_test_runs(uint8_t *data) { 116 uint8_t *data_end = data + STAT_TEST_DATA_LEN; 117 uint16_t runs[6] = { 0, 0, 0, 0, 0, 0 }; 118 uint16_t gaps[6] = { 0, 0, 0, 0, 0, 0 }; 119 uint16_t lo_value[6] = { 2315, 1114, 527, 240, 103, 103 }; 120 uint16_t hi_value[6] = { 2685, 1386, 723, 384, 209, 209 }; 121 int state = 0; 122 uint16_t mask; 123 int i; 124 125 /* 126 * the state variable holds the number of bits in the 127 * current run (or gap, if negative) 128 */ 129 130 while (data < data_end) { 131 132 /* loop over the bits of this byte */ 133 for (mask = 1; mask < 256; mask <<= 1) { 134 if (*data & mask) { 135 136 /* next bit is a one */ 137 if (state > 0) { 138 139 /* prefix is a run, so increment the run-count */ 140 state++; 141 142 /* check for long runs */ 143 if (state > 25) { 144 debug_print(mod_stat, ">25 runs: %d", state); 145 return err_status_algo_fail; 146 } 147 148 } else if (state < 0) { 149 150 /* prefix is a gap */ 151 if (state < -25) { 152 debug_print(mod_stat, ">25 gaps: %d", state); 153 return err_status_algo_fail; /* long-runs test failed */ 154 } 155 if (state < -6) { 156 state = -6; /* group together gaps > 5 */ 157 } 158 gaps[-1-state]++; /* increment gap count */ 159 state = 1; /* set state at one set bit */ 160 } else { 161 162 /* state is zero; this happens only at initialization */ 163 state = 1; 164 } 165 } else { 166 167 /* next bit is a zero */ 168 if (state > 0) { 169 170 /* prefix is a run */ 171 if (state > 25) { 172 debug_print(mod_stat, ">25 runs (2): %d", state); 173 return err_status_algo_fail; /* long-runs test failed */ 174 } 175 if (state > 6) { 176 state = 6; /* group together runs > 5 */ 177 } 178 runs[state-1]++; /* increment run count */ 179 state = -1; /* set state at one zero bit */ 180 } else if (state < 0) { 181 182 /* prefix is a gap, so increment gap-count (decrement state) */ 183 state--; 184 185 /* check for long gaps */ 186 if (state < -25) { 187 debug_print(mod_stat, ">25 gaps (2): %d", state); 188 return err_status_algo_fail; 189 } 190 191 } else { 192 193 /* state is zero; this happens only at initialization */ 194 state = -1; 195 } 196 } 197 } 198 199 /* move along to next octet */ 200 data++; 201 } 202 203 if (mod_stat.on) { 204 debug_print(mod_stat, "runs test", NULL); 205 for (i=0; i < 6; i++) 206 debug_print(mod_stat, " runs[]: %d", runs[i]); 207 for (i=0; i < 6; i++) 208 debug_print(mod_stat, " gaps[]: %d", gaps[i]); 209 } 210 211 /* check run and gap counts against the fixed limits */ 212 for (i=0; i < 6; i++) 213 if ( (runs[i] < lo_value[i] ) || (runs[i] > hi_value[i]) 214 || (gaps[i] < lo_value[i] ) || (gaps[i] > hi_value[i])) 215 return err_status_algo_fail; 216 217 218 return err_status_ok; 219 } 220 221 222 /* 223 * the function stat_test_rand_source applys the FIPS-140-2 statistical 224 * tests to the random source defined by rs 225 * 226 */ 227 228 #define RAND_SRC_BUF_OCTETS 50 /* this value MUST divide 2500! */ 229 230 err_status_t 231 stat_test_rand_source(rand_source_func_t get_rand_bytes) { 232 int i; 233 double poker; 234 uint8_t *data, *data_end; 235 uint16_t f[16] = { 236 0, 0, 0, 0, 0, 0, 0, 0, 237 0, 0, 0, 0, 0, 0, 0, 0 238 }; 239 uint8_t buffer[RAND_SRC_BUF_OCTETS]; 240 err_status_t status; 241 int ones_count = 0; 242 uint16_t runs[6] = { 0, 0, 0, 0, 0, 0 }; 243 uint16_t gaps[6] = { 0, 0, 0, 0, 0, 0 }; 244 uint16_t lo_value[6] = { 2315, 1114, 527, 240, 103, 103 }; 245 uint16_t hi_value[6] = { 2685, 1386, 723, 384, 209, 209 }; 246 int state = 0; 247 uint16_t mask; 248 249 /* counters for monobit, poker, and runs tests are initialized above */ 250 251 /* main loop: fill buffer, update counters for stat tests */ 252 for (i=0; i < 2500; i+=RAND_SRC_BUF_OCTETS) { 253 254 /* fill data buffer */ 255 status = get_rand_bytes(buffer, RAND_SRC_BUF_OCTETS); 256 if (status) { 257 debug_print(mod_stat, "couldn't get rand bytes: %d",status); 258 return status; 259 } 260 261 #if 0 262 debug_print(mod_stat, "%s", 263 octet_string_hex_string(buffer, RAND_SRC_BUF_OCTETS)); 264 #endif 265 266 data = buffer; 267 data_end = data + RAND_SRC_BUF_OCTETS; 268 while (data < data_end) { 269 270 /* update monobit test counter */ 271 ones_count += octet_get_weight(*data); 272 273 /* update poker test counters */ 274 f[*data & 0x0f]++; /* increment freq. count for low nibble */ 275 f[(*data) >> 4]++; /* increment freq. count for high nibble */ 276 277 /* update runs test counters */ 278 /* loop over the bits of this byte */ 279 for (mask = 1; mask < 256; mask <<= 1) { 280 if (*data & mask) { 281 282 /* next bit is a one */ 283 if (state > 0) { 284 285 /* prefix is a run, so increment the run-count */ 286 state++; 287 288 /* check for long runs */ 289 if (state > 25) { 290 debug_print(mod_stat, ">25 runs (3): %d", state); 291 return err_status_algo_fail; 292 } 293 294 } else if (state < 0) { 295 296 /* prefix is a gap */ 297 if (state < -25) { 298 debug_print(mod_stat, ">25 gaps (3): %d", state); 299 return err_status_algo_fail; /* long-runs test failed */ 300 } 301 if (state < -6) { 302 state = -6; /* group together gaps > 5 */ 303 } 304 gaps[-1-state]++; /* increment gap count */ 305 state = 1; /* set state at one set bit */ 306 } else { 307 308 /* state is zero; this happens only at initialization */ 309 state = 1; 310 } 311 } else { 312 313 /* next bit is a zero */ 314 if (state > 0) { 315 316 /* prefix is a run */ 317 if (state > 25) { 318 debug_print(mod_stat, ">25 runs (4): %d", state); 319 return err_status_algo_fail; /* long-runs test failed */ 320 } 321 if (state > 6) { 322 state = 6; /* group together runs > 5 */ 323 } 324 runs[state-1]++; /* increment run count */ 325 state = -1; /* set state at one zero bit */ 326 } else if (state < 0) { 327 328 /* prefix is a gap, so increment gap-count (decrement state) */ 329 state--; 330 331 /* check for long gaps */ 332 if (state < -25) { 333 debug_print(mod_stat, ">25 gaps (4): %d", state); 334 return err_status_algo_fail; 335 } 336 337 } else { 338 339 /* state is zero; this happens only at initialization */ 340 state = -1; 341 } 342 } 343 } 344 345 /* advance data pointer */ 346 data++; 347 } 348 } 349 350 /* check to see if test data is within bounds */ 351 352 /* check monobit test data */ 353 354 debug_print(mod_stat, "stat: bit count: %d", ones_count); 355 356 if ((ones_count < 9725) || (ones_count > 10275)) { 357 debug_print(mod_stat, "stat: failed monobit test %d", ones_count); 358 return err_status_algo_fail; 359 } 360 361 /* check poker test data */ 362 poker = 0.0; 363 for (i=0; i < 16; i++) 364 poker += (double) f[i] * f[i]; 365 366 poker *= (16.0 / 5000.0); 367 poker -= 5000.0; 368 369 debug_print(mod_stat, "stat: poker test: %f", poker); 370 371 if ((poker < 2.16) || (poker > 46.17)) { 372 debug_print(mod_stat, "stat: failed poker test", NULL); 373 return err_status_algo_fail; 374 } 375 376 /* check run and gap counts against the fixed limits */ 377 for (i=0; i < 6; i++) 378 if ((runs[i] < lo_value[i] ) || (runs[i] > hi_value[i]) 379 || (gaps[i] < lo_value[i] ) || (gaps[i] > hi_value[i])) { 380 debug_print(mod_stat, "stat: failed run/gap test", NULL); 381 return err_status_algo_fail; 382 } 383 384 debug_print(mod_stat, "passed random stat test", NULL); 385 return err_status_ok; 386 } 387 388 err_status_t 389 stat_test_rand_source_with_repetition(rand_source_func_t source, unsigned num_trials) { 390 unsigned int i; 391 err_status_t err = err_status_algo_fail; 392 393 for (i=0; i < num_trials; i++) { 394 err = stat_test_rand_source(source); 395 if (err == err_status_ok) { 396 return err_status_ok; 397 } 398 debug_print(mod_stat, "failed stat test (try number %d)\n", i); 399 } 400 401 return err; 402 } 403
