diff options
Diffstat (limited to 'src/VBox/Devices/PC/ipxe/src/crypto/entropy.c')
-rw-r--r-- | src/VBox/Devices/PC/ipxe/src/crypto/entropy.c | 484 |
1 files changed, 484 insertions, 0 deletions
diff --git a/src/VBox/Devices/PC/ipxe/src/crypto/entropy.c b/src/VBox/Devices/PC/ipxe/src/crypto/entropy.c new file mode 100644 index 00000000..ced6fd92 --- /dev/null +++ b/src/VBox/Devices/PC/ipxe/src/crypto/entropy.c @@ -0,0 +1,484 @@ +/* + * Copyright (C) 2012 Michael Brown <mbrown@fensystems.co.uk>. + * + * 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 <stdint.h> +#include <assert.h> +#include <string.h> +#include <errno.h> +#include <ipxe/crypto.h> +#include <ipxe/hash_df.h> +#include <ipxe/entropy.h> + +/* 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 + ( 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++; + 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() / MIN_ENTROPY_SCALE ); + 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; +} |