/* * Copyright (C) 2012 Michael Brown . * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License as * published by the Free Software Foundation; either version 2 of the * License, or any later version. * * This program is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA * 02110-1301, USA. * * You can also choose to distribute this program under the terms of * the Unmodified Binary Distribution Licence (as given in the file * COPYING.UBDL), provided that you have satisfied its requirements. */ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); /** @file * * 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. */ #include #include #include #include #include #include #include /* Disambiguate the various error causes */ #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" ) /** * Calculate cutoff value for the repetition count test * * @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 repetition_count_cutoff ( void ) { 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 + ( 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++; linker_assert ( ( cutoff >= max_repetitions ), rounding_error ); /* 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. */ linker_assert ( __builtin_constant_p ( cutoff ), repetition_count_cutoff_not_constant ); return cutoff; } /** * Perform repetition count test * * @v sample Noise sample * @ret rc Return status code * * This is the Repetition Count Test defined in ANS X9.82 Part 2 * (October 2011 Draft) Section 8.5.2.1.2. */ static int repetition_count_test ( noise_sample_t sample ) { static noise_sample_t most_recent_sample; static unsigned int repetition_count = 0; /* A = the most recently seen sample value * B = the number of times that value A has been seen in a row * C = the cutoff value above which the repetition test should fail */ /* 1. For each new sample processed: * * (Note that the test for "repetition_count > 0" ensures that * the initial value of most_recent_sample is treated as being * undefined.) */ if ( ( sample == most_recent_sample ) && ( repetition_count > 0 ) ) { /* a) If the new sample = A, then B is incremented by one. */ repetition_count++; /* i. If B >= C, then an error condition is raised * due to a failure of the test */ if ( repetition_count >= repetition_count_cutoff() ) return -EPIPE_REPETITION_COUNT_TEST; } else { /* b) Else: * i. A = new sample */ most_recent_sample = sample; /* ii. B = 1 */ repetition_count = 1; } return 0; } /** * 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 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 * * @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 adaptive_proportion_cutoff ( void ) { 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(); cutoff = adaptive_proportion_cutoff_lookup ( n, h ); /* Fail unless cutoff value is a build-time constant */ linker_assert ( __builtin_constant_p ( cutoff ), adaptive_proportion_cutoff_not_constant ); /* Fail if cutoff value is N/A */ linker_assert ( ( cutoff != APC_NA ), adaptive_proportion_cutoff_not_applicable ); return cutoff; } /** * Perform adaptive proportion test * * @v sample Noise sample * @ret rc Return 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. */ static int adaptive_proportion_test ( noise_sample_t sample ) { static noise_sample_t current_counted_sample; static unsigned int sample_count = ADAPTIVE_PROPORTION_WINDOW_SIZE; static unsigned int repetition_count; /* A = the sample value currently being counted * B = the number of samples examined in this run of the test so far * N = the total number of samples that must be observed in * one run of the test, also known as the "window size" of * the test * B = the current number of times that S (sic) has been seen * in the W (sic) samples examined so far * C = the cutoff value above which the repetition test should fail * W = the probability of a false positive: 2^-30 */ /* 1. The entropy source draws the current sample from the * noise source. * * (Nothing to do; we already have the current sample.) */ /* 2. If S = N, then a new run of the test begins: */ if ( sample_count == ADAPTIVE_PROPORTION_WINDOW_SIZE ) { /* a. A = the current sample */ current_counted_sample = sample; /* b. S = 0 */ sample_count = 0; /* c. B = 0 */ repetition_count = 0; } else { /* Else: (the test is already running) * a. S = S + 1 */ sample_count++; /* b. If A = the current sample, then: */ if ( sample == current_counted_sample ) { /* i. B = B + 1 */ repetition_count++; /* ii. If S (sic) > C then raise an error * condition, because the test has * detected a failure */ if ( repetition_count > adaptive_proportion_cutoff() ) return -EPIPE_ADAPTIVE_PROPORTION_TEST; } } return 0; } /** * Get entropy sample * * @ret entropy Entropy sample * @ret rc Return status code * * This is the GetEntropy function defined in ANS X9.82 Part 2 * (October 2011 Draft) Section 6.5.1. */ static int get_entropy ( entropy_sample_t *entropy ) { static int rc = 0; noise_sample_t noise; /* Any failure is permanent */ if ( rc != 0 ) return rc; /* Get noise sample */ if ( ( rc = get_noise ( &noise ) ) != 0 ) return rc; /* Perform Repetition Count Test and Adaptive Proportion Test * as mandated by ANS X9.82 Part 2 (October 2011 Draft) * Section 8.5.2.1.1. */ if ( ( rc = repetition_count_test ( noise ) ) != 0 ) return rc; if ( ( rc = adaptive_proportion_test ( noise ) ) != 0 ) return rc; /* We do not use any optional conditioning component */ *entropy = noise; return 0; } /** * Calculate number of samples required for startup tests * * @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 startup_test_count ( void ) { 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(); linker_assert ( __builtin_constant_p ( num_samples ), startup_test_count_not_constant ); return num_samples; } /** * Create next nonce value * * @ret nonce Nonce * * This is the MakeNextNonce function defined in ANS X9.82 Part 4 * (April 2011 Draft) Section 13.3.4.2. */ static uint32_t make_next_nonce ( void ) { static uint32_t nonce; /* The simplest implementation of a nonce uses a large counter */ nonce++; return nonce; } /** * Obtain entropy input temporary buffer * * @v num_samples Number of entropy samples * @v tmp Temporary buffer * @v tmp_len Length of temporary buffer * @ret rc Return 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. */ int get_entropy_input_tmp ( unsigned int num_samples, uint8_t *tmp, size_t tmp_len ) { static unsigned int startup_tested = 0; struct { uint32_t nonce; entropy_sample_t sample; } __attribute__ (( packed )) data;; uint8_t df_buf[tmp_len]; unsigned int i; int rc; /* Enable entropy gathering */ if ( ( rc = entropy_enable() ) != 0 ) return rc; /* Perform mandatory startup tests, if not yet performed */ for ( ; startup_tested < startup_test_count() ; startup_tested++ ) { if ( ( rc = get_entropy ( &data.sample ) ) != 0 ) goto err_get_entropy; } /* 3. entropy_total = 0 * * (Nothing to do; the number of entropy samples required has * already been precalculated.) */ /* 4. tmp = a fixed n-bit value, such as 0^n */ memset ( tmp, 0, tmp_len ); /* 5. While ( entropy_total < min_entropy ) */ while ( num_samples-- ) { /* 5.1. ( status, entropy_bitstring, assessed_entropy ) * = GetEntropy() * 5.2. If status indicates an error, return ( status, Null ) */ if ( ( rc = get_entropy ( &data.sample ) ) != 0 ) goto err_get_entropy; /* 5.3. nonce = MakeNextNonce() */ data.nonce = make_next_nonce(); /* 5.4. tmp = tmp XOR * df ( ( nonce || entropy_bitstring ), n ) */ hash_df ( &entropy_hash_df_algorithm, &data, sizeof ( data ), df_buf, sizeof ( df_buf ) ); for ( i = 0 ; i < tmp_len ; i++ ) tmp[i] ^= df_buf[i]; /* 5.5. entropy_total = entropy_total + assessed_entropy * * (Nothing to do; the number of entropy samples * required has already been precalculated.) */ } /* Disable entropy gathering */ entropy_disable(); return 0; err_get_entropy: entropy_disable(); return rc; }