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