sys/dev/random/yarrow.c

   1 /*-
   2  * Copyright (c) 2000-2013 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 "opt_random.h"
  33
  34 #include <sys/param.h>
  35 #include <sys/kernel.h>
  36 #include <sys/lock.h>
  37 #include <sys/malloc.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_adaptors.h>
  51 #include <dev/random/random_harvestq.h>
  52 #include <dev/random/uint128.h>
  53 #include <dev/random/yarrow.h>
  54 #else /* !_KERNEL */
  55 #include <sys/param.h>
  56 #include <sys/types.h>
  57 #include <inttypes.h>
  58 #include <stdio.h>
  59 #include <stdlib.h>
  60 #include <string.h>
  61 #include <threads.h>
  62
  63 #include "unit_test.h"
  64
  65 #include <crypto/rijndael/rijndael-api-fst.h>
  66 #include <crypto/sha2/sha2.h>
  67
  68 #include <dev/random/hash.h>
  69 #include <dev/random/randomdev.h>
  70 #include <dev/random/uint128.h>
  71 #include <dev/random/yarrow.h>
  72 #endif /* _KERNEL */
  73
  74 #if !defined(RANDOM_YARROW) && !defined(RANDOM_FORTUNA)
  75 #define RANDOM_YARROW
  76 #elif defined(RANDOM_YARROW) && defined(RANDOM_FORTUNA)
  77 #error "Must define either RANDOM_YARROW or RANDOM_FORTUNA"
  78 #endif
  79
  80 #if defined(RANDOM_YARROW)
  81
  82 #define TIMEBIN         16      /* max value for Pt/t */
  83
  84 #define FAST            0
  85 #define SLOW            1
  86
  87 /* This algorithm (and code) presumes that KEYSIZE is twice as large as BLOCKSIZE */
  88 CTASSERT(BLOCKSIZE == sizeof(uint128_t));
  89 CTASSERT(KEYSIZE == 2*BLOCKSIZE);
  90
  91 /* This is the beastie that needs protecting. It contains all of the
  92  * state that we are excited about.
  93  * Exactly one is instantiated.
  94  */
  95 static struct yarrow_state {
  96         union {
  97                 uint8_t byte[BLOCKSIZE];
  98                 uint128_t whole;
  99         } counter;                      /* C */
 100         struct randomdev_key key;       /* K */
 101         u_int gengateinterval;          /* Pg */
 102         u_int bins;                     /* Pt/t */
 103         u_int outputblocks;             /* count output blocks for gates */
 104         u_int slowoverthresh;           /* slow pool overthreshhold reseed count */
 105         struct pool {
 106                 struct source {
 107                         u_int bits;     /* estimated bits of entropy */
 108                 } source[ENTROPYSOURCE];/* ... per source */
 109                 u_int thresh;           /* pool reseed threshhold */
 110                 struct randomdev_hash hash;     /* accumulated entropy */
 111         } pool[2];                      /* pool[0] is fast, pool[1] is slow */
 112         int seeded;
 113
 114         struct start_cache {
 115                 uint8_t junk[KEYSIZE];
 116                 struct randomdev_hash hash;
 117         } start_cache;
 118 } yarrow_state;
 119
 120 /* The random_reseed_mtx mutex protects seeding and polling/blocking.  */
 121 static mtx_t random_reseed_mtx;
 122
 123 #ifdef _KERNEL
 124 static struct sysctl_ctx_list random_clist;
 125 RANDOM_CHECK_UINT(gengateinterval, 4, 64);
 126 RANDOM_CHECK_UINT(bins, 2, 16);
 127 RANDOM_CHECK_UINT(fastthresh, (BLOCKSIZE*8)/4, (BLOCKSIZE*8)); /* Bit counts */
 128 RANDOM_CHECK_UINT(slowthresh, (BLOCKSIZE*8)/4, (BLOCKSIZE*8)); /* Bit counts */
 129 RANDOM_CHECK_UINT(slowoverthresh, 1, 5);
 130 #else /* !_KERNEL */
 131 static u_int harvest_destination[ENTROPYSOURCE];
 132 #endif /* _KERNEL */
 133
 134 static void generator_gate(void);
 135 static void reseed(u_int);
 136
 137 void
 138 random_yarrow_init_alg(void)
 139 {
 140         int i, j;
 141 #ifdef _KERNEL
 142         struct sysctl_oid *random_yarrow_o;
 143 #endif /* _KERNEL */
 144
 145         memset(yarrow_state.start_cache.junk, 0, KEYSIZE);
 146         randomdev_hash_init(&yarrow_state.start_cache.hash);
 147
 148         /* Set up the lock for the reseed/gate state */
 149 #ifdef _KERNEL
 150         mtx_init(&random_reseed_mtx, "reseed mutex", NULL, MTX_DEF);
 151 #else /* !_KERNEL */
 152         mtx_init(&random_reseed_mtx, mtx_plain);
 153 #endif /* _KERNEL */
 154
 155         /* Start unseeded, therefore blocked. */
 156         yarrow_state.seeded = 0;
 157
 158 #ifdef _KERNEL
 159         /* Yarrow parameters. Do not adjust these unless you have
 160          * have a very good clue about what they do!
 161          */
 162         random_yarrow_o = SYSCTL_ADD_NODE(&random_clist,
 163                 SYSCTL_STATIC_CHILDREN(_kern_random),
 164                 OID_AUTO, "yarrow", CTLFLAG_RW, 0,
 165                 "Yarrow Parameters");
 166
 167         SYSCTL_ADD_PROC(&random_clist,
 168                 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
 169                 "gengateinterval", CTLTYPE_INT|CTLFLAG_RW,
 170                 &yarrow_state.gengateinterval, 10,
 171                 random_check_uint_gengateinterval, "I",
 172                 "Generation gate interval");
 173
 174         SYSCTL_ADD_PROC(&random_clist,
 175                 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
 176                 "bins", CTLTYPE_INT|CTLFLAG_RW,
 177                 &yarrow_state.bins, 10,
 178                 random_check_uint_bins, "I",
 179                 "Execution time tuner");
 180
 181         SYSCTL_ADD_PROC(&random_clist,
 182                 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
 183                 "fastthresh", CTLTYPE_INT|CTLFLAG_RW,
 184                 &yarrow_state.pool[0].thresh, (3*(BLOCKSIZE*8))/4,
 185                 random_check_uint_fastthresh, "I",
 186                 "Fast reseed threshold");
 187
 188         SYSCTL_ADD_PROC(&random_clist,
 189                 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
 190                 "slowthresh", CTLTYPE_INT|CTLFLAG_RW,
 191                 &yarrow_state.pool[1].thresh, (BLOCKSIZE*8),
 192                 random_check_uint_slowthresh, "I",
 193                 "Slow reseed threshold");
 194
 195         SYSCTL_ADD_PROC(&random_clist,
 196                 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
 197                 "slowoverthresh", CTLTYPE_INT|CTLFLAG_RW,
 198                 &yarrow_state.slowoverthresh, 2,
 199                 random_check_uint_slowoverthresh, "I",
 200                 "Slow over-threshold reseed");
 201 #endif /* _KERNEL */
 202
 203         yarrow_state.gengateinterval = 10;
 204         yarrow_state.bins = 10;
 205         yarrow_state.pool[FAST].thresh = (3*(BLOCKSIZE*8))/4;
 206         yarrow_state.pool[SLOW].thresh = (BLOCKSIZE*8);
 207         yarrow_state.slowoverthresh = 2;
 208
 209         /* Ensure that the first time we read, we are gated. */
 210         yarrow_state.outputblocks = yarrow_state.gengateinterval;
 211
 212         /* Initialise the fast and slow entropy pools */
 213         for (i = FAST; i <= SLOW; i++) {
 214                 randomdev_hash_init(&yarrow_state.pool[i].hash);
 215                 for (j = RANDOM_START; j < ENTROPYSOURCE; j++)
 216                         yarrow_state.pool[i].source[j].bits = 0U;
 217         }
 218
 219         /* Clear the counter */
 220         uint128_clear(&yarrow_state.counter.whole);
 221 }
 222
 223 void
 224 random_yarrow_deinit_alg(void)
 225 {
 226
 227         mtx_destroy(&random_reseed_mtx);
 228         memset(&yarrow_state, 0, sizeof(yarrow_state));
 229
 230 #ifdef _KERNEL
 231         sysctl_ctx_free(&random_clist);
 232 #endif
 233 }
 234
 235 static __inline void
 236 random_yarrow_post_insert(void)
 237 {
 238         u_int pl, overthreshhold[2];
 239         enum random_entropy_source src;
 240
 241 #ifdef _KERNEL
 242         mtx_assert(&random_reseed_mtx, MA_OWNED);
 243 #endif
 244         /* Count the over-threshold sources in each pool */
 245         for (pl = 0; pl < 2; pl++) {
 246                 overthreshhold[pl] = 0;
 247                 for (src = RANDOM_START; src < ENTROPYSOURCE; src++) {
 248                         if (yarrow_state.pool[pl].source[src].bits > yarrow_state.pool[pl].thresh)
 249                                 overthreshhold[pl]++;
 250                 }
 251         }
 252
 253         /* If enough slow sources are over threshhold, then slow reseed
 254          * else if any fast source over threshhold, then fast reseed.
 255          */
 256         if (overthreshhold[SLOW] >= yarrow_state.slowoverthresh)
 257                 reseed(SLOW);
 258         else if (overthreshhold[FAST] > 0 && yarrow_state.seeded)
 259                 reseed(FAST);
 260 }
 261
 262 /* Process a single stochastic event off the harvest queue */
 263 void
 264 random_yarrow_process_event(struct harvest_event *event)
 265 {
 266         u_int pl;
 267
 268         mtx_lock(&random_reseed_mtx);
 269
 270         /* Accumulate the event into the appropriate pool
 271          * where each event carries the destination information.
 272          * We lock against pool state modification which can happen
 273          * during accumulation/reseeding and reading/regating
 274          */
 275         pl = event->he_destination % 2;
 276         randomdev_hash_iterate(&yarrow_state.pool[pl].hash, event, sizeof(*event));
 277         yarrow_state.pool[pl].source[event->he_source].bits += event->he_bits;
 278
 279         random_yarrow_post_insert();
 280
 281         mtx_unlock(&random_reseed_mtx);
 282 }
 283
 284 /* Process a block of data suspected to be slightly stochastic */
 285 static void
 286 random_yarrow_process_buffer(uint8_t *buf, u_int length)
 287 {
 288         static struct harvest_event event;
 289         u_int i, pl;
 290
 291         /* Accumulate the data into the appropriate pools
 292          * where each event carries the destination information.
 293          * We lock against pool state modification which can happen
 294          * during accumulation/reseeding and reading/regating
 295          */
 296         memset(event.he_entropy + sizeof(uint32_t), 0, HARVESTSIZE - sizeof(uint32_t));
 297         for (i = 0; i < length/sizeof(uint32_t); i++) {
 298                 event.he_somecounter = get_cyclecount();
 299                 event.he_bits = 0; /* Fake */
 300                 event.he_source = RANDOM_CACHED;
 301                 event.he_destination = harvest_destination[RANDOM_CACHED]++;
 302                 event.he_size = sizeof(uint32_t);
 303                 *((uint32_t *)event.he_entropy) = *((uint32_t *)buf + i);
 304
 305                 /* Do the actual entropy insertion */
 306                 pl = event.he_destination % 2;
 307                 randomdev_hash_iterate(&yarrow_state.pool[pl].hash, &event, sizeof(event));
 308 #ifdef DONT_DO_THIS_HERE
 309                 /* Don't do this here - do it in bulk at the end */
 310                 yarrow_state.pool[pl].source[RANDOM_CACHED].bits += bits;
 311 #endif
 312         }
 313         for (pl = FAST; pl <= SLOW; pl++)
 314                 yarrow_state.pool[pl].source[RANDOM_CACHED].bits += (length >> 4);
 315
 316         random_yarrow_post_insert();
 317 }
 318
 319 static void
 320 reseed(u_int fastslow)
 321 {
 322         /* Interrupt-context stack is a limited resource; make large
 323          * structures static.
 324          */
 325         static uint8_t v[TIMEBIN][KEYSIZE];     /* v[i] */
 326         static uint8_t hash[KEYSIZE];           /* h' */
 327         static uint8_t temp[KEYSIZE];
 328         static struct randomdev_hash context;
 329         u_int i;
 330         enum random_entropy_source j;
 331
 332         KASSERT(yarrow_state.pool[FAST].thresh > 0, ("random: Yarrow fast threshold = 0"));
 333         KASSERT(yarrow_state.pool[SLOW].thresh > 0, ("random: Yarrow slow threshold = 0"));
 334
 335 #ifdef RANDOM_DEBUG
 336 #ifdef RANDOM_DEBUG_VERBOSE
 337         printf("random: %s %s\n", __func__, (fastslow == FAST ? "FAST" : "SLOW"));
 338 #endif
 339         if (!yarrow_state.seeded) {
 340                 printf("random: %s - fast - thresh %d,1 - ", __func__, yarrow_state.pool[FAST].thresh);
 341                 for (i = RANDOM_START; i < ENTROPYSOURCE; i++)
 342                         printf(" %d", yarrow_state.pool[FAST].source[i].bits);
 343                 printf("\n");
 344                 printf("random: %s - slow - thresh %d,%d - ", __func__, yarrow_state.pool[SLOW].thresh, yarrow_state.slowoverthresh);
 345                 for (i = RANDOM_START; i < ENTROPYSOURCE; i++)
 346                         printf(" %d", yarrow_state.pool[SLOW].source[i].bits);
 347                 printf("\n");
 348         }
 349 #endif
 350 #ifdef _KERNEL
 351         mtx_assert(&random_reseed_mtx, MA_OWNED);
 352 #endif
 353
 354         /* 1. Hash the accumulated entropy into v[0] */
 355
 356         randomdev_hash_init(&context);
 357         /* Feed the slow pool hash in if slow */
 358         if (fastslow == SLOW) {
 359                 randomdev_hash_finish(&yarrow_state.pool[SLOW].hash, temp);
 360                 randomdev_hash_iterate(&context, temp, sizeof(temp));
 361         }
 362         randomdev_hash_finish(&yarrow_state.pool[FAST].hash, temp);
 363         randomdev_hash_iterate(&context, temp, sizeof(temp));
 364         randomdev_hash_finish(&context, v[0]);
 365
 366         /* 2. Compute hash values for all v. _Supposed_ to be computationally
 367          *    intensive.
 368          */
 369
 370         if (yarrow_state.bins > TIMEBIN)
 371                 yarrow_state.bins = TIMEBIN;
 372         for (i = 1; i < yarrow_state.bins; i++) {
 373                 randomdev_hash_init(&context);
 374                 /* v[i] #= h(v[i - 1]) */
 375                 randomdev_hash_iterate(&context, v[i - 1], KEYSIZE);
 376                 /* v[i] #= h(v[0]) */
 377                 randomdev_hash_iterate(&context, v[0], KEYSIZE);
 378                 /* v[i] #= h(i) */
 379                 randomdev_hash_iterate(&context, &i, sizeof(i));
 380                 /* Return the hashval */
 381                 randomdev_hash_finish(&context, v[i]);
 382         }
 383
 384         /* 3. Compute a new key; h' is the identity function here;
 385          *    it is not being ignored!
 386          */
 387
 388         randomdev_hash_init(&context);
 389         randomdev_hash_iterate(&context, &yarrow_state.key, KEYSIZE);
 390         for (i = 1; i < yarrow_state.bins; i++)
 391                 randomdev_hash_iterate(&context, v[i], KEYSIZE);
 392         randomdev_hash_finish(&context, temp);
 393         randomdev_encrypt_init(&yarrow_state.key, temp);
 394
 395         /* 4. Recompute the counter */
 396
 397         uint128_clear(&yarrow_state.counter.whole);
 398         randomdev_encrypt(&yarrow_state.key, yarrow_state.counter.byte, temp, BLOCKSIZE);
 399         memcpy(yarrow_state.counter.byte, temp, BLOCKSIZE);
 400
 401         /* 5. Reset entropy estimate accumulators to zero */
 402
 403         for (i = 0; i <= fastslow; i++)
 404                 for (j = RANDOM_START; j < ENTROPYSOURCE; j++)
 405                         yarrow_state.pool[i].source[j].bits = 0;
 406
 407         /* 6. Wipe memory of intermediate values */
 408
 409         memset(v, 0, sizeof(v));
 410         memset(temp, 0, sizeof(temp));
 411         memset(hash, 0, sizeof(hash));
 412         memset(&context, 0, sizeof(context));
 413
 414 #ifdef RANDOM_RWFILE_WRITE_IS_OK /* Not defined so writes ain't gonna happen */
 415         /* 7. Dump to seed file */
 416
 417         /* This pseudo-code is documentation. Please leave it alone. */
 418         seed_file = "<some file>";
 419         error = randomdev_write_file(seed_file, <generated entropy>, PAGE_SIZE);
 420         if (error == 0)
 421                 printf("random: entropy seed file '%s' successfully written\n", seed_file);
 422 #endif
 423
 424         /* Unblock the device if it was blocked due to being unseeded */
 425         if (!yarrow_state.seeded) {
 426                 yarrow_state.seeded = 1;
 427                 random_adaptor_unblock();
 428         }
 429 }
 430
 431 /* Internal function to return processed entropy from the PRNG */
 432 void
 433 random_yarrow_read(uint8_t *buf, u_int bytecount)
 434 {
 435         uint8_t tbuf[BLOCKSIZE];
 436         u_int blockcount, i;
 437
 438         /* Check for initial/final read requests */
 439         if (buf == NULL)
 440                 return;
 441
 442         /* The reseed task must not be jumped on */
 443         mtx_lock(&random_reseed_mtx);
 444
 445         blockcount = (bytecount + BLOCKSIZE - 1)/BLOCKSIZE;
 446         for (i = 0; i < blockcount; i++) {
 447                 if (yarrow_state.outputblocks++ >= yarrow_state.gengateinterval) {
 448                         generator_gate();
 449                         yarrow_state.outputblocks = 0;
 450                 }
 451                 uint128_increment(&yarrow_state.counter.whole);
 452                 if ((i + 1) * BLOCKSIZE > bytecount) {
 453                         /* TODO: FIX! remove memcpy()! */
 454                         randomdev_encrypt(&yarrow_state.key,
 455                             yarrow_state.counter.byte, tbuf, BLOCKSIZE);
 456                         memcpy(buf, tbuf, bytecount - i * BLOCKSIZE);
 457                 } else {
 458                         randomdev_encrypt(&yarrow_state.key,
 459                             yarrow_state.counter.byte, buf, BLOCKSIZE);
 460                         buf += BLOCKSIZE;
 461                 }
 462         }
 463
 464         mtx_unlock(&random_reseed_mtx);
 465 }
 466
 467 /* Internal function to hand external entropy to the PRNG */
 468 void
 469 random_yarrow_write(uint8_t *buf, u_int count)
 470 {
 471         uintmax_t timestamp;
 472
 473         /* We must be locked for all this as plenty of state gets messed with */
 474         mtx_lock(&random_reseed_mtx);
 475
 476         timestamp = get_cyclecount();
 477         randomdev_hash_iterate(&yarrow_state.start_cache.hash, &timestamp, sizeof(timestamp));
 478         randomdev_hash_iterate(&yarrow_state.start_cache.hash, buf, count);
 479         timestamp = get_cyclecount();
 480         randomdev_hash_iterate(&yarrow_state.start_cache.hash, &timestamp, sizeof(timestamp));
 481         randomdev_hash_finish(&yarrow_state.start_cache.hash, yarrow_state.start_cache.junk);
 482         randomdev_hash_init(&yarrow_state.start_cache.hash);
 483
 484 #ifdef RANDOM_DEBUG_VERBOSE
 485         {
 486                 int i;
 487
 488                 printf("random: %s - ", __func__);
 489                 for (i = 0; i < KEYSIZE; i++)
 490                         printf("%02X", yarrow_state.start_cache.junk[i]);
 491                 printf("\n");
 492         }
 493 #endif
 494
 495         random_yarrow_process_buffer(yarrow_state.start_cache.junk, KEYSIZE);
 496         memset(yarrow_state.start_cache.junk, 0, KEYSIZE);
 497
 498         mtx_unlock(&random_reseed_mtx);
 499 }
 500
 501 static void
 502 generator_gate(void)
 503 {
 504         u_int i;
 505         uint8_t temp[KEYSIZE];
 506
 507         for (i = 0; i < KEYSIZE; i += BLOCKSIZE) {
 508                 uint128_increment(&yarrow_state.counter.whole);
 509                 randomdev_encrypt(&yarrow_state.key, yarrow_state.counter.byte, temp + i, BLOCKSIZE);
 510         }
 511
 512         randomdev_encrypt_init(&yarrow_state.key, temp);
 513         memset(temp, 0, KEYSIZE);
 514 }
 515
 516 void
 517 random_yarrow_reseed(void)
 518 {
 519
 520         mtx_lock(&random_reseed_mtx);
 521         reseed(SLOW);
 522         mtx_unlock(&random_reseed_mtx);
 523 }
 524
 525 int
 526 random_yarrow_seeded(void)
 527 {
 528
 529         return (yarrow_state.seeded);
 530 }
 531
 532 #endif /* RANDOM_YARROW */