src/crypto/entropy.c

   1 /*
   2  * Copyright (C) 2012 Michael Brown <mbrown@fensystems.co.uk>.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License as
   6  * published by the Free Software Foundation; either version 2 of the
   7  * License, or any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  17  * 02110-1301, USA.
  18  *
  19  * You can also choose to distribute this program under the terms of
  20  * the Unmodified Binary Distribution Licence (as given in the file
  21  * COPYING.UBDL), provided that you have satisfied its requirements.
  22  */
  23
  24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
  25
  26 /** @file
  27  *
  28  * Entropy source
  29  *
  30  * This algorithm is designed to comply with ANS X9.82 Part 4 (April
  31  * 2011 Draft) Section 13.3.  This standard is unfortunately not
  32  * freely available.
  33  */
  34
  35 #include <stdint.h>
  36 #include <assert.h>
  37 #include <string.h>
  38 #include <errno.h>
  39 #include <ipxe/crypto.h>
  40 #include <ipxe/hash_df.h>
  41 #include <ipxe/entropy.h>
  42
  43 /* Disambiguate the various error causes */
  44 #define EPIPE_REPETITION_COUNT_TEST \
  45         __einfo_error ( EINFO_EPIPE_REPETITION_COUNT_TEST )
  46 #define EINFO_EPIPE_REPETITION_COUNT_TEST \
  47         __einfo_uniqify ( EINFO_EPIPE, 0x01, "Repetition count test failed" )
  48 #define EPIPE_ADAPTIVE_PROPORTION_TEST \
  49         __einfo_error ( EINFO_EPIPE_ADAPTIVE_PROPORTION_TEST )
  50 #define EINFO_EPIPE_ADAPTIVE_PROPORTION_TEST \
  51         __einfo_uniqify ( EINFO_EPIPE, 0x02, "Adaptive proportion test failed" )
  52
  53 /**
  54  * Calculate cutoff value for the repetition count test
  55  *
  56  * @ret cutoff          Cutoff value
  57  *
  58  * This is the cutoff value for the Repetition Count Test defined in
  59  * ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.2.
  60  */
  61 static inline __attribute__ (( always_inline )) unsigned int
  62 repetition_count_cutoff ( void ) {
  63         double max_repetitions;
  64         unsigned int cutoff;
  65
  66         /* The cutoff formula for the repetition test is:
  67          *
  68          *   C = ( 1 + ( -log2(W) / H_min ) )
  69          *
  70          * where W is set at 2^(-30) (in ANS X9.82 Part 2 (October
  71          * 2011 Draft) Section 8.5.2.1.3.1).
  72          */
  73         max_repetitions = ( 1 + ( MIN_ENTROPY ( 30 ) /
  74                                   min_entropy_per_sample() ) );
  75
  76         /* Round up to a whole number of repetitions.  We don't have
  77          * the ceil() function available, so do the rounding by hand.
  78          */
  79         cutoff = max_repetitions;
  80         if ( cutoff < max_repetitions )
  81                 cutoff++;
  82         linker_assert ( ( cutoff >= max_repetitions ), rounding_error );
  83
  84         /* Floating-point operations are not allowed in iPXE since we
  85          * never set up a suitable environment.  Abort the build
  86          * unless the calculated number of repetitions is a
  87          * compile-time constant.
  88          */
  89         linker_assert ( __builtin_constant_p ( cutoff ),
  90                         repetition_count_cutoff_not_constant );
  91
  92         return cutoff;
  93 }
  94
  95 /**
  96  * Perform repetition count test
  97  *
  98  * @v sample            Noise sample
  99  * @ret rc              Return status code
 100  *
 101  * This is the Repetition Count Test defined in ANS X9.82 Part 2
 102  * (October 2011 Draft) Section 8.5.2.1.2.
 103  */
 104 static int repetition_count_test ( noise_sample_t sample ) {
 105         static noise_sample_t most_recent_sample;
 106         static unsigned int repetition_count = 0;
 107
 108         /* A = the most recently seen sample value
 109          * B = the number of times that value A has been seen in a row
 110          * C = the cutoff value above which the repetition test should fail
 111          */
 112
 113         /* 1.  For each new sample processed:
 114          *
 115          * (Note that the test for "repetition_count > 0" ensures that
 116          * the initial value of most_recent_sample is treated as being
 117          * undefined.)
 118          */
 119         if ( ( sample == most_recent_sample ) && ( repetition_count > 0 ) ) {
 120
 121                 /* a) If the new sample = A, then B is incremented by one. */
 122                 repetition_count++;
 123
 124                 /*    i.  If B >= C, then an error condition is raised
 125                  *        due to a failure of the test
 126                  */
 127                 if ( repetition_count >= repetition_count_cutoff() )
 128                         return -EPIPE_REPETITION_COUNT_TEST;
 129
 130         } else {
 131
 132                 /* b) Else:
 133                  *    i.  A = new sample
 134                  */
 135                 most_recent_sample = sample;
 136
 137                 /*    ii. B = 1 */
 138                 repetition_count = 1;
 139         }
 140
 141         return 0;
 142 }
 143
 144 /**
 145  * Window size for the adaptive proportion test
 146  *
 147  * ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.3.1.1 allows
 148  * five possible window sizes: 16, 64, 256, 4096 and 65536.
 149  *
 150  * We expect to generate relatively few (<256) entropy samples during
 151  * a typical iPXE run; the use of a large window size would mean that
 152  * the test would never complete a single cycle.  We use a window size
 153  * of 64, which is the smallest window size that permits values of
 154  * H_min down to one bit per sample.
 155  */
 156 #define ADAPTIVE_PROPORTION_WINDOW_SIZE 64
 157
 158 /**
 159  * Combine adaptive proportion test window size and min-entropy
 160  *
 161  * @v n                 N (window size)
 162  * @v h                 H (min-entropy)
 163  * @ret n_h             (N,H) combined value
 164  */
 165 #define APC_N_H( n, h ) ( ( (n) << 8 ) | (h) )
 166
 167 /**
 168  * Define a row of the adaptive proportion cutoff table
 169  *
 170  * @v h                 H (min-entropy)
 171  * @v c16               Cutoff for N=16
 172  * @v c64               Cutoff for N=64
 173  * @v c256              Cutoff for N=256
 174  * @v c4096             Cutoff for N=4096
 175  * @v c65536            Cutoff for N=65536
 176  */
 177 #define APC_TABLE_ROW( h, c16, c64, c256, c4096, c65536)           \
 178         case APC_N_H ( 16, h ) :        return c16;                \
 179         case APC_N_H ( 64, h ) :        return c64;                \
 180         case APC_N_H ( 256, h ) :       return c256;               \
 181         case APC_N_H ( 4096, h ) :      return c4096;              \
 182         case APC_N_H ( 65536, h ) :     return c65536;
 183
 184 /** Value used to represent "N/A" in adaptive proportion cutoff table */
 185 #define APC_NA 0
 186
 187 /**
 188  * Look up value in adaptive proportion test cutoff table
 189  *
 190  * @v n                 N (window size)
 191  * @v h                 H (min-entropy)
 192  * @ret cutoff          Cutoff
 193  *
 194  * This is the table of cutoff values defined in ANS X9.82 Part 2
 195  * (October 2011 Draft) Section 8.5.2.1.3.1.2.
 196  */
 197 static inline __attribute__ (( always_inline )) unsigned int
 198 adaptive_proportion_cutoff_lookup ( unsigned int n, unsigned int h ) {
 199         switch ( APC_N_H ( n, h ) ) {
 200                 APC_TABLE_ROW (  1, APC_NA,     51,    168,   2240,  33537 );
 201                 APC_TABLE_ROW (  2, APC_NA,     35,    100,   1193,  17053 );
 202                 APC_TABLE_ROW (  3,     10,     24,     61,    643,   8705 );
 203                 APC_TABLE_ROW (  4,      8,     16,     38,    354,   4473 );
 204                 APC_TABLE_ROW (  5,      6,     12,     25,    200,   2321 );
 205                 APC_TABLE_ROW (  6,      5,      9,     17,    117,   1220 );
 206                 APC_TABLE_ROW (  7,      4,      7,     15,     71,    653 );
 207                 APC_TABLE_ROW (  8,      4,      5,      9,     45,    358 );
 208                 APC_TABLE_ROW (  9,      3,      4,      7,     30,    202 );
 209                 APC_TABLE_ROW ( 10,      3,      4,      5,     21,    118 );
 210                 APC_TABLE_ROW ( 11,      2,      3,      4,     15,     71 );
 211                 APC_TABLE_ROW ( 12,      2,      3,      4,     11,     45 );
 212                 APC_TABLE_ROW ( 13,      2,      2,      3,      9,     30 );
 213                 APC_TABLE_ROW ( 14,      2,      2,      3,      7,     21 );
 214                 APC_TABLE_ROW ( 15,      1,      2,      2,      6,     15 );
 215                 APC_TABLE_ROW ( 16,      1,      2,      2,      5,     11 );
 216                 APC_TABLE_ROW ( 17,      1,      1,      2,      4,      9 );
 217                 APC_TABLE_ROW ( 18,      1,      1,      2,      4,      7 );
 218                 APC_TABLE_ROW ( 19,      1,      1,      1,      3,      6 );
 219                 APC_TABLE_ROW ( 20,      1,      1,      1,      3,      5 );
 220         default:
 221                 return APC_NA;
 222         }
 223 }
 224
 225 /**
 226  * Calculate cutoff value for the adaptive proportion test
 227  *
 228  * @ret cutoff          Cutoff value
 229  *
 230  * This is the cutoff value for the Adaptive Proportion Test defined
 231  * in ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.3.1.2.
 232  */
 233 static inline __attribute__ (( always_inline )) unsigned int
 234 adaptive_proportion_cutoff ( void ) {
 235         unsigned int h;
 236         unsigned int n;
 237         unsigned int cutoff;
 238
 239         /* Look up cutoff value in cutoff table */
 240         n = ADAPTIVE_PROPORTION_WINDOW_SIZE;
 241         h = ( min_entropy_per_sample() / MIN_ENTROPY_SCALE );
 242         cutoff = adaptive_proportion_cutoff_lookup ( n, h );
 243
 244         /* Fail unless cutoff value is a build-time constant */
 245         linker_assert ( __builtin_constant_p ( cutoff ),
 246                         adaptive_proportion_cutoff_not_constant );
 247
 248         /* Fail if cutoff value is N/A */
 249         linker_assert ( ( cutoff != APC_NA ),
 250                         adaptive_proportion_cutoff_not_applicable );
 251
 252         return cutoff;
 253 }
 254
 255 /**
 256  * Perform adaptive proportion test
 257  *
 258  * @v sample            Noise sample
 259  * @ret rc              Return status code
 260  *
 261  * This is the Adaptive Proportion Test for the Most Common Value
 262  * defined in ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.3.
 263  */
 264 static int adaptive_proportion_test ( noise_sample_t sample ) {
 265         static noise_sample_t current_counted_sample;
 266         static unsigned int sample_count = ADAPTIVE_PROPORTION_WINDOW_SIZE;
 267         static unsigned int repetition_count;
 268
 269         /* A = the sample value currently being counted
 270          * B = the number of samples examined in this run of the test so far
 271          * N = the total number of samples that must be observed in
 272          *     one run of the test, also known as the "window size" of
 273          *     the test
 274          * B = the current number of times that S (sic) has been seen
 275          *     in the W (sic) samples examined so far
 276          * C = the cutoff value above which the repetition test should fail
 277          * W = the probability of a false positive: 2^-30
 278          */
 279
 280         /* 1.  The entropy source draws the current sample from the
 281          *     noise source.
 282          *
 283          * (Nothing to do; we already have the current sample.)
 284          */
 285
 286         /* 2.  If S = N, then a new run of the test begins: */
 287         if ( sample_count == ADAPTIVE_PROPORTION_WINDOW_SIZE ) {
 288
 289                 /* a.  A = the current sample */
 290                 current_counted_sample = sample;
 291
 292                 /* b.  S = 0 */
 293                 sample_count = 0;
 294
 295                 /* c. B = 0 */
 296                 repetition_count = 0;
 297
 298         } else {
 299
 300                 /* Else: (the test is already running)
 301                  * a.  S = S + 1
 302                  */
 303                 sample_count++;
 304
 305                 /* b.  If A = the current sample, then: */
 306                 if ( sample == current_counted_sample ) {
 307
 308                         /* i.   B = B + 1 */
 309                         repetition_count++;
 310
 311                         /* ii.  If S (sic) > C then raise an error
 312                          *      condition, because the test has
 313                          *      detected a failure
 314                          */
 315                         if ( repetition_count > adaptive_proportion_cutoff() )
 316                                 return -EPIPE_ADAPTIVE_PROPORTION_TEST;
 317
 318                 }
 319         }
 320
 321         return 0;
 322 }
 323
 324 /**
 325  * Get entropy sample
 326  *
 327  * @ret entropy         Entropy sample
 328  * @ret rc              Return status code
 329  *
 330  * This is the GetEntropy function defined in ANS X9.82 Part 2
 331  * (October 2011 Draft) Section 6.5.1.
 332  */
 333 static int get_entropy ( entropy_sample_t *entropy ) {
 334         static int rc = 0;
 335         noise_sample_t noise;
 336
 337         /* Any failure is permanent */
 338         if ( rc != 0 )
 339                 return rc;
 340
 341         /* Get noise sample */
 342         if ( ( rc = get_noise ( &noise ) ) != 0 )
 343                 return rc;
 344
 345         /* Perform Repetition Count Test and Adaptive Proportion Test
 346          * as mandated by ANS X9.82 Part 2 (October 2011 Draft)
 347          * Section 8.5.2.1.1.
 348          */
 349         if ( ( rc = repetition_count_test ( noise ) ) != 0 )
 350                 return rc;
 351         if ( ( rc = adaptive_proportion_test ( noise ) ) != 0 )
 352                 return rc;
 353
 354         /* We do not use any optional conditioning component */
 355         *entropy = noise;
 356
 357         return 0;
 358 }
 359
 360 /**
 361  * Calculate number of samples required for startup tests
 362  *
 363  * @ret num_samples     Number of samples required
 364  *
 365  * ANS X9.82 Part 2 (October 2011 Draft) Section 8.5.2.1.5 requires
 366  * that at least one full cycle of the continuous tests must be
 367  * performed at start-up.
 368  */
 369 static inline __attribute__ (( always_inline )) unsigned int
 370 startup_test_count ( void ) {
 371         unsigned int num_samples;
 372
 373         /* At least max(N,C) samples shall be generated by the noise
 374          * source for start-up testing.
 375          */
 376         num_samples = repetition_count_cutoff();
 377         if ( num_samples < adaptive_proportion_cutoff() )
 378                 num_samples = adaptive_proportion_cutoff();
 379         linker_assert ( __builtin_constant_p ( num_samples ),
 380                         startup_test_count_not_constant );
 381
 382         return num_samples;
 383 }
 384
 385 /**
 386  * Create next nonce value
 387  *
 388  * @ret nonce           Nonce
 389  *
 390  * This is the MakeNextNonce function defined in ANS X9.82 Part 4
 391  * (April 2011 Draft) Section 13.3.4.2.
 392  */
 393 static uint32_t make_next_nonce ( void ) {
 394         static uint32_t nonce;
 395
 396         /* The simplest implementation of a nonce uses a large counter */
 397         nonce++;
 398
 399         return nonce;
 400 }
 401
 402 /**
 403  * Obtain entropy input temporary buffer
 404  *
 405  * @v num_samples       Number of entropy samples
 406  * @v tmp               Temporary buffer
 407  * @v tmp_len           Length of temporary buffer
 408  * @ret rc              Return status code
 409  *
 410  * This is (part of) the implementation of the Get_entropy_input
 411  * function (using an entropy source as the source of entropy input
 412  * and condensing each entropy source output after each GetEntropy
 413  * call) as defined in ANS X9.82 Part 4 (April 2011 Draft) Section
 414  * 13.3.4.2.
 415  *
 416  * To minimise code size, the number of samples required is calculated
 417  * at compilation time.
 418  */
 419 int get_entropy_input_tmp ( unsigned int num_samples, uint8_t *tmp,
 420                             size_t tmp_len ) {
 421         static unsigned int startup_tested = 0;
 422         struct {
 423                 uint32_t nonce;
 424                 entropy_sample_t sample;
 425         } __attribute__ (( packed )) data;;
 426         uint8_t df_buf[tmp_len];
 427         unsigned int i;
 428         int rc;
 429
 430         /* Enable entropy gathering */
 431         if ( ( rc = entropy_enable() ) != 0 )
 432                 return rc;
 433
 434         /* Perform mandatory startup tests, if not yet performed */
 435         for ( ; startup_tested < startup_test_count() ; startup_tested++ ) {
 436                 if ( ( rc = get_entropy ( &data.sample ) ) != 0 )
 437                         goto err_get_entropy;
 438         }
 439
 440         /* 3.  entropy_total = 0
 441          *
 442          * (Nothing to do; the number of entropy samples required has
 443          * already been precalculated.)
 444          */
 445
 446         /* 4.  tmp = a fixed n-bit value, such as 0^n */
 447         memset ( tmp, 0, tmp_len );
 448
 449         /* 5.  While ( entropy_total < min_entropy ) */
 450         while ( num_samples-- ) {
 451                 /* 5.1.  ( status, entropy_bitstring, assessed_entropy )
 452                  *       = GetEntropy()
 453                  * 5.2.  If status indicates an error, return ( status, Null )
 454                  */
 455                 if ( ( rc = get_entropy ( &data.sample ) ) != 0 )
 456                         goto err_get_entropy;
 457
 458                 /* 5.3.  nonce = MakeNextNonce() */
 459                 data.nonce = make_next_nonce();
 460
 461                 /* 5.4.  tmp = tmp XOR
 462                  *             df ( ( nonce || entropy_bitstring ), n )
 463                  */
 464                 hash_df ( &entropy_hash_df_algorithm, &data, sizeof ( data ),
 465                           df_buf, sizeof ( df_buf ) );
 466                 for ( i = 0 ; i < tmp_len ; i++ )
 467                         tmp[i] ^= df_buf[i];
 468
 469                 /* 5.5.  entropy_total = entropy_total + assessed_entropy
 470                  *
 471                  * (Nothing to do; the number of entropy samples
 472                  * required has already been precalculated.)
 473                  */
 474         }
 475
 476         /* Disable entropy gathering */
 477         entropy_disable();
 478
 479         return 0;
 480
 481  err_get_entropy:
 482         entropy_disable();
 483         return rc;
 484 }