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 #include "stat.h" 11 12 debug_module_t mod_stat = { 13 0, /* debugging is off by default */ 14 (char *)"stat test" /* printable module name */ 15 }; 16 17 /* 18 * each test assumes that 20,000 bits (2500 octets) of data is 19 * provided as input 20 */ 21 22 #define STAT_TEST_DATA_LEN 2500 23 24 err_status_t 25 stat_test_monobit(uint8_t *data) { 26 uint8_t *data_end = data + STAT_TEST_DATA_LEN; 27 uint16_t ones_count; 28 29 ones_count = 0; 30 while (data < data_end) { 31 ones_count += octet_get_weight(*data); 32 data++; 33 } 34 35 debug_print(mod_stat, "bit count: %d", ones_count); 36 37 if ((ones_count < 9725) || (ones_count > 10275)) 38 return err_status_algo_fail; 39 40 return err_status_ok; 41 } 42 43 err_status_t 44 stat_test_poker(uint8_t *data) { 45 int i; 46 uint8_t *data_end = data + STAT_TEST_DATA_LEN; 47 double poker; 48 uint16_t f[16] = { 49 0, 0, 0, 0, 0, 0, 0, 0, 50 0, 0, 0, 0, 0, 0, 0, 0 51 }; 52 53 while (data < data_end) { 54 f[*data & 0x0f]++; /* increment freq. count for low nibble */ 55 f[(*data) >> 4]++; /* increment freq. count for high nibble */ 56 data++; 57 } 58 59 poker = 0.0; 60 for (i=0; i < 16; i++) 61 poker += (double) f[i] * f[i]; 62 63 poker *= (16.0 / 5000.0); 64 poker -= 5000.0; 65 66 debug_print(mod_stat, "poker test: %f\n", poker); 67 68 if ((poker < 2.16) || (poker > 46.17)) 69 return err_status_algo_fail; 70 71 return err_status_ok; 72 } 73 74 75 /* 76 * runs[i] holds the number of runs of size (i-1) 77 */ 78 79 err_status_t 80 stat_test_runs(uint8_t *data) { 81 uint8_t *data_end = data + STAT_TEST_DATA_LEN; 82 uint16_t runs[6] = { 0, 0, 0, 0, 0, 0 }; 83 uint16_t gaps[6] = { 0, 0, 0, 0, 0, 0 }; 84 uint16_t lo_value[6] = { 2315, 1114, 527, 240, 103, 103 }; 85 uint16_t hi_value[6] = { 2685, 1386, 723, 384, 209, 209 }; 86 int state = 0; 87 uint16_t mask; 88 int i; 89 90 /* 91 * the state variable holds the number of bits in the 92 * current run (or gap, if negative) 93 */ 94 95 while (data < data_end) { 96 97 /* loop over the bits of this byte */ 98 for (mask = 1; mask < 256; mask <<= 1) { 99 if (*data & mask) { 100 101 /* next bit is a one */ 102 if (state > 0) { 103 104 /* prefix is a run, so increment the run-count */ 105 state++; 106 107 /* check for long runs */ 108 if (state > 25) { 109 debug_print(mod_stat, ">25 runs: %d", state); 110 return err_status_algo_fail; 111 } 112 113 } else if (state < 0) { 114 115 /* prefix is a gap */ 116 if (state < -25) { 117 debug_print(mod_stat, ">25 gaps: %d", state); 118 return err_status_algo_fail; /* long-runs test failed */ 119 } 120 if (state < -6) { 121 state = -6; /* group together gaps > 5 */ 122 } 123 gaps[-1-state]++; /* increment gap count */ 124 state = 1; /* set state at one set bit */ 125 } else { 126 127 /* state is zero; this happens only at initialization */ 128 state = 1; 129 } 130 } else { 131 132 /* next bit is a zero */ 133 if (state > 0) { 134 135 /* prefix is a run */ 136 if (state > 25) { 137 debug_print(mod_stat, ">25 runs (2): %d", state); 138 return err_status_algo_fail; /* long-runs test failed */ 139 } 140 if (state > 6) { 141 state = 6; /* group together runs > 5 */ 142 } 143 runs[state-1]++; /* increment run count */ 144 state = -1; /* set state at one zero bit */ 145 } else if (state < 0) { 146 147 /* prefix is a gap, so increment gap-count (decrement state) */ 148 state--; 149 150 /* check for long gaps */ 151 if (state < -25) { 152 debug_print(mod_stat, ">25 gaps (2): %d", state); 153 return err_status_algo_fail; 154 } 155 156 } else { 157 158 /* state is zero; this happens only at initialization */ 159 state = -1; 160 } 161 } 162 } 163 164 /* move along to next octet */ 165 data++; 166 } 167 168 if (mod_stat.on) { 169 debug_print(mod_stat, "runs test", NULL); 170 for (i=0; i < 6; i++) 171 debug_print(mod_stat, " runs[]: %d", runs[i]); 172 for (i=0; i < 6; i++) 173 debug_print(mod_stat, " gaps[]: %d", gaps[i]); 174 } 175 176 /* check run and gap counts against the fixed limits */ 177 for (i=0; i < 6; i++) 178 if ( (runs[i] < lo_value[i] ) || (runs[i] > hi_value[i]) 179 || (gaps[i] < lo_value[i] ) || (gaps[i] > hi_value[i])) 180 return err_status_algo_fail; 181 182 183 return err_status_ok; 184 } 185 186 187 /* 188 * the function stat_test_rand_source applys the FIPS-140-2 statistical 189 * tests to the random source defined by rs 190 * 191 */ 192 193 #define RAND_SRC_BUF_OCTETS 50 /* this value MUST divide 2500! */ 194 195 err_status_t 196 stat_test_rand_source(rand_source_func_t get_rand_bytes) { 197 int i; 198 double poker; 199 uint8_t *data, *data_end; 200 uint16_t f[16] = { 201 0, 0, 0, 0, 0, 0, 0, 0, 202 0, 0, 0, 0, 0, 0, 0, 0 203 }; 204 uint8_t buffer[RAND_SRC_BUF_OCTETS]; 205 err_status_t status; 206 int ones_count = 0; 207 uint16_t runs[6] = { 0, 0, 0, 0, 0, 0 }; 208 uint16_t gaps[6] = { 0, 0, 0, 0, 0, 0 }; 209 uint16_t lo_value[6] = { 2315, 1114, 527, 240, 103, 103 }; 210 uint16_t hi_value[6] = { 2685, 1386, 723, 384, 209, 209 }; 211 int state = 0; 212 uint16_t mask; 213 214 /* counters for monobit, poker, and runs tests are initialized above */ 215 216 /* main loop: fill buffer, update counters for stat tests */ 217 for (i=0; i < 2500; i+=RAND_SRC_BUF_OCTETS) { 218 219 /* fill data buffer */ 220 status = get_rand_bytes(buffer, RAND_SRC_BUF_OCTETS); 221 if (status) { 222 debug_print(mod_stat, "couldn't get rand bytes: %d",status); 223 return status; 224 } 225 226 #if 0 227 debug_print(mod_stat, "%s", 228 octet_string_hex_string(buffer, RAND_SRC_BUF_OCTETS)); 229 #endif 230 231 data = buffer; 232 data_end = data + RAND_SRC_BUF_OCTETS; 233 while (data < data_end) { 234 235 /* update monobit test counter */ 236 ones_count += octet_get_weight(*data); 237 238 /* update poker test counters */ 239 f[*data & 0x0f]++; /* increment freq. count for low nibble */ 240 f[(*data) >> 4]++; /* increment freq. count for high nibble */ 241 242 /* update runs test counters */ 243 /* loop over the bits of this byte */ 244 for (mask = 1; mask < 256; mask <<= 1) { 245 if (*data & mask) { 246 247 /* next bit is a one */ 248 if (state > 0) { 249 250 /* prefix is a run, so increment the run-count */ 251 state++; 252 253 /* check for long runs */ 254 if (state > 25) { 255 debug_print(mod_stat, ">25 runs (3): %d", state); 256 return err_status_algo_fail; 257 } 258 259 } else if (state < 0) { 260 261 /* prefix is a gap */ 262 if (state < -25) { 263 debug_print(mod_stat, ">25 gaps (3): %d", state); 264 return err_status_algo_fail; /* long-runs test failed */ 265 } 266 if (state < -6) { 267 state = -6; /* group together gaps > 5 */ 268 } 269 gaps[-1-state]++; /* increment gap count */ 270 state = 1; /* set state at one set bit */ 271 } else { 272 273 /* state is zero; this happens only at initialization */ 274 state = 1; 275 } 276 } else { 277 278 /* next bit is a zero */ 279 if (state > 0) { 280 281 /* prefix is a run */ 282 if (state > 25) { 283 debug_print(mod_stat, ">25 runs (4): %d", state); 284 return err_status_algo_fail; /* long-runs test failed */ 285 } 286 if (state > 6) { 287 state = 6; /* group together runs > 5 */ 288 } 289 runs[state-1]++; /* increment run count */ 290 state = -1; /* set state at one zero bit */ 291 } else if (state < 0) { 292 293 /* prefix is a gap, so increment gap-count (decrement state) */ 294 state--; 295 296 /* check for long gaps */ 297 if (state < -25) { 298 debug_print(mod_stat, ">25 gaps (4): %d", state); 299 return err_status_algo_fail; 300 } 301 302 } else { 303 304 /* state is zero; this happens only at initialization */ 305 state = -1; 306 } 307 } 308 } 309 310 /* advance data pointer */ 311 data++; 312 } 313 } 314 315 /* check to see if test data is within bounds */ 316 317 /* check monobit test data */ 318 319 debug_print(mod_stat, "stat: bit count: %d", ones_count); 320 321 if ((ones_count < 9725) || (ones_count > 10275)) { 322 debug_print(mod_stat, "stat: failed monobit test %d", ones_count); 323 return err_status_algo_fail; 324 } 325 326 /* check poker test data */ 327 poker = 0.0; 328 for (i=0; i < 16; i++) 329 poker += (double) f[i] * f[i]; 330 331 poker *= (16.0 / 5000.0); 332 poker -= 5000.0; 333 334 debug_print(mod_stat, "stat: poker test: %f", poker); 335 336 if ((poker < 2.16) || (poker > 46.17)) { 337 debug_print(mod_stat, "stat: failed poker test", NULL); 338 return err_status_algo_fail; 339 } 340 341 /* check run and gap counts against the fixed limits */ 342 for (i=0; i < 6; i++) 343 if ((runs[i] < lo_value[i] ) || (runs[i] > hi_value[i]) 344 || (gaps[i] < lo_value[i] ) || (gaps[i] > hi_value[i])) { 345 debug_print(mod_stat, "stat: failed run/gap test", NULL); 346 return err_status_algo_fail; 347 } 348 349 debug_print(mod_stat, "passed random stat test", NULL); 350 return err_status_ok; 351 } 352 353 err_status_t 354 stat_test_rand_source_with_repetition(rand_source_func_t source, unsigned num_trials) { 355 unsigned int i; 356 err_status_t err = err_status_algo_fail; 357 358 for (i=0; i < num_trials; i++) { 359 err = stat_test_rand_source(source); 360 if (err == err_status_ok) { 361 return err_status_ok; 362 } 363 debug_print(mod_stat, "failed stat test (try number %d)\n", i); 364 } 365 366 return err; 367 } 368
