diff options
Diffstat (limited to 'qemu/roms/ipxe/src/crypto/entropy.c')
| -rw-r--r-- | qemu/roms/ipxe/src/crypto/entropy.c | 483 |
1 files changed, 0 insertions, 483 deletions
diff --git a/qemu/roms/ipxe/src/crypto/entropy.c b/qemu/roms/ipxe/src/crypto/entropy.c deleted file mode 100644 index 5acbc0258..000000000 --- a/qemu/roms/ipxe/src/crypto/entropy.c +++ /dev/null @@ -1,483 +0,0 @@ -/* - * 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 + ( 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; -} |