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