Line data Source code
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 0 : stat_test_monobit(uint8_t *data) {
61 0 : uint8_t *data_end = data + STAT_TEST_DATA_LEN;
62 : uint16_t ones_count;
63 :
64 0 : ones_count = 0;
65 0 : while (data < data_end) {
66 0 : ones_count += octet_get_weight(*data);
67 0 : data++;
68 : }
69 :
70 : debug_print(mod_stat, "bit count: %d", ones_count);
71 :
72 0 : if ((ones_count < 9725) || (ones_count > 10275))
73 0 : return err_status_algo_fail;
74 :
75 0 : return err_status_ok;
76 : }
77 :
78 : err_status_t
79 0 : stat_test_poker(uint8_t *data) {
80 : int i;
81 0 : uint8_t *data_end = data + STAT_TEST_DATA_LEN;
82 : double poker;
83 0 : 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 0 : while (data < data_end) {
89 0 : f[*data & 0x0f]++; /* increment freq. count for low nibble */
90 0 : f[(*data) >> 4]++; /* increment freq. count for high nibble */
91 0 : data++;
92 : }
93 :
94 0 : poker = 0.0;
95 0 : for (i=0; i < 16; i++)
96 0 : poker += (double) f[i] * f[i];
97 :
98 0 : poker *= (16.0 / 5000.0);
99 0 : poker -= 5000.0;
100 :
101 : debug_print(mod_stat, "poker test: %f\n", poker);
102 :
103 0 : if ((poker < 2.16) || (poker > 46.17))
104 0 : return err_status_algo_fail;
105 :
106 0 : 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 0 : stat_test_runs(uint8_t *data) {
116 0 : uint8_t *data_end = data + STAT_TEST_DATA_LEN;
117 0 : uint16_t runs[6] = { 0, 0, 0, 0, 0, 0 };
118 0 : uint16_t gaps[6] = { 0, 0, 0, 0, 0, 0 };
119 0 : uint16_t lo_value[6] = { 2315, 1114, 527, 240, 103, 103 };
120 0 : uint16_t hi_value[6] = { 2685, 1386, 723, 384, 209, 209 };
121 0 : 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 0 : while (data < data_end) {
131 :
132 : /* loop over the bits of this byte */
133 0 : for (mask = 1; mask < 256; mask <<= 1) {
134 0 : if (*data & mask) {
135 :
136 : /* next bit is a one */
137 0 : if (state > 0) {
138 :
139 : /* prefix is a run, so increment the run-count */
140 0 : state++;
141 :
142 : /* check for long runs */
143 0 : if (state > 25) {
144 : debug_print(mod_stat, ">25 runs: %d", state);
145 0 : return err_status_algo_fail;
146 : }
147 :
148 0 : } else if (state < 0) {
149 :
150 : /* prefix is a gap */
151 0 : if (state < -25) {
152 : debug_print(mod_stat, ">25 gaps: %d", state);
153 0 : return err_status_algo_fail; /* long-runs test failed */
154 : }
155 0 : if (state < -6) {
156 0 : state = -6; /* group together gaps > 5 */
157 : }
158 0 : gaps[-1-state]++; /* increment gap count */
159 0 : state = 1; /* set state at one set bit */
160 : } else {
161 :
162 : /* state is zero; this happens only at initialization */
163 0 : state = 1;
164 : }
165 : } else {
166 :
167 : /* next bit is a zero */
168 0 : if (state > 0) {
169 :
170 : /* prefix is a run */
171 0 : if (state > 25) {
172 : debug_print(mod_stat, ">25 runs (2): %d", state);
173 0 : return err_status_algo_fail; /* long-runs test failed */
174 : }
175 0 : if (state > 6) {
176 0 : state = 6; /* group together runs > 5 */
177 : }
178 0 : runs[state-1]++; /* increment run count */
179 0 : state = -1; /* set state at one zero bit */
180 0 : } else if (state < 0) {
181 :
182 : /* prefix is a gap, so increment gap-count (decrement state) */
183 0 : state--;
184 :
185 : /* check for long gaps */
186 0 : if (state < -25) {
187 : debug_print(mod_stat, ">25 gaps (2): %d", state);
188 0 : return err_status_algo_fail;
189 : }
190 :
191 : } else {
192 :
193 : /* state is zero; this happens only at initialization */
194 0 : state = -1;
195 : }
196 : }
197 : }
198 :
199 : /* move along to next octet */
200 0 : data++;
201 : }
202 :
203 0 : if (mod_stat.on) {
204 : debug_print(mod_stat, "runs test", NULL);
205 0 : for (i=0; i < 6; i++)
206 : debug_print(mod_stat, " runs[]: %d", runs[i]);
207 0 : 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 0 : for (i=0; i < 6; i++)
213 0 : if ( (runs[i] < lo_value[i] ) || (runs[i] > hi_value[i])
214 0 : || (gaps[i] < lo_value[i] ) || (gaps[i] > hi_value[i]))
215 0 : return err_status_algo_fail;
216 :
217 :
218 0 : 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 0 : stat_test_rand_source(rand_source_func_t get_rand_bytes) {
232 : int i;
233 : double poker;
234 : uint8_t *data, *data_end;
235 0 : 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 0 : int ones_count = 0;
242 0 : uint16_t runs[6] = { 0, 0, 0, 0, 0, 0 };
243 0 : uint16_t gaps[6] = { 0, 0, 0, 0, 0, 0 };
244 0 : uint16_t lo_value[6] = { 2315, 1114, 527, 240, 103, 103 };
245 0 : uint16_t hi_value[6] = { 2685, 1386, 723, 384, 209, 209 };
246 0 : 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 0 : for (i=0; i < 2500; i+=RAND_SRC_BUF_OCTETS) {
253 :
254 : /* fill data buffer */
255 0 : status = get_rand_bytes(buffer, RAND_SRC_BUF_OCTETS);
256 0 : if (status) {
257 : debug_print(mod_stat, "couldn't get rand bytes: %d",status);
258 0 : 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 0 : data = buffer;
267 0 : data_end = data + RAND_SRC_BUF_OCTETS;
268 0 : while (data < data_end) {
269 :
270 : /* update monobit test counter */
271 0 : ones_count += octet_get_weight(*data);
272 :
273 : /* update poker test counters */
274 0 : f[*data & 0x0f]++; /* increment freq. count for low nibble */
275 0 : f[(*data) >> 4]++; /* increment freq. count for high nibble */
276 :
277 : /* update runs test counters */
278 : /* loop over the bits of this byte */
279 0 : for (mask = 1; mask < 256; mask <<= 1) {
280 0 : if (*data & mask) {
281 :
282 : /* next bit is a one */
283 0 : if (state > 0) {
284 :
285 : /* prefix is a run, so increment the run-count */
286 0 : state++;
287 :
288 : /* check for long runs */
289 0 : if (state > 25) {
290 : debug_print(mod_stat, ">25 runs (3): %d", state);
291 0 : return err_status_algo_fail;
292 : }
293 :
294 0 : } else if (state < 0) {
295 :
296 : /* prefix is a gap */
297 0 : if (state < -25) {
298 : debug_print(mod_stat, ">25 gaps (3): %d", state);
299 0 : return err_status_algo_fail; /* long-runs test failed */
300 : }
301 0 : if (state < -6) {
302 0 : state = -6; /* group together gaps > 5 */
303 : }
304 0 : gaps[-1-state]++; /* increment gap count */
305 0 : state = 1; /* set state at one set bit */
306 : } else {
307 :
308 : /* state is zero; this happens only at initialization */
309 0 : state = 1;
310 : }
311 : } else {
312 :
313 : /* next bit is a zero */
314 0 : if (state > 0) {
315 :
316 : /* prefix is a run */
317 0 : if (state > 25) {
318 : debug_print(mod_stat, ">25 runs (4): %d", state);
319 0 : return err_status_algo_fail; /* long-runs test failed */
320 : }
321 0 : if (state > 6) {
322 0 : state = 6; /* group together runs > 5 */
323 : }
324 0 : runs[state-1]++; /* increment run count */
325 0 : state = -1; /* set state at one zero bit */
326 0 : } else if (state < 0) {
327 :
328 : /* prefix is a gap, so increment gap-count (decrement state) */
329 0 : state--;
330 :
331 : /* check for long gaps */
332 0 : if (state < -25) {
333 : debug_print(mod_stat, ">25 gaps (4): %d", state);
334 0 : return err_status_algo_fail;
335 : }
336 :
337 : } else {
338 :
339 : /* state is zero; this happens only at initialization */
340 0 : state = -1;
341 : }
342 : }
343 : }
344 :
345 : /* advance data pointer */
346 0 : 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 0 : if ((ones_count < 9725) || (ones_count > 10275)) {
357 : debug_print(mod_stat, "stat: failed monobit test %d", ones_count);
358 0 : return err_status_algo_fail;
359 : }
360 :
361 : /* check poker test data */
362 0 : poker = 0.0;
363 0 : for (i=0; i < 16; i++)
364 0 : poker += (double) f[i] * f[i];
365 :
366 0 : poker *= (16.0 / 5000.0);
367 0 : poker -= 5000.0;
368 :
369 : debug_print(mod_stat, "stat: poker test: %f", poker);
370 :
371 0 : if ((poker < 2.16) || (poker > 46.17)) {
372 : debug_print(mod_stat, "stat: failed poker test", NULL);
373 0 : return err_status_algo_fail;
374 : }
375 :
376 : /* check run and gap counts against the fixed limits */
377 0 : for (i=0; i < 6; i++)
378 0 : if ((runs[i] < lo_value[i] ) || (runs[i] > hi_value[i])
379 0 : || (gaps[i] < lo_value[i] ) || (gaps[i] > hi_value[i])) {
380 : debug_print(mod_stat, "stat: failed run/gap test", NULL);
381 0 : return err_status_algo_fail;
382 : }
383 :
384 : debug_print(mod_stat, "passed random stat test", NULL);
385 0 : return err_status_ok;
386 : }
387 :
388 : err_status_t
389 0 : stat_test_rand_source_with_repetition(rand_source_func_t source, unsigned num_trials) {
390 : unsigned int i;
391 0 : err_status_t err = err_status_algo_fail;
392 :
393 0 : for (i=0; i < num_trials; i++) {
394 0 : err = stat_test_rand_source(source);
395 0 : if (err == err_status_ok) {
396 0 : return err_status_ok;
397 : }
398 : debug_print(mod_stat, "failed stat test (try number %d)\n", i);
399 : }
400 :
401 0 : return err;
402 : }
|
