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/rijndael/rijndael-api-fst.h>
  65 #include <crypto/sha2/sha256.h>
  66
  67 #include <dev/random/hash.h>
  68 #include <dev/random/randomdev.h>
  69 #ifdef _KERNEL
  70 #include <dev/random/random_harvestq.h>
  71 #endif
  72 #include <dev/random/uint128.h>
  73 #include <dev/random/fortuna.h>
  74
  75 /* Defined in FS&K */
  76 #define RANDOM_FORTUNA_NPOOLS 32                /* The number of accumulation pools */
  77 #define RANDOM_FORTUNA_DEFPOOLSIZE 64           /* The default pool size/length for a (re)seed */
  78 #define RANDOM_FORTUNA_MAX_READ (1 << 20)       /* Max bytes in a single read */
  79
  80 /*
  81  * The allowable range of RANDOM_FORTUNA_DEFPOOLSIZE. The default value is above.
  82  * Making RANDOM_FORTUNA_DEFPOOLSIZE too large will mean a long time between reseeds,
  83  * and too small may compromise initial security but get faster reseeds.
  84  */
  85 #define RANDOM_FORTUNA_MINPOOLSIZE 16
  86 #define RANDOM_FORTUNA_MAXPOOLSIZE INT_MAX
  87 CTASSERT(RANDOM_FORTUNA_MINPOOLSIZE <= RANDOM_FORTUNA_DEFPOOLSIZE);
  88 CTASSERT(RANDOM_FORTUNA_DEFPOOLSIZE <= RANDOM_FORTUNA_MAXPOOLSIZE);
  89
  90 /* This algorithm (and code) presumes that RANDOM_KEYSIZE is twice as large as RANDOM_BLOCKSIZE */
  91 CTASSERT(RANDOM_BLOCKSIZE == sizeof(uint128_t));
  92 CTASSERT(RANDOM_KEYSIZE == 2*RANDOM_BLOCKSIZE);
  93
  94 /* Probes for dtrace(1) */
  95 #ifdef _KERNEL
  96 SDT_PROVIDER_DECLARE(random);
  97 SDT_PROVIDER_DEFINE(random);
  98 SDT_PROBE_DEFINE2(random, fortuna, event_processor, debug, "u_int", "struct fs_pool *");
  99 #endif /* _KERNEL */
 100
 101 /*
 102  * This is the beastie that needs protecting. It contains all of the
 103  * state that we are excited about. Exactly one is instantiated.
 104  */
 105 static struct fortuna_state {
 106         struct fs_pool {                /* P_i */
 107                 u_int fsp_length;       /* Only the first one is used by Fortuna */
 108                 struct randomdev_hash fsp_hash;
 109         } fs_pool[RANDOM_FORTUNA_NPOOLS];
 110         u_int fs_reseedcount;           /* ReseedCnt */
 111         uint128_t fs_counter;           /* C */
 112         union randomdev_key fs_key;     /* K */
 113         u_int fs_minpoolsize;           /* Extras */
 114         /* Extras for the OS */
 115 #ifdef _KERNEL
 116         /* For use when 'pacing' the reseeds */
 117         sbintime_t fs_lasttime;
 118 #endif
 119         /* Reseed lock */
 120         mtx_t fs_mtx;
 121 } fortuna_state;
 122
 123 #ifdef _KERNEL
 124 static struct sysctl_ctx_list random_clist;
 125 RANDOM_CHECK_UINT(fs_minpoolsize, RANDOM_FORTUNA_MINPOOLSIZE, RANDOM_FORTUNA_MAXPOOLSIZE);
 126 #else
 127 static uint8_t zero_region[RANDOM_ZERO_BLOCKSIZE];
 128 #endif
 129
 130 static void random_fortuna_pre_read(void);
 131 static void random_fortuna_read(uint8_t *, u_int);
 132 static bool random_fortuna_seeded(void);
 133 static bool random_fortuna_seeded_internal(void);
 134 static void random_fortuna_process_event(struct harvest_event *);
 135 static void random_fortuna_init_alg(void *);
 136 static void random_fortuna_deinit_alg(void *);
 137
 138 static void random_fortuna_reseed_internal(uint32_t *entropy_data, u_int blockcount);
 139
 140 struct random_algorithm random_alg_context = {
 141         .ra_ident = "Fortuna",
 142         .ra_init_alg = random_fortuna_init_alg,
 143         .ra_deinit_alg = random_fortuna_deinit_alg,
 144         .ra_pre_read = random_fortuna_pre_read,
 145         .ra_read = random_fortuna_read,
 146         .ra_seeded = random_fortuna_seeded,
 147         .ra_event_processor = random_fortuna_process_event,
 148         .ra_poolcount = RANDOM_FORTUNA_NPOOLS,
 149 };
 150
 151 /* ARGSUSED */
 152 static void
 153 random_fortuna_init_alg(void *unused __unused)
 154 {
 155         int i;
 156 #ifdef _KERNEL
 157         struct sysctl_oid *random_fortuna_o;
 158 #endif
 159
 160         RANDOM_RESEED_INIT_LOCK();
 161         /*
 162          * Fortuna parameters. Do not adjust these unless you have
 163          * have a very good clue about what they do!
 164          */
 165         fortuna_state.fs_minpoolsize = RANDOM_FORTUNA_DEFPOOLSIZE;
 166 #ifdef _KERNEL
 167         fortuna_state.fs_lasttime = 0;
 168         random_fortuna_o = SYSCTL_ADD_NODE(&random_clist,
 169                 SYSCTL_STATIC_CHILDREN(_kern_random),
 170                 OID_AUTO, "fortuna", CTLFLAG_RW, 0,
 171                 "Fortuna Parameters");
 172         SYSCTL_ADD_PROC(&random_clist,
 173                 SYSCTL_CHILDREN(random_fortuna_o), OID_AUTO,
 174                 "minpoolsize", CTLTYPE_UINT | CTLFLAG_RWTUN,
 175                 &fortuna_state.fs_minpoolsize, RANDOM_FORTUNA_DEFPOOLSIZE,
 176                 random_check_uint_fs_minpoolsize, "IU",
 177                 "Minimum pool size necessary to cause a reseed");
 178         KASSERT(fortuna_state.fs_minpoolsize > 0, ("random: Fortuna threshold must be > 0 at startup"));
 179 #endif
 180
 181         /*-
 182          * FS&K - InitializePRNG()
 183          *      - P_i = \epsilon
 184          *      - ReseedCNT = 0
 185          */
 186         for (i = 0; i < RANDOM_FORTUNA_NPOOLS; i++) {
 187                 randomdev_hash_init(&fortuna_state.fs_pool[i].fsp_hash);
 188                 fortuna_state.fs_pool[i].fsp_length = 0;
 189         }
 190         fortuna_state.fs_reseedcount = 0;
 191         /*-
 192          * FS&K - InitializeGenerator()
 193          *      - C = 0
 194          *      - K = 0
 195          */
 196         fortuna_state.fs_counter = UINT128_ZERO;
 197         explicit_bzero(&fortuna_state.fs_key, sizeof(fortuna_state.fs_key));
 198 }
 199
 200 /* ARGSUSED */
 201 static void
 202 random_fortuna_deinit_alg(void *unused __unused)
 203 {
 204
 205         RANDOM_RESEED_DEINIT_LOCK();
 206         explicit_bzero(&fortuna_state, sizeof(fortuna_state));
 207 #ifdef _KERNEL
 208         sysctl_ctx_free(&random_clist);
 209 #endif
 210 }
 211
 212 /*-
 213  * FS&K - AddRandomEvent()
 214  * Process a single stochastic event off the harvest queue
 215  */
 216 static void
 217 random_fortuna_process_event(struct harvest_event *event)
 218 {
 219         u_int pl;
 220
 221         RANDOM_RESEED_LOCK();
 222         /*-
 223          * FS&K - P_i = P_i|<harvested stuff>
 224          * Accumulate the event into the appropriate pool
 225          * where each event carries the destination information.
 226          *
 227          * The hash_init() and hash_finish() calls are done in
 228          * random_fortuna_pre_read().
 229          *
 230          * We must be locked against pool state modification which can happen
 231          * during accumulation/reseeding and reading/regating.
 232          */
 233         pl = event->he_destination % RANDOM_FORTUNA_NPOOLS;
 234         /*
 235          * We ignore low entropy static/counter fields towards the end of the
 236          * he_event structure in order to increase measurable entropy when
 237          * conducting SP800-90B entropy analysis measurements of seed material
 238          * fed into PRNG.
 239          * -- wdf
 240          */
 241         KASSERT(event->he_size <= sizeof(event->he_entropy),
 242             ("%s: event->he_size: %hhu > sizeof(event->he_entropy): %zu\n",
 243             __func__, event->he_size, sizeof(event->he_entropy)));
 244         randomdev_hash_iterate(&fortuna_state.fs_pool[pl].fsp_hash,
 245             &event->he_somecounter, sizeof(event->he_somecounter));
 246         randomdev_hash_iterate(&fortuna_state.fs_pool[pl].fsp_hash,
 247             event->he_entropy, event->he_size);
 248
 249         /*-
 250          * Don't wrap the length.  This is a "saturating" add.
 251          * XXX: FIX!!: We don't actually need lengths for anything but fs_pool[0],
 252          * but it's been useful debugging to see them all.
 253          */
 254         fortuna_state.fs_pool[pl].fsp_length = MIN(RANDOM_FORTUNA_MAXPOOLSIZE,
 255             fortuna_state.fs_pool[pl].fsp_length +
 256             sizeof(event->he_somecounter) + event->he_size);
 257         RANDOM_RESEED_UNLOCK();
 258 }
 259
 260 /*-
 261  * FS&K - Reseed()
 262  * This introduces new key material into the output generator.
 263  * Additionally it increments the output generator's counter
 264  * variable C. When C > 0, the output generator is seeded and
 265  * will deliver output.
 266  * The entropy_data buffer passed is a very specific size; the
 267  * product of RANDOM_FORTUNA_NPOOLS and RANDOM_KEYSIZE.
 268  */
 269 static void
 270 random_fortuna_reseed_internal(uint32_t *entropy_data, u_int blockcount)
 271 {
 272         struct randomdev_hash context;
 273         uint8_t hash[RANDOM_KEYSIZE];
 274         const void *keymaterial;
 275         size_t keysz;
 276         bool seeded;
 277
 278         RANDOM_RESEED_ASSERT_LOCK_OWNED();
 279
 280         seeded = random_fortuna_seeded_internal();
 281         if (seeded) {
 282                 randomdev_getkey(&fortuna_state.fs_key, &keymaterial, &keysz);
 283                 KASSERT(keysz == RANDOM_KEYSIZE, ("%s: key size %zu not %u",
 284                         __func__, keysz, (unsigned)RANDOM_KEYSIZE));
 285         }
 286
 287         /*-
 288          * FS&K - K = Hd(K|s) where Hd(m) is H(H(0^512|m))
 289          *      - C = C + 1
 290          */
 291         randomdev_hash_init(&context);
 292         randomdev_hash_iterate(&context, zero_region, RANDOM_ZERO_BLOCKSIZE);
 293         if (seeded)
 294                 randomdev_hash_iterate(&context, keymaterial, keysz);
 295         randomdev_hash_iterate(&context, entropy_data, RANDOM_KEYSIZE*blockcount);
 296         randomdev_hash_finish(&context, hash);
 297         randomdev_hash_init(&context);
 298         randomdev_hash_iterate(&context, hash, RANDOM_KEYSIZE);
 299         randomdev_hash_finish(&context, hash);
 300         randomdev_encrypt_init(&fortuna_state.fs_key, hash);
 301         explicit_bzero(hash, sizeof(hash));
 302         /* Unblock the device if this is the first time we are reseeding. */
 303         if (uint128_is_zero(fortuna_state.fs_counter))
 304                 randomdev_unblock();
 305         uint128_increment(&fortuna_state.fs_counter);
 306 }
 307
 308 /*-
 309  * FS&K - GenerateBlocks()
 310  * Generate a number of complete blocks of random output.
 311  */
 312 static __inline void
 313 random_fortuna_genblocks(uint8_t *buf, u_int blockcount)
 314 {
 315
 316         RANDOM_RESEED_ASSERT_LOCK_OWNED();
 317         KASSERT(!uint128_is_zero(fortuna_state.fs_counter), ("FS&K: C != 0"));
 318
 319         /*
 320          * Fills buf with RANDOM_BLOCKSIZE * blockcount bytes of keystream.
 321          * Increments fs_counter as it goes.
 322          */
 323         randomdev_keystream(&fortuna_state.fs_key, &fortuna_state.fs_counter,
 324             buf, blockcount);
 325 }
 326
 327 /*-
 328  * FS&K - PseudoRandomData()
 329  * This generates no more than 2^20 bytes of data, and cleans up its
 330  * internal state when finished. It is assumed that a whole number of
 331  * blocks are available for writing; any excess generated will be
 332  * ignored.
 333  */
 334 static __inline void
 335 random_fortuna_genrandom(uint8_t *buf, u_int bytecount)
 336 {
 337         uint8_t temp[RANDOM_BLOCKSIZE * RANDOM_KEYS_PER_BLOCK];
 338         u_int blockcount;
 339
 340         RANDOM_RESEED_ASSERT_LOCK_OWNED();
 341         /*-
 342          * FS&K - assert(n < 2^20 (== 1 MB)
 343          *      - r = first-n-bytes(GenerateBlocks(ceil(n/16)))
 344          *      - K = GenerateBlocks(2)
 345          */
 346         KASSERT((bytecount <= RANDOM_FORTUNA_MAX_READ), ("invalid single read request to Fortuna of %d bytes", bytecount));
 347         blockcount = howmany(bytecount, RANDOM_BLOCKSIZE);
 348         random_fortuna_genblocks(buf, blockcount);
 349         random_fortuna_genblocks(temp, RANDOM_KEYS_PER_BLOCK);
 350         randomdev_encrypt_init(&fortuna_state.fs_key, temp);
 351         explicit_bzero(temp, sizeof(temp));
 352 }
 353
 354 /*-
 355  * FS&K - RandomData() (Part 1)
 356  * Used to return processed entropy from the PRNG. There is a pre_read
 357  * required to be present (but it can be a stub) in order to allow
 358  * specific actions at the begin of the read.
 359  */
 360 void
 361 random_fortuna_pre_read(void)
 362 {
 363 #ifdef _KERNEL
 364         sbintime_t now;
 365 #endif
 366         struct randomdev_hash context;
 367         uint32_t s[RANDOM_FORTUNA_NPOOLS*RANDOM_KEYSIZE_WORDS];
 368         uint8_t temp[RANDOM_KEYSIZE];
 369         u_int i;
 370
 371         KASSERT(fortuna_state.fs_minpoolsize > 0, ("random: Fortuna threshold must be > 0"));
 372         RANDOM_RESEED_LOCK();
 373 #ifdef _KERNEL
 374         /* FS&K - Use 'getsbinuptime()' to prevent reseed-spamming. */
 375         now = getsbinuptime();
 376 #endif
 377
 378         if (fortuna_state.fs_pool[0].fsp_length < fortuna_state.fs_minpoolsize
 379 #ifdef _KERNEL
 380             /*
 381              * FS&K - Use 'getsbinuptime()' to prevent reseed-spamming, but do
 382              * not block initial seeding (fs_lasttime == 0).
 383              */
 384             || (__predict_true(fortuna_state.fs_lasttime != 0) &&
 385                 now - fortuna_state.fs_lasttime <= SBT_1S/10)
 386 #endif
 387         ) {
 388                 RANDOM_RESEED_UNLOCK();
 389                 return;
 390         }
 391
 392 #ifdef _KERNEL
 393         /*
 394          * When set, pretend we do not have enough entropy to reseed yet.
 395          */
 396         KFAIL_POINT_CODE(DEBUG_FP, random_fortuna_pre_read, {
 397                 if (RETURN_VALUE != 0) {
 398                         RANDOM_RESEED_UNLOCK();
 399                         return;
 400                 }
 401         });
 402 #endif
 403
 404 #ifdef _KERNEL
 405         fortuna_state.fs_lasttime = now;
 406 #endif
 407
 408         /* FS&K - ReseedCNT = ReseedCNT + 1 */
 409         fortuna_state.fs_reseedcount++;
 410         /* s = \epsilon at start */
 411         for (i = 0; i < RANDOM_FORTUNA_NPOOLS; i++) {
 412                 /* FS&K - if Divides(ReseedCnt, 2^i) ... */
 413                 if ((fortuna_state.fs_reseedcount % (1 << i)) == 0) {
 414                         /*-
 415                             * FS&K - temp = (P_i)
 416                             *      - P_i = \epsilon
 417                             *      - s = s|H(temp)
 418                             */
 419                         randomdev_hash_finish(&fortuna_state.fs_pool[i].fsp_hash, temp);
 420                         randomdev_hash_init(&fortuna_state.fs_pool[i].fsp_hash);
 421                         fortuna_state.fs_pool[i].fsp_length = 0;
 422                         randomdev_hash_init(&context);
 423                         randomdev_hash_iterate(&context, temp, RANDOM_KEYSIZE);
 424                         randomdev_hash_finish(&context, s + i*RANDOM_KEYSIZE_WORDS);
 425                 } else
 426                         break;
 427         }
 428 #ifdef _KERNEL
 429         SDT_PROBE2(random, fortuna, event_processor, debug, fortuna_state.fs_reseedcount, fortuna_state.fs_pool);
 430 #endif
 431         /* FS&K */
 432         random_fortuna_reseed_internal(s, i);
 433         RANDOM_RESEED_UNLOCK();
 434
 435         /* Clean up and secure */
 436         explicit_bzero(s, sizeof(s));
 437         explicit_bzero(temp, sizeof(temp));
 438 }
 439
 440 /*-
 441  * FS&K - RandomData() (Part 2)
 442  * Main read from Fortuna, continued. May be called multiple times after
 443  * the random_fortuna_pre_read() above.
 444  * The supplied buf MUST be a multiple of RANDOM_BLOCKSIZE in size.
 445  * Lots of code presumes this for efficiency, both here and in other
 446  * routines. You are NOT allowed to break this!
 447  */
 448 void
 449 random_fortuna_read(uint8_t *buf, u_int bytecount)
 450 {
 451
 452         KASSERT((bytecount % RANDOM_BLOCKSIZE) == 0, ("%s(): bytecount (= %d) must be a multiple of %d", __func__, bytecount, RANDOM_BLOCKSIZE ));
 453         RANDOM_RESEED_LOCK();
 454         random_fortuna_genrandom(buf, bytecount);
 455         RANDOM_RESEED_UNLOCK();
 456 }
 457
 458 #ifdef _KERNEL
 459 static bool block_seeded_status = false;
 460 SYSCTL_BOOL(_kern_random, OID_AUTO, block_seeded_status, CTLFLAG_RWTUN,
 461     &block_seeded_status, 0,
 462     "If non-zero, pretend Fortuna is in an unseeded state.  By setting "
 463     "this as a tunable, boot can be tested as if the random device is "
 464     "unavailable.");
 465 #endif
 466
 467 static bool
 468 random_fortuna_seeded_internal(void)
 469 {
 470         return (!uint128_is_zero(fortuna_state.fs_counter));
 471 }
 472
 473 static bool
 474 random_fortuna_seeded(void)
 475 {
 476
 477 #ifdef _KERNEL
 478         if (block_seeded_status)
 479                 return (false);
 480 #endif
 481
 482         if (__predict_true(random_fortuna_seeded_internal()))
 483                 return (true);
 484
 485         /*
 486          * Maybe we have enough entropy in the zeroth pool but just haven't
 487          * kicked the initial seed step.  Do so now.
 488          */
 489         random_fortuna_pre_read();
 490
 491         return (random_fortuna_seeded_internal());
 492 }