sys/dev/random/fortuna.c

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