iPXE
Macros | Functions
entropy.c File Reference

Entropy source. More...

#include <stdint.h>
#include <assert.h>
#include <string.h>
#include <errno.h>
#include <ipxe/crypto.h>
#include <ipxe/hash_df.h>
#include <ipxe/entropy.h>

Go to the source code of this file.

Macros

#define EPIPE_REPETITION_COUNT_TEST   __einfo_error ( EINFO_EPIPE_REPETITION_COUNT_TEST )
 
#define EINFO_EPIPE_REPETITION_COUNT_TEST   __einfo_uniqify ( EINFO_EPIPE, 0x01, "Repetition count test failed" )
 
#define EPIPE_ADAPTIVE_PROPORTION_TEST   __einfo_error ( EINFO_EPIPE_ADAPTIVE_PROPORTION_TEST )
 
#define EINFO_EPIPE_ADAPTIVE_PROPORTION_TEST   __einfo_uniqify ( EINFO_EPIPE, 0x02, "Adaptive proportion test failed" )
 
#define ADAPTIVE_PROPORTION_WINDOW_SIZE   64
 Window size for the adaptive proportion test. More...
 
#define APC_N_H(n, h)   ( ( (n) << 8 ) | (h) )
 Combine adaptive proportion test window size and min-entropy. More...
 
#define APC_TABLE_ROW(h, c16, c64, c256, c4096, c65536)
 Define a row of the adaptive proportion cutoff table. More...
 
#define APC_NA   0
 Value used to represent "N/A" in adaptive proportion cutoff table. More...
 

Functions

 FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
 
static __attribute__ ((always_inline))
 Calculate cutoff value for the repetition count test. More...
 
static int repetition_count_test (noise_sample_t sample)
 Perform repetition count test. More...
 
static int adaptive_proportion_test (noise_sample_t sample)
 Perform adaptive proportion test. More...
 
static int get_entropy (entropy_sample_t *entropy)
 Get entropy sample. More...
 
static uint32_t make_next_nonce (void)
 Create next nonce value. More...
 
int get_entropy_input_tmp (unsigned int num_samples, uint8_t *tmp, size_t tmp_len)
 Obtain entropy input temporary buffer. More...
 

Detailed Description

Entropy source.

This algorithm is designed to comply with ANS X9.82 Part 4 (April 2011 Draft) Section 13.3. This standard is unfortunately not freely available.

Definition in file entropy.c.

Macro Definition Documentation

◆ EPIPE_REPETITION_COUNT_TEST

#define EPIPE_REPETITION_COUNT_TEST   __einfo_error ( EINFO_EPIPE_REPETITION_COUNT_TEST )

Definition at line 44 of file entropy.c.

◆ EINFO_EPIPE_REPETITION_COUNT_TEST

#define EINFO_EPIPE_REPETITION_COUNT_TEST   __einfo_uniqify ( EINFO_EPIPE, 0x01, "Repetition count test failed" )

Definition at line 46 of file entropy.c.

◆ EPIPE_ADAPTIVE_PROPORTION_TEST

#define EPIPE_ADAPTIVE_PROPORTION_TEST   __einfo_error ( EINFO_EPIPE_ADAPTIVE_PROPORTION_TEST )

Definition at line 48 of file entropy.c.

◆ EINFO_EPIPE_ADAPTIVE_PROPORTION_TEST

#define EINFO_EPIPE_ADAPTIVE_PROPORTION_TEST   __einfo_uniqify ( EINFO_EPIPE, 0x02, "Adaptive proportion test failed" )

Definition at line 50 of file entropy.c.

◆ ADAPTIVE_PROPORTION_WINDOW_SIZE

#define ADAPTIVE_PROPORTION_WINDOW_SIZE   64

Window size for the adaptive proportion test.

ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.3.1.1 allows five possible window sizes: 16, 64, 256, 4096 and 65536.

We expect to generate relatively few (<256) entropy samples during a typical iPXE run; the use of a large window size would mean that the test would never complete a single cycle. We use a window size of 64, which is the smallest window size that permits values of H_min down to one bit per sample.

Definition at line 156 of file entropy.c.

◆ APC_N_H

#define APC_N_H (   n,
  h 
)    ( ( (n) << 8 ) | (h) )

Combine adaptive proportion test window size and min-entropy.

Parameters
nN (window size)
hH (min-entropy)
Return values
n_h(N,H) combined value

Definition at line 165 of file entropy.c.

◆ APC_TABLE_ROW

#define APC_TABLE_ROW (   h,
  c16,
  c64,
  c256,
  c4096,
  c65536 
)
Value:
case APC_N_H ( 16, h ) : return c16; \
case APC_N_H ( 64, h ) : return c64; \
case APC_N_H ( 256, h ) : return c256; \
case APC_N_H ( 4096, h ) : return c4096; \
case APC_N_H ( 65536, h ) : return c65536;
#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
return
Definition: natsemi.h:326

Define a row of the adaptive proportion cutoff table.

Parameters
hH (min-entropy)
c16Cutoff for N=16
c64Cutoff for N=64
c256Cutoff for N=256
c4096Cutoff for N=4096
c65536Cutoff for N=65536

Definition at line 177 of file entropy.c.

◆ APC_NA

#define APC_NA   0

Value used to represent "N/A" in adaptive proportion cutoff table.

Definition at line 185 of file entropy.c.

Function Documentation

◆ FILE_LICENCE()

FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL  )

◆ __attribute__()

static __attribute__ ( (always_inline)  )
inlinestatic

Calculate cutoff value for the repetition count test.

Calculate number of samples required for startup tests.

