1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/netwerk/srtp/src/crypto/math/stat.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,402 @@
1.4 +/*
1.5 + * stats.c
1.6 + *
1.7 + * statistical tests for randomness (FIPS 140-2, Section 4.9)
1.8 + *
1.9 + * David A. McGrew
1.10 + * Cisco Systems, Inc.
1.11 + */
1.12 +/*
1.13 + *
1.14 + * Copyright (c) 2001-2006, Cisco Systems, Inc.
1.15 + * All rights reserved.
1.16 + *
1.17 + * Redistribution and use in source and binary forms, with or without
1.18 + * modification, are permitted provided that the following conditions
1.19 + * are met:
1.20 + *
1.21 + * Redistributions of source code must retain the above copyright
1.22 + * notice, this list of conditions and the following disclaimer.
1.23 + *
1.24 + * Redistributions in binary form must reproduce the above
1.25 + * copyright notice, this list of conditions and the following
1.26 + * disclaimer in the documentation and/or other materials provided
1.27 + * with the distribution.
1.28 + *
1.29 + * Neither the name of the Cisco Systems, Inc. nor the names of its
1.30 + * contributors may be used to endorse or promote products derived
1.31 + * from this software without specific prior written permission.
1.32 + *
1.33 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1.34 + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1.35 + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
1.36 + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
1.37 + * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
1.38 + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
1.39 + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
1.40 + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
1.41 + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
1.42 + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
1.43 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
1.44 + * OF THE POSSIBILITY OF SUCH DAMAGE.
1.45 + *
1.46 + */
1.47 +
1.48 +#include "stat.h"
1.49 +
1.50 +debug_module_t mod_stat = {
1.51 + 0, /* debugging is off by default */
1.52 + (char *)"stat test" /* printable module name */
1.53 +};
1.54 +
1.55 +/*
1.56 + * each test assumes that 20,000 bits (2500 octets) of data is
1.57 + * provided as input
1.58 + */
1.59 +
1.60 +#define STAT_TEST_DATA_LEN 2500
1.61 +
1.62 +err_status_t
1.63 +stat_test_monobit(uint8_t *data) {
1.64 + uint8_t *data_end = data + STAT_TEST_DATA_LEN;
1.65 + uint16_t ones_count;
1.66 +
1.67 + ones_count = 0;
1.68 + while (data < data_end) {
1.69 + ones_count += octet_get_weight(*data);
1.70 + data++;
1.71 + }
1.72 +
1.73 + debug_print(mod_stat, "bit count: %d", ones_count);
1.74 +
1.75 + if ((ones_count < 9725) || (ones_count > 10275))
1.76 + return err_status_algo_fail;
1.77 +
1.78 + return err_status_ok;
1.79 +}
1.80 +
1.81 +err_status_t
1.82 +stat_test_poker(uint8_t *data) {
1.83 + int i;
1.84 + uint8_t *data_end = data + STAT_TEST_DATA_LEN;
1.85 + double poker;
1.86 + uint16_t f[16] = {
1.87 + 0, 0, 0, 0, 0, 0, 0, 0,
1.88 + 0, 0, 0, 0, 0, 0, 0, 0
1.89 + };
1.90 +
1.91 + while (data < data_end) {
1.92 + f[*data & 0x0f]++; /* increment freq. count for low nibble */
1.93 + f[(*data) >> 4]++; /* increment freq. count for high nibble */
1.94 + data++;
1.95 + }
1.96 +
1.97 + poker = 0.0;
1.98 + for (i=0; i < 16; i++)
1.99 + poker += (double) f[i] * f[i];
1.100 +
1.101 + poker *= (16.0 / 5000.0);
1.102 + poker -= 5000.0;
1.103 +
1.104 + debug_print(mod_stat, "poker test: %f\n", poker);
1.105 +
1.106 + if ((poker < 2.16) || (poker > 46.17))
1.107 + return err_status_algo_fail;
1.108 +
1.109 + return err_status_ok;
1.110 +}
1.111 +
1.112 +
1.113 +/*
1.114 + * runs[i] holds the number of runs of size (i-1)
1.115 + */
1.116 +
1.117 +err_status_t
1.118 +stat_test_runs(uint8_t *data) {
1.119 + uint8_t *data_end = data + STAT_TEST_DATA_LEN;
1.120 + uint16_t runs[6] = { 0, 0, 0, 0, 0, 0 };
1.121 + uint16_t gaps[6] = { 0, 0, 0, 0, 0, 0 };
1.122 + uint16_t lo_value[6] = { 2315, 1114, 527, 240, 103, 103 };
1.123 + uint16_t hi_value[6] = { 2685, 1386, 723, 384, 209, 209 };
1.124 + int state = 0;
1.125 + uint16_t mask;
1.126 + int i;
1.127 +
1.128 + /*
1.129 + * the state variable holds the number of bits in the
1.130 + * current run (or gap, if negative)
1.131 + */
1.132 +
1.133 + while (data < data_end) {
1.134 +
1.135 + /* loop over the bits of this byte */
1.136 + for (mask = 1; mask < 256; mask <<= 1) {
1.137 + if (*data & mask) {
1.138 +
1.139 + /* next bit is a one */
1.140 + if (state > 0) {
1.141 +
1.142 + /* prefix is a run, so increment the run-count */
1.143 + state++;
1.144 +
1.145 + /* check for long runs */
1.146 + if (state > 25) {
1.147 + debug_print(mod_stat, ">25 runs: %d", state);
1.148 + return err_status_algo_fail;
1.149 + }
1.150 +
1.151 + } else if (state < 0) {
1.152 +
1.153 + /* prefix is a gap */
1.154 + if (state < -25) {
1.155 + debug_print(mod_stat, ">25 gaps: %d", state);
1.156 + return err_status_algo_fail; /* long-runs test failed */
1.157 + }
1.158 + if (state < -6) {
1.159 + state = -6; /* group together gaps > 5 */
1.160 + }
1.161 + gaps[-1-state]++; /* increment gap count */
1.162 + state = 1; /* set state at one set bit */
1.163 + } else {
1.164 +
1.165 + /* state is zero; this happens only at initialization */
1.166 + state = 1;
1.167 + }
1.168 + } else {
1.169 +
1.170 + /* next bit is a zero */
1.171 + if (state > 0) {
1.172 +
1.173 + /* prefix is a run */
1.174 + if (state > 25) {
1.175 + debug_print(mod_stat, ">25 runs (2): %d", state);
1.176 + return err_status_algo_fail; /* long-runs test failed */
1.177 + }
1.178 + if (state > 6) {
1.179 + state = 6; /* group together runs > 5 */
1.180 + }
1.181 + runs[state-1]++; /* increment run count */
1.182 + state = -1; /* set state at one zero bit */
1.183 + } else if (state < 0) {
1.184 +
1.185 + /* prefix is a gap, so increment gap-count (decrement state) */
1.186 + state--;
1.187 +
1.188 + /* check for long gaps */
1.189 + if (state < -25) {
1.190 + debug_print(mod_stat, ">25 gaps (2): %d", state);
1.191 + return err_status_algo_fail;
1.192 + }
1.193 +
1.194 + } else {
1.195 +
1.196 + /* state is zero; this happens only at initialization */
1.197 + state = -1;
1.198 + }
1.199 + }
1.200 + }
1.201 +
1.202 + /* move along to next octet */
1.203 + data++;
1.204 + }
1.205 +
1.206 + if (mod_stat.on) {
1.207 + debug_print(mod_stat, "runs test", NULL);
1.208 + for (i=0; i < 6; i++)
1.209 + debug_print(mod_stat, " runs[]: %d", runs[i]);
1.210 + for (i=0; i < 6; i++)
1.211 + debug_print(mod_stat, " gaps[]: %d", gaps[i]);
1.212 + }
1.213 +
1.214 + /* check run and gap counts against the fixed limits */
1.215 + for (i=0; i < 6; i++)
1.216 + if ( (runs[i] < lo_value[i] ) || (runs[i] > hi_value[i])
1.217 + || (gaps[i] < lo_value[i] ) || (gaps[i] > hi_value[i]))
1.218 + return err_status_algo_fail;
1.219 +
1.220 +
1.221 + return err_status_ok;
1.222 +}
1.223 +
1.224 +
1.225 +/*
1.226 + * the function stat_test_rand_source applys the FIPS-140-2 statistical
1.227 + * tests to the random source defined by rs
1.228 + *
1.229 + */
1.230 +
1.231 +#define RAND_SRC_BUF_OCTETS 50 /* this value MUST divide 2500! */
1.232 +
1.233 +err_status_t
1.234 +stat_test_rand_source(rand_source_func_t get_rand_bytes) {
1.235 + int i;
1.236 + double poker;
1.237 + uint8_t *data, *data_end;
1.238 + uint16_t f[16] = {
1.239 + 0, 0, 0, 0, 0, 0, 0, 0,
1.240 + 0, 0, 0, 0, 0, 0, 0, 0
1.241 + };
1.242 + uint8_t buffer[RAND_SRC_BUF_OCTETS];
1.243 + err_status_t status;
1.244 + int ones_count = 0;
1.245 + uint16_t runs[6] = { 0, 0, 0, 0, 0, 0 };
1.246 + uint16_t gaps[6] = { 0, 0, 0, 0, 0, 0 };
1.247 + uint16_t lo_value[6] = { 2315, 1114, 527, 240, 103, 103 };
1.248 + uint16_t hi_value[6] = { 2685, 1386, 723, 384, 209, 209 };
1.249 + int state = 0;
1.250 + uint16_t mask;
1.251 +
1.252 + /* counters for monobit, poker, and runs tests are initialized above */
1.253 +
1.254 + /* main loop: fill buffer, update counters for stat tests */
1.255 + for (i=0; i < 2500; i+=RAND_SRC_BUF_OCTETS) {
1.256 +
1.257 + /* fill data buffer */
1.258 + status = get_rand_bytes(buffer, RAND_SRC_BUF_OCTETS);
1.259 + if (status) {
1.260 + debug_print(mod_stat, "couldn't get rand bytes: %d",status);
1.261 + return status;
1.262 + }
1.263 +
1.264 +#if 0
1.265 + debug_print(mod_stat, "%s",
1.266 + octet_string_hex_string(buffer, RAND_SRC_BUF_OCTETS));
1.267 +#endif
1.268 +
1.269 + data = buffer;
1.270 + data_end = data + RAND_SRC_BUF_OCTETS;
1.271 + while (data < data_end) {
1.272 +
1.273 + /* update monobit test counter */
1.274 + ones_count += octet_get_weight(*data);
1.275 +
1.276 + /* update poker test counters */
1.277 + f[*data & 0x0f]++; /* increment freq. count for low nibble */
1.278 + f[(*data) >> 4]++; /* increment freq. count for high nibble */
1.279 +
1.280 + /* update runs test counters */
1.281 + /* loop over the bits of this byte */
1.282 + for (mask = 1; mask < 256; mask <<= 1) {
1.283 + if (*data & mask) {
1.284 +
1.285 + /* next bit is a one */
1.286 + if (state > 0) {
1.287 +
1.288 + /* prefix is a run, so increment the run-count */
1.289 + state++;
1.290 +
1.291 + /* check for long runs */
1.292 + if (state > 25) {
1.293 + debug_print(mod_stat, ">25 runs (3): %d", state);
1.294 + return err_status_algo_fail;
1.295 + }
1.296 +
1.297 + } else if (state < 0) {
1.298 +
1.299 + /* prefix is a gap */
1.300 + if (state < -25) {
1.301 + debug_print(mod_stat, ">25 gaps (3): %d", state);
1.302 + return err_status_algo_fail; /* long-runs test failed */
1.303 + }
1.304 + if (state < -6) {
1.305 + state = -6; /* group together gaps > 5 */
1.306 + }
1.307 + gaps[-1-state]++; /* increment gap count */
1.308 + state = 1; /* set state at one set bit */
1.309 + } else {
1.310 +
1.311 + /* state is zero; this happens only at initialization */
1.312 + state = 1;
1.313 + }
1.314 + } else {
1.315 +
1.316 + /* next bit is a zero */
1.317 + if (state > 0) {
1.318 +
1.319 + /* prefix is a run */
1.320 + if (state > 25) {
1.321 + debug_print(mod_stat, ">25 runs (4): %d", state);
1.322 + return err_status_algo_fail; /* long-runs test failed */
1.323 + }
1.324 + if (state > 6) {
1.325 + state = 6; /* group together runs > 5 */
1.326 + }
1.327 + runs[state-1]++; /* increment run count */
1.328 + state = -1; /* set state at one zero bit */
1.329 + } else if (state < 0) {
1.330 +
1.331 + /* prefix is a gap, so increment gap-count (decrement state) */
1.332 + state--;
1.333 +
1.334 + /* check for long gaps */
1.335 + if (state < -25) {
1.336 + debug_print(mod_stat, ">25 gaps (4): %d", state);
1.337 + return err_status_algo_fail;
1.338 + }
1.339 +
1.340 + } else {
1.341 +
1.342 + /* state is zero; this happens only at initialization */
1.343 + state = -1;
1.344 + }
1.345 + }
1.346 + }
1.347 +
1.348 + /* advance data pointer */
1.349 + data++;
1.350 + }
1.351 + }
1.352 +
1.353 + /* check to see if test data is within bounds */
1.354 +
1.355 + /* check monobit test data */
1.356 +
1.357 + debug_print(mod_stat, "stat: bit count: %d", ones_count);
1.358 +
1.359 + if ((ones_count < 9725) || (ones_count > 10275)) {
1.360 + debug_print(mod_stat, "stat: failed monobit test %d", ones_count);
1.361 + return err_status_algo_fail;
1.362 + }
1.363 +
1.364 + /* check poker test data */
1.365 + poker = 0.0;
1.366 + for (i=0; i < 16; i++)
1.367 + poker += (double) f[i] * f[i];
1.368 +
1.369 + poker *= (16.0 / 5000.0);
1.370 + poker -= 5000.0;
1.371 +
1.372 + debug_print(mod_stat, "stat: poker test: %f", poker);
1.373 +
1.374 + if ((poker < 2.16) || (poker > 46.17)) {
1.375 + debug_print(mod_stat, "stat: failed poker test", NULL);
1.376 + return err_status_algo_fail;
1.377 + }
1.378 +
1.379 + /* check run and gap counts against the fixed limits */
1.380 + for (i=0; i < 6; i++)
1.381 + if ((runs[i] < lo_value[i] ) || (runs[i] > hi_value[i])
1.382 + || (gaps[i] < lo_value[i] ) || (gaps[i] > hi_value[i])) {
1.383 + debug_print(mod_stat, "stat: failed run/gap test", NULL);
1.384 + return err_status_algo_fail;
1.385 + }
1.386 +
1.387 + debug_print(mod_stat, "passed random stat test", NULL);
1.388 + return err_status_ok;
1.389 +}
1.390 +
1.391 +err_status_t
1.392 +stat_test_rand_source_with_repetition(rand_source_func_t source, unsigned num_trials) {
1.393 + unsigned int i;
1.394 + err_status_t err = err_status_algo_fail;
1.395 +
1.396 + for (i=0; i < num_trials; i++) {
1.397 + err = stat_test_rand_source(source);
1.398 + if (err == err_status_ok) {
1.399 + return err_status_ok;
1.400 + }
1.401 + debug_print(mod_stat, "failed stat test (try number %d)\n", i);
1.402 + }
1.403 +
1.404 + return err;
1.405 +}
