netwerk/srtp/src/crypto/math/stat.c@6474c204b198
netwerk/srtp/src/crypto/math/stat.c
Wed, 31 Dec 2014 06:09:35 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Wed, 31 Dec 2014 06:09:35 +0100
- changeset 0
- 6474c204b198
- permissions
- -rw-r--r--
Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.
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 */
45 #include "stat.h"
47 debug_module_t mod_stat = {
48 0, /* debugging is off by default */
49 (char *)"stat test" /* printable module name */
50 };
52 /*
53 * each test assumes that 20,000 bits (2500 octets) of data is
54 * provided as input
55 */
57 #define STAT_TEST_DATA_LEN 2500
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;
64 ones_count = 0;
65 while (data < data_end) {
66 ones_count += octet_get_weight(*data);
67 data++;
68 }
70 debug_print(mod_stat, "bit count: %d", ones_count);
72 if ((ones_count < 9725) || (ones_count > 10275))
73 return err_status_algo_fail;
75 return err_status_ok;
76 }
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 };
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 }
94 poker = 0.0;
95 for (i=0; i < 16; i++)
96 poker += (double) f[i] * f[i];
98 poker *= (16.0 / 5000.0);
99 poker -= 5000.0;
101 debug_print(mod_stat, "poker test: %f\n", poker);
103 if ((poker < 2.16) || (poker > 46.17))
104 return err_status_algo_fail;
106 return err_status_ok;
107 }
110 /*
111 * runs[i] holds the number of runs of size (i-1)
112 */
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;
125 /*
126 * the state variable holds the number of bits in the
127 * current run (or gap, if negative)
128 */
130 while (data < data_end) {
132 /* loop over the bits of this byte */
133 for (mask = 1; mask < 256; mask <<= 1) {
134 if (*data & mask) {
136 /* next bit is a one */
137 if (state > 0) {
139 /* prefix is a run, so increment the run-count */
140 state++;
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 }
148 } else if (state < 0) {
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 {
162 /* state is zero; this happens only at initialization */
163 state = 1;
164 }
165 } else {
167 /* next bit is a zero */
168 if (state > 0) {
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) {
182 /* prefix is a gap, so increment gap-count (decrement state) */
183 state--;
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 }
191 } else {
193 /* state is zero; this happens only at initialization */
194 state = -1;
195 }
196 }
197 }
199 /* move along to next octet */
200 data++;
201 }
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 }
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;
218 return err_status_ok;
219 }
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 */
228 #define RAND_SRC_BUF_OCTETS 50 /* this value MUST divide 2500! */
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;
249 /* counters for monobit, poker, and runs tests are initialized above */
251 /* main loop: fill buffer, update counters for stat tests */
252 for (i=0; i < 2500; i+=RAND_SRC_BUF_OCTETS) {
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 }
261 #if 0
262 debug_print(mod_stat, "%s",
263 octet_string_hex_string(buffer, RAND_SRC_BUF_OCTETS));
264 #endif
266 data = buffer;
267 data_end = data + RAND_SRC_BUF_OCTETS;
268 while (data < data_end) {
270 /* update monobit test counter */
271 ones_count += octet_get_weight(*data);
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 */
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) {
282 /* next bit is a one */
283 if (state > 0) {
285 /* prefix is a run, so increment the run-count */
286 state++;
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 }
294 } else if (state < 0) {
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 {
308 /* state is zero; this happens only at initialization */
309 state = 1;
310 }
311 } else {
313 /* next bit is a zero */
314 if (state > 0) {
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) {
328 /* prefix is a gap, so increment gap-count (decrement state) */
329 state--;
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 }
337 } else {
339 /* state is zero; this happens only at initialization */
340 state = -1;
341 }
342 }
343 }
345 /* advance data pointer */
346 data++;
347 }
348 }
350 /* check to see if test data is within bounds */
352 /* check monobit test data */
354 debug_print(mod_stat, "stat: bit count: %d", ones_count);
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 }
361 /* check poker test data */
362 poker = 0.0;
363 for (i=0; i < 16; i++)
364 poker += (double) f[i] * f[i];
366 poker *= (16.0 / 5000.0);
367 poker -= 5000.0;
369 debug_print(mod_stat, "stat: poker test: %f", poker);
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 }
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 }
384 debug_print(mod_stat, "passed random stat test", NULL);
385 return err_status_ok;
386 }
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;
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 }
401 return err;
402 }
