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