iPXE
entropy.h
Go to the documentation of this file.
1 #ifndef _IPXE_ENTROPY_H
2 #define _IPXE_ENTROPY_H
3 
4 /** @file
5  *
6  * Entropy source
7  *
8  */
9 
10 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
11 
12 #include <stdint.h>
13 #include <string.h>
14 #include <assert.h>
15 #include <ipxe/hash_df.h>
16 #include <ipxe/sha256.h>
17 #include <ipxe/tables.h>
18 #include <config/entropy.h>
19 
20 /** A noise sample */
22 
23 /** An entropy sample */
25 
26 /** An amount of min-entropy
27  *
28  * Expressed as a fixed-point quantity in order to avoid floating
29  * point calculations.
30  */
31 typedef unsigned int min_entropy_t;
32 
33 /** Fixed-point scale for min-entropy amounts */
34 #define MIN_ENTROPY_SCALE ( 1 << 16 )
35 
36 /**
37  * Construct a min-entropy fixed-point value
38  *
39  * @v bits min-entropy in bits
40  * @ret min_entropy min-entropy as a fixed-point value
41  */
42 #define MIN_ENTROPY( bits ) \
43  ( ( min_entropy_t ) ( (bits) * MIN_ENTROPY_SCALE ) )
44 
45 /**
46  * Repetition count test state
47  *
48  * This is the state for the repetition Count Test defined in ANS
49  * X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.2.
50  */
52  /**
53  * A = the most recently seen sample value
54  */
56  /**
57  * B = the number of times that value A has been seen in a row
58  */
59  unsigned int repetition_count;
60  /**
61  * C = the cutoff value above which the repetition test should fail
62  *
63  * Filled in by entropy_init().
64  */
65  unsigned int cutoff;
66 };
67 
68 /**
69  * Adaptive proportion test state
70  *
71  * This is the state for the Adaptive Proportion Test for the Most
72  * Common Value defined in ANS X9.82 Part 2 (October 2011 Draft)
73  * Section 8.5.2.1.3.
74  */
76  /**
77  * A = the sample value currently being counted
78  */
80  /**
81  * S = the number of samples examined in this run of the test so far
82  */
83  unsigned int sample_count;
84  /**
85  * B = the current number of times that S (sic) has been seen
86  * in the W (sic) samples examined so far
87  */
88  unsigned int repetition_count;
89  /**
90  * C = the cutoff value above which the repetition test should fail
91  *
92  * Filled in by entropy_init().
93  */
94  unsigned int cutoff;
95 };
96 
97 /**
98  * Startup test state
99  *
100  * ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.5 requires
101  * that at least one full cycle of the continuous tests must be
102  * performed at start-up.
103  */
105  /** Number of startup tests performed */
106  unsigned int tested;
107  /**
108  * Number of startup tests required for one full cycle
109  *
110  * Filled in by entropy_init().
111  */
112  unsigned int count;
113 };
114 
115 /** An entropy source */
117  /** Name */
118  const char *name;
119  /**
120  * min-entropy per sample
121  *
122  * min-entropy is defined in ANS X9.82 Part 1-2006 Section 8.3 and in
123  * NIST SP 800-90 Appendix C.3 as
124  *
125  * H_min = -log2 ( p_max )
126  *
127  * where p_max is the probability of the most likely sample value.
128  *
129  * Filled in by entropy_init().
130  */
132  /** Repetition count test state */
134  /** Adaptive proportion test state */
136  /** Startup test state */
138  /**
139  * Failure status (if any)
140  *
141  * Any failure of an entropy source is regarded as permanent.
142  */
143  int rc;
144 
145  /**
146  * Enable entropy gathering
147  *
148  * @ret rc Return status code
149  */
150  int ( * enable ) ( void );
151  /**
152  * Disable entropy gathering
153  *
154  */
155  void ( * disable ) ( void );
156  /**
157  * Get noise sample
158  *
159  * @ret noise Noise sample
160  * @ret rc Return status code
161  *
162  * This is the GetNoise function defined in ANS X9.82 Part 2
163  * (October 2011 Draft) Section 6.5.2.
164  */
165  int ( * get_noise ) ( noise_sample_t *noise );
166 };
167 
168 /** Entropy source table */
169 #define ENTROPY_SOURCES __table ( struct entropy_source, "entropy_sources" )
170 
171 /** Declare an entropy source */
172 #define __entropy_source( order ) __table_entry ( ENTROPY_SOURCES, order )
173 
174 /** @defgroup entropy_source_order Entropy source order
175  *
176  * @{
177  */
178 
179 #define ENTROPY_PREFERRED 01 /**< Preferred entropy source */
180 #define ENTROPY_NORMAL 02 /**< Normal entropy source */
181 #define ENTROPY_FALLBACK 03 /**< Fallback entropy source */
182 
183 /** @} */
184 
185 extern int get_entropy_input_tmp ( min_entropy_t min_entropy, uint8_t *tmp,
186  size_t tmp_len );
187 
188 /** Use SHA-256 as the underlying hash algorithm for Hash_df
189  *
190  * Hash_df using SHA-256 is an Approved algorithm in ANS X9.82.
191  */
192 #define entropy_hash_df_algorithm sha256_algorithm
193 
194 /** Underlying hash algorithm output length (in bytes) */
195 #define ENTROPY_HASH_DF_OUTLEN_BYTES SHA256_DIGEST_SIZE
196 
197 /**
198  * Get noise sample
199  *
200  * @v source Entropy source
201  * @ret noise Noise sample
202  * @ret rc Return status code
203  *
204  * This is the GetNoise function defined in ANS X9.82 Part 2
205  * (October 2011 Draft) Section 6.5.2.
206  */
207 static inline __attribute__ (( always_inline )) int
208 get_noise ( struct entropy_source *source, noise_sample_t *noise ) {
209 
210  return source->get_noise ( noise );
211 }
212 
213 /**
214  * Obtain entropy input
215  *
216  * @v min_entropy_bits Minimum amount of entropy, in bits
217  * @v data Data buffer
218  * @v min_len Minimum length of entropy input, in bytes
219  * @v max_len Maximum length of entropy input, in bytes
220  * @ret len Length of entropy input, in bytes, or negative error
221  *
222  * This is the implementation of the Get_entropy_input function (using
223  * an entropy source as the source of entropy input and condensing
224  * each entropy source output after each GetEntropy call) as defined
225  * in ANS X9.82 Part 4 (April 2011 Draft) Section 13.3.4.2.
226  *
227  * This function is inlined since the entropy amount and length inputs
228  * are always compile-time constants.
229  */
230 static inline __attribute__ (( always_inline )) int
231 get_entropy_input ( unsigned int min_entropy_bits, void *data, size_t min_len,
232  size_t max_len ) {
233  size_t tmp_len = ( ( ( min_entropy_bits * 2 ) + 7 ) / 8 );
234  uint8_t tmp_buf[ tmp_len ];
235  uint8_t *tmp = ( ( tmp_len > max_len ) ? tmp_buf : data );
236  unsigned int n;
237  int rc;
238 
239  /* Sanity check */
240  build_assert ( min_entropy_bits <= ( 8 * max_len ) );
241 
242  /* Round up minimum entropy to an integral number of bytes */
243  min_entropy_bits = ( ( min_entropy_bits + 7 ) & ~7 );
244 
245  /* (Unnumbered). The output length of the hash function shall
246  * meet or exceed the security strength indicated by the
247  * min_entropy parameter.
248  */
250  min_entropy_bits );
251 
252  /* 1. If ( min_length > max_length ), then return ( FAILURE, Null ) */
253  build_assert ( min_len <= max_len );
254 
255  /* 2. n = 2 * min_entropy */
256  n = ( 2 * min_entropy_bits );
257 
258  /* 3. entropy_total = 0
259  * 4. tmp = a fixed n-bit value, such as 0^n
260  * 5. While ( entropy_total < min_entropy )
261  * 5.1. ( status, entropy_bitstring, assessed_entropy )
262  * = GetEntropy()
263  * 5.2. If status indicates an error, return ( status, Null )
264  * 5.3. nonce = MakeNextNonce()
265  * 5.4. tmp = tmp XOR df ( ( nonce || entropy_bitstring ), n )
266  * 5.5. entropy_total = entropy_total + assessed_entropy
267  *
268  * (The implementation of these steps is inside the function
269  * get_entropy_input_tmp().)
270  */
271  build_assert ( __builtin_constant_p ( tmp_len ) );
272  build_assert ( n == ( 8 * tmp_len ) );
273  if ( ( rc = get_entropy_input_tmp ( MIN_ENTROPY ( min_entropy_bits ),
274  tmp, tmp_len ) ) != 0 ) {
275  return rc;
276  }
277 
278  /* 6. If ( n < min_length ), then tmp = tmp || 0^(min_length-n)
279  * 7. If ( n > max_length ), then tmp = df ( tmp, max_length )
280  * 8. Return ( SUCCESS, tmp )
281  */
282  if ( tmp_len < min_len ) {
283  /* (Data is already in-place.) */
284  build_assert ( data == tmp );
285  memset ( ( data + tmp_len ), 0, ( min_len - tmp_len ) );
286  return min_len;
287  } else if ( tmp_len > max_len ) {
288  build_assert ( tmp == tmp_buf );
290  data, max_len );
291  return max_len;
292  } else {
293  /* (Data is already in-place.) */
294  build_assert ( data == tmp );
295  return tmp_len;
296  }
297 }
298 
299 /**
300  * Calculate cutoff value for the repetition count test
301  *
302  * @v min_entropy_per_sample Min-entropy per sample
303  * @ret cutoff Cutoff value
304  *
305  * This is the cutoff value for the Repetition Count Test defined in
306  * ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.2.
307  */
308 static inline __attribute__ (( always_inline )) unsigned int
309 entropy_repetition_count_cutoff ( min_entropy_t min_entropy_per_sample ) {
310  double max_repetitions;
311  unsigned int cutoff;
312 
313  /* The cutoff formula for the repetition test is:
314  *
315  * C = ( 1 + ( -log2(W) / H_min ) )
316  *
317  * where W is set at 2^(-30) (in ANS X9.82 Part 2 (October
318  * 2011 Draft) Section 8.5.2.1.3.1).
319  */
320  max_repetitions = ( 1 + ( MIN_ENTROPY ( 30 ) /
321  min_entropy_per_sample ) );
322 
323  /* Round up to a whole number of repetitions. We don't have
324  * the ceil() function available, so do the rounding by hand.
325  */
326  cutoff = max_repetitions;
327  if ( cutoff < max_repetitions )
328  cutoff++;
329  build_assert ( cutoff >= max_repetitions );
330 
331  /* Floating-point operations are not allowed in iPXE since we
332  * never set up a suitable environment. Abort the build
333  * unless the calculated number of repetitions is a
334  * compile-time constant.
335  */
336  build_assert ( __builtin_constant_p ( cutoff ) );
337 
338  return cutoff;
339 }
340 
341 /**
342  * Window size for the adaptive proportion test
343  *
344  * ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.3.1.1 allows
345  * five possible window sizes: 16, 64, 256, 4096 and 65536.
346  *
347  * We expect to generate relatively few (<256) entropy samples during
348  * a typical iPXE run; the use of a large window size would mean that
349  * the test would never complete a single cycle. We use a window size
350  * of 64, which is the smallest window size that permits values of
351  * H_min down to one bit per sample.
352  */
353 #define ADAPTIVE_PROPORTION_WINDOW_SIZE 64
354 
355 /**
356  * Combine adaptive proportion test window size and min-entropy
357  *
358  * @v n N (window size)
359  * @v h H (min-entropy)
360  * @ret n_h (N,H) combined value
361  */
362 #define APC_N_H( n, h ) ( ( (n) << 8 ) | (h) )
363 
364 /**
365  * Define a row of the adaptive proportion cutoff table
366  *
367  * @v h H (min-entropy)
368  * @v c16 Cutoff for N=16
369  * @v c64 Cutoff for N=64
370  * @v c256 Cutoff for N=256
371  * @v c4096 Cutoff for N=4096
372  * @v c65536 Cutoff for N=65536
373  */
374 #define APC_TABLE_ROW( h, c16, c64, c256, c4096, c65536) \
375  case APC_N_H ( 16, h ) : return c16; \
376  case APC_N_H ( 64, h ) : return c64; \
377  case APC_N_H ( 256, h ) : return c256; \
378  case APC_N_H ( 4096, h ) : return c4096; \
379  case APC_N_H ( 65536, h ) : return c65536;
380 
381 /** Value used to represent "N/A" in adaptive proportion cutoff table */
382 #define APC_NA 0
383 
384 /**
385  * Look up value in adaptive proportion test cutoff table
386  *
387  * @v n N (window size)
388  * @v h H (min-entropy)
389  * @ret cutoff Cutoff
390  *
391  * This is the table of cutoff values defined in ANS X9.82 Part 2
392  * (October 2011 Draft) Section 8.5.2.1.3.1.2.
393  */
394 static inline __attribute__ (( always_inline )) unsigned int
395 entropy_adaptive_proportion_cutoff_lookup ( unsigned int n, unsigned int h ) {
396  switch ( APC_N_H ( n, h ) ) {
397  APC_TABLE_ROW ( 1, APC_NA, 51, 168, 2240, 33537 );
398  APC_TABLE_ROW ( 2, APC_NA, 35, 100, 1193, 17053 );
399  APC_TABLE_ROW ( 3, 10, 24, 61, 643, 8705 );
400  APC_TABLE_ROW ( 4, 8, 16, 38, 354, 4473 );
401  APC_TABLE_ROW ( 5, 6, 12, 25, 200, 2321 );
402  APC_TABLE_ROW ( 6, 5, 9, 17, 117, 1220 );
403  APC_TABLE_ROW ( 7, 4, 7, 15, 71, 653 );
404  APC_TABLE_ROW ( 8, 4, 5, 9, 45, 358 );
405  APC_TABLE_ROW ( 9, 3, 4, 7, 30, 202 );
406  APC_TABLE_ROW ( 10, 3, 4, 5, 21, 118 );
407  APC_TABLE_ROW ( 11, 2, 3, 4, 15, 71 );
408  APC_TABLE_ROW ( 12, 2, 3, 4, 11, 45 );
409  APC_TABLE_ROW ( 13, 2, 2, 3, 9, 30 );
410  APC_TABLE_ROW ( 14, 2, 2, 3, 7, 21 );
411  APC_TABLE_ROW ( 15, 1, 2, 2, 6, 15 );
412  APC_TABLE_ROW ( 16, 1, 2, 2, 5, 11 );
413  APC_TABLE_ROW ( 17, 1, 1, 2, 4, 9 );
414  APC_TABLE_ROW ( 18, 1, 1, 2, 4, 7 );
415  APC_TABLE_ROW ( 19, 1, 1, 1, 3, 6 );
416  APC_TABLE_ROW ( 20, 1, 1, 1, 3, 5 );
417  default:
418  return APC_NA;
419  }
420 }
421 
422 /**
423  * Calculate cutoff value for the adaptive proportion test
424  *
425  * @v min_entropy_per_sample Min-entropy per sample
426  * @ret cutoff Cutoff value
427  *
428  * This is the cutoff value for the Adaptive Proportion Test defined
429  * in ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.3.1.2.
430  */
431 static inline __attribute__ (( always_inline )) unsigned int
433  unsigned int h;
434  unsigned int n;
435  unsigned int cutoff;
436 
437  /* Look up cutoff value in cutoff table */
439  h = ( min_entropy_per_sample / MIN_ENTROPY_SCALE );
441 
442  /* Fail unless cutoff value is a compile-time constant */
443  build_assert ( __builtin_constant_p ( cutoff ) );
444 
445  /* Fail if cutoff value is N/A */
446  build_assert ( cutoff != APC_NA );
447 
448  return cutoff;
449 }
450 
451 /**
452  * Calculate number of samples required for startup tests
453  *
454  * @v repetition_count_cutoff Repetition count test cutoff value
455  * @v adaptive_proportion_cutoff Adaptive proportion test cutoff value
456  * @ret num_samples Number of samples required
457  *
458  * ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.5 requires
459  * that at least one full cycle of the continuous tests must be
460  * performed at start-up.
461  */
462 static inline __attribute__ (( always_inline )) unsigned int
463 entropy_startup_test_count ( unsigned int repetition_count_cutoff,
464  unsigned int adaptive_proportion_cutoff ) {
465  unsigned int num_samples;
466 
467  /* At least max(N,C) samples shall be generated by the noise
468  * source for start-up testing.
469  */
470  num_samples = repetition_count_cutoff;
471  if ( num_samples < adaptive_proportion_cutoff )
472  num_samples = adaptive_proportion_cutoff;
473  build_assert ( __builtin_constant_p ( num_samples ) );
474 
475  return num_samples;
476 }
477 
478 /**
479  * Initialise entropy source
480  *
481  * @v source Entropy source
482  * @v min_entropy_per_sample Min-entropy per sample
483  *
484  * The cutoff value calculations for the repetition count test and the
485  * adaptive proportion test are provided as static inline functions
486  * since the results will always be compile-time constants.
487  */
488 static inline __attribute__ (( always_inline )) void
489 entropy_init ( struct entropy_source *source,
490  min_entropy_t min_entropy_per_sample ) {
491  unsigned int repetition_count_cutoff;
492  unsigned int adaptive_proportion_cutoff;
493  unsigned int startup_test_count;
494 
495  /* Sanity check */
496  build_assert ( min_entropy_per_sample > MIN_ENTROPY ( 0 ) );
497  build_assert ( min_entropy_per_sample <=
498  MIN_ENTROPY ( 8 * sizeof ( noise_sample_t ) ) );
499 
500  /* Calculate test cutoff values */
501  repetition_count_cutoff =
502  entropy_repetition_count_cutoff ( min_entropy_per_sample );
503  adaptive_proportion_cutoff =
504  entropy_adaptive_proportion_cutoff ( min_entropy_per_sample );
505  startup_test_count =
506  entropy_startup_test_count ( repetition_count_cutoff,
507  adaptive_proportion_cutoff );
508 
509  /* Record min-entropy per sample and test cutoff values */
510  source->min_entropy_per_sample = min_entropy_per_sample;
511  source->repetition_count_test.cutoff = repetition_count_cutoff;
512  source->adaptive_proportion_test.cutoff = adaptive_proportion_cutoff;
513  source->startup_test.count = startup_test_count;
514 }
515 
516 extern int entropy_enable ( struct entropy_source *source );
517 extern void entropy_disable ( struct entropy_source *source );
518 extern int get_noise ( struct entropy_source *source, noise_sample_t *noise );
519 
520 #endif /* _IPXE_ENTROPY_H */
#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
static int get_entropy_input(unsigned int min_entropy_bits, void *data, size_t min_len, size_t max_len)
Obtain entropy input.
Definition: entropy.h:231
static unsigned int entropy_adaptive_proportion_cutoff(min_entropy_t min_entropy_per_sample)
Calculate cutoff value for the adaptive proportion test.
Definition: entropy.h:432
#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
uint16_t max_len
Maximum length (in bytes)
Definition: ntlm.h:18
int(* enable)(void)
Enable entropy gathering.
Definition: entropy.h:150
static unsigned int entropy_startup_test_count(unsigned int repetition_count_cutoff, unsigned int adaptive_proportion_cutoff)
Calculate number of samples required for startup tests.
Definition: entropy.h:463
min_entropy_t min_entropy_per_sample
min-entropy per sample
Definition: entropy.h:131
Hash-based derivation function (Hash_df)
An entropy source.
Definition: entropy.h:116
const char * name
Name.
Definition: entropy.h:118
unsigned long tmp
Definition: linux_pci.h:53
void entropy_disable(struct entropy_source *source)
Disable entropy gathering.
Definition: entropy.c:385
Repetition count test state.
Definition: entropy.h:51
struct entropy_repetition_count_test repetition_count_test
Repetition count test state.
Definition: entropy.h:133
Entropy API configuration.
Assertions.
struct entropy_startup_test startup_test
Startup test state.
Definition: entropy.h:137
uint32_t h
Definition: sha256.c:35
static unsigned int entropy_repetition_count_cutoff(min_entropy_t min_entropy_per_sample)
Calculate cutoff value for the repetition count test.
Definition: entropy.h:309
#define build_assert(condition)
Assert a condition at build time (after dead code elimination)
Definition: assert.h:76
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
#define APC_N_H(n, h)
Combine adaptive proportion test window size and min-entropy.
Definition: entropy.h:362
noise_sample_t most_recent_sample
A = the most recently seen sample value.
Definition: entropy.h:55
int(* get_noise)(noise_sample_t *noise)
Get noise sample.
Definition: entropy.h:165
static unsigned int entropy_adaptive_proportion_cutoff_lookup(unsigned int n, unsigned int h)
Look up value in adaptive proportion test cutoff table.
Definition: entropy.h:395
unsigned int repetition_count
B = the number of times that value A has been seen in a row.
Definition: entropy.h:59
#define ENTROPY_HASH_DF_OUTLEN_BYTES
Underlying hash algorithm output length (in bytes)
Definition: entropy.h:195
unsigned int sample_count
S = the number of samples examined in this run of the test so far.
Definition: entropy.h:83
int entropy_enable(struct entropy_source *source)
Enable entropy gathering.
Definition: entropy.c:302
unsigned int repetition_count
B = the current number of times that S (sic) has been seen in the W (sic) samples examined so far.
Definition: entropy.h:88
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
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
noise_sample_t current_counted_sample
A = the sample value currently being counted.
Definition: entropy.h:79
#define ADAPTIVE_PROPORTION_WINDOW_SIZE
Window size for the adaptive proportion test.
Definition: entropy.h:353
#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
FILE_LICENCE(GPL2_OR_LATER_OR_UBDL)
#define APC_TABLE_ROW(h, c16, c64, c256, c4096, c65536)
Define a row of the adaptive proportion cutoff table.
Definition: entropy.h:374
uint8_t data[48]
Additional event data.
Definition: ena.h:22
Linker tables.
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
unsigned int cutoff
C = the cutoff value above which the repetition test should fail.
Definition: entropy.h:65
#define APC_NA
Value used to represent "N/A" in adaptive proportion cutoff table.
Definition: entropy.h:382
static void entropy_init(struct entropy_source *source, min_entropy_t min_entropy_per_sample)
Initialise entropy source.
Definition: entropy.h:489
SHA-256 algorithm.
unsigned int cutoff
C = the cutoff value above which the repetition test should fail.
Definition: entropy.h:94
String functions.
Adaptive proportion test state.
Definition: entropy.h:75
void * memset(void *dest, int character, size_t len) __nonnull