← Back to branch summary

~noskcaj/ubuntu/saucy/sflphone/merge-1.2.3-2

« back to all changes in this revision

Viewing changes to daemon/libs/pjproject/third_party/srtp/crypto/math/stat.c

  • Committer: Jackson Doak
  • Date: 2013-07-10 21:04:46 UTC
  • mfrom: (20.1.3 sid)
  • Revision ID: noskcaj@ubuntu.com-20130710210446-y8f587vza807icr9
https://launchpad.net/bugs/1196978
Properly merged from upstream.

Show diffs side-by-side

added added

removed removed

Lines of Context:
daemon/libs/pjproject/third_party/srtp/crypto/math/stat.c
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
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
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
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
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
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
 
}