sys/dev/random/fortuna.c

   1 /*-
   2  * Copyright (c) 2013-2014 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 /* This implementation of Fortuna is based on the descriptions found in
  29  * ISBN 0-471-22357-3 "Practical Cryptography" by Ferguson and Schneier
  30  * ("F&S").
  31  *
  32  * The above book is superseded by ISBN 978-0-470-47424-2 "Cryptography
  33  * Engineering" by Ferguson, Schneier and Kohno ("FS&K").  The code has
  34  * not yet fully caught up with FS&K.
  35  */
  36
  37 #include <sys/cdefs.h>
  38 __FBSDID("$FreeBSD$");
  39
  40 #ifdef _KERNEL
  41 #include "opt_random.h"
  42
  43 #include <sys/param.h>
  44 #include <sys/kernel.h>
  45 #include <sys/lock.h>
  46 #include <sys/malloc.h>
  47 #include <sys/mutex.h>
  48 #include <sys/random.h>
  49 #include <sys/sysctl.h>
  50 #include <sys/systm.h>
  51
  52 #include <machine/cpu.h>
  53
  54 #include <crypto/rijndael/rijndael-api-fst.h>
  55 #include <crypto/sha2/sha2.h>
  56
  57 #include <dev/random/hash.h>
  58 #include <dev/random/randomdev.h>
  59 #include <dev/random/random_adaptors.h>
  60 #include <dev/random/random_harvestq.h>
  61 #include <dev/random/uint128.h>
  62 #include <dev/random/fortuna.h>
  63 #else /* !_KERNEL */
  64 #include <sys/param.h>
  65 #include <sys/types.h>
  66 #include <inttypes.h>
  67 #include <stdio.h>
  68 #include <stdlib.h>
  69 #include <string.h>
  70 #include <threads.h>
  71
  72 #include "unit_test.h"
  73
  74 #include <crypto/rijndael/rijndael-api-fst.h>
  75 #include <crypto/sha2/sha2.h>
  76
  77 #include <dev/random/hash.h>
  78 #include <dev/random/uint128.h>
  79 #include <dev/random/fortuna.h>
  80 #endif /* _KERNEL */
  81
  82 #if !defined(RANDOM_YARROW) && !defined(RANDOM_FORTUNA)
  83 #define RANDOM_YARROW
  84 #elif defined(RANDOM_YARROW) && defined(RANDOM_FORTUNA)
  85 #error "Must define either RANDOM_YARROW or RANDOM_FORTUNA"
  86 #endif
  87
  88 #if defined(RANDOM_FORTUNA)
  89
  90 #define NPOOLS 32
  91 #define MINPOOLSIZE 64
  92 #define DEFPOOLSIZE 256
  93 #define MAXPOOLSIZE 65536
  94
  95 /* This algorithm (and code) presumes that KEYSIZE is twice as large as BLOCKSIZE */
  96 CTASSERT(BLOCKSIZE == sizeof(uint128_t));
  97 CTASSERT(KEYSIZE == 2*BLOCKSIZE);
  98
  99 /* This is the beastie that needs protecting. It contains all of the
 100  * state that we are excited about.
 101  * Exactly one is instantiated.
 102  */
 103 static struct fortuna_state {
 104         /* P_i */
 105         struct pool {
 106                 u_int length;
 107                 struct randomdev_hash hash;
 108         } pool[NPOOLS];
 109
 110         /* ReseedCnt */
 111         u_int reseedcount;
 112
 113         /* C - 128 bits */
 114         union {
 115                 uint8_t byte[BLOCKSIZE];
 116                 uint128_t whole;
 117         } counter;
 118
 119         /* K */
 120         struct randomdev_key key;
 121
 122         /* Extras */
 123         u_int minpoolsize;
 124
 125         /* Extras for the OS */
 126
 127 #ifdef _KERNEL
 128         /* For use when 'pacing' the reseeds */
 129         sbintime_t lasttime;
 130 #endif
 131 } fortuna_state;
 132
 133 /* The random_reseed_mtx mutex protects seeding and polling/blocking.  */
 134 static mtx_t random_reseed_mtx;
 135
 136 static struct fortuna_start_cache {
 137         uint8_t junk[PAGE_SIZE];
 138         size_t length;
 139         struct randomdev_hash hash;
 140 } fortuna_start_cache;
 141
 142 #ifdef _KERNEL
 143 static struct sysctl_ctx_list random_clist;
 144 RANDOM_CHECK_UINT(minpoolsize, MINPOOLSIZE, MAXPOOLSIZE);
 145 #endif
 146
 147 void
 148 random_fortuna_init_alg(void)
 149 {
 150         int i;
 151 #ifdef _KERNEL
 152         struct sysctl_oid *random_fortuna_o;
 153 #endif
 154
 155         memset(fortuna_start_cache.junk, 0, sizeof(fortuna_start_cache.junk));
 156         fortuna_start_cache.length = 0U;
 157         randomdev_hash_init(&fortuna_start_cache.hash);
 158
 159         /* Set up a lock for the reseed process */
 160 #ifdef _KERNEL
 161         mtx_init(&random_reseed_mtx, "reseed mutex", NULL, MTX_DEF);
 162 #else /* !_KERNEL */
 163         mtx_init(&random_reseed_mtx, mtx_plain);
 164 #endif /* _KERNEL */
 165
 166 #ifdef _KERNEL
 167         /* Fortuna parameters. Do not adjust these unless you have
 168          * have a very good clue about what they do!
 169          */
 170         random_fortuna_o = SYSCTL_ADD_NODE(&random_clist,
 171                 SYSCTL_STATIC_CHILDREN(_kern_random),
 172                 OID_AUTO, "fortuna", CTLFLAG_RW, 0,
 173                 "Fortuna Parameters");
 174
 175         SYSCTL_ADD_PROC(&random_clist,
 176                 SYSCTL_CHILDREN(random_fortuna_o), OID_AUTO,
 177                 "minpoolsize", CTLTYPE_UINT|CTLFLAG_RW,
 178                 &fortuna_state.minpoolsize, DEFPOOLSIZE,
 179                 random_check_uint_minpoolsize, "IU",
 180                 "Minimum pool size necessary to cause a reseed automatically");
 181
 182         fortuna_state.lasttime = 0U;
 183 #endif
 184
 185         fortuna_state.minpoolsize = DEFPOOLSIZE;
 186
 187         /* F&S - InitializePRNG() */
 188
 189         /* F&S - P_i = \epsilon */
 190         for (i = 0; i < NPOOLS; i++) {
 191                 randomdev_hash_init(&fortuna_state.pool[i].hash);
 192                 fortuna_state.pool[i].length = 0U;
 193         }
 194
 195         /* F&S - ReseedCNT = 0 */
 196         fortuna_state.reseedcount = 0U;
 197
 198         /* F&S - InitializeGenerator() */
 199
 200         /* F&S - C = 0 */
 201         uint128_clear(&fortuna_state.counter.whole);
 202
 203         /* F&S - K = 0 */
 204         memset(&fortuna_state.key, 0, sizeof(fortuna_state.key));
 205 }
 206
 207 void
 208 random_fortuna_deinit_alg(void)
 209 {
 210
 211         mtx_destroy(&random_reseed_mtx);
 212         memset(&fortuna_state, 0, sizeof(fortuna_state));
 213 }
 214
 215 /* F&S - AddRandomEvent() */
 216 /* Process a single stochastic event off the harvest queue */
 217 void
 218 random_fortuna_process_event(struct harvest_event *event)
 219 {
 220         u_int pl;
 221
 222         /* We must be locked for all this as plenty of state gets messed with */
 223         mtx_lock(&random_reseed_mtx);
 224
 225         /* Accumulate the event into the appropriate pool
 226          * where each event carries the destination information
 227          */
 228         /* F&S - P_i = P_i|<harvested stuff> */
 229         /* The hash_init and hash_finish are done in random_fortuna_read() below */
 230         pl = event->he_destination % NPOOLS;
 231         randomdev_hash_iterate(&fortuna_state.pool[pl].hash, event, sizeof(*event));
 232         /* No point in counting above the outside maximum */
 233         fortuna_state.pool[pl].length += event->he_size;
 234         fortuna_state.pool[pl].length = MIN(fortuna_state.pool[pl].length, MAXPOOLSIZE);
 235
 236         /* Done with state-messing */
 237         mtx_unlock(&random_reseed_mtx);
 238 }
 239
 240 /* F&S - Reseed() */
 241 /* Reseed Mutex is held */
 242 static void
 243 reseed(uint8_t *junk, u_int length)
 244 {
 245         struct randomdev_hash context;
 246         uint8_t hash[KEYSIZE];
 247
 248         KASSERT(fortuna_state.minpoolsize > 0, ("random: Fortuna threshold = 0"));
 249 #ifdef _KERNEL
 250         mtx_assert(&random_reseed_mtx, MA_OWNED);
 251 #endif
 252
 253         /* FS&K - K = Hd(K|s) where Hd(m) is H(H(0^512|m)) */
 254         randomdev_hash_init(&context);
 255         randomdev_hash_iterate(&context, zero_region, 512/8);
 256         randomdev_hash_iterate(&context, &fortuna_state.key, sizeof(fortuna_state.key));
 257         randomdev_hash_iterate(&context, junk, length);
 258         randomdev_hash_finish(&context, hash);
 259         randomdev_hash_init(&context);
 260         randomdev_hash_iterate(&context, hash, KEYSIZE);
 261         randomdev_hash_finish(&context, hash);
 262         randomdev_encrypt_init(&fortuna_state.key, hash);
 263         memset(hash, 0, sizeof(hash));
 264
 265         /* Unblock the device if it was blocked due to being unseeded */
 266         if (uint128_is_zero(fortuna_state.counter.whole))
 267                 random_adaptor_unblock();
 268         /* FS&K - C = C + 1 */
 269         uint128_increment(&fortuna_state.counter.whole);
 270 }
 271
 272 /* F&S - GenerateBlocks() */
 273 /* Reseed Mutex is held, and buf points to a whole number of blocks. */
 274 static __inline void
 275 random_fortuna_genblocks(uint8_t *buf, u_int blockcount)
 276 {
 277         u_int i;
 278
 279         for (i = 0u; i < blockcount; i++) {
 280                 /* F&S - r = r|E(K,C) */
 281                 randomdev_encrypt(&fortuna_state.key, fortuna_state.counter.byte, buf, BLOCKSIZE);
 282                 buf += BLOCKSIZE;
 283
 284                 /* F&S - C = C + 1 */
 285                 uint128_increment(&fortuna_state.counter.whole);
 286         }
 287 }
 288
 289 /* F&S - PseudoRandomData() */
 290 /* Reseed Mutex is held, and buf points to a whole number of blocks. */
 291 static __inline void
 292 random_fortuna_genrandom(uint8_t *buf, u_int bytecount)
 293 {
 294         static uint8_t temp[BLOCKSIZE*(KEYSIZE/BLOCKSIZE)];
 295         u_int blockcount;
 296
 297         /* F&S - assert(n < 2^20) */
 298         KASSERT((bytecount <= (1 << 20)), ("invalid single read request to fortuna of %d bytes", bytecount));
 299
 300         /* F&S - r = first-n-bytes(GenerateBlocks(ceil(n/16))) */
 301         blockcount = (bytecount + BLOCKSIZE - 1)/BLOCKSIZE;
 302         random_fortuna_genblocks(buf, blockcount);
 303
 304         /* F&S - K = GenerateBlocks(2) */
 305         random_fortuna_genblocks(temp, KEYSIZE/BLOCKSIZE);
 306         randomdev_encrypt_init(&fortuna_state.key, temp);
 307         memset(temp, 0, sizeof(temp));
 308 }
 309
 310 /* F&S - RandomData() */
 311 /* Used to return processed entropy from the PRNG */
 312 /* The argument buf points to a whole number of blocks. */
 313 void
 314 random_fortuna_read(uint8_t *buf, u_int bytecount)
 315 {
 316 #ifdef _KERNEL
 317         sbintime_t thistime;
 318 #endif
 319         struct randomdev_hash context;
 320         uint8_t s[NPOOLS*KEYSIZE], temp[KEYSIZE];
 321         int i;
 322         u_int seedlength;
 323
 324         /* We must be locked for all this as plenty of state gets messed with */
 325         mtx_lock(&random_reseed_mtx);
 326
 327         /* if buf == NULL and bytecount == 0 then this is the pre-read. */
 328         /* if buf == NULL and bytecount != 0 then this is the post-read; ignore. */
 329         if (buf == NULL) {
 330                 if (bytecount == 0) {
 331                         if (fortuna_state.pool[0].length >= fortuna_state.minpoolsize
 332 #ifdef _KERNEL
 333                         /* F&S - Use 'getsbinuptime()' to prevent reseed-spamming. */
 334                         && ((thistime = getsbinuptime()) - fortuna_state.lasttime > hz/10)
 335 #endif
 336                         ) {
 337 #ifdef _KERNEL
 338                                 fortuna_state.lasttime = thistime;
 339 #endif
 340
 341                                 seedlength = 0U;
 342                                 /* F&S - ReseedCNT = ReseedCNT + 1 */
 343                                 fortuna_state.reseedcount++;
 344                                 /* s = \epsilon by default */
 345                                 for (i = 0; i < NPOOLS; i++) {
 346                                         /* F&S - if Divides(ReseedCnt, 2^i) ... */
 347                                         if ((fortuna_state.reseedcount % (1 << i)) == 0U) {
 348                                                 seedlength += KEYSIZE;
 349                                                 /* F&S - temp = (P_i) */
 350                                                 randomdev_hash_finish(&fortuna_state.pool[i].hash, temp);
 351                                                 /* F&S - P_i = \epsilon */
 352                                                 randomdev_hash_init(&fortuna_state.pool[i].hash);
 353                                                 fortuna_state.pool[i].length = 0U;
 354                                                 /* F&S - s = s|H(temp) */
 355                                                 randomdev_hash_init(&context);
 356                                                 randomdev_hash_iterate(&context, temp, KEYSIZE);
 357                                                 randomdev_hash_finish(&context, s + i*KEYSIZE);
 358                                         }
 359                                         else
 360                                                 break;
 361                                 }
 362 #ifdef RANDOM_DEBUG
 363                                 printf("random: active reseed: reseedcount [%d] ", fortuna_state.reseedcount);
 364                                 for (i = 0; i < NPOOLS; i++)
 365                                         printf(" %d", fortuna_state.pool[i].length);
 366                                 printf("\n");
 367 #endif
 368                                 /* F&S */
 369                                 reseed(s, seedlength);
 370
 371                                 /* Clean up */
 372                                 memset(s, 0, seedlength);
 373                                 seedlength = 0U;
 374                                 memset(temp, 0, sizeof(temp));
 375                                 memset(&context, 0, sizeof(context));
 376                         }
 377                 }
 378         }
 379         /* if buf != NULL do a regular read. */
 380         else
 381                 random_fortuna_genrandom(buf, bytecount);
 382
 383         mtx_unlock(&random_reseed_mtx);
 384 }
 385
 386 /* Internal function to hand external entropy to the PRNG */
 387 void
 388 random_fortuna_write(uint8_t *buf, u_int count)
 389 {
 390         uint8_t temp[KEYSIZE];
 391         int i;
 392         uintmax_t timestamp;
 393
 394         timestamp = get_cyclecount();
 395         randomdev_hash_iterate(&fortuna_start_cache.hash, &timestamp, sizeof(timestamp));
 396         randomdev_hash_iterate(&fortuna_start_cache.hash, buf, count);
 397         timestamp = get_cyclecount();
 398         randomdev_hash_iterate(&fortuna_start_cache.hash, &timestamp, sizeof(timestamp));
 399         randomdev_hash_finish(&fortuna_start_cache.hash, temp);
 400         for (i = 0; i < KEYSIZE; i++)
 401                 fortuna_start_cache.junk[(fortuna_start_cache.length + i)%PAGE_SIZE] ^= temp[i];
 402         fortuna_start_cache.length += KEYSIZE;
 403
 404 #ifdef RANDOM_DEBUG
 405         printf("random: %s - ", __func__);
 406         for (i = 0; i < KEYSIZE; i++)
 407                 printf("%02X", temp[i]);
 408         printf("\n");
 409 #endif
 410
 411         memset(temp, 0, KEYSIZE);
 412
 413         /* We must be locked for all this as plenty of state gets messed with */
 414         mtx_lock(&random_reseed_mtx);
 415
 416         randomdev_hash_init(&fortuna_start_cache.hash);
 417
 418         reseed(fortuna_start_cache.junk, MIN(PAGE_SIZE, fortuna_start_cache.length));
 419         memset(fortuna_start_cache.junk, 0, sizeof(fortuna_start_cache.junk));
 420
 421         mtx_unlock(&random_reseed_mtx);
 422 }
 423
 424 void
 425 random_fortuna_reseed(void)
 426 {
 427
 428         /* CWOT */
 429 }
 430
 431 int
 432 random_fortuna_seeded(void)
 433 {
 434
 435         return (!uint128_is_zero(fortuna_state.counter.whole));
 436 }
 437
 438 #endif /* RANDOM_FORTUNA */