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