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
47debug_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
59err_status_t
60stat_test_monobit(uint8_t *data) {
61  uint8_t *data_end = data + STAT_TEST_DATA_LEN;
62  uint16_t ones_count;
63
64  ones_count = 0;
65  while (data < data_end) {
66    ones_count += octet_get_weight(*data);
67    data++;
68  }
69
70  debug_print(mod_stat, "bit count: %d", ones_count);
71
72  if ((ones_count < 9725) || (ones_count > 10275))
73    return err_status_algo_fail;
74
75  return err_status_ok;
76}
77
78err_status_t
79stat_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  };
87
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  }
93
94  poker = 0.0;
95  for (i=0; i < 16; i++)
96    poker += (double) f[i] * f[i];
97
98  poker *= (16.0 / 5000.0);
99  poker -= 5000.0;
100
101  debug_print(mod_stat, "poker test: %f\n", poker);
102
103  if ((poker < 2.16) || (poker > 46.17))
104    return err_status_algo_fail;
105
106  return err_status_ok;
107}
108
109
110/*
111 * runs[i] holds the number of runs of size (i-1)
112 */
113
114err_status_t
115stat_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;
124
125  /*
126   * the state variable holds the number of bits in the
127   * current run (or gap, if negative)
128   */
129
130  while (data < data_end) {
131
132    /* loop over the bits of this byte */
133    for (mask = 1; mask < 256; mask <<= 1) {
134      if (*data & mask) {
135
136 	/* next bit is a one  */
137	if (state > 0) {
138
139	  /* prefix is a run, so increment the run-count  */
140	  state++;
141
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	  }
147
148	} else if (state < 0) {
149
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 {
161
162	  /* state is zero; this happens only at initialization        */
163	  state = 1;
164	}
165      } else {
166
167	/* next bit is a zero  */
168	if (state > 0) {
169
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) {
181
182	  /* prefix is a gap, so increment gap-count (decrement state) */
183	  state--;
184
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	  }
190
191	} else {
192
193	  /* state is zero; this happens only at initialization        */
194	  state = -1;
195	}
196      }
197    }
198
199    /* move along to next octet */
200    data++;
201  }
202
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  }
210
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;
216
217
218  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
230err_status_t
231stat_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;
248
249  /* counters for monobit, poker, and runs tests are initialized above */
250
251  /* main loop: fill buffer, update counters for stat tests */
252  for (i=0; i < 2500; i+=RAND_SRC_BUF_OCTETS) {
253
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	}
260
261#if 0
262    debug_print(mod_stat, "%s",
263		octet_string_hex_string(buffer, RAND_SRC_BUF_OCTETS));
264#endif
265
266    data = buffer;
267    data_end = data + RAND_SRC_BUF_OCTETS;
268    while (data < data_end) {
269
270      /* update monobit test counter */
271      ones_count += octet_get_weight(*data);
272
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 */
276
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) {
281
282	  /* next bit is a one  */
283	  if (state > 0) {
284
285	    /* prefix is a run, so increment the run-count  */
286	    state++;
287
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		}
293
294	  } else if (state < 0) {
295
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 {
307
308	    /* state is zero; this happens only at initialization        */
309	    state = 1;
310	  }
311	} else {
312
313	  /* next bit is a zero  */
314	  if (state > 0) {
315
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) {
327
328	    /* prefix is a gap, so increment gap-count (decrement state) */
329	    state--;
330
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		}
336
337	  } else {
338
339	    /* state is zero; this happens only at initialization        */
340	    state = -1;
341	  }
342	}
343      }
344
345      /* advance data pointer */
346      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  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  }
360
361  /* check poker test data */
362  poker = 0.0;
363  for (i=0; i < 16; i++)
364    poker += (double) f[i] * f[i];
365
366  poker *= (16.0 / 5000.0);
367  poker -= 5000.0;
368
369  debug_print(mod_stat, "stat: poker test: %f", poker);
370
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  }
375
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    }
383
384  debug_print(mod_stat, "passed random stat test", NULL);
385  return err_status_ok;
386}
387
388err_status_t
389stat_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;
392
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  }
400
401  return err;
402}
403