iPXE
entropy.c
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2012 Michael Brown <mbrown@fensystems.co.uk>.
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License as
6  * published by the Free Software Foundation; either version 2 of the
7  * License, or any later version.
8  *
9  * This program is distributed in the hope that it will be useful, but
10  * WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
17  * 02110-1301, USA.
18  *
19  * You can also choose to distribute this program under the terms of
20  * the Unmodified Binary Distribution Licence (as given in the file
21  * COPYING.UBDL), provided that you have satisfied its requirements.
22  */
23 
24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
25 
26 /** @file
27  *
28  * Entropy source
29  *
30  * This algorithm is designed to comply with ANS X9.82 Part 4 (April
31  * 2011 Draft) Section 13.3. This standard is unfortunately not
32  * freely available.
33  */
34 
35 #include <stdint.h>
36 #include <assert.h>
37 #include <string.h>
38 #include <errno.h>
39 #include <ipxe/crypto.h>
40 #include <ipxe/hash_df.h>
41 #include <ipxe/entropy.h>
42 
43 /* Disambiguate the various error causes */
44 #define EPIPE_REPETITION_COUNT_TEST \
45  __einfo_error ( EINFO_EPIPE_REPETITION_COUNT_TEST )
46 #define EINFO_EPIPE_REPETITION_COUNT_TEST \
47  __einfo_uniqify ( EINFO_EPIPE, 0x01, "Repetition count test failed" )
48 #define EPIPE_ADAPTIVE_PROPORTION_TEST \
49  __einfo_error ( EINFO_EPIPE_ADAPTIVE_PROPORTION_TEST )
50 #define EINFO_EPIPE_ADAPTIVE_PROPORTION_TEST \
51  __einfo_uniqify ( EINFO_EPIPE, 0x02, "Adaptive proportion test failed" )
52 
53 /**
54  * Initialise repetition count test
55  *
56  * @v source Entropy source
57  */
58 static void repetition_count_test_init ( struct entropy_source *source ) {
60  &source->repetition_count_test;
61 
62  /* Sanity checks */
63  assert ( test->repetition_count == 0 );
64  assert ( test->cutoff > 0 );
65 }
66 
67 /**
68  * Perform repetition count test
69  *
70  * @v source Entropy source
71  * @v sample Noise sample
72  * @ret rc Return status code
73  *
74  * This is the Repetition Count Test defined in ANS X9.82 Part 2
75  * (October 2011 Draft) Section 8.5.2.1.2.
76  */
77 static int repetition_count_test ( struct entropy_source *source,
78  noise_sample_t sample ) {
80  &source->repetition_count_test;
81 
82  /* A = the most recently seen sample value
83  * B = the number of times that value A has been seen in a row
84  * C = the cutoff value above which the repetition test should fail
85  */
86 
87  /* 1. For each new sample processed:
88  *
89  * (Note that the test for "repetition_count > 0" ensures that
90  * the initial value of most_recent_sample is treated as being
91  * undefined.)
92  */
93  if ( ( sample == test->most_recent_sample ) &&
94  ( test->repetition_count > 0 ) ) {
95 
96  /* a) If the new sample = A, then B is incremented by one. */
97  test->repetition_count++;
98 
99  /* i. If B >= C, then an error condition is raised
100  * due to a failure of the test
101  */
102  if ( test->repetition_count >= test->cutoff ) {
103  DBGC ( source, "ENTROPY %s excessively repeated "
104  "value %d (%d/%d)\n", source->name, sample,
105  test->repetition_count, test->cutoff );
107  }
108 
109  } else {
110 
111  /* b) Else:
112  * i. A = new sample
113  */
114  test->most_recent_sample = sample;
115 
116  /* ii. B = 1 */
117  test->repetition_count = 1;
118  }
119 
120  return 0;
121 }
122 
123 /**
124  * Initialise adaptive proportion test
125  *
126  * @v source Entropy source
127  */
128 static void adaptive_proportion_test_init ( struct entropy_source *source ) {
130  &source->adaptive_proportion_test;
131 
132  /* Sanity checks */
133  assert ( test->sample_count == 0 );
134  assert ( test->repetition_count == 0 );
135  assert ( test->cutoff > 0 );
136 
137  /* Ensure that a new test run starts immediately */
138  test->sample_count = ADAPTIVE_PROPORTION_WINDOW_SIZE;
139 }
140 
141 /**
142  * Perform adaptive proportion test
143  *
144  * @v source Entropy source
145  * @v sample Noise sample
146  * @ret rc Return status code
147  *
148  * This is the Adaptive Proportion Test for the Most Common Value
149  * defined in ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.3.
150  */
151 static int adaptive_proportion_test ( struct entropy_source *source,
152  noise_sample_t sample ) {
154  &source->adaptive_proportion_test;
155 
156  /* A = the sample value currently being counted
157  * S = the number of samples examined in this run of the test so far
158  * N = the total number of samples that must be observed in
159  * one run of the test, also known as the "window size" of
160  * the test
161  * B = the current number of times that S (sic) has been seen
162  * in the W (sic) samples examined so far
163  * C = the cutoff value above which the repetition test should fail
164  * W = the probability of a false positive: 2^-30
165  */
166 
167  /* 1. The entropy source draws the current sample from the
168  * noise source.
169  *
170  * (Nothing to do; we already have the current sample.)
171  */
172 
173  /* 2. If S = N, then a new run of the test begins: */
174  if ( test->sample_count == ADAPTIVE_PROPORTION_WINDOW_SIZE ) {
175 
176  /* a. A = the current sample */
177  test->current_counted_sample = sample;
178 
179  /* b. S = 0 */
180  test->sample_count = 0;
181 
182  /* c. B = 0 */
183  test->repetition_count = 0;
184 
185  } else {
186 
187  /* Else: (the test is already running)
188  * a. S = S + 1
189  */
190  test->sample_count++;
191 
192  /* b. If A = the current sample, then: */
193  if ( sample == test->current_counted_sample ) {
194 
195  /* i. B = B + 1 */
196  test->repetition_count++;
197 
198  /* ii. If S (sic) > C then raise an error
199  * condition, because the test has
200  * detected a failure
201  */
202  if ( test->repetition_count > test->cutoff ) {
203  DBGC ( source, "ENTROPY %s excessively "
204  "repeated value %d (%d/%d)\n",
205  source->name, sample,
206  test->repetition_count, test->cutoff );
208  }
209  }
210  }
211 
212  return 0;
213 }
214 
215 /**
216  * Get entropy sample
217  *
218  * @v source Entropy source
219  * @ret entropy Entropy sample
220  * @ret rc Return status code
221  *
222  * This is the GetEntropy function defined in ANS X9.82 Part 2
223  * (October 2011 Draft) Section 6.5.1.
224  */
225 static int get_entropy ( struct entropy_source *source,
226  entropy_sample_t *entropy ) {
227  noise_sample_t noise;
228  int rc;
229 
230  /* Any failure is permanent */
231  if ( ( rc = source->rc ) != 0 )
232  goto err_broken;
233 
234  /* Get noise sample */
235  if ( ( rc = get_noise ( source, &noise ) ) != 0 )
236  goto err_get_noise;
237 
238  /* Perform Repetition Count Test and Adaptive Proportion Test
239  * as mandated by ANS X9.82 Part 2 (October 2011 Draft)
240  * Section 8.5.2.1.1.
241  */
242  if ( ( rc = repetition_count_test ( source, noise ) ) != 0 )
243  goto err_repetition_count_test;
244  if ( ( rc = adaptive_proportion_test ( source, noise ) ) != 0 )
245  goto err_adaptive_proportion_test;
246 
247  /* We do not use any optional conditioning component */
248  *entropy = noise;
249 
250  return 0;
251 
252  err_adaptive_proportion_test:
253  err_repetition_count_test:
254  err_get_noise:
255  source->rc = rc;
256  err_broken:
257  return rc;
258 }
259 
260 /**
261  * Initialise startup test
262  *
263  * @v source Entropy source
264  */
265 static void startup_test_init ( struct entropy_source *source ) {
266  struct entropy_startup_test *test = &source->startup_test;
267 
268  /* Sanity check */
269  assert ( test->tested == 0 );
270  assert ( test->count > 0 );
271 }
272 
273 /**
274  * Perform startup test
275  *
276  * @v source Entropy source
277  * @ret rc Return status code
278  */
279 static int startup_test ( struct entropy_source *source ) {
280  struct entropy_startup_test *test = &source->startup_test;
281  entropy_sample_t sample;
282  int rc;
283 
284  /* Perform mandatory number of startup tests */
285  for ( ; test->tested < test->count ; test->tested++ ) {
286  if ( ( rc = get_entropy ( source, &sample ) ) != 0 ) {
287  DBGC ( source, "ENTROPY %s failed: %s\n",
288  source->name, strerror ( rc ) );
289  return rc;
290  }
291  }
292 
293  return 0;
294 }
295 
296 /**
297  * Enable entropy gathering
298  *
299  * @v source Entropy source
300  * @ret rc Return status code
301  */
302 int entropy_enable ( struct entropy_source *source ) {
303  int rc;
304 
305  /* Refuse to enable a previously failed source */
306  if ( ( rc = source->rc ) != 0 )
307  return rc;
308 
309  /* Enable entropy source */
310  if ( ( rc = source->enable() ) != 0 ) {
311  DBGC ( source, "ENTROPY %s could not enable: %s\n",
312  source->name, strerror ( rc ) );
313  source->rc = rc;
314  return rc;
315  }
316 
317  /* Sanity check */
318  assert ( source->min_entropy_per_sample > 0 );
319 
320  /* Initialise test state if this source has not previously been used */
321  if ( source->startup_test.tested == 0 ) {
322  repetition_count_test_init ( source );
324  startup_test_init ( source );
325  }
326 
327  DBGC ( source, "ENTROPY %s enabled\n", source->name );
328  return 0;
329 }
330 
331 /**
332  * Enable and test entropy source
333  *
334  * @v source Entropy source
335  * @ret rc Return status code
336  */
337 static int entropy_enable_and_test ( struct entropy_source *source ) {
338  int rc;
339 
340  /* Enable source */
341  if ( ( rc = entropy_enable ( source ) ) != 0 )
342  goto err_enable;
343 
344  /* Test source */
345  if ( ( rc = startup_test ( source ) ) != 0 )
346  goto err_test;
347 
348  DBGC ( source, "ENTROPY %s passed %d startup tests\n",
349  source->name, source->startup_test.count );
350  return 0;
351 
352  err_test:
353  entropy_disable ( source );
354  err_enable:
355  assert ( source->rc == rc );
356  return rc;
357 }
358 
359 /**
360  * Enable first working entropy source
361  *
362  * @v source Entropy source to fill in
363  * @ret rc Return status code
364  */
365 static int entropy_enable_working ( struct entropy_source **source ) {
366  int rc;
367 
368  /* Find the first working source */
369  rc = -ENOENT;
371  if ( ( rc = entropy_enable_and_test ( *source ) ) == 0 )
372  return 0;
373  }
374 
375  DBGC ( *source, "ENTROPY has no working sources: %s\n",
376  strerror ( rc ) );
377  return rc;
378 }
379 
380 /**
381  * Disable entropy gathering
382  *
383  * @v source Entropy source
384  */
385 void entropy_disable ( struct entropy_source *source ) {
386 
387  /* Disable entropy gathering, if applicable */
388  if ( source->disable )
389  source->disable();
390 
391  DBGC ( source, "ENTROPY %s disabled\n", source->name );
392 }
393 
394 /**
395  * Create next nonce value
396  *
397  * @ret nonce Nonce
398  *
399  * This is the MakeNextNonce function defined in ANS X9.82 Part 4
400  * (April 2011 Draft) Section 13.3.4.2.
401  */
402 static uint32_t make_next_nonce ( void ) {
403  static uint32_t nonce;
404 
405  /* The simplest implementation of a nonce uses a large counter */
406  nonce++;
407 
408  return nonce;
409 }
410 
411 /**
412  * Obtain entropy input temporary buffer
413  *
414  * @v min_entropy Min-entropy required
415  * @v tmp Temporary buffer
416  * @v tmp_len Length of temporary buffer
417  * @ret rc Return status code
418  *
419  * This is (part of) the implementation of the Get_entropy_input
420  * function (using an entropy source as the source of entropy input
421  * and condensing each entropy source output after each GetEntropy
422  * call) as defined in ANS X9.82 Part 4 (April 2011 Draft) Section
423  * 13.3.4.2.
424  */
426  size_t tmp_len ) {
427  struct entropy_source *source;
428  struct {
429  uint32_t nonce;
430  entropy_sample_t sample;
431  } __attribute__ (( packed )) data;;
432  uint8_t df_buf[tmp_len];
433  min_entropy_t entropy_total;
434  unsigned int num_samples;
435  unsigned int i;
436  int rc;
437 
438  /* Enable entropy gathering */
439  if ( ( rc = entropy_enable_working ( &source ) ) != 0 )
440  goto err_enable_working;
441 
442  /* Sanity checks */
443  assert ( source->startup_test.count > 0 );
444  assert ( source->startup_test.tested >= source->startup_test.count );
445 
446  /* 3. entropy_total = 0 */
447  entropy_total = MIN_ENTROPY ( 0 );
448 
449  /* 4. tmp = a fixed n-bit value, such as 0^n */
450  memset ( tmp, 0, tmp_len );
451 
452  /* 5. While ( entropy_total < min_entropy ) */
453  for ( num_samples = 0 ; entropy_total < min_entropy ; num_samples++ ) {
454  /* 5.1. ( status, entropy_bitstring, assessed_entropy )
455  * = GetEntropy()
456  * 5.2. If status indicates an error, return ( status, Null )
457  */
458  if ( ( rc = get_entropy ( source, &data.sample ) ) != 0 )
459  goto err_get_entropy;
460 
461  /* 5.3. nonce = MakeNextNonce() */
462  data.nonce = make_next_nonce();
463 
464  /* 5.4. tmp = tmp XOR
465  * df ( ( nonce || entropy_bitstring ), n )
466  */
467  hash_df ( &entropy_hash_df_algorithm, &data, sizeof ( data ),
468  df_buf, sizeof ( df_buf ) );
469  for ( i = 0 ; i < tmp_len ; i++ )
470  tmp[i] ^= df_buf[i];
471 
472  /* 5.5. entropy_total = entropy_total + assessed_entropy */
473  entropy_total += source->min_entropy_per_sample;
474  }
475 
476  /* Disable entropy gathering */
477  entropy_disable ( source );
478 
479  DBGC ( source, "ENTROPY %s gathered %d bits in %d samples\n",
480  source->name, ( min_entropy / MIN_ENTROPY_SCALE ), num_samples );
481  return 0;
482 
483  err_get_entropy:
484  entropy_disable ( source );
485  assert ( source->rc == rc );
486  err_enable_working:
487  return rc;
488 }
489 
490 /* Drag in objects via entropy_enable */
492 
493 /* Drag in entropy configuration */
494 REQUIRE_OBJECT ( config_entropy );
#define __attribute__(x)
Definition: compiler.h:10
int rc
Failure status (if any)
Definition: entropy.h:143
struct arbelprm_rc_send_wqe rc
Definition: arbel.h:14
unsigned int tested
Number of startup tests performed.
Definition: entropy.h:106
Error codes.
#define MIN_ENTROPY_SCALE
Fixed-point scale for min-entropy amounts.
Definition: entropy.h:34
void(* disable)(void)
Disable entropy gathering.
Definition: entropy.h:155
static int repetition_count_test(struct entropy_source *source, noise_sample_t sample)
Perform repetition count test.
Definition: entropy.c:77
int(* enable)(void)
Enable entropy gathering.
Definition: entropy.h:150
#define DBGC(...)
Definition: compiler.h:505
#define ENOENT
No such file or directory.
Definition: errno.h:514
Cryptographic API.
min_entropy_t min_entropy_per_sample
min-entropy per sample
Definition: entropy.h:131
static void adaptive_proportion_test_init(struct entropy_source *source)
Initialise adaptive proportion test.
Definition: entropy.c:128
Hash-based derivation function (Hash_df)
#define EPIPE_ADAPTIVE_PROPORTION_TEST
Definition: entropy.c:48
#define ENTROPY_SOURCES
Entropy source table.
Definition: entropy.h:169
An entropy source.
Definition: entropy.h:116
int get_entropy_input_tmp(min_entropy_t min_entropy, uint8_t *tmp, size_t tmp_len)
Obtain entropy input temporary buffer.
Definition: entropy.c:425
static int startup_test(struct entropy_source *source)
Perform startup test.
Definition: entropy.c:279
static int adaptive_proportion_test(struct entropy_source *source, noise_sample_t sample)
Perform adaptive proportion test.
Definition: entropy.c:151
const char * name
Name.
Definition: entropy.h:118
static uint32_t make_next_nonce(void)
Create next nonce value.
Definition: entropy.c:402
unsigned long tmp
Definition: linux_pci.h:53
#define EPIPE_REPETITION_COUNT_TEST
Definition: entropy.c:44
Repetition count test state.
Definition: entropy.h:51
struct entropy_repetition_count_test repetition_count_test
Repetition count test state.
Definition: entropy.h:133
Assertions.
assert((readw(&hdr->flags) &(GTF_reading|GTF_writing))==0)
struct entropy_startup_test startup_test
Startup test state.
Definition: entropy.h:137
static void startup_test_init(struct entropy_source *source)
Initialise startup test.
Definition: entropy.c:265
static void repetition_count_test_init(struct entropy_source *source)
Initialise repetition count test.
Definition: entropy.c:58
char * strerror(int errno)
Retrieve string representation of error number.
Definition: strerror.c:78
REQUIRING_SYMBOL(entropy_enable)
void hash_df(struct digest_algorithm *hash, const void *input, size_t input_len, void *output, size_t output_len)
Distribute entropy throughout a buffer.
Definition: hash_df.c:84
#define for_each_table_entry(pointer, table)
Iterate through all entries within a linker table.
Definition: tables.h:385
REQUIRE_OBJECT(config_entropy)
static int get_noise(struct entropy_source *source, noise_sample_t *noise)
Get noise sample.
Definition: entropy.h:208
unsigned char uint8_t
Definition: stdint.h:10
static int entropy_enable_working(struct entropy_source **source)
Enable first working entropy source.
Definition: entropy.c:365
static int get_entropy(struct entropy_source *source, entropy_sample_t *entropy)
Get entropy sample.
Definition: entropy.c:225
int entropy_enable(struct entropy_source *source)
Enable entropy gathering.
Definition: entropy.c:302
#define ADAPTIVE_PROPORTION_WINDOW_SIZE
Window size for the adaptive proportion test.
Definition: entropy.h:353
unsigned int uint32_t
Definition: stdint.h:12
#define MIN_ENTROPY(bits)
Construct a min-entropy fixed-point value.
Definition: entropy.h:42
unsigned int min_entropy_t
An amount of min-entropy.
Definition: entropy.h:31
uint8_t entropy_sample_t
An entropy sample.
Definition: entropy.h:24
Startup test state.
Definition: entropy.h:104
struct entropy_adaptive_proportion_test adaptive_proportion_test
Adaptive proportion test state.
Definition: entropy.h:135
unsigned int count
Number of startup tests required for one full cycle.
Definition: entropy.h:112
uint8_t data[48]
Additional event data.
Definition: ena.h:22
uint8_t noise_sample_t
A noise sample.
Definition: entropy.h:21
#define entropy_hash_df_algorithm
Use SHA-256 as the underlying hash algorithm for Hash_df.
Definition: entropy.h:192
void entropy_disable(struct entropy_source *source)
Disable entropy gathering.
Definition: entropy.c:385
String functions.
FILE_LICENCE(GPL2_OR_LATER_OR_UBDL)
Entropy source.
static int entropy_enable_and_test(struct entropy_source *source)
Enable and test entropy source.
Definition: entropy.c:337
struct ntlm_nonce nonce
Server nonce.
Definition: ntlm.h:18
static int test
Definition: epic100.c:73
Adaptive proportion test state.
Definition: entropy.h:75
void * memset(void *dest, int character, size_t len) __nonnull