sys/dev/random/yarrow.c

   1 /*-
   2  * Copyright (c) 2000-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 #include <sys/cdefs.h>
  29 __FBSDID("$FreeBSD$");
  30
  31 #ifdef _KERNEL
  32 #include <sys/param.h>
  33 #include <sys/lock.h>
  34 #include <sys/malloc.h>
  35 #include <sys/mutex.h>
  36 #include <sys/random.h>
  37 #include <sys/sdt.h>
  38 #include <sys/sysctl.h>
  39 #include <sys/systm.h>
  40
  41 #include <machine/cpu.h>
  42
  43 #include <crypto/rijndael/rijndael-api-fst.h>
  44 #include <crypto/sha2/sha256.h>
  45
  46 #include <dev/random/hash.h>
  47 #include <dev/random/randomdev.h>
  48 #include <dev/random/random_harvestq.h>
  49 #include <dev/random/uint128.h>
  50 #include <dev/random/yarrow.h>
  51 #else /* !_KERNEL */
  52 #include <inttypes.h>
  53 #include <stdbool.h>
  54 #include <stdio.h>
  55 #include <stdlib.h>
  56 #include <stdint.h>
  57 #include <string.h>
  58 #include <threads.h>
  59
  60 #include "unit_test.h"
  61
  62 #include <crypto/rijndael/rijndael-api-fst.h>
  63 #include <crypto/sha2/sha256.h>
  64
  65 #include <dev/random/hash.h>
  66 #include <dev/random/randomdev.h>
  67 #include <dev/random/uint128.h>
  68 #include <dev/random/yarrow.h>
  69 #endif /* _KERNEL */
  70
  71 #define RANDOM_YARROW_TIMEBIN   16      /* max value for Pt/t */
  72
  73 #define RANDOM_YARROW_FAST      0
  74 #define RANDOM_YARROW_SLOW      1
  75 #define RANDOM_YARROW_NPOOLS    2
  76
  77 /* This algorithm (and code) presumes that RANDOM_KEYSIZE is twice as large as RANDOM_BLOCKSIZE */
  78 CTASSERT(RANDOM_BLOCKSIZE == sizeof(uint128_t));
  79 CTASSERT(RANDOM_KEYSIZE == 2*RANDOM_BLOCKSIZE);
  80
  81 /* Probes for dtrace(1) */
  82 SDT_PROVIDER_DECLARE(random);
  83 SDT_PROVIDER_DEFINE(random);
  84 SDT_PROBE_DEFINE3(random, yarrow, event_processor, debug, "boolean", "u_int", "struct ys_pool *");
  85
  86 /*
  87  * This is the beastie that needs protecting. It contains all of the
  88  * state that we are excited about. Exactly one is instantiated.
  89  */
  90 static struct yarrow_state {
  91         uint128_t ys_counter;           /* C */
  92         struct randomdev_key ys_key;    /* K */
  93         u_int ys_gengateinterval;       /* Pg */
  94         u_int ys_bins;                  /* Pt/t */
  95         u_int ys_outputblocks;          /* count output blocks for gates */
  96         u_int ys_slowoverthresh;        /* slow pool overthreshhold reseed count */
  97         struct ys_pool {
  98                 u_int ysp_source_bits[ENTROPYSOURCE];   /* estimated bits of entropy per source */
  99                 u_int ysp_thresh;       /* pool reseed threshold */
 100                 struct randomdev_hash ysp_hash; /* accumulated entropy */
 101         } ys_pool[RANDOM_YARROW_NPOOLS];/* pool[0] is fast, pool[1] is slow */
 102         bool ys_seeded;
 103         /* Reseed lock */
 104         mtx_t ys_mtx;
 105 } yarrow_state;
 106
 107 #ifdef _KERNEL
 108 static struct sysctl_ctx_list random_clist;
 109 RANDOM_CHECK_UINT(gengateinterval, 4, 64);
 110 RANDOM_CHECK_UINT(bins, RANDOM_YARROW_NPOOLS, 16);
 111 RANDOM_CHECK_UINT(fastthresh, (RANDOM_BLOCKSIZE*8)/4, (RANDOM_BLOCKSIZE*8)); /* Bit counts */
 112 RANDOM_CHECK_UINT(slowthresh, (RANDOM_BLOCKSIZE*8)/4, (RANDOM_BLOCKSIZE*8)); /* Bit counts */
 113 RANDOM_CHECK_UINT(slowoverthresh, 1, 5);
 114 #endif /* _KERNEL */
 115
 116 static void random_yarrow_pre_read(void);
 117 static void random_yarrow_read(uint8_t *, u_int);
 118 static bool random_yarrow_seeded(void);
 119 static void random_yarrow_process_event(struct harvest_event *);
 120 static void random_yarrow_init_alg(void *);
 121 static void random_yarrow_deinit_alg(void *);
 122
 123 static void random_yarrow_reseed_internal(u_int);
 124
 125 struct random_algorithm random_alg_context = {
 126         .ra_ident = "Yarrow",
 127         .ra_init_alg = random_yarrow_init_alg,
 128         .ra_deinit_alg = random_yarrow_deinit_alg,
 129         .ra_pre_read = random_yarrow_pre_read,
 130         .ra_read = random_yarrow_read,
 131         .ra_seeded = random_yarrow_seeded,
 132         .ra_event_processor = random_yarrow_process_event,
 133         .ra_poolcount = RANDOM_YARROW_NPOOLS,
 134 };
 135
 136 /* ARGSUSED */
 137 static void
 138 random_yarrow_init_alg(void *unused __unused)
 139 {
 140         int i, j;
 141 #ifdef _KERNEL
 142         struct sysctl_oid *random_yarrow_o;
 143 #endif
 144
 145         RANDOM_RESEED_INIT_LOCK();
 146         /* Start unseeded, therefore blocked. */
 147         yarrow_state.ys_seeded = false;
 148 #ifdef _KERNEL
 149         /*
 150          * Yarrow parameters. Do not adjust these unless you have
 151          * have a very good clue about what they do!
 152          */
 153         random_yarrow_o = SYSCTL_ADD_NODE(&random_clist,
 154                 SYSCTL_STATIC_CHILDREN(_kern_random),
 155                 OID_AUTO, "yarrow", CTLFLAG_RW, 0,
 156                 "Yarrow Parameters");
 157         SYSCTL_ADD_PROC(&random_clist,
 158                 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
 159                 "gengateinterval", CTLTYPE_UINT | CTLFLAG_RWTUN,
 160                 &yarrow_state.ys_gengateinterval, 0,
 161                 random_check_uint_gengateinterval, "UI",
 162                 "Generation gate interval");
 163         SYSCTL_ADD_PROC(&random_clist,
 164                 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
 165                 "bins", CTLTYPE_UINT | CTLFLAG_RWTUN,
 166                 &yarrow_state.ys_bins, 0,
 167                 random_check_uint_bins, "UI",
 168                 "Execution time tuner");
 169         SYSCTL_ADD_PROC(&random_clist,
 170                 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
 171                 "fastthresh", CTLTYPE_UINT | CTLFLAG_RWTUN,
 172                 &yarrow_state.ys_pool[0].ysp_thresh, 0,
 173                 random_check_uint_fastthresh, "UI",
 174                 "Fast reseed threshold");
 175         SYSCTL_ADD_PROC(&random_clist,
 176                 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
 177                 "slowthresh", CTLTYPE_UINT | CTLFLAG_RWTUN,
 178                 &yarrow_state.ys_pool[1].ysp_thresh, 0,
 179                 random_check_uint_slowthresh, "UI",
 180                 "Slow reseed threshold");
 181         SYSCTL_ADD_PROC(&random_clist,
 182                 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
 183                 "slowoverthresh", CTLTYPE_UINT | CTLFLAG_RWTUN,
 184                 &yarrow_state.ys_slowoverthresh, 0,
 185                 random_check_uint_slowoverthresh, "UI",
 186                 "Slow over-threshold reseed");
 187 #endif /* _KERNEL */
 188         yarrow_state.ys_gengateinterval = 10;
 189         yarrow_state.ys_bins = 10;
 190         yarrow_state.ys_pool[RANDOM_YARROW_FAST].ysp_thresh = (3*(RANDOM_BLOCKSIZE*8))/4;
 191         yarrow_state.ys_pool[RANDOM_YARROW_SLOW].ysp_thresh = (RANDOM_BLOCKSIZE*8);
 192         yarrow_state.ys_slowoverthresh = 2;
 193         /* Ensure that the first time we read, we are gated. */
 194         yarrow_state.ys_outputblocks = yarrow_state.ys_gengateinterval;
 195         /* Initialise the fast and slow entropy pools */
 196         for (i = RANDOM_YARROW_FAST; i <= RANDOM_YARROW_SLOW; i++) {
 197                 randomdev_hash_init(&yarrow_state.ys_pool[i].ysp_hash);
 198                 for (j = RANDOM_START; j < ENTROPYSOURCE; j++)
 199                         yarrow_state.ys_pool[i].ysp_source_bits[j] = 0;
 200         }
 201         /* Clear the counter */
 202         yarrow_state.ys_counter = UINT128_ZERO;
 203 }
 204
 205 /* ARGSUSED */
 206 static void
 207 random_yarrow_deinit_alg(void *unused __unused)
 208 {
 209
 210         RANDOM_RESEED_DEINIT_LOCK();
 211         explicit_bzero(&yarrow_state, sizeof(yarrow_state));
 212 #ifdef _KERNEL
 213         sysctl_ctx_free(&random_clist);
 214 #endif
 215 }
 216
 217 /* Process a single stochastic event off the harvest queue */
 218 static void
 219 random_yarrow_process_event(struct harvest_event *event)
 220 {
 221         u_int pl, overthreshhold[RANDOM_YARROW_NPOOLS];
 222         enum random_entropy_source src;
 223
 224         RANDOM_RESEED_LOCK();
 225         /*
 226          * Accumulate the event into the appropriate pool
 227          * where each event carries the destination information.
 228          * We lock against pool state modification which can happen
 229          * during accumulation/reseeding and reading/regating
 230          */
 231         pl = event->he_destination % RANDOM_YARROW_NPOOLS;
 232         randomdev_hash_iterate(&yarrow_state.ys_pool[pl].ysp_hash, event, sizeof(*event));
 233         yarrow_state.ys_pool[pl].ysp_source_bits[event->he_source] += event->he_bits;
 234         /* Count the over-threshold sources in each pool */
 235         for (pl = RANDOM_YARROW_FAST; pl <= RANDOM_YARROW_SLOW; pl++) {
 236                 overthreshhold[pl] = 0;
 237                 for (src = RANDOM_START; src < ENTROPYSOURCE; src++) {
 238                         if (yarrow_state.ys_pool[pl].ysp_source_bits[src] > yarrow_state.ys_pool[pl].ysp_thresh)
 239                                 overthreshhold[pl]++;
 240                 }
 241         }
 242         /*
 243          * If enough slow sources are over threshold, then slow reseed
 244          * else if any fast source over threshold, then fast reseed.
 245          */
 246         if (overthreshhold[RANDOM_YARROW_SLOW] >= yarrow_state.ys_slowoverthresh)
 247                 random_yarrow_reseed_internal(RANDOM_YARROW_SLOW);
 248         else if (overthreshhold[RANDOM_YARROW_FAST] > 0 && yarrow_state.ys_seeded)
 249                 random_yarrow_reseed_internal(RANDOM_YARROW_FAST);
 250         explicit_bzero(event, sizeof(*event));
 251         RANDOM_RESEED_UNLOCK();
 252 }
 253
 254 static void
 255 random_yarrow_reseed_internal(u_int fastslow)
 256 {
 257         /*
 258          * Interrupt-context stack is a limited resource; make large
 259          * structures static.
 260          */
 261         static uint8_t v[RANDOM_YARROW_TIMEBIN][RANDOM_KEYSIZE];        /* v[i] */
 262         static uint128_t temp;
 263         static struct randomdev_hash context;
 264         u_int i;
 265         enum random_entropy_source j;
 266
 267         KASSERT(yarrow_state.ys_pool[RANDOM_YARROW_FAST].ysp_thresh > 0, ("random: Yarrow fast threshold = 0"));
 268         KASSERT(yarrow_state.ys_pool[RANDOM_YARROW_SLOW].ysp_thresh > 0, ("random: Yarrow slow threshold = 0"));
 269         RANDOM_RESEED_ASSERT_LOCK_OWNED();
 270         SDT_PROBE3(random, yarrow, event_processor, debug, yarrow_state.ys_seeded, yarrow_state.ys_slowoverthresh, yarrow_state.ys_pool);
 271         /* 1. Hash the accumulated entropy into v[0] */
 272         randomdev_hash_init(&context);
 273         /* Feed the slow pool hash in if slow */
 274         if (fastslow == RANDOM_YARROW_SLOW) {
 275                 randomdev_hash_finish(&yarrow_state.ys_pool[RANDOM_YARROW_SLOW].ysp_hash, &temp);
 276                 randomdev_hash_iterate(&context, &temp, sizeof(temp));
 277         }
 278         randomdev_hash_finish(&yarrow_state.ys_pool[RANDOM_YARROW_FAST].ysp_hash, &temp);
 279         randomdev_hash_iterate(&context, &temp, sizeof(temp));
 280         randomdev_hash_finish(&context, v[0]);
 281         /*-
 282          * 2. Compute hash values for all v. _Supposed_ to be computationally
 283          *    intensive.
 284          */
 285         if (yarrow_state.ys_bins > RANDOM_YARROW_TIMEBIN)
 286                 yarrow_state.ys_bins = RANDOM_YARROW_TIMEBIN;
 287         for (i = 1; i < yarrow_state.ys_bins; i++) {
 288                 randomdev_hash_init(&context);
 289                 /* v[i] #= h(v[i - 1]) */
 290                 randomdev_hash_iterate(&context, v[i - 1], RANDOM_KEYSIZE);
 291                 /* v[i] #= h(v[0]) */
 292                 randomdev_hash_iterate(&context, v[0], RANDOM_KEYSIZE);
 293                 /* v[i] #= h(i) */
 294                 randomdev_hash_iterate(&context, &i, sizeof(i));
 295                 /* Return the hashval */
 296                 randomdev_hash_finish(&context, v[i]);
 297         }
 298         /*-
 299          * 3. Compute a new key; h' is the identity function here;
 300          *    it is not being ignored!
 301          */
 302         randomdev_hash_init(&context);
 303         randomdev_hash_iterate(&context, &yarrow_state.ys_key, RANDOM_KEYSIZE);
 304         for (i = 1; i < yarrow_state.ys_bins; i++)
 305                 randomdev_hash_iterate(&context, v[i], RANDOM_KEYSIZE);
 306         randomdev_hash_finish(&context, &temp);
 307         randomdev_encrypt_init(&yarrow_state.ys_key, &temp);
 308         /* 4. Recompute the counter */
 309         yarrow_state.ys_counter = UINT128_ZERO;
 310         randomdev_encrypt(&yarrow_state.ys_key, &yarrow_state.ys_counter, &temp, RANDOM_BLOCKSIZE);
 311         yarrow_state.ys_counter = temp;
 312         /* 5. Reset entropy estimate accumulators to zero */
 313         for (i = 0; i <= fastslow; i++)
 314                 for (j = RANDOM_START; j < ENTROPYSOURCE; j++)
 315                         yarrow_state.ys_pool[i].ysp_source_bits[j] = 0;
 316         /* 6. Wipe memory of intermediate values */
 317         explicit_bzero(v, sizeof(v));
 318         explicit_bzero(&temp, sizeof(temp));
 319         explicit_bzero(&context, sizeof(context));
 320 /* Not defined so writes ain't gonna happen. Kept for documenting. */
 321 #ifdef RANDOM_RWFILE_WRITE_IS_OK
 322         /*-
 323          * 7. Dump to seed file.
 324          * This pseudo-code is documentation. Please leave it alone.
 325          */
 326         seed_file = "<some file>";
 327         error = randomdev_write_file(seed_file, <generated entropy>, PAGE_SIZE);
 328         if (error == 0)
 329                 printf("random: entropy seed file '%s' successfully written\n", seed_file);
 330 #endif
 331         /* Unblock the device if it was blocked due to being unseeded */
 332         if (!yarrow_state.ys_seeded) {
 333                 yarrow_state.ys_seeded = true;
 334                 randomdev_unblock();
 335         }
 336 }
 337
 338 static __inline void
 339 random_yarrow_generator_gate(void)
 340 {
 341         u_int i;
 342         uint8_t temp[RANDOM_KEYSIZE];
 343
 344         RANDOM_RESEED_ASSERT_LOCK_OWNED();
 345         uint128_increment(&yarrow_state.ys_counter);
 346         for (i = 0; i < RANDOM_KEYSIZE; i += RANDOM_BLOCKSIZE)
 347                 randomdev_encrypt(&yarrow_state.ys_key, &yarrow_state.ys_counter, temp + i, RANDOM_BLOCKSIZE);
 348         randomdev_encrypt_init(&yarrow_state.ys_key, temp);
 349         explicit_bzero(temp, sizeof(temp));
 350 }
 351
 352 /*-
 353  * Used to return processed entropy from the PRNG. There is a pre_read
 354  * required to be present (but it can be a stub) in order to allow
 355  * specific actions at the begin of the read.
 356  * Yarrow does its reseeding in its own thread; _pre_read() is not used
 357  * by Yarrow but must be kept for completeness.
 358  */
 359 void
 360 random_yarrow_pre_read(void)
 361 {
 362 }
 363
 364 /*-
 365  * Main read from Yarrow.
 366  * The supplied buf MUST be a multiple (>=0) of RANDOM_BLOCKSIZE in size.
 367  * Lots of code presumes this for efficiency, both here and in other
 368  * routines. You are NOT allowed to break this!
 369  */
 370 void
 371 random_yarrow_read(uint8_t *buf, u_int bytecount)
 372 {
 373         u_int blockcount, i;
 374
 375         KASSERT((bytecount % RANDOM_BLOCKSIZE) == 0, ("%s(): bytecount (= %d) must be a multiple of %d", __func__, bytecount, RANDOM_BLOCKSIZE ));
 376         RANDOM_RESEED_LOCK();
 377         blockcount = howmany(bytecount, RANDOM_BLOCKSIZE);
 378         for (i = 0; i < blockcount; i++) {
 379                 if (yarrow_state.ys_outputblocks++ >= yarrow_state.ys_gengateinterval) {
 380                         random_yarrow_generator_gate();
 381                         yarrow_state.ys_outputblocks = 0;
 382                 }
 383                 uint128_increment(&yarrow_state.ys_counter);
 384                 randomdev_encrypt(&yarrow_state.ys_key, &yarrow_state.ys_counter, buf, RANDOM_BLOCKSIZE);
 385                 buf += RANDOM_BLOCKSIZE;
 386         }
 387         RANDOM_RESEED_UNLOCK();
 388 }
 389
 390 bool
 391 random_yarrow_seeded(void)
 392 {
 393
 394         return (yarrow_state.ys_seeded);
 395 }