2 * Copyright (C) 2012 Michael Brown <mbrown@fensystems.co.uk>.
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.
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.
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
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.
24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL
);
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
39 #include <ipxe/crypto.h>
40 #include <ipxe/hash_df.h>
41 #include <ipxe/entropy.h>
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" )
54 * Calculate cutoff value for the repetition count test
56 * @ret cutoff Cutoff value
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.
61 static inline __attribute__ (( always_inline
)) unsigned int
62 repetition_count_cutoff ( void ) {
63 double max_repetitions
;
66 /* The cutoff formula for the repetition test is:
68 * C = ( 1 + ( -log2(W) / H_min ) )
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).
73 max_repetitions
= ( 1 + ( MIN_ENTROPY ( 30 ) /
74 min_entropy_per_sample() ) );
76 /* Round up to a whole number of repetitions. We don't have
77 * the ceil() function available, so do the rounding by hand.
79 cutoff
= max_repetitions
;
80 if ( cutoff
< max_repetitions
)
82 linker_assert ( ( cutoff
>= max_repetitions
), rounding_error
);
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.
89 linker_assert ( __builtin_constant_p ( cutoff
),
90 repetition_count_cutoff_not_constant
);
96 * Perform repetition count test
98 * @v sample Noise sample
99 * @ret rc Return status code
101 * This is the Repetition Count Test defined in ANS X9.82 Part 2
102 * (October 2011 Draft) Section 8.5.2.1.2.
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;
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
113 /* 1. For each new sample processed:
115 * (Note that the test for "repetition_count > 0" ensures that
116 * the initial value of most_recent_sample is treated as being
119 if ( ( sample
== most_recent_sample
) && ( repetition_count
> 0 ) ) {
121 /* a) If the new sample = A, then B is incremented by one. */
124 /* i. If B >= C, then an error condition is raised
125 * due to a failure of the test
127 if ( repetition_count
>= repetition_count_cutoff() )
128 return -EPIPE_REPETITION_COUNT_TEST
;
135 most_recent_sample
= sample
;
138 repetition_count
= 1;
145 * Window size for the adaptive proportion test
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.
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.
156 #define ADAPTIVE_PROPORTION_WINDOW_SIZE 64
159 * Combine adaptive proportion test window size and min-entropy
161 * @v n N (window size)
162 * @v h H (min-entropy)
163 * @ret n_h (N,H) combined value
165 #define APC_N_H( n, h ) ( ( (n) << 8 ) | (h) )
168 * Define a row of the adaptive proportion cutoff table
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
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;
184 /** Value used to represent "N/A" in adaptive proportion cutoff table */
188 * Look up value in adaptive proportion test cutoff table
190 * @v n N (window size)
191 * @v h H (min-entropy)
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.
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 );
226 * Calculate cutoff value for the adaptive proportion test
228 * @ret cutoff Cutoff value
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.
233 static inline __attribute__ (( always_inline
)) unsigned int
234 adaptive_proportion_cutoff ( void ) {
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
);
244 /* Fail unless cutoff value is a build-time constant */
245 linker_assert ( __builtin_constant_p ( cutoff
),
246 adaptive_proportion_cutoff_not_constant
);
248 /* Fail if cutoff value is N/A */
249 linker_assert ( ( cutoff
!= APC_NA
),
250 adaptive_proportion_cutoff_not_applicable
);
256 * Perform adaptive proportion test
258 * @v sample Noise sample
259 * @ret rc Return status code
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.
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
;
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
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
280 /* 1. The entropy source draws the current sample from the
283 * (Nothing to do; we already have the current sample.)
286 /* 2. If S = N, then a new run of the test begins: */
287 if ( sample_count
== ADAPTIVE_PROPORTION_WINDOW_SIZE
) {
289 /* a. A = the current sample */
290 current_counted_sample
= sample
;
296 repetition_count
= 0;
300 /* Else: (the test is already running)
305 /* b. If A = the current sample, then: */
306 if ( sample
== current_counted_sample
) {
311 /* ii. If S (sic) > C then raise an error
312 * condition, because the test has
315 if ( repetition_count
> adaptive_proportion_cutoff() )
316 return -EPIPE_ADAPTIVE_PROPORTION_TEST
;
327 * @ret entropy Entropy sample
328 * @ret rc Return status code
330 * This is the GetEntropy function defined in ANS X9.82 Part 2
331 * (October 2011 Draft) Section 6.5.1.
333 static int get_entropy ( entropy_sample_t
*entropy
) {
335 noise_sample_t noise
;
337 /* Any failure is permanent */
341 /* Get noise sample */
342 if ( ( rc
= get_noise ( &noise
) ) != 0 )
345 /* Perform Repetition Count Test and Adaptive Proportion Test
346 * as mandated by ANS X9.82 Part 2 (October 2011 Draft)
349 if ( ( rc
= repetition_count_test ( noise
) ) != 0 )
351 if ( ( rc
= adaptive_proportion_test ( noise
) ) != 0 )
354 /* We do not use any optional conditioning component */
361 * Calculate number of samples required for startup tests
363 * @ret num_samples Number of samples required
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.
369 static inline __attribute__ (( always_inline
)) unsigned int
370 startup_test_count ( void ) {
371 unsigned int num_samples
;
373 /* At least max(N,C) samples shall be generated by the noise
374 * source for start-up testing.
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
);
386 * Create next nonce value
390 * This is the MakeNextNonce function defined in ANS X9.82 Part 4
391 * (April 2011 Draft) Section 13.3.4.2.
393 static uint32_t make_next_nonce ( void ) {
394 static uint32_t nonce
;
396 /* The simplest implementation of a nonce uses a large counter */
403 * Obtain entropy input temporary buffer
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
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
416 * To minimise code size, the number of samples required is calculated
417 * at compilation time.
419 int get_entropy_input_tmp ( unsigned int num_samples
, uint8_t *tmp
,
421 static unsigned int startup_tested
= 0;
424 entropy_sample_t sample
;
425 } __attribute__ (( packed
)) data
;;
426 uint8_t df_buf
[tmp_len
];
430 /* Enable entropy gathering */
431 if ( ( rc
= entropy_enable() ) != 0 )
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
;
440 /* 3. entropy_total = 0
442 * (Nothing to do; the number of entropy samples required has
443 * already been precalculated.)
446 /* 4. tmp = a fixed n-bit value, such as 0^n */
447 memset ( tmp
, 0, tmp_len
);
449 /* 5. While ( entropy_total < min_entropy ) */
450 while ( num_samples
-- ) {
451 /* 5.1. ( status, entropy_bitstring, assessed_entropy )
453 * 5.2. If status indicates an error, return ( status, Null )
455 if ( ( rc
= get_entropy ( &data
.sample
) ) != 0 )
456 goto err_get_entropy
;
458 /* 5.3. nonce = MakeNextNonce() */
459 data
.nonce
= make_next_nonce();
461 /* 5.4. tmp = tmp XOR
462 * df ( ( nonce || entropy_bitstring ), n )
464 hash_df ( &entropy_hash_df_algorithm
, &data
, sizeof ( data
),
465 df_buf
, sizeof ( df_buf
) );
466 for ( i
= 0 ; i
< tmp_len
; i
++ )
469 /* 5.5. entropy_total = entropy_total + assessed_entropy
471 * (Nothing to do; the number of entropy samples
472 * required has already been precalculated.)
476 /* Disable entropy gathering */