← Back to branch summary

~ubuntu-branches/ubuntu/wily/sflphone/wily

« back to all changes in this revision

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

  • Committer: Package Import Robot
  • Author(s): Jonathan Riddell
  • Date: 2015-01-07 14:51:16 UTC
  • mfrom: (4.3.5 sid)
  • Revision ID: package-import@ubuntu.com-20150107145116-yxnafinf4lrdvrmx
Tags: 1.4.1-0.1ubuntu1
* Merge with Debian, remaining changes:
 - Drop soprano, nepomuk build-dep
* Drop ubuntu patches, now upstream

Show diffs side-by-side

added added

removed removed

Lines of Context:
daemon/libs/pjproject-2.2.1/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
}