1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
|
#ifndef _IPXE_ENTROPY_H
#define _IPXE_ENTROPY_H
/** @file
*
* Entropy source
*
*/
FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
#include <stdint.h>
#include <string.h>
#include <assert.h>
#include <ipxe/hash_df.h>
#include <ipxe/sha256.h>
#include <ipxe/tables.h>
#include <config/entropy.h>
/** A noise sample */
typedef uint8_t noise_sample_t;
/** An entropy sample */
typedef uint8_t entropy_sample_t;
/** An amount of min-entropy
*
* Expressed as a fixed-point quantity in order to avoid floating
* point calculations.
*/
typedef unsigned int min_entropy_t;
/** Fixed-point scale for min-entropy amounts */
#define MIN_ENTROPY_SCALE ( 1 << 16 )
/**
* Construct a min-entropy fixed-point value
*
* @v bits min-entropy in bits
* @ret min_entropy min-entropy as a fixed-point value
*/
#define MIN_ENTROPY( bits ) \
( ( min_entropy_t ) ( (bits) * MIN_ENTROPY_SCALE ) )
/** An entropy source */
struct entropy_source {
/** Name */
const char *name;
/**
* min-entropy per sample
*
* min-entropy is defined in ANS X9.82 Part 1-2006 Section 8.3 and in
* NIST SP 800-90 Appendix C.3 as
*
* H_min = -log2 ( p_max )
*
* where p_max is the probability of the most likely sample value.
*
* Filled in by entropy_init().
*/
min_entropy_t min_entropy_per_sample;
/**
* Repetition count test 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.
*
* Filled in by entropy_init().
*/
unsigned int repetition_count_cutoff;
/**
* Adaptive proportion test 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.
*
* Filled in by entropy_init().
*/
unsigned int adaptive_proportion_cutoff;
/**
* Startup test count
*
* 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.
*/
unsigned int startup_test_count;
/**
* Enable entropy gathering
*
* @ret rc Return status code
*/
int ( * enable ) ( void );
/**
* Disable entropy gathering
*
*/
void ( * disable ) ( void );
/**
* Get noise sample
*
* @ret noise Noise sample
* @ret rc Return status code
*
* This is the GetNoise function defined in ANS X9.82 Part 2
* (October 2011 Draft) Section 6.5.2.
*/
int ( * get_noise ) ( noise_sample_t *noise );
};
/** Entropy source table */
#define ENTROPY_SOURCES __table ( struct entropy_source, "entropy_sources" )
/** Declare an entropy source */
#define __entropy_source( order ) __table_entry ( ENTROPY_SOURCES, order )
/** @defgroup entropy_source_order Entropy source order
*
* @{
*/
#define ENTROPY_PREFERRED 01 /**< Preferred entropy source */
#define ENTROPY_NORMAL 02 /**< Normal entropy source */
#define ENTROPY_FALLBACK 03 /**< Fallback entropy source */
/** @} */
extern int get_entropy_input_tmp ( min_entropy_t min_entropy, uint8_t *tmp,
size_t tmp_len );
/** Use SHA-256 as the underlying hash algorithm for Hash_df
*
* Hash_df using SHA-256 is an Approved algorithm in ANS X9.82.
*/
#define entropy_hash_df_algorithm sha256_algorithm
/** Underlying hash algorithm output length (in bytes) */
#define ENTROPY_HASH_DF_OUTLEN_BYTES SHA256_DIGEST_SIZE
/**
* Obtain entropy input
*
* @v min_entropy_bits Minimum amount of entropy, in bits
* @v data Data buffer
* @v min_len Minimum length of entropy input, in bytes
* @v max_len Maximum length of entropy input, in bytes
* @ret len Length of entropy input, in bytes, or negative error
*
* This is 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.
*
* This function is inlined to avoid unnecessarily linking in
* hash_df(), since the length inputs are always compile-time
* constants.
*/
static inline __attribute__ (( always_inline )) int
get_entropy_input ( unsigned int min_entropy_bits, void *data, size_t min_len,
size_t max_len ) {
size_t tmp_len = ( ( ( min_entropy_bits * 2 ) + 7 ) / 8 );
uint8_t tmp_buf[ tmp_len ];
uint8_t *tmp = ( ( tmp_len > max_len ) ? tmp_buf : data );
unsigned int n;
int rc;
/* Sanity check */
linker_assert ( ( min_entropy_bits <= ( 8 * max_len ) ),
entropy_buffer_too_small );
/* Round up minimum entropy to an integral number of bytes */
min_entropy_bits = ( ( min_entropy_bits + 7 ) & ~7 );
/* (Unnumbered). The output length of the hash function shall
* meet or exceed the security strength indicated by the
* min_entropy parameter.
*/
linker_assert ( ( ( 8 * ENTROPY_HASH_DF_OUTLEN_BYTES ) >=
min_entropy_bits ), hash_df_algorithm_too_weak );
/* 1. If ( min_length > max_length ), then return ( FAILURE, Null ) */
linker_assert ( ( min_len <= max_len ), min_len_greater_than_max_len );
/* 2. n = 2 * min_entropy */
n = ( 2 * min_entropy_bits );
/* 3. entropy_total = 0
* 4. tmp = a fixed n-bit value, such as 0^n
* 5. While ( entropy_total < min_entropy )
* 5.1. ( status, entropy_bitstring, assessed_entropy )
* = GetEntropy()
* 5.2. If status indicates an error, return ( status, Null )
* 5.3. nonce = MakeNextNonce()
* 5.4. tmp = tmp XOR df ( ( nonce || entropy_bitstring ), n )
* 5.5. entropy_total = entropy_total + assessed_entropy
*
* (The implementation of these steps is inside the function
* get_entropy_input_tmp().)
*/
linker_assert ( __builtin_constant_p ( tmp_len ),
tmp_len_not_constant );
linker_assert ( ( n == ( 8 * tmp_len ) ), tmp_len_mismatch );
if ( ( rc = get_entropy_input_tmp ( MIN_ENTROPY ( min_entropy_bits ),
tmp, tmp_len ) ) != 0 ) {
return rc;
}
/* 6. If ( n < min_length ), then tmp = tmp || 0^(min_length-n)
* 7. If ( n > max_length ), then tmp = df ( tmp, max_length )
* 8. Return ( SUCCESS, tmp )
*/
if ( tmp_len < min_len ) {
/* (Data is already in-place.) */
linker_assert ( ( data == tmp ), data_not_inplace );
memset ( ( data + tmp_len ), 0, ( min_len - tmp_len ) );
return min_len;
} else if ( tmp_len > max_len ) {
linker_assert ( ( tmp == tmp_buf ), data_inplace );
hash_df ( &entropy_hash_df_algorithm, tmp, tmp_len,
data, max_len );
return max_len;
} else {
/* (Data is already in-place.) */
linker_assert ( ( data == tmp ), data_not_inplace );
return tmp_len;
}
}
/**
* Calculate cutoff value for the repetition count test
*
* @v min_entropy_per_sample Min-entropy per sample
* @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
entropy_repetition_count_cutoff ( min_entropy_t min_entropy_per_sample ) {
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 + ( MIN_ENTROPY ( 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;
}
/**
* 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
entropy_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
*
* @v min_entropy_per_sample Min-entropy per sample
* @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
entropy_adaptive_proportion_cutoff ( min_entropy_t min_entropy_per_sample ) {
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 / MIN_ENTROPY_SCALE );
cutoff = entropy_adaptive_proportion_cutoff_lookup ( n, h );
/* Fail unless cutoff value is a compile-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;
}
/**
* Calculate number of samples required for startup tests
*
* @v repetition_count_cutoff Repetition count test cutoff value
* @v adaptive_proportion_cutoff Adaptive proportion test cutoff value
* @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
entropy_startup_test_count ( unsigned int repetition_count_cutoff,
unsigned int adaptive_proportion_cutoff ) {
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;
}
/**
* Initialise entropy source
*
* @v source Entropy source
* @v min_entropy_per_sample Min-entropy per sample
*
* The cutoff value calculations for the repetition count test and the
* adaptive proportion test are provided as static inline functions
* since the results will always be compile-time constants.
*/
static inline __attribute__ (( always_inline )) void
entropy_init ( struct entropy_source *source,
min_entropy_t min_entropy_per_sample ) {
unsigned int repetition_count_cutoff;
unsigned int adaptive_proportion_cutoff;
unsigned int startup_test_count;
/* Sanity check */
linker_assert ( ( min_entropy_per_sample <=
MIN_ENTROPY ( 8 * sizeof ( noise_sample_t ) ) ),
min_entropy_per_sample_is_impossibly_high );
/* Calculate test cutoff values */
repetition_count_cutoff =
entropy_repetition_count_cutoff ( min_entropy_per_sample );
adaptive_proportion_cutoff =
entropy_adaptive_proportion_cutoff ( min_entropy_per_sample );
startup_test_count =
entropy_startup_test_count ( repetition_count_cutoff,
adaptive_proportion_cutoff );
/* Record min-entropy per sample and test cutoff values */
source->min_entropy_per_sample = min_entropy_per_sample;
source->repetition_count_cutoff = repetition_count_cutoff;
source->adaptive_proportion_cutoff = adaptive_proportion_cutoff;
source->startup_test_count = startup_test_count;
}
extern int entropy_enable ( void );
extern void entropy_disable ( void );
extern int get_noise ( noise_sample_t *noise );
#endif /* _IPXE_ENTROPY_H */
|