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
stat_test_monobit(uint8_t * data)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
stat_test_poker(uint8_t * data)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
stat_test_runs(uint8_t * data)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
stat_test_rand_source(rand_source_func_t get_rand_bytes)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
stat_test_rand_source_with_repetition(rand_source_func_t source,unsigned num_trials)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