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