iPXE
entropy.c
Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2012 Michael Brown <mbrown@fensystems.co.uk>.
00003  *
00004  * This program is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU General Public License as
00006  * published by the Free Software Foundation; either version 2 of the
00007  * License, or any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful, but
00010  * WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012  * General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software
00016  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
00017  * 02110-1301, USA.
00018  *
00019  * You can also choose to distribute this program under the terms of
00020  * the Unmodified Binary Distribution Licence (as given in the file
00021  * COPYING.UBDL), provided that you have satisfied its requirements.
00022  */
00023 
00024 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
00025 
00026 /** @file
00027  *
00028  * Entropy source
00029  *
00030  * This algorithm is designed to comply with ANS X9.82 Part 4 (April
00031  * 2011 Draft) Section 13.3.  This standard is unfortunately not
00032  * freely available.
00033  */
00034 
00035 #include <stdint.h>
00036 #include <assert.h>
00037 #include <string.h>
00038 #include <errno.h>
00039 #include <ipxe/crypto.h>
00040 #include <ipxe/hash_df.h>
00041 #include <ipxe/entropy.h>
00042 
00043 /* Disambiguate the various error causes */
00044 #define EPIPE_REPETITION_COUNT_TEST \
00045         __einfo_error ( EINFO_EPIPE_REPETITION_COUNT_TEST )
00046 #define EINFO_EPIPE_REPETITION_COUNT_TEST \
00047         __einfo_uniqify ( EINFO_EPIPE, 0x01, "Repetition count test failed" )
00048 #define EPIPE_ADAPTIVE_PROPORTION_TEST \
00049         __einfo_error ( EINFO_EPIPE_ADAPTIVE_PROPORTION_TEST )
00050 #define EINFO_EPIPE_ADAPTIVE_PROPORTION_TEST \
00051         __einfo_uniqify ( EINFO_EPIPE, 0x02, "Adaptive proportion test failed" )
00052 
00053 /**
00054  * Calculate cutoff value for the repetition count test
00055  *
00056  * @ret cutoff          Cutoff value
00057  *
00058  * This is the cutoff value for the Repetition Count Test defined in
00059  * ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.2.
00060  */
00061 static inline __attribute__ (( always_inline )) unsigned int
00062 repetition_count_cutoff ( void ) {
00063         double max_repetitions;
00064         unsigned int cutoff;
00065 
00066         /* The cutoff formula for the repetition test is:
00067          *
00068          *   C = ( 1 + ( -log2(W) / H_min ) )
00069          *
00070          * where W is set at 2^(-30) (in ANS X9.82 Part 2 (October
00071          * 2011 Draft) Section 8.5.2.1.3.1).
00072          */
00073         max_repetitions = ( 1 + ( MIN_ENTROPY ( 30 ) /
00074                                   min_entropy_per_sample() ) );
00075 
00076         /* Round up to a whole number of repetitions.  We don't have
00077          * the ceil() function available, so do the rounding by hand.
00078          */
00079         cutoff = max_repetitions;
00080         if ( cutoff < max_repetitions )
00081                 cutoff++;
00082         linker_assert ( ( cutoff >= max_repetitions ), rounding_error );
00083 
00084         /* Floating-point operations are not allowed in iPXE since we
00085          * never set up a suitable environment.  Abort the build
00086          * unless the calculated number of repetitions is a
00087          * compile-time constant.
00088          */
00089         linker_assert ( __builtin_constant_p ( cutoff ),
00090                         repetition_count_cutoff_not_constant );
00091 
00092         return cutoff;
00093 }
00094 
00095 /**
00096  * Perform repetition count test
00097  *
00098  * @v sample            Noise sample
00099  * @ret rc              Return status code
00100  *
00101  * This is the Repetition Count Test defined in ANS X9.82 Part 2
00102  * (October 2011 Draft) Section 8.5.2.1.2.
00103  */
00104 static int repetition_count_test ( noise_sample_t sample ) {
00105         static noise_sample_t most_recent_sample;
00106         static unsigned int repetition_count = 0;
00107 
00108         /* A = the most recently seen sample value
00109          * B = the number of times that value A has been seen in a row
00110          * C = the cutoff value above which the repetition test should fail
00111          */
00112 
00113         /* 1.  For each new sample processed:
00114          *
00115          * (Note that the test for "repetition_count > 0" ensures that
00116          * the initial value of most_recent_sample is treated as being
00117          * undefined.)
00118          */
00119         if ( ( sample == most_recent_sample ) && ( repetition_count > 0 ) ) {
00120 
00121                 /* a) If the new sample = A, then B is incremented by one. */
00122                 repetition_count++;
00123 
00124                 /*    i.  If B >= C, then an error condition is raised
00125                  *        due to a failure of the test
00126                  */
00127                 if ( repetition_count >= repetition_count_cutoff() )
00128                         return -EPIPE_REPETITION_COUNT_TEST;
00129 
00130         } else {
00131 
00132                 /* b) Else:
00133                  *    i.  A = new sample
00134                  */
00135                 most_recent_sample = sample;
00136 
00137                 /*    ii. B = 1 */
00138                 repetition_count = 1;
00139         }
00140 
00141         return 0;
00142 }
00143 
00144 /**
00145  * Window size for the adaptive proportion test
00146  *
00147  * ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.3.1.1 allows
00148  * five possible window sizes: 16, 64, 256, 4096 and 65536.
00149  *
00150  * We expect to generate relatively few (<256) entropy samples during
00151  * a typical iPXE run; the use of a large window size would mean that
00152  * the test would never complete a single cycle.  We use a window size
00153  * of 64, which is the smallest window size that permits values of
00154  * H_min down to one bit per sample.
00155  */
00156 #define ADAPTIVE_PROPORTION_WINDOW_SIZE 64
00157 
00158 /**
00159  * Combine adaptive proportion test window size and min-entropy
00160  *
00161  * @v n                 N (window size)
00162  * @v h                 H (min-entropy)
00163  * @ret n_h             (N,H) combined value
00164  */
00165 #define APC_N_H( n, h ) ( ( (n) << 8 ) | (h) )
00166 
00167 /**
00168  * Define a row of the adaptive proportion cutoff table
00169  *
00170  * @v h                 H (min-entropy)
00171  * @v c16               Cutoff for N=16
00172  * @v c64               Cutoff for N=64
00173  * @v c256              Cutoff for N=256
00174  * @v c4096             Cutoff for N=4096
00175  * @v c65536            Cutoff for N=65536
00176  */
00177 #define APC_TABLE_ROW( h, c16, c64, c256, c4096, c65536)           \
00178         case APC_N_H ( 16, h ) :        return c16;                \
00179         case APC_N_H ( 64, h ) :        return c64;                \
00180         case APC_N_H ( 256, h ) :       return c256;               \
00181         case APC_N_H ( 4096, h ) :      return c4096;              \
00182         case APC_N_H ( 65536, h ) :     return c65536;
00183 
00184 /** Value used to represent "N/A" in adaptive proportion cutoff table */
00185 #define APC_NA 0
00186 
00187 /**
00188  * Look up value in adaptive proportion test cutoff table
00189  *
00190  * @v n                 N (window size)
00191  * @v h                 H (min-entropy)
00192  * @ret cutoff          Cutoff
00193  *
00194  * This is the table of cutoff values defined in ANS X9.82 Part 2
00195  * (October 2011 Draft) Section 8.5.2.1.3.1.2.
00196  */
00197 static inline __attribute__ (( always_inline )) unsigned int
00198 adaptive_proportion_cutoff_lookup ( unsigned int n, unsigned int h ) {
00199         switch ( APC_N_H ( n, h ) ) {
00200                 APC_TABLE_ROW (  1, APC_NA,     51,    168,   2240,  33537 );
00201                 APC_TABLE_ROW (  2, APC_NA,     35,    100,   1193,  17053 );
00202                 APC_TABLE_ROW (  3,     10,     24,     61,    643,   8705 );
00203                 APC_TABLE_ROW (  4,      8,     16,     38,    354,   4473 );
00204                 APC_TABLE_ROW (  5,      6,     12,     25,    200,   2321 );
00205                 APC_TABLE_ROW (  6,      5,      9,     17,    117,   1220 );
00206                 APC_TABLE_ROW (  7,      4,      7,     15,     71,    653 );
00207                 APC_TABLE_ROW (  8,      4,      5,      9,     45,    358 );
00208                 APC_TABLE_ROW (  9,      3,      4,      7,     30,    202 );
00209                 APC_TABLE_ROW ( 10,      3,      4,      5,     21,    118 );
00210                 APC_TABLE_ROW ( 11,      2,      3,      4,     15,     71 );
00211                 APC_TABLE_ROW ( 12,      2,      3,      4,     11,     45 );
00212                 APC_TABLE_ROW ( 13,      2,      2,      3,      9,     30 );
00213                 APC_TABLE_ROW ( 14,      2,      2,      3,      7,     21 );
00214                 APC_TABLE_ROW ( 15,      1,      2,      2,      6,     15 );
00215                 APC_TABLE_ROW ( 16,      1,      2,      2,      5,     11 );
00216                 APC_TABLE_ROW ( 17,      1,      1,      2,      4,      9 );
00217                 APC_TABLE_ROW ( 18,      1,      1,      2,      4,      7 );
00218                 APC_TABLE_ROW ( 19,      1,      1,      1,      3,      6 );
00219                 APC_TABLE_ROW ( 20,      1,      1,      1,      3,      5 );
00220         default:
00221                 return APC_NA;
00222         }
00223 }
00224 
00225 /**
00226  * Calculate cutoff value for the adaptive proportion test
00227  *
00228  * @ret cutoff          Cutoff value
00229  *
00230  * This is the cutoff value for the Adaptive Proportion Test defined
00231  * in ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.3.1.2.
00232  */
00233 static inline __attribute__ (( always_inline )) unsigned int
00234 adaptive_proportion_cutoff ( void ) {
00235         unsigned int h;
00236         unsigned int n;
00237         unsigned int cutoff;
00238 
00239         /* Look up cutoff value in cutoff table */
00240         n = ADAPTIVE_PROPORTION_WINDOW_SIZE;
00241         h = ( min_entropy_per_sample() / MIN_ENTROPY_SCALE );
00242         cutoff = adaptive_proportion_cutoff_lookup ( n, h );
00243 
00244         /* Fail unless cutoff value is a build-time constant */
00245         linker_assert ( __builtin_constant_p ( cutoff ),
00246                         adaptive_proportion_cutoff_not_constant );
00247 
00248         /* Fail if cutoff value is N/A */
00249         linker_assert ( ( cutoff != APC_NA ),
00250                         adaptive_proportion_cutoff_not_applicable );
00251 
00252         return cutoff;
00253 }
00254 
00255 /**
00256  * Perform adaptive proportion test
00257  *
00258  * @v sample            Noise sample
00259  * @ret rc              Return status code
00260  *
00261  * This is the Adaptive Proportion Test for the Most Common Value
00262  * defined in ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.3.
00263  */
00264 static int adaptive_proportion_test ( noise_sample_t sample ) {
00265         static noise_sample_t current_counted_sample;
00266         static unsigned int sample_count = ADAPTIVE_PROPORTION_WINDOW_SIZE;
00267         static unsigned int repetition_count;
00268 
00269         /* A = the sample value currently being counted
00270          * B = the number of samples examined in this run of the test so far
00271          * N = the total number of samples that must be observed in
00272          *     one run of the test, also known as the "window size" of
00273          *     the test
00274          * B = the current number of times that S (sic) has been seen
00275          *     in the W (sic) samples examined so far
00276          * C = the cutoff value above which the repetition test should fail
00277          * W = the probability of a false positive: 2^-30
00278          */
00279 
00280         /* 1.  The entropy source draws the current sample from the
00281          *     noise source.
00282          *
00283          * (Nothing to do; we already have the current sample.)
00284          */
00285 
00286         /* 2.  If S = N, then a new run of the test begins: */
00287         if ( sample_count == ADAPTIVE_PROPORTION_WINDOW_SIZE ) {
00288 
00289                 /* a.  A = the current sample */
00290                 current_counted_sample = sample;
00291 
00292                 /* b.  S = 0 */
00293                 sample_count = 0;
00294 
00295                 /* c. B = 0 */
00296                 repetition_count = 0;
00297 
00298         } else {
00299 
00300                 /* Else: (the test is already running)
00301                  * a.  S = S + 1
00302                  */
00303                 sample_count++;
00304 
00305                 /* b.  If A = the current sample, then: */
00306                 if ( sample == current_counted_sample ) {
00307 
00308                         /* i.   B = B + 1 */
00309                         repetition_count++;
00310 
00311                         /* ii.  If S (sic) > C then raise an error
00312                          *      condition, because the test has
00313                          *      detected a failure
00314                          */
00315                         if ( repetition_count > adaptive_proportion_cutoff() )
00316                                 return -EPIPE_ADAPTIVE_PROPORTION_TEST;
00317 
00318                 }
00319         }
00320 
00321         return 0;
00322 }
00323 
00324 /**
00325  * Get entropy sample
00326  *
00327  * @ret entropy         Entropy sample
00328  * @ret rc              Return status code
00329  *
00330  * This is the GetEntropy function defined in ANS X9.82 Part 2
00331  * (October 2011 Draft) Section 6.5.1.
00332  */
00333 static int get_entropy ( entropy_sample_t *entropy ) {
00334         static int rc = 0;
00335         noise_sample_t noise;
00336 
00337         /* Any failure is permanent */
00338         if ( rc != 0 )
00339                 return rc;
00340 
00341         /* Get noise sample */
00342         if ( ( rc = get_noise ( &noise ) ) != 0 )
00343                 return rc;
00344 
00345         /* Perform Repetition Count Test and Adaptive Proportion Test
00346          * as mandated by ANS X9.82 Part 2 (October 2011 Draft)
00347          * Section 8.5.2.1.1.
00348          */
00349         if ( ( rc = repetition_count_test ( noise ) ) != 0 )
00350                 return rc;
00351         if ( ( rc = adaptive_proportion_test ( noise ) ) != 0 )
00352                 return rc;
00353 
00354         /* We do not use any optional conditioning component */
00355         *entropy = noise;
00356 
00357         return 0;
00358 }
00359 
00360 /**
00361  * Calculate number of samples required for startup tests
00362  *
00363  * @ret num_samples     Number of samples required
00364  *
00365  * ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.5 requires
00366  * that at least one full cycle of the continuous tests must be
00367  * performed at start-up.
00368  */
00369 static inline __attribute__ (( always_inline )) unsigned int
00370 startup_test_count ( void ) {
00371         unsigned int num_samples;
00372 
00373         /* At least max(N,C) samples shall be generated by the noise
00374          * source for start-up testing.
00375          */
00376         num_samples = repetition_count_cutoff();
00377         if ( num_samples < adaptive_proportion_cutoff() )
00378                 num_samples = adaptive_proportion_cutoff();
00379         linker_assert ( __builtin_constant_p ( num_samples ),
00380                         startup_test_count_not_constant );
00381 
00382         return num_samples;
00383 }
00384 
00385 /**
00386  * Create next nonce value
00387  *
00388  * @ret nonce           Nonce
00389  *
00390  * This is the MakeNextNonce function defined in ANS X9.82 Part 4
00391  * (April 2011 Draft) Section 13.3.4.2.
00392  */
00393 static uint32_t make_next_nonce ( void ) {
00394         static uint32_t nonce;
00395 
00396         /* The simplest implementation of a nonce uses a large counter */
00397         nonce++;
00398 
00399         return nonce;
00400 }
00401 
00402 /**
00403  * Obtain entropy input temporary buffer
00404  *
00405  * @v num_samples       Number of entropy samples
00406  * @v tmp               Temporary buffer
00407  * @v tmp_len           Length of temporary buffer
00408  * @ret rc              Return status code
00409  *
00410  * This is (part of) the implementation of the Get_entropy_input
00411  * function (using an entropy source as the source of entropy input
00412  * and condensing each entropy source output after each GetEntropy
00413  * call) as defined in ANS X9.82 Part 4 (April 2011 Draft) Section
00414  * 13.3.4.2.
00415  *
00416  * To minimise code size, the number of samples required is calculated
00417  * at compilation time.
00418  */
00419 int get_entropy_input_tmp ( unsigned int num_samples, uint8_t *tmp,
00420                             size_t tmp_len ) {
00421         static unsigned int startup_tested = 0;
00422         struct {
00423                 uint32_t nonce;
00424                 entropy_sample_t sample;
00425         } __attribute__ (( packed )) data;;
00426         uint8_t df_buf[tmp_len];
00427         unsigned int i;
00428         int rc;
00429 
00430         /* Enable entropy gathering */
00431         if ( ( rc = entropy_enable() ) != 0 )
00432                 return rc;
00433 
00434         /* Perform mandatory startup tests, if not yet performed */
00435         for ( ; startup_tested < startup_test_count() ; startup_tested++ ) {
00436                 if ( ( rc = get_entropy ( &data.sample ) ) != 0 )
00437                         goto err_get_entropy;
00438         }
00439 
00440         /* 3.  entropy_total = 0
00441          *
00442          * (Nothing to do; the number of entropy samples required has
00443          * already been precalculated.)
00444          */
00445 
00446         /* 4.  tmp = a fixed n-bit value, such as 0^n */
00447         memset ( tmp, 0, tmp_len );
00448 
00449         /* 5.  While ( entropy_total < min_entropy ) */
00450         while ( num_samples-- ) {
00451                 /* 5.1.  ( status, entropy_bitstring, assessed_entropy )
00452                  *       = GetEntropy()
00453                  * 5.2.  If status indicates an error, return ( status, Null )
00454                  */
00455                 if ( ( rc = get_entropy ( &data.sample ) ) != 0 )
00456                         goto err_get_entropy;
00457 
00458                 /* 5.3.  nonce = MakeNextNonce() */
00459                 data.nonce = make_next_nonce();
00460 
00461                 /* 5.4.  tmp = tmp XOR
00462                  *             df ( ( nonce || entropy_bitstring ), n )
00463                  */
00464                 hash_df ( &entropy_hash_df_algorithm, &data, sizeof ( data ),
00465                           df_buf, sizeof ( df_buf ) );
00466                 for ( i = 0 ; i < tmp_len ; i++ )
00467                         tmp[i] ^= df_buf[i];
00468 
00469                 /* 5.5.  entropy_total = entropy_total + assessed_entropy
00470                  *
00471                  * (Nothing to do; the number of entropy samples
00472                  * required has already been precalculated.)
00473                  */
00474         }
00475 
00476         /* Disable entropy gathering */
00477         entropy_disable();
00478 
00479         return 0;
00480 
00481  err_get_entropy:
00482         entropy_disable();
00483         return rc;
00484 }