1 /*-
2 * Copyright (c) 2017 W. Dean Freeman
3 * Copyright (c) 2013-2015 Mark R V Murray
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer
11 * in this position and unchanged.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 *
27 */
28
29 /*
30 * This implementation of Fortuna is based on the descriptions found in
31 * ISBN 978-0-470-47424-2 "Cryptography Engineering" by Ferguson, Schneier
32 * and Kohno ("FS&K").
33 */
34
35 #include <sys/param.h>
36 #include <sys/limits.h>
37
38 #ifdef _KERNEL
39 #include <sys/fail.h>
40 #include <sys/kernel.h>
41 #include <sys/lock.h>
42 #include <sys/malloc.h>
43 #include <sys/mutex.h>
44 #include <sys/random.h>
45 #include <sys/sdt.h>
46 #include <sys/sysctl.h>
47 #include <sys/systm.h>
48
49 #include <machine/cpu.h>
50 #else /* !_KERNEL */
51 #include <inttypes.h>
52 #include <stdbool.h>
53 #include <stdio.h>
54 #include <stdlib.h>
55 #include <string.h>
56 #include <threads.h>
57
58 #include "unit_test.h"
59 #endif /* _KERNEL */
60
61 #include <crypto/chacha20/chacha.h>
62 #include <crypto/rijndael/rijndael-api-fst.h>
63 #include <crypto/sha2/sha256.h>
64
65 #include <dev/random/hash.h>
66 #include <dev/random/randomdev.h>
67 #ifdef _KERNEL
68 #include <dev/random/random_harvestq.h>
69 #endif
70 #include <dev/random/uint128.h>
71 #include <dev/random/fortuna.h>
72
73 /* Defined in FS&K */
74 #define RANDOM_FORTUNA_MAX_READ (1 << 20) /* Max bytes from AES before rekeying */
75 #define RANDOM_FORTUNA_BLOCKS_PER_KEY (1 << 16) /* Max blocks from AES before rekeying */
76 CTASSERT(RANDOM_FORTUNA_BLOCKS_PER_KEY * RANDOM_BLOCKSIZE ==
77 RANDOM_FORTUNA_MAX_READ);
78
79 /*
80 * The allowable range of RANDOM_FORTUNA_DEFPOOLSIZE. The default value is above.
81 * Making RANDOM_FORTUNA_DEFPOOLSIZE too large will mean a long time between reseeds,
82 * and too small may compromise initial security but get faster reseeds.
83 */
84 #define RANDOM_FORTUNA_MINPOOLSIZE 16
85 #define RANDOM_FORTUNA_MAXPOOLSIZE INT_MAX
86 CTASSERT(RANDOM_FORTUNA_MINPOOLSIZE <= RANDOM_FORTUNA_DEFPOOLSIZE);
87 CTASSERT(RANDOM_FORTUNA_DEFPOOLSIZE <= RANDOM_FORTUNA_MAXPOOLSIZE);
88
89 /* This algorithm (and code) presumes that RANDOM_KEYSIZE is twice as large as RANDOM_BLOCKSIZE */
90 CTASSERT(RANDOM_BLOCKSIZE == sizeof(uint128_t));
91 CTASSERT(RANDOM_KEYSIZE == 2*RANDOM_BLOCKSIZE);
92
93 /* Probes for dtrace(1) */
94 #ifdef _KERNEL
95 SDT_PROVIDER_DECLARE(random);
96 SDT_PROVIDER_DEFINE(random);
97 SDT_PROBE_DEFINE2(random, fortuna, event_processor, debug, "u_int", "struct fs_pool *");
98 #endif /* _KERNEL */
99
100 /*
101 * This is the beastie that needs protecting. It contains all of the
102 * state that we are excited about. Exactly one is instantiated.
103 */
104 static struct fortuna_state {
105 struct fs_pool { /* P_i */
106 u_int fsp_length; /* Only the first one is used by Fortuna */
107 struct randomdev_hash fsp_hash;
108 } fs_pool[RANDOM_FORTUNA_NPOOLS];
109 u_int fs_reseedcount; /* ReseedCnt */
110 uint128_t fs_counter; /* C */
111 union randomdev_key fs_key; /* K */
112 u_int fs_minpoolsize; /* Extras */
113 /* Extras for the OS */
114 #ifdef _KERNEL
115 /* For use when 'pacing' the reseeds */
116 sbintime_t fs_lasttime;
117 #endif
118 /* Reseed lock */
119 mtx_t fs_mtx;
120 } fortuna_state;
121
122 /*
123 * This knob enables or disables the "Concurrent Reads" Fortuna feature.
124 *
125 * The benefit of Concurrent Reads is improved concurrency in Fortuna. That is
126 * reflected in two related aspects:
127 *
128 * 1. Concurrent full-rate devrandom readers can achieve similar throughput to
129 * a single reader thread (at least up to a modest number of cores; the
130 * non-concurrent design falls over at 2 readers).
131 *
132 * 2. The rand_harvestq process spends much less time spinning when one or more
133 * readers is processing a large request. Partially this is due to
134 * rand_harvestq / ra_event_processor design, which only passes one event at
135 * a time to the underlying algorithm. Each time, Fortuna must take its
136 * global state mutex, potentially blocking on a reader. Our adaptive
137 * mutexes assume that a lock holder currently on CPU will release the lock
138 * quickly, and spin if the owning thread is currently running.
139 *
140 * (There is no reason rand_harvestq necessarily has to use the same lock as
141 * the generator, or that it must necessarily drop and retake locks
142 * repeatedly, but that is the current status quo.)
143 *
144 * The concern is that the reduced lock scope might results in a less safe
145 * random(4) design. However, the reduced-lock scope design is still
146 * fundamentally Fortuna. This is discussed below.
147 *
148 * Fortuna Read() only needs mutual exclusion between readers to correctly
149 * update the shared read-side state: C, the 128-bit counter; and K, the
150 * current cipher/PRF key.
151 *
152 * In the Fortuna design, the global counter C should provide an independent
153 * range of values per request.
154 *
155 * Under lock, we can save a copy of C on the stack, and increment the global C
156 * by the number of blocks a Read request will require.
157 *
158 * Still under lock, we can save a copy of the key K on the stack, and then
159 * perform the usual key erasure K' <- Keystream(C, K, ...). This does require
160 * generating 256 bits (32 bytes) of cryptographic keystream output with the
161 * global lock held, but that's all; none of the API keystream generation must
162 * be performed under lock.
163 *
164 * At this point, we may unlock.
165 *
166 * Some example timelines below (to oversimplify, all requests are in units of
167 * native blocks, and the keysize happens to be equal or less to the native
168 * blocksize of the underlying cipher, and the same sequence of two requests
169 * arrive in the same order). The possibly expensive consumer keystream
170 * generation portion is marked with '**'.
171 *
172 * Status Quo fortuna_read() Reduced-scope locking
173 * ------------------------- ---------------------
174 * C=C_0, K=K_0 C=C_0, K=K_0
175 * <Thr 1 requests N blocks> <Thr 1 requests N blocks>
176 * 1:Lock() 1:Lock()
177 * <Thr 2 requests M blocks> <Thr 2 requests M blocks>
178 * 1:GenBytes() 1:stack_C := C_0
179 * 1: Keystream(C_0, K_0, N) 1:stack_K := K_0
180 * 1: <N blocks generated>** 1:C' := C_0 + N
181 * 1: C' := C_0 + N 1:K' := Keystream(C', K_0, 1)
182 * 1: <- Keystream 1: <1 block generated>
183 * 1: K' := Keystream(C', K_0, 1) 1: C'' := C' + 1
184 * 1: <1 block generated> 1: <- Keystream
185 * 1: C'' := C' + 1 1:Unlock()
186 * 1: <- Keystream
187 * 1: <- GenBytes()
188 * 1:Unlock()
189 *
190 * Just prior to unlock, shared state is identical:
191 * ------------------------------------------------
192 * C'' == C_0 + N + 1 C'' == C_0 + N + 1
193 * K' == keystream generated from K' == keystream generated from
194 * C_0 + N, K_0. C_0 + N, K_0.
195 * K_0 has been erased. K_0 has been erased.
196 *
197 * After both designs unlock, the 2nd reader is unblocked.
198 *
199 * 2:Lock() 2:Lock()
200 * 2:GenBytes() 2:stack_C' := C''
201 * 2: Keystream(C'', K', M) 2:stack_K' := K'
202 * 2: <M blocks generated>** 2:C''' := C'' + M
203 * 2: C''' := C'' + M 2:K'' := Keystream(C''', K', 1)
204 * 2: <- Keystream 2: <1 block generated>
205 * 2: K'' := Keystream(C''', K', 1) 2: C'''' := C''' + 1
206 * 2: <1 block generated> 2: <- Keystream
207 * 2: C'''' := C''' + 1 2:Unlock()
208 * 2: <- Keystream
209 * 2: <- GenBytes()
210 * 2:Unlock()
211 *
212 * Just prior to unlock, global state is identical:
213 * ------------------------------------------------------
214 *
215 * C'''' == (C_0 + N + 1) + M + 1 C'''' == (C_0 + N + 1) + M + 1
216 * K'' == keystream generated from K'' == keystream generated from
217 * C_0 + N + 1 + M, K'. C_0 + N + 1 + M, K'.
218 * K' has been erased. K' has been erased.
219 *
220 * Finally, in the new design, the two consumer threads can finish the
221 * remainder of the generation at any time (including simultaneously):
222 *
223 * 1: GenBytes()
224 * 1: Keystream(stack_C, stack_K, N)
225 * 1: <N blocks generated>**
226 * 1: <- Keystream
227 * 1: <- GenBytes
228 * 1:ExplicitBzero(stack_C, stack_K)
229 *
230 * 2: GenBytes()
231 * 2: Keystream(stack_C', stack_K', M)
232 * 2: <M blocks generated>**
233 * 2: <- Keystream
234 * 2: <- GenBytes
235 * 2:ExplicitBzero(stack_C', stack_K')
236 *
237 * The generated user keystream for both threads is identical between the two
238 * implementations:
239 *
240 * 1: Keystream(C_0, K_0, N) 1: Keystream(stack_C, stack_K, N)
241 * 2: Keystream(C'', K', M) 2: Keystream(stack_C', stack_K', M)
242 *
243 * (stack_C == C_0; stack_K == K_0; stack_C' == C''; stack_K' == K'.)
244 */
245 static bool fortuna_concurrent_read __read_frequently = true;
246
247 #ifdef _KERNEL
248 static struct sysctl_ctx_list random_clist;
249 RANDOM_CHECK_UINT(fs_minpoolsize, RANDOM_FORTUNA_MINPOOLSIZE, RANDOM_FORTUNA_MAXPOOLSIZE);
250 #else
251 static uint8_t zero_region[RANDOM_ZERO_BLOCKSIZE];
252 #endif
253
254 static void random_fortuna_pre_read(void);
255 static void random_fortuna_read(uint8_t *, size_t);
256 static bool random_fortuna_seeded(void);
257 static bool random_fortuna_seeded_internal(void);
258 static void random_fortuna_process_event(struct harvest_event *);
259
260 static void random_fortuna_reseed_internal(uint32_t *entropy_data, u_int blockcount);
261
262 #ifdef RANDOM_LOADABLE
263 static
264 #endif
265 const struct random_algorithm random_alg_context = {
266 .ra_ident = "Fortuna",
267 .ra_pre_read = random_fortuna_pre_read,
268 .ra_read = random_fortuna_read,
269 .ra_seeded = random_fortuna_seeded,
270 .ra_event_processor = random_fortuna_process_event,
271 .ra_poolcount = RANDOM_FORTUNA_NPOOLS,
272 };
273
274 /* ARGSUSED */
275 static void
random_fortuna_init_alg(void * unused __unused)276 random_fortuna_init_alg(void *unused __unused)
277 {
278 int i;
279 #ifdef _KERNEL
280 struct sysctl_oid *random_fortuna_o;
281 #endif
282
283 #ifdef RANDOM_LOADABLE
284 p_random_alg_context = &random_alg_context;
285 #endif
286
287 RANDOM_RESEED_INIT_LOCK();
288 /*
289 * Fortuna parameters. Do not adjust these unless you have
290 * have a very good clue about what they do!
291 */
292 fortuna_state.fs_minpoolsize = RANDOM_FORTUNA_DEFPOOLSIZE;
293 #ifdef _KERNEL
294 fortuna_state.fs_lasttime = 0;
295 random_fortuna_o = SYSCTL_ADD_NODE(&random_clist,
296 SYSCTL_STATIC_CHILDREN(_kern_random),
297 OID_AUTO, "fortuna", CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
298 "Fortuna Parameters");
299 SYSCTL_ADD_PROC(&random_clist,
300 SYSCTL_CHILDREN(random_fortuna_o), OID_AUTO, "minpoolsize",
301 CTLTYPE_UINT | CTLFLAG_RWTUN | CTLFLAG_MPSAFE,
302 &fortuna_state.fs_minpoolsize, RANDOM_FORTUNA_DEFPOOLSIZE,
303 random_check_uint_fs_minpoolsize, "IU",
304 "Minimum pool size necessary to cause a reseed");
305 KASSERT(fortuna_state.fs_minpoolsize > 0, ("random: Fortuna threshold must be > 0 at startup"));
306
307 SYSCTL_ADD_BOOL(&random_clist, SYSCTL_CHILDREN(random_fortuna_o),
308 OID_AUTO, "concurrent_read", CTLFLAG_RDTUN,
309 &fortuna_concurrent_read, 0, "If non-zero, enable "
310 "feature to improve concurrent Fortuna performance.");
311 #endif
312
313 /*-
314 * FS&K - InitializePRNG()
315 * - P_i = \epsilon
316 * - ReseedCNT = 0
317 */
318 for (i = 0; i < RANDOM_FORTUNA_NPOOLS; i++) {
319 randomdev_hash_init(&fortuna_state.fs_pool[i].fsp_hash);
320 fortuna_state.fs_pool[i].fsp_length = 0;
321 }
322 fortuna_state.fs_reseedcount = 0;
323 /*-
324 * FS&K - InitializeGenerator()
325 * - C = 0
326 * - K = 0
327 */
328 fortuna_state.fs_counter = UINT128_ZERO;
329 explicit_bzero(&fortuna_state.fs_key, sizeof(fortuna_state.fs_key));
330 }
331 SYSINIT(random_alg, SI_SUB_RANDOM, SI_ORDER_SECOND, random_fortuna_init_alg,
332 NULL);
333
334 /*-
335 * FS&K - AddRandomEvent()
336 * Process a single stochastic event off the harvest queue
337 */
338 static void
random_fortuna_process_event(struct harvest_event * event)339 random_fortuna_process_event(struct harvest_event *event)
340 {
341 u_int pl;
342
343 RANDOM_RESEED_LOCK();
344 /*
345 * Run SP 800-90B health tests on the source if so configured.
346 */
347 if (!random_harvest_healthtest(event)) {
348 RANDOM_RESEED_UNLOCK();
349 return;
350 }
351 /*-
352 * FS&K - P_i = P_i|<harvested stuff>
353 * Accumulate the event into the appropriate pool
354 * where each event carries the destination information.
355 *
356 * The hash_init() and hash_finish() calls are done in
357 * random_fortuna_pre_read().
358 *
359 * We must be locked against pool state modification which can happen
360 * during accumulation/reseeding and reading/regating.
361 */
362 pl = event->he_destination % RANDOM_FORTUNA_NPOOLS;
363 /*
364 * If a VM generation ID changes (clone and play or VM rewind), we want
365 * to incorporate that as soon as possible. Override destingation pool
366 * for immediate next use.
367 */
368 if (event->he_source == RANDOM_PURE_VMGENID)
369 pl = 0;
370 /*
371 * We ignore low entropy static/counter fields towards the end of the
372 * he_event structure in order to increase measurable entropy when
373 * conducting SP800-90B entropy analysis measurements of seed material
374 * fed into PRNG.
375 * -- wdf
376 */
377 KASSERT(event->he_size <= sizeof(event->he_entropy),
378 ("%s: event->he_size: %hhu > sizeof(event->he_entropy): %zu\n",
379 __func__, event->he_size, sizeof(event->he_entropy)));
380 randomdev_hash_iterate(&fortuna_state.fs_pool[pl].fsp_hash,
381 &event->he_somecounter, sizeof(event->he_somecounter));
382 randomdev_hash_iterate(&fortuna_state.fs_pool[pl].fsp_hash,
383 event->he_entropy, event->he_size);
384
385 /*-
386 * Don't wrap the length. This is a "saturating" add.
387 * XXX: FIX!!: We don't actually need lengths for anything but fs_pool[0],
388 * but it's been useful debugging to see them all.
389 */
390 fortuna_state.fs_pool[pl].fsp_length = MIN(RANDOM_FORTUNA_MAXPOOLSIZE,
391 fortuna_state.fs_pool[pl].fsp_length +
392 sizeof(event->he_somecounter) + event->he_size);
393 RANDOM_RESEED_UNLOCK();
394 }
395
396 /*-
397 * FS&K - Reseed()
398 * This introduces new key material into the output generator.
399 * Additionally it increments the output generator's counter
400 * variable C. When C > 0, the output generator is seeded and
401 * will deliver output.
402 * The entropy_data buffer passed is a very specific size; the
403 * product of RANDOM_FORTUNA_NPOOLS and RANDOM_KEYSIZE.
404 */
405 static void
random_fortuna_reseed_internal(uint32_t * entropy_data,u_int blockcount)406 random_fortuna_reseed_internal(uint32_t *entropy_data, u_int blockcount)
407 {
408 struct randomdev_hash context;
409 uint8_t hash[RANDOM_KEYSIZE];
410 const void *keymaterial;
411 size_t keysz;
412 bool seeded;
413
414 RANDOM_RESEED_ASSERT_LOCK_OWNED();
415
416 seeded = random_fortuna_seeded_internal();
417 if (seeded) {
418 randomdev_getkey(&fortuna_state.fs_key, &keymaterial, &keysz);
419 KASSERT(keysz == RANDOM_KEYSIZE, ("%s: key size %zu not %u",
420 __func__, keysz, (unsigned)RANDOM_KEYSIZE));
421 }
422
423 /*-
424 * FS&K - K = Hd(K|s) where Hd(m) is H(H(0^512|m))
425 * - C = C + 1
426 */
427 randomdev_hash_init(&context);
428 randomdev_hash_iterate(&context, zero_region, RANDOM_ZERO_BLOCKSIZE);
429 if (seeded)
430 randomdev_hash_iterate(&context, keymaterial, keysz);
431 randomdev_hash_iterate(&context, entropy_data, RANDOM_KEYSIZE*blockcount);
432 randomdev_hash_finish(&context, hash);
433 randomdev_hash_init(&context);
434 randomdev_hash_iterate(&context, hash, RANDOM_KEYSIZE);
435 randomdev_hash_finish(&context, hash);
436 randomdev_encrypt_init(&fortuna_state.fs_key, hash);
437 explicit_bzero(hash, sizeof(hash));
438 /* Unblock the device if this is the first time we are reseeding. */
439 if (uint128_is_zero(fortuna_state.fs_counter))
440 randomdev_unblock();
441 uint128_increment(&fortuna_state.fs_counter);
442 }
443
444 /*-
445 * FS&K - RandomData() (Part 1)
446 * Used to return processed entropy from the PRNG. There is a pre_read
447 * required to be present (but it can be a stub) in order to allow
448 * specific actions at the begin of the read.
449 */
450 void
random_fortuna_pre_read(void)451 random_fortuna_pre_read(void)
452 {
453 #ifdef _KERNEL
454 sbintime_t now;
455 #endif
456 struct randomdev_hash context;
457 uint32_t s[RANDOM_FORTUNA_NPOOLS*RANDOM_KEYSIZE_WORDS];
458 uint8_t temp[RANDOM_KEYSIZE];
459 u_int i;
460
461 KASSERT(fortuna_state.fs_minpoolsize > 0, ("random: Fortuna threshold must be > 0"));
462 RANDOM_RESEED_LOCK();
463 #ifdef _KERNEL
464 /* FS&K - Use 'getsbinuptime()' to prevent reseed-spamming. */
465 now = getsbinuptime();
466 #endif
467
468 if (fortuna_state.fs_pool[0].fsp_length < fortuna_state.fs_minpoolsize
469 #ifdef _KERNEL
470 /*
471 * FS&K - Use 'getsbinuptime()' to prevent reseed-spamming, but do
472 * not block initial seeding (fs_lasttime == 0).
473 */
474 || (__predict_true(fortuna_state.fs_lasttime != 0) &&
475 now - fortuna_state.fs_lasttime <= SBT_1S/10)
476 #endif
477 ) {
478 RANDOM_RESEED_UNLOCK();
479 return;
480 }
481
482 #ifdef _KERNEL
483 /*
484 * When set, pretend we do not have enough entropy to reseed yet.
485 */
486 KFAIL_POINT_CODE(DEBUG_FP, random_fortuna_pre_read, {
487 if (RETURN_VALUE != 0) {
488 RANDOM_RESEED_UNLOCK();
489 return;
490 }
491 });
492 #endif
493
494 #ifdef _KERNEL
495 fortuna_state.fs_lasttime = now;
496 #endif
497
498 /* FS&K - ReseedCNT = ReseedCNT + 1 */
499 fortuna_state.fs_reseedcount++;
500 /* s = \epsilon at start */
501 for (i = 0; i < RANDOM_FORTUNA_NPOOLS; i++) {
502 /* FS&K - if Divides(ReseedCnt, 2^i) ... */
503 if ((fortuna_state.fs_reseedcount % (1 << i)) == 0) {
504 /*-
505 * FS&K - temp = (P_i)
506 * - P_i = \epsilon
507 * - s = s|H(temp)
508 */
509 randomdev_hash_finish(&fortuna_state.fs_pool[i].fsp_hash, temp);
510 randomdev_hash_init(&fortuna_state.fs_pool[i].fsp_hash);
511 fortuna_state.fs_pool[i].fsp_length = 0;
512 randomdev_hash_init(&context);
513 randomdev_hash_iterate(&context, temp, RANDOM_KEYSIZE);
514 randomdev_hash_finish(&context, s + i*RANDOM_KEYSIZE_WORDS);
515 } else
516 break;
517 }
518 #ifdef _KERNEL
519 SDT_PROBE2(random, fortuna, event_processor, debug, fortuna_state.fs_reseedcount, fortuna_state.fs_pool);
520 #endif
521 /* FS&K */
522 random_fortuna_reseed_internal(s, i);
523 RANDOM_RESEED_UNLOCK();
524
525 /* Clean up and secure */
526 explicit_bzero(s, sizeof(s));
527 explicit_bzero(temp, sizeof(temp));
528 }
529
530 /*
531 * This is basically GenerateBlocks() from FS&K.
532 *
533 * It differs in two ways:
534 *
535 * 1. Chacha20 is tolerant of non-block-multiple request sizes, so we do not
536 * need to handle any remainder bytes specially and can just pass the length
537 * directly to the PRF construction; and
538 *
539 * 2. Chacha20 is a 512-bit block size cipher (whereas AES has 128-bit block
540 * size, regardless of key size). This means Chacha does not require re-keying
541 * every 1MiB. This is implied by the math in FS&K 9.4 and mentioned
542 * explicitly in the conclusion, "If we had a block cipher with a 256-bit [or
543 * greater] block size, then the collisions would not have been an issue at
544 * all" (p. 144).
545 *
546 * 3. In conventional ("locked") mode, we produce a maximum of PAGE_SIZE output
547 * at a time before dropping the lock, to not bully the lock especially. This
548 * has been the status quo since 2015 (r284959).
549 *
550 * The upstream caller random_fortuna_read is responsible for zeroing out
551 * sensitive buffers provided as parameters to this routine.
552 */
553 enum {
554 FORTUNA_UNLOCKED = false,
555 FORTUNA_LOCKED = true
556 };
557 static void
random_fortuna_genbytes(uint8_t * buf,size_t bytecount,uint8_t newkey[static RANDOM_KEYSIZE],uint128_t * p_counter,union randomdev_key * p_key,bool locked)558 random_fortuna_genbytes(uint8_t *buf, size_t bytecount,
559 uint8_t newkey[static RANDOM_KEYSIZE], uint128_t *p_counter,
560 union randomdev_key *p_key, bool locked)
561 {
562 uint8_t remainder_buf[RANDOM_BLOCKSIZE];
563 size_t chunk_size;
564
565 if (locked)
566 RANDOM_RESEED_ASSERT_LOCK_OWNED();
567 else
568 RANDOM_RESEED_ASSERT_LOCK_NOT_OWNED();
569
570 /*
571 * Easy case: don't have to worry about bullying the global mutex,
572 * don't have to worry about rekeying Chacha; API is byte-oriented.
573 */
574 if (!locked && random_chachamode) {
575 randomdev_keystream(p_key, p_counter, buf, bytecount);
576 return;
577 }
578
579 if (locked) {
580 /*
581 * While holding the global lock, limit PRF generation to
582 * mitigate, but not eliminate, bullying symptoms.
583 */
584 chunk_size = PAGE_SIZE;
585 } else {
586 /*
587 * 128-bit block ciphers like AES must be re-keyed at 1MB
588 * intervals to avoid unacceptable statistical differentiation
589 * from true random data (FS&K 9.4, p. 143-144).
590 */
591 MPASS(!random_chachamode);
592 chunk_size = RANDOM_FORTUNA_MAX_READ;
593 }
594
595 chunk_size = MIN(bytecount, chunk_size);
596 if (!random_chachamode)
597 chunk_size = rounddown(chunk_size, RANDOM_BLOCKSIZE);
598
599 while (bytecount >= chunk_size && chunk_size > 0) {
600 randomdev_keystream(p_key, p_counter, buf, chunk_size);
601
602 buf += chunk_size;
603 bytecount -= chunk_size;
604
605 /* We have to rekey if there is any data remaining to be
606 * generated, in two scenarios:
607 *
608 * locked: we need to rekey before we unlock and release the
609 * global state to another consumer; or
610 *
611 * unlocked: we need to rekey because we're in AES mode and are
612 * required to rekey at chunk_size==1MB. But we do not need to
613 * rekey during the last trailing <1MB chunk.
614 */
615 if (bytecount > 0) {
616 if (locked || chunk_size == RANDOM_FORTUNA_MAX_READ) {
617 randomdev_keystream(p_key, p_counter, newkey,
618 RANDOM_KEYSIZE);
619 randomdev_encrypt_init(p_key, newkey);
620 }
621
622 /*
623 * If we're holding the global lock, yield it briefly
624 * now.
625 */
626 if (locked) {
627 RANDOM_RESEED_UNLOCK();
628 RANDOM_RESEED_LOCK();
629 }
630
631 /*
632 * At the trailing end, scale down chunk_size from 1MB or
633 * PAGE_SIZE to all remaining full blocks (AES) or all
634 * remaining bytes (Chacha).
635 */
636 if (bytecount < chunk_size) {
637 if (random_chachamode)
638 chunk_size = bytecount;
639 else if (bytecount >= RANDOM_BLOCKSIZE)
640 chunk_size = rounddown(bytecount,
641 RANDOM_BLOCKSIZE);
642 else
643 break;
644 }
645 }
646 }
647
648 /*
649 * Generate any partial AES block remaining into a temporary buffer and
650 * copy the desired substring out.
651 */
652 if (bytecount > 0) {
653 MPASS(!random_chachamode);
654
655 randomdev_keystream(p_key, p_counter, remainder_buf,
656 sizeof(remainder_buf));
657 }
658
659 /*
660 * In locked mode, re-key global K before dropping the lock, which we
661 * don't need for memcpy/bzero below.
662 */
663 if (locked) {
664 randomdev_keystream(p_key, p_counter, newkey, RANDOM_KEYSIZE);
665 randomdev_encrypt_init(p_key, newkey);
666 RANDOM_RESEED_UNLOCK();
667 }
668
669 if (bytecount > 0) {
670 memcpy(buf, remainder_buf, bytecount);
671 explicit_bzero(remainder_buf, sizeof(remainder_buf));
672 }
673 }
674
675
676 /*
677 * Handle only "concurrency-enabled" Fortuna reads to simplify logic.
678 *
679 * Caller (random_fortuna_read) is responsible for zeroing out sensitive
680 * buffers provided as parameters to this routine.
681 */
682 static void
random_fortuna_read_concurrent(uint8_t * buf,size_t bytecount,uint8_t newkey[static RANDOM_KEYSIZE])683 random_fortuna_read_concurrent(uint8_t *buf, size_t bytecount,
684 uint8_t newkey[static RANDOM_KEYSIZE])
685 {
686 union randomdev_key key_copy;
687 uint128_t counter_copy;
688 size_t blockcount;
689
690 MPASS(fortuna_concurrent_read);
691
692 /*
693 * Compute number of blocks required for the PRF request ('delta C').
694 * We will step the global counter 'C' by this number under lock, and
695 * then actually consume the counter values outside the lock.
696 *
697 * This ensures that contemporaneous but independent requests for
698 * randomness receive distinct 'C' values and thus independent PRF
699 * results.
700 */
701 if (random_chachamode) {
702 blockcount = howmany(bytecount, CHACHA_BLOCKLEN);
703 } else {
704 blockcount = howmany(bytecount, RANDOM_BLOCKSIZE);
705
706 /*
707 * Need to account for the additional blocks generated by
708 * rekeying when updating the global fs_counter.
709 */
710 blockcount += RANDOM_KEYS_PER_BLOCK *
711 (blockcount / RANDOM_FORTUNA_BLOCKS_PER_KEY);
712 }
713
714 RANDOM_RESEED_LOCK();
715 KASSERT(!uint128_is_zero(fortuna_state.fs_counter), ("FS&K: C != 0"));
716
717 /*
718 * Save the original counter and key values that will be used as the
719 * PRF for this particular consumer.
720 */
721 memcpy(&counter_copy, &fortuna_state.fs_counter, sizeof(counter_copy));
722 memcpy(&key_copy, &fortuna_state.fs_key, sizeof(key_copy));
723
724 /*
725 * Step the counter as if we had generated 'bytecount' blocks for this
726 * consumer. I.e., ensure that the next consumer gets an independent
727 * range of counter values once we drop the global lock.
728 */
729 uint128_add64(&fortuna_state.fs_counter, blockcount);
730
731 /*
732 * We still need to Rekey the global 'K' between independent calls;
733 * this is no different from conventional Fortuna. Note that
734 * 'randomdev_keystream()' will step the fs_counter 'C' appropriately
735 * for the blocks needed for the 'newkey'.
736 *
737 * (This is part of PseudoRandomData() in FS&K, 9.4.4.)
738 */
739 randomdev_keystream(&fortuna_state.fs_key, &fortuna_state.fs_counter,
740 newkey, RANDOM_KEYSIZE);
741 randomdev_encrypt_init(&fortuna_state.fs_key, newkey);
742
743 /*
744 * We have everything we need to generate a unique PRF for this
745 * consumer without touching global state.
746 */
747 RANDOM_RESEED_UNLOCK();
748
749 random_fortuna_genbytes(buf, bytecount, newkey, &counter_copy,
750 &key_copy, FORTUNA_UNLOCKED);
751 RANDOM_RESEED_ASSERT_LOCK_NOT_OWNED();
752
753 explicit_bzero(&counter_copy, sizeof(counter_copy));
754 explicit_bzero(&key_copy, sizeof(key_copy));
755 }
756
757 /*-
758 * FS&K - RandomData() (Part 2)
759 * Main read from Fortuna, continued. May be called multiple times after
760 * the random_fortuna_pre_read() above.
761 *
762 * The supplied buf MAY not be a multiple of RANDOM_BLOCKSIZE in size; it is
763 * the responsibility of the algorithm to accommodate partial block reads, if a
764 * block output mode is used.
765 */
766 void
random_fortuna_read(uint8_t * buf,size_t bytecount)767 random_fortuna_read(uint8_t *buf, size_t bytecount)
768 {
769 uint8_t newkey[RANDOM_KEYSIZE];
770
771 if (fortuna_concurrent_read) {
772 random_fortuna_read_concurrent(buf, bytecount, newkey);
773 goto out;
774 }
775
776 RANDOM_RESEED_LOCK();
777 KASSERT(!uint128_is_zero(fortuna_state.fs_counter), ("FS&K: C != 0"));
778
779 random_fortuna_genbytes(buf, bytecount, newkey,
780 &fortuna_state.fs_counter, &fortuna_state.fs_key, FORTUNA_LOCKED);
781 /* Returns unlocked */
782 RANDOM_RESEED_ASSERT_LOCK_NOT_OWNED();
783
784 out:
785 explicit_bzero(newkey, sizeof(newkey));
786 }
787
788 #ifdef _KERNEL
789 static bool block_seeded_status = false;
790 SYSCTL_BOOL(_kern_random, OID_AUTO, block_seeded_status, CTLFLAG_RWTUN,
791 &block_seeded_status, 0,
792 "If non-zero, pretend Fortuna is in an unseeded state. By setting "
793 "this as a tunable, boot can be tested as if the random device is "
794 "unavailable.");
795 #endif
796
797 static bool
random_fortuna_seeded_internal(void)798 random_fortuna_seeded_internal(void)
799 {
800 return (!uint128_is_zero(fortuna_state.fs_counter));
801 }
802
803 static bool
random_fortuna_seeded(void)804 random_fortuna_seeded(void)
805 {
806
807 #ifdef _KERNEL
808 if (block_seeded_status)
809 return (false);
810 #endif
811
812 if (__predict_true(random_fortuna_seeded_internal()))
813 return (true);
814
815 /*
816 * Maybe we have enough entropy in the zeroth pool but just haven't
817 * kicked the initial seed step. Do so now.
818 */
819 random_fortuna_pre_read();
820
821 return (random_fortuna_seeded_internal());
822 }
823