michael@0: /*
michael@0:  * stats.c
michael@0:  *
michael@0:  * statistical tests for randomness (FIPS 140-2, Section 4.9)
michael@0:  * 
michael@0:  * David A. McGrew
michael@0:  * Cisco Systems, Inc.
michael@0:  */
michael@0: /*
michael@0:  *	
michael@0:  * Copyright (c) 2001-2006, Cisco Systems, Inc.
michael@0:  * All rights reserved.
michael@0:  * 
michael@0:  * Redistribution and use in source and binary forms, with or without
michael@0:  * modification, are permitted provided that the following conditions
michael@0:  * are met:
michael@0:  * 
michael@0:  *   Redistributions of source code must retain the above copyright
michael@0:  *   notice, this list of conditions and the following disclaimer.
michael@0:  * 
michael@0:  *   Redistributions in binary form must reproduce the above
michael@0:  *   copyright notice, this list of conditions and the following
michael@0:  *   disclaimer in the documentation and/or other materials provided
michael@0:  *   with the distribution.
michael@0:  * 
michael@0:  *   Neither the name of the Cisco Systems, Inc. nor the names of its
michael@0:  *   contributors may be used to endorse or promote products derived
michael@0:  *   from this software without specific prior written permission.
michael@0:  * 
michael@0:  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
michael@0:  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
michael@0:  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
michael@0:  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
michael@0:  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
michael@0:  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
michael@0:  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
michael@0:  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
michael@0:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
michael@0:  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
michael@0:  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
michael@0:  * OF THE POSSIBILITY OF SUCH DAMAGE.
michael@0:  *
michael@0:  */
michael@0: 
michael@0: #include "stat.h"
michael@0: 
michael@0: debug_module_t mod_stat = {
michael@0:   0,                 /* debugging is off by default */
michael@0:   (char *)"stat test"        /* printable module name       */
michael@0: };
michael@0: 
michael@0: /*
michael@0:  * each test assumes that 20,000 bits (2500 octets) of data is
michael@0:  * provided as input
michael@0:  */
michael@0: 
michael@0: #define STAT_TEST_DATA_LEN 2500
michael@0: 
michael@0: err_status_t
michael@0: stat_test_monobit(uint8_t *data) {
michael@0:   uint8_t *data_end = data + STAT_TEST_DATA_LEN;
michael@0:   uint16_t ones_count;
michael@0: 
michael@0:   ones_count = 0;
michael@0:   while (data < data_end) {
michael@0:     ones_count += octet_get_weight(*data);
michael@0:     data++;
michael@0:   }
michael@0: 
michael@0:   debug_print(mod_stat, "bit count: %d", ones_count);
michael@0:   
michael@0:   if ((ones_count < 9725) || (ones_count > 10275))
michael@0:     return err_status_algo_fail;
michael@0: 
michael@0:   return err_status_ok;
michael@0: }
michael@0: 
michael@0: err_status_t
michael@0: stat_test_poker(uint8_t *data) {
michael@0:   int i;
michael@0:   uint8_t *data_end = data + STAT_TEST_DATA_LEN;
michael@0:   double poker;
michael@0:   uint16_t f[16] = {
michael@0:     0, 0, 0, 0, 0, 0, 0, 0,
michael@0:     0, 0, 0, 0, 0, 0, 0, 0
michael@0:   };
michael@0:   
michael@0:   while (data < data_end) {
michael@0:     f[*data & 0x0f]++;    /* increment freq. count for low nibble  */
michael@0:     f[(*data) >> 4]++;    /* increment freq. count for high nibble */
michael@0:     data++;
michael@0:   }
michael@0: 
michael@0:   poker = 0.0;
michael@0:   for (i=0; i < 16; i++) 
michael@0:     poker += (double) f[i] * f[i];
michael@0: 
michael@0:   poker *= (16.0 / 5000.0);
michael@0:   poker -= 5000.0;
michael@0: 
michael@0:   debug_print(mod_stat, "poker test: %f\n", poker);
michael@0:     
michael@0:   if ((poker < 2.16) || (poker > 46.17))
michael@0:     return err_status_algo_fail;
michael@0:   
michael@0:   return err_status_ok;
michael@0: }
michael@0: 
michael@0: 
michael@0: /*
michael@0:  * runs[i] holds the number of runs of size (i-1)
michael@0:  */
michael@0: 
michael@0: err_status_t
michael@0: stat_test_runs(uint8_t *data) {
michael@0:   uint8_t *data_end = data + STAT_TEST_DATA_LEN;
michael@0:   uint16_t runs[6] = { 0, 0, 0, 0, 0, 0 }; 
michael@0:   uint16_t gaps[6] = { 0, 0, 0, 0, 0, 0 };
michael@0:   uint16_t lo_value[6] = { 2315, 1114, 527, 240, 103, 103 };
michael@0:   uint16_t hi_value[6] = { 2685, 1386, 723, 384, 209, 209 };
michael@0:   int state = 0;
michael@0:   uint16_t mask;
michael@0:   int i;
michael@0:   
michael@0:   /*
michael@0:    * the state variable holds the number of bits in the
michael@0:    * current run (or gap, if negative)
michael@0:    */
michael@0:   
michael@0:   while (data < data_end) {
michael@0: 
michael@0:     /* loop over the bits of this byte */
michael@0:     for (mask = 1; mask < 256; mask <<= 1) {
michael@0:       if (*data & mask) {
michael@0: 
michael@0:  	/* next bit is a one  */
michael@0: 	if (state > 0) {
michael@0: 
michael@0: 	  /* prefix is a run, so increment the run-count  */
michael@0: 	  state++;                          
michael@0: 
michael@0: 	  /* check for long runs */ 
michael@0: 	  if (state > 25) {
michael@0: 		debug_print(mod_stat, ">25 runs: %d", state);
michael@0: 		return err_status_algo_fail;
michael@0: 	  }
michael@0: 
michael@0: 	} else if (state < 0) {
michael@0: 
michael@0: 	  /* prefix is a gap  */
michael@0: 	  if (state < -25) {
michael@0: 		debug_print(mod_stat, ">25 gaps: %d", state);
michael@0: 	    return err_status_algo_fail;    /* long-runs test failed   */
michael@0: 	  }
michael@0: 	  if (state < -6) {
michael@0: 	    state = -6;                     /* group together gaps > 5 */
michael@0: 	  }
michael@0: 	  gaps[-1-state]++;                 /* increment gap count      */
michael@0:           state = 1;                        /* set state at one set bit */
michael@0: 	} else {
michael@0: 
michael@0: 	  /* state is zero; this happens only at initialization        */
michael@0: 	  state = 1;            
michael@0: 	}
michael@0:       } else {
michael@0: 
michael@0: 	/* next bit is a zero  */
michael@0: 	if (state > 0) {
michael@0: 
michael@0: 	  /* prefix is a run */
michael@0: 	  if (state > 25) {
michael@0: 		debug_print(mod_stat, ">25 runs (2): %d", state);
michael@0: 	    return err_status_algo_fail;    /* long-runs test failed   */
michael@0: 	  }
michael@0: 	  if (state > 6) {
michael@0: 	    state = 6;                      /* group together runs > 5 */
michael@0: 	  }
michael@0: 	  runs[state-1]++;                  /* increment run count       */
michael@0:           state = -1;                       /* set state at one zero bit */
michael@0: 	} else if (state < 0) {
michael@0: 
michael@0: 	  /* prefix is a gap, so increment gap-count (decrement state) */
michael@0: 	  state--;
michael@0: 
michael@0: 	  /* check for long gaps */ 
michael@0: 	  if (state < -25) {
michael@0: 		debug_print(mod_stat, ">25 gaps (2): %d", state);
michael@0: 	    return err_status_algo_fail;
michael@0: 	  }
michael@0: 
michael@0: 	} else {
michael@0: 
michael@0: 	  /* state is zero; this happens only at initialization        */
michael@0: 	  state = -1;
michael@0: 	}
michael@0:       }
michael@0:     }
michael@0: 
michael@0:     /* move along to next octet */
michael@0:     data++;
michael@0:   }
michael@0: 
michael@0:   if (mod_stat.on) {
michael@0:     debug_print(mod_stat, "runs test", NULL);
michael@0:     for (i=0; i < 6; i++)
michael@0:       debug_print(mod_stat, "  runs[]: %d", runs[i]);
michael@0:     for (i=0; i < 6; i++)
michael@0:       debug_print(mod_stat, "  gaps[]: %d", gaps[i]);
michael@0:   }
michael@0: 
michael@0:   /* check run and gap counts against the fixed limits */
michael@0:   for (i=0; i < 6; i++) 
michael@0:     if (   (runs[i] < lo_value[i] ) || (runs[i] > hi_value[i])
michael@0: 	|| (gaps[i] < lo_value[i] ) || (gaps[i] > hi_value[i]))
michael@0:       return err_status_algo_fail;
michael@0: 
michael@0:   
michael@0:   return err_status_ok;
michael@0: }
michael@0: 
michael@0: 
michael@0: /*
michael@0:  * the function stat_test_rand_source applys the FIPS-140-2 statistical
michael@0:  * tests to the random source defined by rs
michael@0:  *
michael@0:  */
michael@0: 
michael@0: #define RAND_SRC_BUF_OCTETS 50 /* this value MUST divide 2500! */ 
michael@0: 
michael@0: err_status_t
michael@0: stat_test_rand_source(rand_source_func_t get_rand_bytes) {
michael@0:   int i;
michael@0:   double poker;
michael@0:   uint8_t *data, *data_end;
michael@0:   uint16_t f[16] = {
michael@0:     0, 0, 0, 0, 0, 0, 0, 0,
michael@0:     0, 0, 0, 0, 0, 0, 0, 0
michael@0:   };
michael@0:   uint8_t buffer[RAND_SRC_BUF_OCTETS];
michael@0:   err_status_t status;
michael@0:   int ones_count = 0;
michael@0:   uint16_t runs[6] = { 0, 0, 0, 0, 0, 0 }; 
michael@0:   uint16_t gaps[6] = { 0, 0, 0, 0, 0, 0 };
michael@0:   uint16_t lo_value[6] = { 2315, 1114, 527, 240, 103, 103 };
michael@0:   uint16_t hi_value[6] = { 2685, 1386, 723, 384, 209, 209 };
michael@0:   int state = 0;
michael@0:   uint16_t mask;
michael@0:   
michael@0:   /* counters for monobit, poker, and runs tests are initialized above */
michael@0: 
michael@0:   /* main loop: fill buffer, update counters for stat tests */
michael@0:   for (i=0; i < 2500; i+=RAND_SRC_BUF_OCTETS) {
michael@0:     
michael@0:     /* fill data buffer */
michael@0:     status = get_rand_bytes(buffer, RAND_SRC_BUF_OCTETS);
michael@0:     if (status) {
michael@0: 	  debug_print(mod_stat, "couldn't get rand bytes: %d",status);
michael@0:       return status;
michael@0: 	}
michael@0: 
michael@0: #if 0
michael@0:     debug_print(mod_stat, "%s", 
michael@0: 		octet_string_hex_string(buffer, RAND_SRC_BUF_OCTETS));
michael@0: #endif
michael@0:   
michael@0:     data = buffer;
michael@0:     data_end = data + RAND_SRC_BUF_OCTETS;
michael@0:     while (data < data_end) {
michael@0: 
michael@0:       /* update monobit test counter */
michael@0:       ones_count += octet_get_weight(*data);
michael@0: 
michael@0:       /* update poker test counters */
michael@0:       f[*data & 0x0f]++;    /* increment freq. count for low nibble  */
michael@0:       f[(*data) >> 4]++;    /* increment freq. count for high nibble */
michael@0: 
michael@0:       /* update runs test counters */
michael@0:       /* loop over the bits of this byte */
michael@0:       for (mask = 1; mask < 256; mask <<= 1) {
michael@0: 	if (*data & mask) {
michael@0: 	  
michael@0: 	  /* next bit is a one  */
michael@0: 	  if (state > 0) {
michael@0: 	    
michael@0: 	    /* prefix is a run, so increment the run-count  */
michael@0: 	    state++;                          
michael@0: 	    
michael@0: 	    /* check for long runs */ 
michael@0: 	    if (state > 25) {
michael@0: 		  debug_print(mod_stat, ">25 runs (3): %d", state);
michael@0: 	      return err_status_algo_fail;
michael@0: 		}
michael@0: 	    
michael@0: 	  } else if (state < 0) {
michael@0: 	    
michael@0: 	    /* prefix is a gap  */
michael@0: 	    if (state < -25) {
michael@0: 		  debug_print(mod_stat, ">25 gaps (3): %d", state);
michael@0: 	      return err_status_algo_fail;    /* long-runs test failed   */
michael@0: 	    }
michael@0: 	    if (state < -6) {
michael@0: 	      state = -6;                     /* group together gaps > 5 */
michael@0: 	    }
michael@0: 	    gaps[-1-state]++;                 /* increment gap count      */
michael@0: 	    state = 1;                        /* set state at one set bit */
michael@0: 	  } else {
michael@0: 	    
michael@0: 	    /* state is zero; this happens only at initialization        */
michael@0: 	    state = 1;            
michael@0: 	  }
michael@0: 	} else {
michael@0: 	  
michael@0: 	  /* next bit is a zero  */
michael@0: 	  if (state > 0) {
michael@0: 	    
michael@0: 	    /* prefix is a run */
michael@0: 	    if (state > 25) {
michael@0: 		  debug_print(mod_stat, ">25 runs (4): %d", state);
michael@0: 	      return err_status_algo_fail;    /* long-runs test failed   */
michael@0: 	    }
michael@0: 	    if (state > 6) {
michael@0: 	      state = 6;                      /* group together runs > 5 */
michael@0: 	    }
michael@0: 	    runs[state-1]++;                  /* increment run count       */
michael@0: 	    state = -1;                       /* set state at one zero bit */
michael@0: 	  } else if (state < 0) {
michael@0: 	    
michael@0: 	    /* prefix is a gap, so increment gap-count (decrement state) */
michael@0: 	    state--;
michael@0: 	    
michael@0: 	    /* check for long gaps */ 
michael@0: 	    if (state < -25) {
michael@0: 		  debug_print(mod_stat, ">25 gaps (4): %d", state);
michael@0: 	      return err_status_algo_fail;
michael@0: 		}
michael@0: 	    
michael@0: 	  } else {
michael@0: 	    
michael@0: 	    /* state is zero; this happens only at initialization        */
michael@0: 	    state = -1;
michael@0: 	  }
michael@0: 	}
michael@0:       }
michael@0:       
michael@0:       /* advance data pointer */
michael@0:       data++;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   /* check to see if test data is within bounds */
michael@0: 
michael@0:   /* check monobit test data */
michael@0: 
michael@0:   debug_print(mod_stat, "stat: bit count: %d", ones_count);
michael@0:   
michael@0:   if ((ones_count < 9725) || (ones_count > 10275)) {
michael@0:     debug_print(mod_stat, "stat: failed monobit test %d", ones_count);
michael@0:     return err_status_algo_fail;
michael@0:   }
michael@0:   
michael@0:   /* check poker test data */
michael@0:   poker = 0.0;
michael@0:   for (i=0; i < 16; i++) 
michael@0:     poker += (double) f[i] * f[i];
michael@0: 
michael@0:   poker *= (16.0 / 5000.0);
michael@0:   poker -= 5000.0;
michael@0: 
michael@0:   debug_print(mod_stat, "stat: poker test: %f", poker);
michael@0:     
michael@0:   if ((poker < 2.16) || (poker > 46.17)) {
michael@0:     debug_print(mod_stat, "stat: failed poker test", NULL);
michael@0:     return err_status_algo_fail;
michael@0:   }
michael@0: 
michael@0:   /* check run and gap counts against the fixed limits */
michael@0:   for (i=0; i < 6; i++) 
michael@0:     if ((runs[i] < lo_value[i] ) || (runs[i] > hi_value[i])
michael@0: 	 || (gaps[i] < lo_value[i] ) || (gaps[i] > hi_value[i])) {
michael@0:       debug_print(mod_stat, "stat: failed run/gap test", NULL);
michael@0:       return err_status_algo_fail; 
michael@0:     }
michael@0: 
michael@0:   debug_print(mod_stat, "passed random stat test", NULL);
michael@0:   return err_status_ok;
michael@0: }
michael@0: 
michael@0: err_status_t
michael@0: stat_test_rand_source_with_repetition(rand_source_func_t source, unsigned num_trials) {
michael@0:   unsigned int i;
michael@0:   err_status_t err = err_status_algo_fail;
michael@0: 
michael@0:   for (i=0; i < num_trials; i++) {
michael@0:     err = stat_test_rand_source(source);
michael@0:     if (err == err_status_ok) {
michael@0:       return err_status_ok;  
michael@0:     }
michael@0:     debug_print(mod_stat, "failed stat test (try number %d)\n", i);
michael@0:   }
michael@0:   
michael@0:   return err;
michael@0: }