crypto/math/stat.c

/*
 * stats.c
 *
 * statistical tests 
 * 
 * David A. McGrew
 * Cisco Systems, Inc.
 */

#ifdef HAVE_CONFIG_H
    #include <config.h>
#endif

#include "stat.h"

srtp_debug_module_t mod_stat = {
  0,                 /* debugging is off by default */
  (char *)"stat test"        /* printable module name       */
};

/*
 * each test assumes that 20,000 bits (2500 octets) of data is
 * provided as input
 */

#define STAT_TEST_DATA_LEN 2500

srtp_err_status_t
stat_test_monobit(uint8_t *data) {
  uint8_t *data_end = data + STAT_TEST_DATA_LEN;
  uint16_t ones_count;

  ones_count = 0;
  while (data < data_end) {
    ones_count += octet_get_weight(*data);
    data++;
  }

  debug_print(mod_stat, "bit count: %d", ones_count);
  
  if ((ones_count < 9725) || (ones_count > 10275))
    return srtp_err_status_algo_fail;

  return srtp_err_status_ok;
}

srtp_err_status_t
stat_test_poker(uint8_t *data) {
  int i;
  uint8_t *data_end = data + STAT_TEST_DATA_LEN;
  double poker;
  uint16_t f[16] = {
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0
  };
  
  while (data < data_end) {
    f[*data & 0x0f]++;    /* increment freq. count for low nibble  */
    f[(*data) >> 4]++;    /* increment freq. count for high nibble */
    data++;
  }

  poker = 0.0;
  for (i=0; i < 16; i++) 
    poker += (double) f[i] * f[i];

  poker *= (16.0 / 5000.0);
  poker -= 5000.0;

  debug_print(mod_stat, "poker test: %f\n", poker);
    
  if ((poker < 2.16) || (poker > 46.17))
    return srtp_err_status_algo_fail;
  
  return srtp_err_status_ok;
}


/*
 * runs[i] holds the number of runs of size (i-1)
 */

srtp_err_status_t
stat_test_runs(uint8_t *data) {
  uint8_t *data_end = data + STAT_TEST_DATA_LEN;
  uint16_t runs[6] = { 0, 0, 0, 0, 0, 0 }; 
  uint16_t gaps[6] = { 0, 0, 0, 0, 0, 0 };
  uint16_t lo_value[6] = { 2315, 1114, 527, 240, 103, 103 };
  uint16_t hi_value[6] = { 2685, 1386, 723, 384, 209, 209 };
  int state = 0;
  uint16_t mask;
  int i;
  
  /*
   * the state variable holds the number of bits in the
   * current run (or gap, if negative)
   */
  
  while (data < data_end) {

    /* loop over the bits of this byte */
    for (mask = 1; mask < 256; mask <<= 1) {
      if (*data & mask) {

 	/* next bit is a one  */
	if (state > 0) {

	  /* prefix is a run, so increment the run-count  */
	  state++;                          

	  /* check for long runs */ 
	  if (state > 25) {
		debug_print(mod_stat, ">25 runs: %d", state);
		return srtp_err_status_algo_fail;
	  }

	} else if (state < 0) {

	  /* prefix is a gap  */
	  if (state < -25) {
		debug_print(mod_stat, ">25 gaps: %d", state);
	    return srtp_err_status_algo_fail;    /* long-runs test failed   */
	  }
	  if (state < -6) {
	    state = -6;                     /* group together gaps > 5 */
	  }
	  gaps[-1-state]++;                 /* increment gap count      */
          state = 1;                        /* set state at one set bit */
	} else {

	  /* state is zero; this happens only at initialization        */
	  state = 1;            
	}
      } else {

	/* next bit is a zero  */
	if (state > 0) {

	  /* prefix is a run */
	  if (state > 25) {
		debug_print(mod_stat, ">25 runs (2): %d", state);
	    return srtp_err_status_algo_fail;    /* long-runs test failed   */
	  }
	  if (state > 6) {
	    state = 6;                      /* group together runs > 5 */
	  }
	  runs[state-1]++;                  /* increment run count       */
          state = -1;                       /* set state at one zero bit */
	} else if (state < 0) {

	  /* prefix is a gap, so increment gap-count (decrement state) */
	  state--;

	  /* check for long gaps */ 
	  if (state < -25) {
		debug_print(mod_stat, ">25 gaps (2): %d", state);
	    return srtp_err_status_algo_fail;
	  }

	} else {

	  /* state is zero; this happens only at initialization        */
	  state = -1;
	}
      }
    }

    /* move along to next octet */
    data++;
  }

  if (mod_stat.on) {
    debug_print(mod_stat, "runs test", NULL);
    for (i=0; i < 6; i++)
      debug_print(mod_stat, "  runs[]: %d", runs[i]);
    for (i=0; i < 6; i++)
      debug_print(mod_stat, "  gaps[]: %d", gaps[i]);
  }

  /* check run and gap counts against the fixed limits */
  for (i=0; i < 6; i++) 
    if (   (runs[i] < lo_value[i] ) || (runs[i] > hi_value[i])
	|| (gaps[i] < lo_value[i] ) || (gaps[i] > hi_value[i]))
      return srtp_err_status_algo_fail;

  
  return srtp_err_status_ok;
}