Calculate cutoff value for the adaptive proportion test.

Look up value in adaptive proportion test cutoff table.

Return values
cutoffCutoff value

This is the cutoff value for the Repetition Count Test defined in ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.2.

Parameters
nN (window size)
hH (min-entropy)
Return values
cutoffCutoff

This is the table of cutoff values defined in ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.3.1.2.

Return values
cutoffCutoff value

This is the cutoff value for the Adaptive Proportion Test defined in ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.3.1.2.

Return values
num_samplesNumber of samples required

ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.5 requires that at least one full cycle of the continuous tests must be performed at start-up.

Definition at line 61 of file entropy.c.

62  {
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 }
min_entropy_t min_entropy_per_sample(void)
min-entropy per sample
#define MIN_ENTROPY(bits)
Construct a min-entropy fixed-point value.
Definition: entropy.h:71
#define linker_assert(condition, error_symbol)
Assert a condition at link-time.
Definition: assert.h:68

References linker_assert, MIN_ENTROPY, and min_entropy_per_sample().

Referenced by get_entropy_input_tmp().

◆ repetition_count_test()

static int repetition_count_test ( noise_sample_t  sample)
static

Perform repetition count test.

Parameters
sampleNoise sample
Return values
rcReturn status code

This is the Repetition Count Test defined in ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.2.

Definition at line 104 of file entropy.c.

104  {
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 }
#define EPIPE_REPETITION_COUNT_TEST
Definition: entropy.c:44
uint8_t noise_sample_t
A noise sample.
Definition: entropy.h:50

References EPIPE_REPETITION_COUNT_TEST.

Referenced by get_entropy().

◆ adaptive_proportion_test()

static int adaptive_proportion_test ( noise_sample_t  sample)
static

Perform adaptive proportion test.

Parameters
sampleNoise sample
Return values
rcReturn status code

This is the Adaptive Proportion Test for the Most Common Value defined in ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.3.

Definition at line 264 of file entropy.c.

264  {
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 }
#define EPIPE_ADAPTIVE_PROPORTION_TEST
Definition: entropy.c:48
#define ADAPTIVE_PROPORTION_WINDOW_SIZE
Window size for the adaptive proportion test.
Definition: entropy.c:156
uint8_t noise_sample_t
A noise sample.
Definition: entropy.h:50

References ADAPTIVE_PROPORTION_WINDOW_SIZE, and EPIPE_ADAPTIVE_PROPORTION_TEST.

Referenced by get_entropy().

◆ get_entropy()

static int get_entropy ( entropy_sample_t entropy)
static

Get entropy sample.

Return values
entropyEntropy sample
rcReturn status code

This is the GetEntropy function defined in ANS X9.82 Part 2 (October 2011 Draft) Section 6.5.1.

Definition at line 333 of file entropy.c.

333  {
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 }
struct arbelprm_rc_send_wqe rc
Definition: arbel.h:14
int get_noise(noise_sample_t *noise)
Get noise sample.
static int adaptive_proportion_test(noise_sample_t sample)
Perform adaptive proportion test.
Definition: entropy.c:264
static int repetition_count_test(noise_sample_t sample)
Perform repetition count test.
Definition: entropy.c:104
uint8_t noise_sample_t
A noise sample.
Definition: entropy.h:50

References adaptive_proportion_test(), get_noise(), rc, and repetition_count_test().

Referenced by get_entropy_input_tmp().

◆ make_next_nonce()

static uint32_t make_next_nonce ( void  )
static

Create next nonce value.

Return values
nonceNonce

This is the MakeNextNonce function defined in ANS X9.82 Part 4 (April 2011 Draft) Section 13.3.4.2.

Definition at line 393 of file entropy.c.

393  {
394  static uint32_t nonce;
395 
396  /* The simplest implementation of a nonce uses a large counter */
397  nonce++;
398 
399  return nonce;
400 }
unsigned int uint32_t
Definition: stdint.h:12
struct ntlm_nonce nonce
Server nonce.
Definition: ntlm.h:18

References nonce.

Referenced by get_entropy_input_tmp().

◆ get_entropy_input_tmp()

int get_entropy_input_tmp ( unsigned int  num_samples,
uint8_t tmp,
size_t  tmp_len 
)

Obtain entropy input temporary buffer.

Parameters
num_samplesNumber of entropy samples
tmpTemporary buffer
tmp_lenLength of temporary buffer
Return values
rcReturn status code

This is (part of) the implementation of the Get_entropy_input function (using an entropy source as the source of entropy input and condensing each entropy source output after each GetEntropy call) as defined in ANS X9.82 Part 4 (April 2011 Draft) Section 13.3.4.2.

To minimise code size, the number of samples required is calculated at compilation time.

Definition at line 419 of file entropy.c.

420  {
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
unsigned int num_samples
Definition: entropy.h:158
static uint32_t make_next_nonce(void)
Create next nonce value.
Definition: entropy.c:393
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
unsigned char uint8_t
Definition: stdint.h:10
unsigned int uint32_t
Definition: stdint.h:12
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
#define entropy_hash_df_algorithm
Use SHA-256 as the underlying hash algorithm for Hash_df.
Definition: entropy.h:129
struct arbelprm_port_state_change_st data
Message.
Definition: arbel.h:12
struct ntlm_nonce nonce
Server nonce.
Definition: ntlm.h:18
void * memset(void *dest, int character, size_t len) __nonnull

References __attribute__(), data, entropy_disable(), entropy_enable(), entropy_hash_df_algorithm, get_entropy(), hash_df(), make_next_nonce(), memset(), nonce, num_samples, rc, tmp, and tmp_len.