sys/dev/random/fortuna.c

   1 /*-
   2  * Copyright (c) 2013-2015 Mark R V Murray
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer
  10  *    in this position and unchanged.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  18  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  *
  26  */
  27
  28 /*
  29  * This implementation of Fortuna is based on the descriptions found in
  30  * ISBN 978-0-470-47424-2 "Cryptography Engineering" by Ferguson, Schneier
  31  * and Kohno ("FS&K").
  32  */
  33
  34 #include <sys/cdefs.h>
  35 __FBSDID("$FreeBSD$");
  36
  37 #include <sys/limits.h>
  38
  39 #ifdef _KERNEL
  40 #include <sys/param.h>
  41 #include <sys/kernel.h>
  42 #include <sys/lock.h>
  43 #include <sys/malloc.h>
  44 #include <sys/mutex.h>
  45 #include <sys/random.h>
  46 #include <sys/sdt.h>
  47 #include <sys/sysctl.h>
  48 #include <sys/systm.h>
  49
  50 #include <machine/cpu.h>
  51
  52 #include <crypto/rijndael/rijndael-api-fst.h>
  53 #include <crypto/sha2/sha256.h>
  54
  55 #include <dev/random/hash.h>
  56 #include <dev/random/randomdev.h>
  57 #include <dev/random/random_harvestq.h>
  58 #include <dev/random/uint128.h>
  59 #include <dev/random/fortuna.h>
  60 #else /* !_KERNEL */
  61 #include <inttypes.h>
  62 #include <stdbool.h>
  63 #include <stdio.h>
  64 #include <stdlib.h>
  65 #include <string.h>
  66 #include <threads.h>
  67
  68 #include "unit_test.h"
  69
  70 #include <crypto/rijndael/rijndael-api-fst.h>
  71 #include <crypto/sha2/sha256.h>
  72
  73 #include <dev/random/hash.h>
  74 #include <dev/random/randomdev.h>
  75 #include <dev/random/uint128.h>
  76 #include <dev/random/fortuna.h>
  77 #endif /* _KERNEL */
  78
  79 /* Defined in FS&K */
  80 #define RANDOM_FORTUNA_NPOOLS 32                /* The number of accumulation pools */
  81 #define RANDOM_FORTUNA_DEFPOOLSIZE 64           /* The default pool size/length for a (re)seed */
  82 #define RANDOM_FORTUNA_MAX_READ (1 << 20)       /* Max bytes in a single 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 UINT_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 SDT_PROVIDER_DECLARE(random);
 100 SDT_PROVIDER_DEFINE(random);
 101 SDT_PROBE_DEFINE2(random, fortuna, event_processor, debug, "u_int", "struct fs_pool *");
 102
 103 /*
 104  * This is the beastie that needs protecting. It contains all of the
 105  * state that we are excited about. Exactly one is instantiated.
 106  */
 107 static struct fortuna_state {
 108         struct fs_pool {                /* P_i */
 109                 u_int fsp_length;       /* Only the first one is used by Fortuna */
 110                 struct randomdev_hash fsp_hash;
 111         } fs_pool[RANDOM_FORTUNA_NPOOLS];
 112         u_int fs_reseedcount;           /* ReseedCnt */
 113         uint128_t fs_counter;           /* C */
 114         struct randomdev_key fs_key;    /* K */
 115         u_int fs_minpoolsize;           /* Extras */
 116         /* Extras for the OS */
 117 #ifdef _KERNEL
 118         /* For use when 'pacing' the reseeds */
 119         sbintime_t fs_lasttime;
 120 #endif
 121         /* Reseed lock */
 122         mtx_t fs_mtx;
 123 } fortuna_state;
 124
 125 #ifdef _KERNEL
 126 static struct sysctl_ctx_list random_clist;
 127 RANDOM_CHECK_UINT(fs_minpoolsize, RANDOM_FORTUNA_MINPOOLSIZE, RANDOM_FORTUNA_MAXPOOLSIZE);
 128 #else
 129 static uint8_t zero_region[RANDOM_ZERO_BLOCKSIZE];
 130 #endif
 131
 132 static void random_fortuna_pre_read(void);
 133 static void random_fortuna_read(uint8_t *, u_int);
 134 static bool random_fortuna_seeded(void);
 135 static void random_fortuna_process_event(struct harvest_event *);
 136 static void random_fortuna_init_alg(void *);
 137 static void random_fortuna_deinit_alg(void *);
 138
 139 static void random_fortuna_reseed_internal(uint32_t *entropy_data, u_int blockcount);
 140
 141 struct random_algorithm random_alg_context = {
 142         .ra_ident = "Fortuna",
 143         .ra_init_alg = random_fortuna_init_alg,
 144         .ra_deinit_alg = random_fortuna_deinit_alg,
 145         .ra_pre_read = random_fortuna_pre_read,
 146         .ra_read = random_fortuna_read,
 147         .ra_seeded = random_fortuna_seeded,
 148         .ra_event_processor = random_fortuna_process_event,
 149         .ra_poolcount = RANDOM_FORTUNA_NPOOLS,
 150 };
 151
 152 /* ARGSUSED */
 153 static void
 154 random_fortuna_init_alg(void *unused __unused)
 155 {
 156         int i;
 157 #ifdef _KERNEL
 158         struct sysctl_oid *random_fortuna_o;
 159 #endif
 160
 161         RANDOM_RESEED_INIT_LOCK();
 162         /*
 163          * Fortuna parameters. Do not adjust these unless you have
 164          * have a very good clue about what they do!
 165          */
 166         fortuna_state.fs_minpoolsize = RANDOM_FORTUNA_DEFPOOLSIZE;
 167 #ifdef _KERNEL
 168         fortuna_state.fs_lasttime = 0;
 169         random_fortuna_o = SYSCTL_ADD_NODE(&random_clist,
 170                 SYSCTL_STATIC_CHILDREN(_kern_random),
 171                 OID_AUTO, "fortuna", CTLFLAG_RW, 0,
 172                 "Fortuna Parameters");
 173         SYSCTL_ADD_PROC(&random_clist,
 174                 SYSCTL_CHILDREN(random_fortuna_o), OID_AUTO,
 175                 "minpoolsize", CTLTYPE_UINT | CTLFLAG_RWTUN,
 176                 &fortuna_state.fs_minpoolsize, RANDOM_FORTUNA_DEFPOOLSIZE,
 177                 random_check_uint_fs_minpoolsize, "IU",
 178                 "Minimum pool size necessary to cause a reseed");
 179         KASSERT(fortuna_state.fs_minpoolsize > 0, ("random: Fortuna threshold must be > 0 at startup"));
 180 #endif
 181
 182         /*-
 183          * FS&K - InitializePRNG()
 184          *      - P_i = \epsilon
 185          *      - ReseedCNT = 0
 186          */
 187         for (i = 0; i < RANDOM_FORTUNA_NPOOLS; i++) {
 188                 randomdev_hash_init(&fortuna_state.fs_pool[i].fsp_hash);
 189                 fortuna_state.fs_pool[i].fsp_length = 0;
 190         }
 191         fortuna_state.fs_reseedcount = 0;
 192         /*-
 193          * FS&K - InitializeGenerator()
 194          *      - C = 0
 195          *      - K = 0
 196          */
 197         fortuna_state.fs_counter = UINT128_ZERO;
 198         explicit_bzero(&fortuna_state.fs_key, sizeof(fortuna_state.fs_key));
 199 }
 200
 201 /* ARGSUSED */
 202 static void
 203 random_fortuna_deinit_alg(void *unused __unused)
 204 {
 205
 206         RANDOM_RESEED_DEINIT_LOCK();
 207         explicit_bzero(&fortuna_state, sizeof(fortuna_state));
 208 #ifdef _KERNEL
 209         sysctl_ctx_free(&random_clist);
 210 #endif
 211 }
 212
 213 /*-
 214  * FS&K - AddRandomEvent()
 215  * Process a single stochastic event off the harvest queue
 216  */
 217 static void
 218 random_fortuna_process_event(struct harvest_event *event)
 219 {
 220         u_int pl;
 221
 222         RANDOM_RESEED_LOCK();
 223         /*-
 224          * FS&K - P_i = P_i|<harvested stuff>
 225          * Accumulate the event into the appropriate pool
 226          * where each event carries the destination information.
 227          *
 228          * The hash_init() and hash_finish() calls are done in
 229          * random_fortuna_pre_read().
 230          *
 231          * We must be locked against pool state modification which can happen
 232          * during accumulation/reseeding and reading/regating.
 233          */
 234         pl = event->he_destination % RANDOM_FORTUNA_NPOOLS;
 235         randomdev_hash_iterate(&fortuna_state.fs_pool[pl].fsp_hash, event, sizeof(*event));
 236         /*-
 237          * Don't wrap the length. Doing this the hard way so as not to wrap at MAXUINT.
 238          * This is a "saturating" add.
 239          * XXX: FIX!!: We don't actually need lengths for anything but fs_pool[0],
 240          * but it's been useful debugging to see them all.
 241          */
 242         if (RANDOM_FORTUNA_MAXPOOLSIZE - fortuna_state.fs_pool[pl].fsp_length > event->he_size)
 243                 fortuna_state.fs_pool[pl].fsp_length += event->he_size;
 244         else
 245                 fortuna_state.fs_pool[pl].fsp_length = RANDOM_FORTUNA_MAXPOOLSIZE;
 246         explicit_bzero(event, sizeof(*event));
 247         RANDOM_RESEED_UNLOCK();
 248 }
 249
 250 /*-
 251  * FS&K - Reseed()
 252  * This introduces new key material into the output generator.
 253  * Additionally it increments the output generator's counter
 254  * variable C. When C > 0, the output generator is seeded and
 255  * will deliver output.
 256  * The entropy_data buffer passed is a very specific size; the
 257  * product of RANDOM_FORTUNA_NPOOLS and RANDOM_KEYSIZE.
 258  */
 259 static void
 260 random_fortuna_reseed_internal(uint32_t *entropy_data, u_int blockcount)
 261 {
 262         struct randomdev_hash context;
 263         uint8_t hash[RANDOM_KEYSIZE];
 264
 265         RANDOM_RESEED_ASSERT_LOCK_OWNED();
 266         /*-
 267          * FS&K - K = Hd(K|s) where Hd(m) is H(H(0^512|m))
 268          *      - C = C + 1
 269          */
 270         randomdev_hash_init(&context);
 271         randomdev_hash_iterate(&context, zero_region, RANDOM_ZERO_BLOCKSIZE);
 272         randomdev_hash_iterate(&context, &fortuna_state.fs_key, sizeof(fortuna_state.fs_key));
 273         randomdev_hash_iterate(&context, entropy_data, RANDOM_KEYSIZE*blockcount);
 274         randomdev_hash_finish(&context, hash);
 275         randomdev_hash_init(&context);
 276         randomdev_hash_iterate(&context, hash, RANDOM_KEYSIZE);
 277         randomdev_hash_finish(&context, hash);
 278         randomdev_encrypt_init(&fortuna_state.fs_key, hash);
 279         explicit_bzero(hash, sizeof(hash));
 280         /* Unblock the device if this is the first time we are reseeding. */
 281         if (uint128_is_zero(fortuna_state.fs_counter))
 282                 randomdev_unblock();
 283         uint128_increment(&fortuna_state.fs_counter);
 284 }
 285
 286 /*-
 287  * FS&K - GenerateBlocks()
 288  * Generate a number of complete blocks of random output.
 289  */
 290 static __inline void
 291 random_fortuna_genblocks(uint8_t *buf, u_int blockcount)
 292 {
 293         u_int i;
 294
 295         RANDOM_RESEED_ASSERT_LOCK_OWNED();
 296         for (i = 0; i < blockcount; i++) {
 297                 /*-
 298                  * FS&K - r = r|E(K,C)
 299                  *      - C = C + 1
 300                  */
 301                 randomdev_encrypt(&fortuna_state.fs_key, &fortuna_state.fs_counter, buf, RANDOM_BLOCKSIZE);
 302                 buf += RANDOM_BLOCKSIZE;
 303                 uint128_increment(&fortuna_state.fs_counter);
 304         }
 305 }
 306
 307 /*-
 308  * FS&K - PseudoRandomData()
 309  * This generates no more than 2^20 bytes of data, and cleans up its
 310  * internal state when finished. It is assumed that a whole number of
 311  * blocks are available for writing; any excess generated will be
 312  * ignored.
 313  */
 314 static __inline void
 315 random_fortuna_genrandom(uint8_t *buf, u_int bytecount)
 316 {
 317         static uint8_t temp[RANDOM_BLOCKSIZE*(RANDOM_KEYS_PER_BLOCK)];
 318         u_int blockcount;
 319
 320         RANDOM_RESEED_ASSERT_LOCK_OWNED();
 321         /*-
 322          * FS&K - assert(n < 2^20 (== 1 MB)
 323          *      - r = first-n-bytes(GenerateBlocks(ceil(n/16)))
 324          *      - K = GenerateBlocks(2)
 325          */
 326         KASSERT((bytecount <= RANDOM_FORTUNA_MAX_READ), ("invalid single read request to Fortuna of %d bytes", bytecount));
 327         blockcount = howmany(bytecount, RANDOM_BLOCKSIZE);
 328         random_fortuna_genblocks(buf, blockcount);
 329         random_fortuna_genblocks(temp, RANDOM_KEYS_PER_BLOCK);
 330         randomdev_encrypt_init(&fortuna_state.fs_key, temp);
 331         explicit_bzero(temp, sizeof(temp));
 332 }
 333
 334 /*-
 335  * FS&K - RandomData() (Part 1)
 336  * Used to return processed entropy from the PRNG. There is a pre_read
 337  * required to be present (but it can be a stub) in order to allow
 338  * specific actions at the begin of the read.
 339  */
 340 void
 341 random_fortuna_pre_read(void)
 342 {
 343 #ifdef _KERNEL
 344         sbintime_t now;
 345 #endif
 346         struct randomdev_hash context;
 347         uint32_t s[RANDOM_FORTUNA_NPOOLS*RANDOM_KEYSIZE_WORDS];
 348         uint8_t temp[RANDOM_KEYSIZE];
 349         u_int i;
 350
 351         KASSERT(fortuna_state.fs_minpoolsize > 0, ("random: Fortuna threshold must be > 0"));
 352 #ifdef _KERNEL
 353         /* FS&K - Use 'getsbinuptime()' to prevent reseed-spamming. */
 354         now = getsbinuptime();
 355 #endif
 356         RANDOM_RESEED_LOCK();
 357
 358         if (fortuna_state.fs_pool[0].fsp_length >= fortuna_state.fs_minpoolsize
 359 #ifdef _KERNEL
 360             /* FS&K - Use 'getsbinuptime()' to prevent reseed-spamming. */
 361             && (now - fortuna_state.fs_lasttime > hz/10)
 362 #endif
 363         ) {
 364 #ifdef _KERNEL
 365                 fortuna_state.fs_lasttime = now;
 366 #endif
 367
 368                 /* FS&K - ReseedCNT = ReseedCNT + 1 */
 369                 fortuna_state.fs_reseedcount++;
 370                 /* s = \epsilon at start */
 371                 for (i = 0; i < RANDOM_FORTUNA_NPOOLS; i++) {
 372                         /* FS&K - if Divides(ReseedCnt, 2^i) ... */
 373                         if ((fortuna_state.fs_reseedcount % (1 << i)) == 0) {
 374                                 /*-
 375                                  * FS&K - temp = (P_i)
 376                                  *      - P_i = \epsilon
 377                                  *      - s = s|H(temp)
 378                                  */
 379                                 randomdev_hash_finish(&fortuna_state.fs_pool[i].fsp_hash, temp);
 380                                 randomdev_hash_init(&fortuna_state.fs_pool[i].fsp_hash);
 381                                 fortuna_state.fs_pool[i].fsp_length = 0;
 382                                 randomdev_hash_init(&context);
 383                                 randomdev_hash_iterate(&context, temp, RANDOM_KEYSIZE);
 384                                 randomdev_hash_finish(&context, s + i*RANDOM_KEYSIZE_WORDS);
 385                         } else
 386                                 break;
 387                 }
 388                 SDT_PROBE2(random, fortuna, event_processor, debug, fortuna_state.fs_reseedcount, fortuna_state.fs_pool);
 389                 /* FS&K */
 390                 random_fortuna_reseed_internal(s, i < RANDOM_FORTUNA_NPOOLS ? i + 1 : RANDOM_FORTUNA_NPOOLS);
 391                 /* Clean up and secure */
 392                 explicit_bzero(s, sizeof(s));
 393                 explicit_bzero(temp, sizeof(temp));
 394                 explicit_bzero(&context, sizeof(context));
 395         }
 396         RANDOM_RESEED_UNLOCK();
 397 }
 398
 399 /*-
 400  * FS&K - RandomData() (Part 2)
 401  * Main read from Fortuna, continued. May be called multiple times after
 402  * the random_fortuna_pre_read() above.
 403  * The supplied buf MUST be a multiple of RANDOM_BLOCKSIZE in size.
 404  * Lots of code presumes this for efficiency, both here and in other
 405  * routines. You are NOT allowed to break this!
 406  */
 407 void
 408 random_fortuna_read(uint8_t *buf, u_int bytecount)
 409 {
 410
 411         KASSERT((bytecount % RANDOM_BLOCKSIZE) == 0, ("%s(): bytecount (= %d) must be a multiple of %d", __func__, bytecount, RANDOM_BLOCKSIZE ));
 412         RANDOM_RESEED_LOCK();
 413         random_fortuna_genrandom(buf, bytecount);
 414         RANDOM_RESEED_UNLOCK();
 415 }
 416
 417 bool
 418 random_fortuna_seeded(void)
 419 {
 420
 421         return (!uint128_is_zero(fortuna_state.fs_counter));
 422 }