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 #include "opt_random.h"
  32
  33 #include <sys/param.h>
  34 #include <sys/kernel.h>
  35 #include <sys/lock.h>
  36 #include <sys/malloc.h>
  37 #include <sys/mutex.h>
  38 #include <sys/random.h>
  39 #include <sys/sysctl.h>
  40 #include <sys/systm.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/random_adaptors.h>
  47 #include <dev/random/randomdev_soft.h>
  48 #include <dev/random/yarrow.h>
  49
  50 #define TIMEBIN         16      /* max value for Pt/t */
  51
  52 #define FAST            0
  53 #define SLOW            1
  54
  55 /* This is the beastie that needs protecting. It contains all of the
  56  * state that we are excited about.
  57  * Exactly one is instantiated.
  58  */
  59 static struct random_state {
  60         union {
  61                 uint8_t byte[BLOCKSIZE];
  62                 uint64_t qword[BLOCKSIZE/sizeof(uint64_t)];
  63         } counter;              /* C */
  64         struct randomdev_key key; /* K */
  65         u_int gengateinterval;  /* Pg */
  66         u_int bins;             /* Pt/t */
  67         u_int outputblocks;     /* count output blocks for gates */
  68         u_int slowoverthresh;   /* slow pool overthreshhold reseed count */
  69         struct pool {
  70                 struct source {
  71                         u_int bits;     /* estimated bits of entropy */
  72                 } source[ENTROPYSOURCE];
  73                 u_int thresh;   /* pool reseed threshhold */
  74                 struct randomdev_hash hash;     /* accumulated entropy */
  75         } pool[2];              /* pool[0] is fast, pool[1] is slow */
  76         u_int which;            /* toggle - sets the current insertion pool */
  77 } random_state;
  78
  79 RANDOM_CHECK_UINT(gengateinterval, 4, 64);
  80 RANDOM_CHECK_UINT(bins, 2, 16);
  81 RANDOM_CHECK_UINT(fastthresh, (BLOCKSIZE*8)/4, (BLOCKSIZE*8)); /* Bit counts */
  82 RANDOM_CHECK_UINT(slowthresh, (BLOCKSIZE*8)/4, (BLOCKSIZE*8)); /* Bit counts */
  83 RANDOM_CHECK_UINT(slowoverthresh, 1, 5);
  84
  85 static void generator_gate(void);
  86 static void reseed(u_int);
  87
  88 /* The reseed thread mutex */
  89 struct mtx random_reseed_mtx;
  90
  91 /* 128-bit C = 0 */
  92 /* Nothing to see here, folks, just an ugly mess. */
  93 static void
  94 clear_counter(void)
  95 {
  96         random_state.counter.qword[0] = 0UL;
  97         random_state.counter.qword[1] = 0UL;
  98 }
  99
 100 /* 128-bit C = C + 1 */
 101 /* Nothing to see here, folks, just an ugly mess. */
 102 /* TODO: Make a Galois counter instead? */
 103 static void
 104 increment_counter(void)
 105 {
 106         random_state.counter.qword[0]++;
 107         if (!random_state.counter.qword[0])
 108                 random_state.counter.qword[1]++;
 109 }
 110
 111 /* Process a single stochastic event off the harvest queue */
 112 void
 113 random_process_event(struct harvest *event)
 114 {
 115         u_int pl, overthreshhold[2];
 116         struct source *source;
 117         enum esource src;
 118
 119 #if 0
 120         /* Do this better with DTrace */
 121         {
 122                 int i;
 123
 124                 printf("Harvest:%16jX ", event->somecounter);
 125                 for (i = 0; i < event->size; i++)
 126                         printf("%02X", event->entropy[i]);
 127                 for (; i < 16; i++)
 128                         printf("  ");
 129                 printf(" %2d %2d %02X\n", event->size, event->bits, event->source);
 130         }
 131 #endif
 132
 133         /* Accumulate the event into the appropriate pool */
 134         pl = random_state.which;
 135         source = &random_state.pool[pl].source[event->source];
 136         randomdev_hash_iterate(&random_state.pool[pl].hash, event,
 137                 sizeof(*event));
 138         source->bits += event->bits;
 139
 140         /* Count the over-threshold sources in each pool */
 141         for (pl = 0; pl < 2; pl++) {
 142                 overthreshhold[pl] = 0;
 143                 for (src = RANDOM_START; src < ENTROPYSOURCE; src++) {
 144                         if (random_state.pool[pl].source[src].bits
 145                                 > random_state.pool[pl].thresh)
 146                                 overthreshhold[pl]++;
 147                 }
 148         }
 149
 150         /* if any fast source over threshhold, reseed */
 151         if (overthreshhold[FAST])
 152                 reseed(FAST);
 153
 154         /* if enough slow sources are over threshhold, reseed */
 155         if (overthreshhold[SLOW] >= random_state.slowoverthresh)
 156                 reseed(SLOW);
 157
 158         /* Invert the fast/slow pool selector bit */
 159         random_state.which = !random_state.which;
 160 }
 161
 162 void
 163 random_yarrow_init_alg(struct sysctl_ctx_list *clist)
 164 {
 165         int i;
 166         struct sysctl_oid *random_yarrow_o;
 167
 168         /* Yarrow parameters. Do not adjust these unless you have
 169          * have a very good clue about what they do!
 170          */
 171         random_yarrow_o = SYSCTL_ADD_NODE(clist,
 172                 SYSCTL_STATIC_CHILDREN(_kern_random),
 173                 OID_AUTO, "yarrow", CTLFLAG_RW, 0,
 174                 "Yarrow Parameters");
 175
 176         SYSCTL_ADD_PROC(clist,
 177                 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
 178                 "gengateinterval", CTLTYPE_INT|CTLFLAG_RW,
 179                 &random_state.gengateinterval, 10,
 180                 random_check_uint_gengateinterval, "I",
 181                 "Generation gate interval");
 182
 183         SYSCTL_ADD_PROC(clist,
 184                 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
 185                 "bins", CTLTYPE_INT|CTLFLAG_RW,
 186                 &random_state.bins, 10,
 187                 random_check_uint_bins, "I",
 188                 "Execution time tuner");
 189
 190         SYSCTL_ADD_PROC(clist,
 191                 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
 192                 "fastthresh", CTLTYPE_INT|CTLFLAG_RW,
 193                 &random_state.pool[0].thresh, (3*(BLOCKSIZE*8))/4,
 194                 random_check_uint_fastthresh, "I",
 195                 "Fast reseed threshold");
 196
 197         SYSCTL_ADD_PROC(clist,
 198                 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
 199                 "slowthresh", CTLTYPE_INT|CTLFLAG_RW,
 200                 &random_state.pool[1].thresh, (BLOCKSIZE*8),
 201                 random_check_uint_slowthresh, "I",
 202                 "Slow reseed threshold");
 203
 204         SYSCTL_ADD_PROC(clist,
 205                 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
 206                 "slowoverthresh", CTLTYPE_INT|CTLFLAG_RW,
 207                 &random_state.slowoverthresh, 2,
 208                 random_check_uint_slowoverthresh, "I",
 209                 "Slow over-threshold reseed");
 210
 211         random_state.gengateinterval = 10;
 212         random_state.bins = 10;
 213         random_state.pool[0].thresh = (3*(BLOCKSIZE*8))/4;
 214         random_state.pool[1].thresh = (BLOCKSIZE*8);
 215         random_state.slowoverthresh = 2;
 216         random_state.which = FAST;
 217
 218         /* Initialise the fast and slow entropy pools */
 219         for (i = 0; i < 2; i++)
 220                 randomdev_hash_init(&random_state.pool[i].hash);
 221
 222         /* Clear the counter */
 223         clear_counter();
 224
 225         /* Set up a lock for the reseed process */
 226         mtx_init(&random_reseed_mtx, "Yarrow reseed", NULL, MTX_DEF);
 227 }
 228
 229 void
 230 random_yarrow_deinit_alg(void)
 231 {
 232         mtx_destroy(&random_reseed_mtx);
 233 }
 234
 235 static void
 236 reseed(u_int fastslow)
 237 {
 238         /* Interrupt-context stack is a limited resource; make large
 239          * structures static.
 240          */
 241         static uint8_t v[TIMEBIN][KEYSIZE];     /* v[i] */
 242         static struct randomdev_hash context;
 243         uint8_t hash[KEYSIZE];                  /* h' */
 244         uint8_t temp[KEYSIZE];
 245         u_int i;
 246         enum esource j;
 247
 248 #if 0
 249         printf("Yarrow: %s reseed\n", fastslow == FAST ? "fast" : "slow");
 250 #endif
 251
 252         /* The reseed task must not be jumped on */
 253         mtx_lock(&random_reseed_mtx);
 254
 255         /* 1. Hash the accumulated entropy into v[0] */
 256
 257         randomdev_hash_init(&context);
 258         /* Feed the slow pool hash in if slow */
 259         if (fastslow == SLOW)
 260                 randomdev_hash_iterate(&context,
 261                         &random_state.pool[SLOW].hash,
 262                         sizeof(struct randomdev_hash));
 263         randomdev_hash_iterate(&context,
 264                 &random_state.pool[FAST].hash, sizeof(struct randomdev_hash));
 265         randomdev_hash_finish(&context, v[0]);
 266
 267         /* 2. Compute hash values for all v. _Supposed_ to be computationally
 268          *    intensive.
 269          */
 270
 271         if (random_state.bins > TIMEBIN)
 272                 random_state.bins = TIMEBIN;
 273         for (i = 1; i < random_state.bins; i++) {
 274                 randomdev_hash_init(&context);
 275                 /* v[i] #= h(v[i - 1]) */
 276                 randomdev_hash_iterate(&context, v[i - 1], KEYSIZE);
 277                 /* v[i] #= h(v[0]) */
 278                 randomdev_hash_iterate(&context, v[0], KEYSIZE);
 279                 /* v[i] #= h(i) */
 280                 randomdev_hash_iterate(&context, &i, sizeof(u_int));
 281                 /* Return the hashval */
 282                 randomdev_hash_finish(&context, v[i]);
 283         }
 284
 285         /* 3. Compute a new key; h' is the identity function here;
 286          *    it is not being ignored!
 287          */
 288
 289         randomdev_hash_init(&context);
 290         randomdev_hash_iterate(&context, &random_state.key, KEYSIZE);
 291         for (i = 1; i < random_state.bins; i++)
 292                 randomdev_hash_iterate(&context, &v[i], KEYSIZE);
 293         randomdev_hash_finish(&context, temp);
 294         randomdev_encrypt_init(&random_state.key, temp);
 295
 296         /* 4. Recompute the counter */
 297
 298         clear_counter();
 299         randomdev_encrypt(&random_state.key, random_state.counter.byte, temp, BLOCKSIZE);
 300         memcpy(random_state.counter.byte, temp, BLOCKSIZE);
 301
 302         /* 5. Reset entropy estimate accumulators to zero */
 303
 304         for (i = 0; i <= fastslow; i++)
 305                 for (j = RANDOM_START; j < ENTROPYSOURCE; j++)
 306                         random_state.pool[i].source[j].bits = 0;
 307
 308         /* 6. Wipe memory of intermediate values */
 309
 310         memset((void *)v, 0, sizeof(v));
 311         memset((void *)temp, 0, sizeof(temp));
 312         memset((void *)hash, 0, sizeof(hash));
 313
 314         /* 7. Dump to seed file */
 315         /* XXX Not done here yet */
 316
 317         /* Unblock the device if it was blocked due to being unseeded */
 318         randomdev_unblock();
 319
 320         /* Release the reseed mutex */
 321         mtx_unlock(&random_reseed_mtx);
 322 }
 323
 324 /* Internal function to return processed entropy from the PRNG */
 325 int
 326 random_yarrow_read(void *buf, int count)
 327 {
 328         static int cur = 0;
 329         static int gate = 1;
 330         static uint8_t genval[KEYSIZE];
 331         size_t tomove;
 332         int i;
 333         int retval;
 334
 335         /* Check for final read request */
 336         if (buf == NULL && count == 0)
 337                 return (0);
 338
 339         /* The reseed task must not be jumped on */
 340         mtx_lock(&random_reseed_mtx);
 341
 342         if (gate) {
 343                 generator_gate();
 344                 random_state.outputblocks = 0;
 345                 gate = 0;
 346         }
 347         if (count > 0 && (size_t)count >= BLOCKSIZE) {
 348                 retval = 0;
 349                 for (i = 0; i < count; i += BLOCKSIZE) {
 350                         increment_counter();
 351                         randomdev_encrypt(&random_state.key, random_state.counter.byte, genval, BLOCKSIZE);
 352                         tomove = MIN(count - i, BLOCKSIZE);
 353                         memcpy((char *)buf + i, genval, tomove);
 354                         if (++random_state.outputblocks >= random_state.gengateinterval) {
 355                                 generator_gate();
 356                                 random_state.outputblocks = 0;
 357                         }
 358                         retval += (int)tomove;
 359                         cur = 0;
 360                 }
 361         }
 362         else {
 363                 if (!cur) {
 364                         increment_counter();
 365                         randomdev_encrypt(&random_state.key, random_state.counter.byte, genval, BLOCKSIZE);
 366                         memcpy(buf, genval, (size_t)count);
 367                         cur = BLOCKSIZE - count;
 368                         if (++random_state.outputblocks >= random_state.gengateinterval) {
 369                                 generator_gate();
 370                                 random_state.outputblocks = 0;
 371                         }
 372                         retval = count;
 373                 }
 374                 else {
 375                         retval = MIN(cur, count);
 376                         memcpy(buf, &genval[BLOCKSIZE - cur], (size_t)retval);
 377                         cur -= retval;
 378                 }
 379         }
 380         mtx_unlock(&random_reseed_mtx);
 381         return (retval);
 382 }
 383
 384 static void
 385 generator_gate(void)
 386 {
 387         u_int i;
 388         uint8_t temp[KEYSIZE];
 389
 390         for (i = 0; i < KEYSIZE; i += BLOCKSIZE) {
 391                 increment_counter();
 392                 randomdev_encrypt(&random_state.key, random_state.counter.byte, temp + i, BLOCKSIZE);
 393         }
 394
 395         randomdev_encrypt_init(&random_state.key, temp);
 396         memset((void *)temp, 0, KEYSIZE);
 397 }
 398
 399 /* Helper routine to perform explicit reseeds */
 400 void
 401 random_yarrow_reseed(void)
 402 {
 403 #ifdef RANDOM_DEBUG
 404         int i;
 405
 406         printf("%s(): fast:", __func__);
 407         for (i = RANDOM_START; i < ENTROPYSOURCE; ++i)
 408                 printf(" %d", random_state.pool[FAST].source[i].bits);
 409         printf("\n");
 410         printf("%s(): slow:", __func__);
 411         for (i = RANDOM_START; i < ENTROPYSOURCE; ++i)
 412                 printf(" %d", random_state.pool[SLOW].source[i].bits);
 413         printf("\n");
 414 #endif
 415         reseed(SLOW);
 416 }