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  * Calculate cutoff value for the repetition count test
55  *
56  * @ret cutoff Cutoff value
57  *
58  * This is the cutoff value for the Repetition Count Test defined in
59  * ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.2.
60  */
61 static inline __attribute__ (( always_inline )) unsigned int
62 repetition_count_cutoff ( void ) {
63  double max_repetitions;
64  unsigned int cutoff;
65 
66  /* The cutoff formula for the repetition test is:
67  *
68  * C = ( 1 + ( -log2(W) / H_min ) )
69  *
70  * where W is set at 2^(-30) (in ANS X9.82 Part 2 (October
71  * 2011 Draft) Section 8.5.2.1.3.1).
72  */
73  max_repetitions = ( 1 + ( MIN_ENTROPY ( 30 ) /
75 
76  /* Round up to a whole number of repetitions. We don't have
77  * the ceil() function available, so do the rounding by hand.
78  */
79  cutoff = max_repetitions;
80  if ( cutoff < max_repetitions )
81  cutoff++;
82  linker_assert ( ( cutoff >= max_repetitions ), rounding_error );
83 
84  /* Floating-point operations are not allowed in iPXE since we
85  * never set up a suitable environment. Abort the build
86  * unless the calculated number of repetitions is a
87  * compile-time constant.
88  */
89  linker_assert ( __builtin_constant_p ( cutoff ),
90  repetition_count_cutoff_not_constant );
91 
92  return cutoff;
93 }
94 
95 /**
96  * Perform repetition count test
97  *
98  * @v sample Noise sample
99  * @ret rc Return status code
100  *
101  * This is the Repetition Count Test defined in ANS X9.82 Part 2
102  * (October 2011 Draft) Section 8.5.2.1.2.
103  */
104 static int repetition_count_test ( noise_sample_t sample ) {
105  static noise_sample_t most_recent_sample;
106  static unsigned int repetition_count = 0;
107 
108  /* A = the most recently seen sample value
109  * B = the number of times that value A has been seen in a row
110  * C = the cutoff value above which the repetition test should fail
111  */
112 
113  /* 1. For each new sample processed:
114  *
115  * (Note that the test for "repetition_count > 0" ensures that
116  * the initial value of most_recent_sample is treated as being
117  * undefined.)
118  */
119  if ( ( sample == most_recent_sample ) && ( repetition_count > 0 ) ) {
120 
121  /* a) If the new sample = A, then B is incremented by one. */
122  repetition_count++;
123 
124  /* i. If B >= C, then an error condition is raised
125  * due to a failure of the test
126  */
127  if ( repetition_count >= repetition_count_cutoff() )
129 
130  } else {
131 
132  /* b) Else:
133  * i. A = new sample
134  */
135  most_recent_sample = sample;
136 
137  /* ii. B = 1 */
138  repetition_count = 1;
139  }
140 
141  return 0;
142 }
143 
144 /**
145  * Window size for the adaptive proportion test
146  *
147  * ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.3.1.1 allows
148  * five possible window sizes: 16, 64, 256, 4096 and 65536.
149  *
150  * We expect to generate relatively few (<256) entropy samples during
151  * a typical iPXE run; the use of a large window size would mean that
152  * the test would never complete a single cycle. We use a window size
153  * of 64, which is the smallest window size that permits values of
154  * H_min down to one bit per sample.
155  */
156 #define ADAPTIVE_PROPORTION_WINDOW_SIZE 64
157 
158 /**
159  * Combine adaptive proportion test window size and min-entropy
160  *
161  * @v n N (window size)
162  * @v h H (min-entropy)
163  * @ret n_h (N,H) combined value
164  */
165 #define APC_N_H( n, h ) ( ( (n) << 8 ) | (h) )
166 
167 /**
168  * Define a row of the adaptive proportion cutoff table
169  *
170  * @v h H (min-entropy)
171  * @v c16 Cutoff for N=16
172  * @v c64 Cutoff for N=64
173  * @v c256 Cutoff for N=256
174  * @v c4096 Cutoff for N=4096
175  * @v c65536 Cutoff for N=65536
176  */
177 #define APC_TABLE_ROW( h, c16, c64, c256, c4096, c65536) \
178  case APC_N_H ( 16, h ) : return c16; \
179  case APC_N_H ( 64, h ) : return c64; \
180  case APC_N_H ( 256, h ) : return c256; \
181  case APC_N_H ( 4096, h ) : return c4096; \
182  case APC_N_H ( 65536, h ) : return c65536;
183 
184 /** Value used to represent "N/A" in adaptive proportion cutoff table */
185 #define APC_NA 0
186 
187 /**
188  * Look up value in adaptive proportion test cutoff table
189  *
190  * @v n N (window size)
191  * @v h H (min-entropy)
192  * @ret cutoff Cutoff
193  *
194  * This is the table of cutoff values defined in ANS X9.82 Part 2
195  * (October 2011 Draft) Section 8.5.2.1.3.1.2.
196  */
197 static inline __attribute__ (( always_inline )) unsigned int
198 adaptive_proportion_cutoff_lookup ( unsigned int n, unsigned int h ) {
199  switch ( APC_N_H ( n, h ) ) {
200  APC_TABLE_ROW ( 1, APC_NA, 51, 168, 2240, 33537 );
201  APC_TABLE_ROW ( 2, APC_NA, 35, 100, 1193, 17053 );
202  APC_TABLE_ROW ( 3, 10, 24, 61, 643, 8705 );
203  APC_TABLE_ROW ( 4, 8, 16, 38, 354, 4473 );
204  APC_TABLE_ROW ( 5, 6, 12, 25, 200, 2321 );
205  APC_TABLE_ROW ( 6, 5, 9, 17, 117, 1220 );
206  APC_TABLE_ROW ( 7, 4, 7, 15, 71, 653 );
207  APC_TABLE_ROW ( 8, 4, 5, 9, 45, 358 );
208  APC_TABLE_ROW ( 9, 3, 4, 7, 30, 202 );
209  APC_TABLE_ROW ( 10, 3, 4, 5, 21, 118 );
210  APC_TABLE_ROW ( 11, 2, 3, 4, 15, 71 );
211  APC_TABLE_ROW ( 12, 2, 3, 4, 11, 45 );
212  APC_TABLE_ROW ( 13, 2, 2, 3, 9, 30 );
213  APC_TABLE_ROW ( 14, 2, 2, 3, 7, 21 );
214  APC_TABLE_ROW ( 15, 1, 2, 2, 6, 15 );
215  APC_TABLE_ROW ( 16, 1, 2, 2, 5, 11 );
216  APC_TABLE_ROW ( 17, 1, 1, 2, 4, 9 );
217  APC_TABLE_ROW ( 18, 1, 1, 2, 4, 7 );
218  APC_TABLE_ROW ( 19, 1, 1, 1, 3, 6 );
219  APC_TABLE_ROW ( 20, 1, 1, 1, 3, 5 );
220  default:
221  return APC_NA;
222  }
223 }
224 
225 /**
226  * Calculate cutoff value for the adaptive proportion test
227  *
228  * @ret cutoff Cutoff value
229  *
230  * This is the cutoff value for the Adaptive Proportion Test defined
231  * in ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.3.1.2.
232  */
233 static inline __attribute__ (( always_inline )) unsigned int
234 adaptive_proportion_cutoff ( void ) {
235  unsigned int h;
236  unsigned int n;
237  unsigned int cutoff;
238 
239  /* Look up cutoff value in cutoff table */
242  cutoff = adaptive_proportion_cutoff_lookup ( n, h );
243 
244  /* Fail unless cutoff value is a build-time constant */
245  linker_assert ( __builtin_constant_p ( cutoff ),
246  adaptive_proportion_cutoff_not_constant );
247 
248  /* Fail if cutoff value is N/A */
249  linker_assert ( ( cutoff != APC_NA ),
250  adaptive_proportion_cutoff_not_applicable );
251 
252  return cutoff;
253 }
254 
255 /**
256  * Perform adaptive proportion test
257  *
258  * @v sample Noise sample
259  * @ret rc Return status code
260  *
261  * This is the Adaptive Proportion Test for the Most Common Value
262  * defined in ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.3.
263  */
265  static noise_sample_t current_counted_sample;
266  static unsigned int sample_count = ADAPTIVE_PROPORTION_WINDOW_SIZE;
267  static unsigned int repetition_count;
268 
269  /* A = the sample value currently being counted
270  * B = the number of samples examined in this run of the test so far
271  * N = the total number of samples that must be observed in
272  * one run of the test, also known as the "window size" of
273  * the test
274  * B = the current number of times that S (sic) has been seen
275  * in the W (sic) samples examined so far
276  * C = the cutoff value above which the repetition test should fail
277  * W = the probability of a false positive: 2^-30
278  */
279 
280  /* 1. The entropy source draws the current sample from the
281  * noise source.
282  *
283  * (Nothing to do; we already have the current sample.)
284  */
285 
286  /* 2. If S = N, then a new run of the test begins: */
287  if ( sample_count == ADAPTIVE_PROPORTION_WINDOW_SIZE ) {
288 
289  /* a. A = the current sample */
290  current_counted_sample = sample;
291 
292  /* b. S = 0 */
293  sample_count = 0;
294 
295  /* c. B = 0 */
296  repetition_count = 0;
297 
298  } else {
299 
300  /* Else: (the test is already running)
301  * a. S = S + 1
302  */
303  sample_count++;
304 
305  /* b. If A = the current sample, then: */
306  if ( sample == current_counted_sample ) {
307 
308  /* i. B = B + 1 */
309  repetition_count++;
310 
311  /* ii. If S (sic) > C then raise an error
312  * condition, because the test has
313  * detected a failure
314  */
315  if ( repetition_count > adaptive_proportion_cutoff() )
317 
318  }
319  }
320 
321  return 0;
322 }
323 
324 /**
325  * Get entropy sample
326  *
327  * @ret entropy Entropy sample
328  * @ret rc Return status code
329  *
330  * This is the GetEntropy function defined in ANS X9.82 Part 2
331  * (October 2011 Draft) Section 6.5.1.
332  */
333 static int get_entropy ( entropy_sample_t *entropy ) {
334  static int rc = 0;
335  noise_sample_t noise;
336 
337  /* Any failure is permanent */
338  if ( rc != 0 )
339  return rc;
340 
341  /* Get noise sample */
342  if ( ( rc = get_noise ( &noise ) ) != 0 )
343  return rc;
344 
345  /* Perform Repetition Count Test and Adaptive Proportion Test
346  * as mandated by ANS X9.82 Part 2 (October 2011 Draft)
347  * Section 8.5.2.1.1.
348  */
349  if ( ( rc = repetition_count_test ( noise ) ) != 0 )
350  return rc;
351  if ( ( rc = adaptive_proportion_test ( noise ) ) != 0 )
352  return rc;
353 
354  /* We do not use any optional conditioning component */
355  *entropy = noise;
356 
357  return 0;
358 }
359 
360 /**
361  * Calculate number of samples required for startup tests
362  *
363  * @ret num_samples Number of samples required
364  *
365  * ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.5 requires
366  * that at least one full cycle of the continuous tests must be
367  * performed at start-up.
368  */
369 static inline __attribute__ (( always_inline )) unsigned int
370 startup_test_count ( void ) {
371  unsigned int num_samples;
372 
373  /* At least max(N,C) samples shall be generated by the noise
374  * source for start-up testing.
375  */
376  num_samples = repetition_count_cutoff();
377  if ( num_samples < adaptive_proportion_cutoff() )
378  num_samples = adaptive_proportion_cutoff();
379  linker_assert ( __builtin_constant_p ( num_samples ),
380  startup_test_count_not_constant );
381 
382  return num_samples;
383 }
384 
385 /**
386  * Create next nonce value
387  *
388  * @ret nonce Nonce
389  *
390  * This is the MakeNextNonce function defined in ANS X9.82 Part 4
391  * (April 2011 Draft) Section 13.3.4.2.
392  */
393 static uint32_t make_next_nonce ( void ) {
394  static uint32_t nonce;
395 
396  /* The simplest implementation of a nonce uses a large counter */
397  nonce++;
398 
399  return nonce;
400 }
401 
402 /**
403  * Obtain entropy input temporary buffer
404  *
405  * @v num_samples Number of entropy samples
406  * @v tmp Temporary buffer
407  * @v tmp_len Length of temporary buffer
408  * @ret rc Return status code
409  *
410  * This is (part of) the implementation of the Get_entropy_input
411  * function (using an entropy source as the source of entropy input
412  * and condensing each entropy source output after each GetEntropy
413  * call) as defined in ANS X9.82 Part 4 (April 2011 Draft) Section
414  * 13.3.4.2.
415  *
416  * To minimise code size, the number of samples required is calculated
417  * at compilation time.
418  */
420  size_t tmp_len ) {
421  static unsigned int startup_tested = 0;
422  struct {
423  uint32_t nonce;
424  entropy_sample_t sample;
425  } __attribute__ (( packed )) data;;
426  uint8_t df_buf[tmp_len];
427  unsigned int i;
428  int rc;
429 
430  /* Enable entropy gathering */
431  if ( ( rc = entropy_enable() ) != 0 )
432  return rc;
433 
434  /* Perform mandatory startup tests, if not yet performed */
435  for ( ; startup_tested < startup_test_count() ; startup_tested++ ) {
436  if ( ( rc = get_entropy ( &data.sample ) ) != 0 )
437  goto err_get_entropy;
438  }
439 
440  /* 3. entropy_total = 0
441  *
442  * (Nothing to do; the number of entropy samples required has
443  * already been precalculated.)
444  */
445 
446  /* 4. tmp = a fixed n-bit value, such as 0^n */
447  memset ( tmp, 0, tmp_len );
448 
449  /* 5. While ( entropy_total < min_entropy ) */
450  while ( num_samples-- ) {
451  /* 5.1. ( status, entropy_bitstring, assessed_entropy )
452  * = GetEntropy()
453  * 5.2. If status indicates an error, return ( status, Null )
454  */
455  if ( ( rc = get_entropy ( &data.sample ) ) != 0 )
456  goto err_get_entropy;
457 
458  /* 5.3. nonce = MakeNextNonce() */
459  data.nonce = make_next_nonce();
460 
461  /* 5.4. tmp = tmp XOR
462  * df ( ( nonce || entropy_bitstring ), n )
463  */
464  hash_df ( &entropy_hash_df_algorithm, &data, sizeof ( data ),
465  df_buf, sizeof ( df_buf ) );
466  for ( i = 0 ; i < tmp_len ; i++ )
467  tmp[i] ^= df_buf[i];
468 
469  /* 5.5. entropy_total = entropy_total + assessed_entropy
470  *
471  * (Nothing to do; the number of entropy samples
472  * required has already been precalculated.)
473  */
474  }
475 
476  /* Disable entropy gathering */
477  entropy_disable();
478 
479  return 0;
480 
481  err_get_entropy:
482  entropy_disable();
483  return rc;
484 }
struct arbelprm_rc_send_wqe rc
Definition: arbel.h:14
void entropy_disable(void)
Disable entropy gathering.
return tmp_len
Definition: entropy.h:241
static __attribute__((always_inline))
Calculate cutoff value for the repetition count test.
Definition: entropy.c:61
#define APC_NA
Value used to represent "N/A" in adaptive proportion cutoff table.
Definition: entropy.c:185
Error codes.
#define MIN_ENTROPY_SCALE
Fixed-point scale for min-entropy amounts.
Definition: entropy.h:63
min_entropy_t min_entropy_per_sample(void)
min-entropy per sample
unsigned int num_samples
Definition: entropy.h:158
int get_noise(noise_sample_t *noise)
Get noise sample.
Cryptographic API.
int get_entropy_input_tmp(unsigned int num_samples, uint8_t *tmp, size_t tmp_len)
Obtain entropy input temporary buffer.
Definition: entropy.c:419
Hash-based derivation function (Hash_df)
#define EPIPE_ADAPTIVE_PROPORTION_TEST
Definition: entropy.c:48
static int adaptive_proportion_test(noise_sample_t sample)
Perform adaptive proportion test.
Definition: entropy.c:264
static uint32_t make_next_nonce(void)
Create next nonce value.
Definition: entropy.c:393
#define EPIPE_REPETITION_COUNT_TEST
Definition: entropy.c:44
Assertions.
#define APC_N_H(n, h)
Combine adaptive proportion test window size and min-entropy.
Definition: entropy.c:165
uint8_t h
Definition: registers.h:18
int entropy_enable(void)
Enable entropy gathering.
uint8_t * tmp
Definition: entropy.h:156
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 repetition_count_test(noise_sample_t sample)
Perform repetition count test.
Definition: entropy.c:104
unsigned char uint8_t
Definition: stdint.h:10
unsigned int uint32_t
Definition: stdint.h:12
#define ADAPTIVE_PROPORTION_WINDOW_SIZE
Window size for the adaptive proportion test.
Definition: entropy.c:156
#define APC_TABLE_ROW(h, c16, c64, c256, c4096, c65536)
Define a row of the adaptive proportion cutoff table.
Definition: entropy.c:177
#define MIN_ENTROPY(bits)
Construct a min-entropy fixed-point value.
Definition: entropy.h:71
uint8_t entropy_sample_t
An entropy sample.
Definition: entropy.h:53
static int get_entropy(entropy_sample_t *entropy)
Get entropy sample.
Definition: entropy.c:333
uint8_t noise_sample_t
A noise sample.
Definition: entropy.h:50
#define entropy_hash_df_algorithm
Use SHA-256 as the underlying hash algorithm for Hash_df.
Definition: entropy.h:129
unsigned int n
Definition: entropy.h:159
struct arbelprm_port_state_change_st data
Message.
Definition: arbel.h:12
#define linker_assert(condition, error_symbol)
Assert a condition at link-time.
Definition: assert.h:68
String functions.
FILE_LICENCE(GPL2_OR_LATER_OR_UBDL)
Entropy source.
struct ntlm_nonce nonce
Server nonce.
Definition: ntlm.h:18
void * memset(void *dest, int character, size_t len) __nonnull