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
12debug_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
24err_status_t
25stat_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
43err_status_t
44stat_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
79err_status_t
80stat_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
195err_status_t
196stat_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
353err_status_t
354stat_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