#ifndef _IPXE_ENTROPY_H #define _IPXE_ENTROPY_H /** @file * * Entropy source * */ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); #include #include #include #include #include #include #include /** A noise sample */ typedef uint8_t noise_sample_t; /** An entropy sample */ typedef uint8_t entropy_sample_t; /** An amount of min-entropy * * Expressed as a fixed-point quantity in order to avoid floating * point calculations. */ typedef unsigned int min_entropy_t; /** Fixed-point scale for min-entropy amounts */ #define MIN_ENTROPY_SCALE ( 1 << 16 ) /** * Construct a min-entropy fixed-point value * * @v bits min-entropy in bits * @ret min_entropy min-entropy as a fixed-point value */ #define MIN_ENTROPY( bits ) \ ( ( min_entropy_t ) ( (bits) * MIN_ENTROPY_SCALE ) ) /** * Repetition count test state * * This is the state for the repetition Count Test defined in ANS * X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.2. */ struct entropy_repetition_count_test { /** * A = the most recently seen sample value */ noise_sample_t most_recent_sample; /** * B = the number of times that value A has been seen in a row */ unsigned int repetition_count; /** * C = the cutoff value above which the repetition test should fail * * Filled in by entropy_init(). */ unsigned int cutoff; }; /** * Adaptive proportion test state * * This is the state for 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. */ struct entropy_adaptive_proportion_test { /** * A = the sample value currently being counted */ noise_sample_t current_counted_sample; /** * S = the number of samples examined in this run of the test so far */ unsigned int sample_count; /** * B = the current number of times that S (sic) has been seen * in the W (sic) samples examined so far */ unsigned int repetition_count; /** * C = the cutoff value above which the repetition test should fail * * Filled in by entropy_init(). */ unsigned int cutoff; }; /** * Startup test state * * 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. */ struct entropy_startup_test { /** Number of startup tests performed */ unsigned int tested; /** * Number of startup tests required for one full cycle * * Filled in by entropy_init(). */ unsigned int count; }; /** An entropy source */ struct entropy_source { /** Name */ const char *name; /** * min-entropy per sample * * min-entropy is defined in ANS X9.82 Part 1-2006 Section 8.3 and in * NIST SP 800-90 Appendix C.3 as * * H_min = -log2 ( p_max ) * * where p_max is the probability of the most likely sample value. * * Filled in by entropy_init(). */ min_entropy_t min_entropy_per_sample; /** Repetition count test state */ struct entropy_repetition_count_test repetition_count_test; /** Adaptive proportion test state */ struct entropy_adaptive_proportion_test adaptive_proportion_test; /** Startup test state */ struct entropy_startup_test startup_test; /** * Failure status (if any) * * Any failure of an entropy source is regarded as permanent. */ int rc; /** * Enable entropy gathering * * @ret rc Return status code */ int ( * enable ) ( void ); /** * Disable entropy gathering * */ void ( * disable ) ( void ); /** * Get noise sample * * @ret noise Noise sample * @ret rc Return status code * * This is the GetNoise function defined in ANS X9.82 Part 2 * (October 2011 Draft) Section 6.5.2. */ int ( * get_noise ) ( noise_sample_t *noise ); }; /** Entropy source table */ #define ENTROPY_SOURCES __table ( struct entropy_source, "entropy_sources" ) /** Declare an entropy source */ #define __entropy_source( order ) __table_entry ( ENTROPY_SOURCES, order ) /** @defgroup entropy_source_order Entropy source order * * @{ */ #define ENTROPY_PREFERRED 01 /**< Preferred entropy source */ #define ENTROPY_NORMAL 02 /**< Normal entropy source */ #define ENTROPY_FALLBACK 03 /**< Fallback entropy source */ /** @} */ extern int get_entropy_input_tmp ( min_entropy_t min_entropy, uint8_t *tmp, size_t tmp_len ); /** Use SHA-256 as the underlying hash algorithm for Hash_df * * Hash_df using SHA-256 is an Approved algorithm in ANS X9.82. */ #define entropy_hash_df_algorithm sha256_algorithm /** Underlying hash algorithm output length (in bytes) */ #define ENTROPY_HASH_DF_OUTLEN_BYTES SHA256_DIGEST_SIZE /** * Get noise sample * * @v source Entropy source * @ret noise Noise sample * @ret rc Return status code * * This is the GetNoise function defined in ANS X9.82 Part 2 * (October 2011 Draft) Section 6.5.2. */ static inline __attribute__ (( always_inline )) int get_noise ( struct entropy_source *source, noise_sample_t *noise ) { return source->get_noise ( noise ); } /** * Obtain entropy input * * @v min_entropy_bits Minimum amount of entropy, in bits * @v data Data buffer * @v min_len Minimum length of entropy input, in bytes * @v max_len Maximum length of entropy input, in bytes * @ret len Length of entropy input, in bytes, or negative error * * This is 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. * * This function is inlined since the entropy amount and length inputs * are always compile-time constants. */ static inline __attribute__ (( always_inline )) int get_entropy_input ( unsigned int min_entropy_bits, void *data, size_t min_len, size_t max_len ) { size_t tmp_len = ( ( ( min_entropy_bits * 2 ) + 7 ) / 8 ); uint8_t tmp_buf[ tmp_len ]; uint8_t *tmp = ( ( tmp_len > max_len ) ? tmp_buf : data ); unsigned int n; int rc; /* Sanity check */ build_assert ( min_entropy_bits <= ( 8 * max_len ) ); /* Round up minimum entropy to an integral number of bytes */ min_entropy_bits = ( ( min_entropy_bits + 7 ) & ~7 ); /* (Unnumbered). The output length of the hash function shall * meet or exceed the security strength indicated by the * min_entropy parameter. */ build_assert ( ( 8 * ENTROPY_HASH_DF_OUTLEN_BYTES ) >= min_entropy_bits ); /* 1. If ( min_length > max_length ), then return ( FAILURE, Null ) */ build_assert ( min_len <= max_len ); /* 2. n = 2 * min_entropy */ n = ( 2 * min_entropy_bits ); /* 3. entropy_total = 0 * 4. tmp = a fixed n-bit value, such as 0^n * 5. While ( entropy_total < min_entropy ) * 5.1. ( status, entropy_bitstring, assessed_entropy ) * = GetEntropy() * 5.2. If status indicates an error, return ( status, Null ) * 5.3. nonce = MakeNextNonce() * 5.4. tmp = tmp XOR df ( ( nonce || entropy_bitstring ), n ) * 5.5. entropy_total = entropy_total + assessed_entropy * * (The implementation of these steps is inside the function * get_entropy_input_tmp().) */ build_assert ( __builtin_constant_p ( tmp_len ) ); build_assert ( n == ( 8 * tmp_len ) ); if ( ( rc = get_entropy_input_tmp ( MIN_ENTROPY ( min_entropy_bits ), tmp, tmp_len ) ) != 0 ) { return rc; } /* 6. If ( n < min_length ), then tmp = tmp || 0^(min_length-n) * 7. If ( n > max_length ), then tmp = df ( tmp, max_length ) * 8. Return ( SUCCESS, tmp ) */ if ( tmp_len < min_len ) { /* (Data is already in-place.) */ build_assert ( data == tmp ); memset ( ( data + tmp_len ), 0, ( min_len - tmp_len ) ); return min_len; } else if ( tmp_len > max_len ) { build_assert ( tmp == tmp_buf ); hash_df ( &entropy_hash_df_algorithm, tmp, tmp_len, data, max_len ); return max_len; } else { /* (Data is already in-place.) */ build_assert ( data == tmp ); return tmp_len; } } /** * Calculate cutoff value for the repetition count test * * @v min_entropy_per_sample Min-entropy per sample * @ret cutoff Cutoff 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. */ static inline __attribute__ (( always_inline )) unsigned int entropy_repetition_count_cutoff ( min_entropy_t min_entropy_per_sample ) { double max_repetitions; unsigned int cutoff; /* The cutoff formula for the repetition test is: * * C = ( 1 + ( -log2(W) / H_min ) ) * * where W is set at 2^(-30) (in ANS X9.82 Part 2 (October * 2011 Draft) Section 8.5.2.1.3.1). */ max_repetitions = ( 1 + ( MIN_ENTROPY ( 30 ) / min_entropy_per_sample ) ); /* Round up to a whole number of repetitions. We don't have * the ceil() function available, so do the rounding by hand. */ cutoff = max_repetitions; if ( cutoff < max_repetitions ) cutoff++; build_assert ( cutoff >= max_repetitions ); /* Floating-point operations are not allowed in iPXE since we * never set up a suitable environment. Abort the build * unless the calculated number of repetitions is a * compile-time constant. */ build_assert ( __builtin_constant_p ( cutoff ) ); return cutoff; } /** * 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. */ #define ADAPTIVE_PROPORTION_WINDOW_SIZE 64 /** * Combine adaptive proportion test window size and min-entropy * * @v n N (window size) * @v h H (min-entropy) * @ret n_h (N,H) combined value */ #define APC_N_H( n, h ) ( ( (n) << 8 ) | (h) ) /** * Define a row of the adaptive proportion cutoff table * * @v h H (min-entropy) * @v c16 Cutoff for N=16 * @v c64 Cutoff for N=64 * @v c256 Cutoff for N=256 * @v c4096 Cutoff for N=4096 * @v c65536 Cutoff for N=65536 */ #define APC_TABLE_ROW( h, c16, c64, c256, c4096, c65536) \ 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; /** Value used to represent "N/A" in adaptive proportion cutoff table */ #define APC_NA 0 /** * Look up value in adaptive proportion test cutoff table * * @v n N (window size) * @v h H (min-entropy) * @ret cutoff Cutoff * * 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. */ static inline __attribute__ (( always_inline )) unsigned int entropy_adaptive_proportion_cutoff_lookup ( unsigned int n, unsigned int h ) { switch ( APC_N_H ( n, h ) ) { APC_TABLE_ROW ( 1, APC_NA, 51, 168, 2240, 33537 ); APC_TABLE_ROW ( 2, APC_NA, 35, 100, 1193, 17053 ); APC_TABLE_ROW ( 3, 10, 24, 61, 643, 8705 ); APC_TABLE_ROW ( 4, 8, 16, 38, 354, 4473 ); APC_TABLE_ROW ( 5, 6, 12, 25, 200, 2321 ); APC_TABLE_ROW ( 6, 5, 9, 17, 117, 1220 ); APC_TABLE_ROW ( 7, 4, 7, 15, 71, 653 ); APC_TABLE_ROW ( 8, 4, 5, 9, 45, 358 ); APC_TABLE_ROW ( 9, 3, 4, 7, 30, 202 ); APC_TABLE_ROW ( 10, 3, 4, 5, 21, 118 ); APC_TABLE_ROW ( 11, 2, 3, 4, 15, 71 ); APC_TABLE_ROW ( 12, 2, 3, 4, 11, 45 ); APC_TABLE_ROW ( 13, 2, 2, 3, 9, 30 ); APC_TABLE_ROW ( 14, 2, 2, 3, 7, 21 ); APC_TABLE_ROW ( 15, 1, 2, 2, 6, 15 ); APC_TABLE_ROW ( 16, 1, 2, 2, 5, 11 ); APC_TABLE_ROW ( 17, 1, 1, 2, 4, 9 ); APC_TABLE_ROW ( 18, 1, 1, 2, 4, 7 ); APC_TABLE_ROW ( 19, 1, 1, 1, 3, 6 ); APC_TABLE_ROW ( 20, 1, 1, 1, 3, 5 ); default: return APC_NA; } } /** * Calculate cutoff value for the adaptive proportion test * * @v min_entropy_per_sample Min-entropy per sample * @ret cutoff Cutoff 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. */ static inline __attribute__ (( always_inline )) unsigned int entropy_adaptive_proportion_cutoff ( min_entropy_t min_entropy_per_sample ) { unsigned int h; unsigned int n; unsigned int cutoff; /* Look up cutoff value in cutoff table */ n = ADAPTIVE_PROPORTION_WINDOW_SIZE; h = ( min_entropy_per_sample / MIN_ENTROPY_SCALE ); cutoff = entropy_adaptive_proportion_cutoff_lookup ( n, h ); /* Fail unless cutoff value is a compile-time constant */ build_assert ( __builtin_constant_p ( cutoff ) ); /* Fail if cutoff value is N/A */ build_assert ( cutoff != APC_NA ); return cutoff; } /** * Calculate number of samples required for startup tests * * @v repetition_count_cutoff Repetition count test cutoff value * @v adaptive_proportion_cutoff Adaptive proportion test cutoff value * @ret num_samples Number 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. */ static inline __attribute__ (( always_inline )) unsigned int entropy_startup_test_count ( unsigned int repetition_count_cutoff, unsigned int adaptive_proportion_cutoff ) { unsigned int num_samples; /* At least max(N,C) samples shall be generated by the noise * source for start-up testing. */ num_samples = repetition_count_cutoff; if ( num_samples < adaptive_proportion_cutoff ) num_samples = adaptive_proportion_cutoff; build_assert ( __builtin_constant_p ( num_samples ) ); return num_samples; } /** * Initialise entropy source * * @v source Entropy source * @v min_entropy_per_sample Min-entropy per sample * * The cutoff value calculations for the repetition count test and the * adaptive proportion test are provided as static inline functions * since the results will always be compile-time constants. */ static inline __attribute__ (( always_inline )) void entropy_init ( struct entropy_source *source, min_entropy_t min_entropy_per_sample ) { unsigned int repetition_count_cutoff; unsigned int adaptive_proportion_cutoff; unsigned int startup_test_count; /* Sanity check */ build_assert ( min_entropy_per_sample > MIN_ENTROPY ( 0 ) ); build_assert ( min_entropy_per_sample <= MIN_ENTROPY ( 8 * sizeof ( noise_sample_t ) ) ); /* Calculate test cutoff values */ repetition_count_cutoff = entropy_repetition_count_cutoff ( min_entropy_per_sample ); adaptive_proportion_cutoff = entropy_adaptive_proportion_cutoff ( min_entropy_per_sample ); startup_test_count = entropy_startup_test_count ( repetition_count_cutoff, adaptive_proportion_cutoff ); /* Record min-entropy per sample and test cutoff values */ source->min_entropy_per_sample = min_entropy_per_sample; source->repetition_count_test.cutoff = repetition_count_cutoff; source->adaptive_proportion_test.cutoff = adaptive_proportion_cutoff; source->startup_test.count = startup_test_count; } extern int entropy_enable ( struct entropy_source *source ); extern void entropy_disable ( struct entropy_source *source ); extern int get_noise ( struct entropy_source *source, noise_sample_t *noise ); #endif /* _IPXE_ENTROPY_H */