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