1 /*- 2 * Copyright (c) 2017 W. Dean Freeman 3 * Copyright (c) 2013-2015 Mark R V Murray 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer 11 * in this position and unchanged. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 17 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 19 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 21 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 * 27 */ 28 29 /* 30 * This implementation of Fortuna is based on the descriptions found in 31 * ISBN 978-0-470-47424-2 "Cryptography Engineering" by Ferguson, Schneier 32 * and Kohno ("FS&K"). 33 */ 34 35 #include <sys/cdefs.h> 36 __FBSDID("$FreeBSD$"); 37 38 #include <sys/param.h> 39 #include <sys/limits.h> 40 41 #ifdef _KERNEL 42 #include <sys/fail.h> 43 #include <sys/kernel.h> 44 #include <sys/lock.h> 45 #include <sys/malloc.h> 46 #include <sys/mutex.h> 47 #include <sys/random.h> 48 #include <sys/sdt.h> 49 #include <sys/sysctl.h> 50 #include <sys/systm.h> 51 52 #include <machine/cpu.h> 53 #else /* !_KERNEL */ 54 #include <inttypes.h> 55 #include <stdbool.h> 56 #include <stdio.h> 57 #include <stdlib.h> 58 #include <string.h> 59 #include <threads.h> 60 61 #include "unit_test.h" 62 #endif /* _KERNEL */ 63 64 #include <crypto/rijndael/rijndael-api-fst.h> 65 #include <crypto/sha2/sha256.h> 66 67 #include <dev/random/hash.h> 68 #include <dev/random/randomdev.h> 69 #ifdef _KERNEL 70 #include <dev/random/random_harvestq.h> 71 #endif 72 #include <dev/random/uint128.h> 73 #include <dev/random/fortuna.h> 74 75 /* Defined in FS&K */ 76 #define RANDOM_FORTUNA_NPOOLS 32 /* The number of accumulation pools */ 77 #define RANDOM_FORTUNA_DEFPOOLSIZE 64 /* The default pool size/length for a (re)seed */ 78 #define RANDOM_FORTUNA_MAX_READ (1 << 20) /* Max bytes in a single read */ 79 80 /* 81 * The allowable range of RANDOM_FORTUNA_DEFPOOLSIZE. The default value is above. 82 * Making RANDOM_FORTUNA_DEFPOOLSIZE too large will mean a long time between reseeds, 83 * and too small may compromise initial security but get faster reseeds. 84 */ 85 #define RANDOM_FORTUNA_MINPOOLSIZE 16 86 #define RANDOM_FORTUNA_MAXPOOLSIZE INT_MAX 87 CTASSERT(RANDOM_FORTUNA_MINPOOLSIZE <= RANDOM_FORTUNA_DEFPOOLSIZE); 88 CTASSERT(RANDOM_FORTUNA_DEFPOOLSIZE <= RANDOM_FORTUNA_MAXPOOLSIZE); 89 90 /* This algorithm (and code) presumes that RANDOM_KEYSIZE is twice as large as RANDOM_BLOCKSIZE */ 91 CTASSERT(RANDOM_BLOCKSIZE == sizeof(uint128_t)); 92 CTASSERT(RANDOM_KEYSIZE == 2*RANDOM_BLOCKSIZE); 93 94 /* Probes for dtrace(1) */ 95 #ifdef _KERNEL 96 SDT_PROVIDER_DECLARE(random); 97 SDT_PROVIDER_DEFINE(random); 98 SDT_PROBE_DEFINE2(random, fortuna, event_processor, debug, "u_int", "struct fs_pool *"); 99 #endif /* _KERNEL */ 100 101 /* 102 * This is the beastie that needs protecting. It contains all of the 103 * state that we are excited about. Exactly one is instantiated. 104 */ 105 static struct fortuna_state { 106 struct fs_pool { /* P_i */ 107 u_int fsp_length; /* Only the first one is used by Fortuna */ 108 struct randomdev_hash fsp_hash; 109 } fs_pool[RANDOM_FORTUNA_NPOOLS]; 110 u_int fs_reseedcount; /* ReseedCnt */ 111 uint128_t fs_counter; /* C */ 112 union randomdev_key fs_key; /* K */ 113 u_int fs_minpoolsize; /* Extras */ 114 /* Extras for the OS */ 115 #ifdef _KERNEL 116 /* For use when 'pacing' the reseeds */ 117 sbintime_t fs_lasttime; 118 #endif 119 /* Reseed lock */ 120 mtx_t fs_mtx; 121 } fortuna_state; 122 123 #ifdef _KERNEL 124 static struct sysctl_ctx_list random_clist; 125 RANDOM_CHECK_UINT(fs_minpoolsize, RANDOM_FORTUNA_MINPOOLSIZE, RANDOM_FORTUNA_MAXPOOLSIZE); 126 #else 127 static uint8_t zero_region[RANDOM_ZERO_BLOCKSIZE]; 128 #endif 129 130 static void random_fortuna_pre_read(void); 131 static void random_fortuna_read(uint8_t *, u_int); 132 static bool random_fortuna_seeded(void); 133 static bool random_fortuna_seeded_internal(void); 134 static void random_fortuna_process_event(struct harvest_event *); 135 static void random_fortuna_init_alg(void *); 136 static void random_fortuna_deinit_alg(void *); 137 138 static void random_fortuna_reseed_internal(uint32_t *entropy_data, u_int blockcount); 139 140 struct random_algorithm random_alg_context = { 141 .ra_ident = "Fortuna", 142 .ra_init_alg = random_fortuna_init_alg, 143 .ra_deinit_alg = random_fortuna_deinit_alg, 144 .ra_pre_read = random_fortuna_pre_read, 145 .ra_read = random_fortuna_read, 146 .ra_seeded = random_fortuna_seeded, 147 .ra_event_processor = random_fortuna_process_event, 148 .ra_poolcount = RANDOM_FORTUNA_NPOOLS, 149 }; 150 151 /* ARGSUSED */ 152 static void 153 random_fortuna_init_alg(void *unused __unused) 154 { 155 int i; 156 #ifdef _KERNEL 157 struct sysctl_oid *random_fortuna_o; 158 #endif 159 160 RANDOM_RESEED_INIT_LOCK(); 161 /* 162 * Fortuna parameters. Do not adjust these unless you have 163 * have a very good clue about what they do! 164 */ 165 fortuna_state.fs_minpoolsize = RANDOM_FORTUNA_DEFPOOLSIZE; 166 #ifdef _KERNEL 167 fortuna_state.fs_lasttime = 0; 168 random_fortuna_o = SYSCTL_ADD_NODE(&random_clist, 169 SYSCTL_STATIC_CHILDREN(_kern_random), 170 OID_AUTO, "fortuna", CTLFLAG_RW, 0, 171 "Fortuna Parameters"); 172 SYSCTL_ADD_PROC(&random_clist, 173 SYSCTL_CHILDREN(random_fortuna_o), OID_AUTO, 174 "minpoolsize", CTLTYPE_UINT | CTLFLAG_RWTUN, 175 &fortuna_state.fs_minpoolsize, RANDOM_FORTUNA_DEFPOOLSIZE, 176 random_check_uint_fs_minpoolsize, "IU", 177 "Minimum pool size necessary to cause a reseed"); 178 KASSERT(fortuna_state.fs_minpoolsize > 0, ("random: Fortuna threshold must be > 0 at startup")); 179 #endif 180 181 /*- 182 * FS&K - InitializePRNG() 183 * - P_i = \epsilon 184 * - ReseedCNT = 0 185 */ 186 for (i = 0; i < RANDOM_FORTUNA_NPOOLS; i++) { 187 randomdev_hash_init(&fortuna_state.fs_pool[i].fsp_hash); 188 fortuna_state.fs_pool[i].fsp_length = 0; 189 } 190 fortuna_state.fs_reseedcount = 0; 191 /*- 192 * FS&K - InitializeGenerator() 193 * - C = 0 194 * - K = 0 195 */ 196 fortuna_state.fs_counter = UINT128_ZERO; 197 explicit_bzero(&fortuna_state.fs_key, sizeof(fortuna_state.fs_key)); 198 } 199 200 /* ARGSUSED */ 201 static void 202 random_fortuna_deinit_alg(void *unused __unused) 203 { 204 205 RANDOM_RESEED_DEINIT_LOCK(); 206 explicit_bzero(&fortuna_state, sizeof(fortuna_state)); 207 #ifdef _KERNEL 208 sysctl_ctx_free(&random_clist); 209 #endif 210 } 211 212 /*- 213 * FS&K - AddRandomEvent() 214 * Process a single stochastic event off the harvest queue 215 */ 216 static void 217 random_fortuna_process_event(struct harvest_event *event) 218 { 219 u_int pl; 220 221 RANDOM_RESEED_LOCK(); 222 /*- 223 * FS&K - P_i = P_i|<harvested stuff> 224 * Accumulate the event into the appropriate pool 225 * where each event carries the destination information. 226 * 227 * The hash_init() and hash_finish() calls are done in 228 * random_fortuna_pre_read(). 229 * 230 * We must be locked against pool state modification which can happen 231 * during accumulation/reseeding and reading/regating. 232 */ 233 pl = event->he_destination % RANDOM_FORTUNA_NPOOLS; 234 /* 235 * We ignore low entropy static/counter fields towards the end of the 236 * he_event structure in order to increase measurable entropy when 237 * conducting SP800-90B entropy analysis measurements of seed material 238 * fed into PRNG. 239 * -- wdf 240 */ 241 KASSERT(event->he_size <= sizeof(event->he_entropy), 242 ("%s: event->he_size: %hhu > sizeof(event->he_entropy): %zu\n", 243 __func__, event->he_size, sizeof(event->he_entropy))); 244 randomdev_hash_iterate(&fortuna_state.fs_pool[pl].fsp_hash, 245 &event->he_somecounter, sizeof(event->he_somecounter)); 246 randomdev_hash_iterate(&fortuna_state.fs_pool[pl].fsp_hash, 247 event->he_entropy, event->he_size); 248 249 /*- 250 * Don't wrap the length. This is a "saturating" add. 251 * XXX: FIX!!: We don't actually need lengths for anything but fs_pool[0], 252 * but it's been useful debugging to see them all. 253 */ 254 fortuna_state.fs_pool[pl].fsp_length = MIN(RANDOM_FORTUNA_MAXPOOLSIZE, 255 fortuna_state.fs_pool[pl].fsp_length + 256 sizeof(event->he_somecounter) + event->he_size); 257 explicit_bzero(event, sizeof(*event)); 258 RANDOM_RESEED_UNLOCK(); 259 } 260 261 /*- 262 * FS&K - Reseed() 263 * This introduces new key material into the output generator. 264 * Additionally it increments the output generator's counter 265 * variable C. When C > 0, the output generator is seeded and 266 * will deliver output. 267 * The entropy_data buffer passed is a very specific size; the 268 * product of RANDOM_FORTUNA_NPOOLS and RANDOM_KEYSIZE. 269 */ 270 static void 271 random_fortuna_reseed_internal(uint32_t *entropy_data, u_int blockcount) 272 { 273 struct randomdev_hash context; 274 uint8_t hash[RANDOM_KEYSIZE]; 275 const void *keymaterial; 276 size_t keysz; 277 bool seeded; 278 279 RANDOM_RESEED_ASSERT_LOCK_OWNED(); 280 281 seeded = random_fortuna_seeded_internal(); 282 if (seeded) { 283 randomdev_getkey(&fortuna_state.fs_key, &keymaterial, &keysz); 284 KASSERT(keysz == RANDOM_KEYSIZE, ("%s: key size %zu not %u", 285 __func__, keysz, (unsigned)RANDOM_KEYSIZE)); 286 } 287 288 /*- 289 * FS&K - K = Hd(K|s) where Hd(m) is H(H(0^512|m)) 290 * - C = C + 1 291 */ 292 randomdev_hash_init(&context); 293 randomdev_hash_iterate(&context, zero_region, RANDOM_ZERO_BLOCKSIZE); 294 if (seeded) 295 randomdev_hash_iterate(&context, keymaterial, keysz); 296 randomdev_hash_iterate(&context, entropy_data, RANDOM_KEYSIZE*blockcount); 297 randomdev_hash_finish(&context, hash); 298 randomdev_hash_init(&context); 299 randomdev_hash_iterate(&context, hash, RANDOM_KEYSIZE); 300 randomdev_hash_finish(&context, hash); 301 randomdev_encrypt_init(&fortuna_state.fs_key, hash); 302 explicit_bzero(hash, sizeof(hash)); 303 /* Unblock the device if this is the first time we are reseeding. */ 304 if (uint128_is_zero(fortuna_state.fs_counter)) 305 randomdev_unblock(); 306 uint128_increment(&fortuna_state.fs_counter); 307 } 308 309 /*- 310 * FS&K - GenerateBlocks() 311 * Generate a number of complete blocks of random output. 312 */ 313 static __inline void 314 random_fortuna_genblocks(uint8_t *buf, u_int blockcount) 315 { 316 317 RANDOM_RESEED_ASSERT_LOCK_OWNED(); 318 KASSERT(!uint128_is_zero(fortuna_state.fs_counter), ("FS&K: C != 0")); 319 320 /* 321 * Fills buf with RANDOM_BLOCKSIZE * blockcount bytes of keystream. 322 * Increments fs_counter as it goes. 323 */ 324 randomdev_keystream(&fortuna_state.fs_key, &fortuna_state.fs_counter, 325 buf, blockcount); 326 } 327 328 /*- 329 * FS&K - PseudoRandomData() 330 * This generates no more than 2^20 bytes of data, and cleans up its 331 * internal state when finished. It is assumed that a whole number of 332 * blocks are available for writing; any excess generated will be 333 * ignored. 334 */ 335 static __inline void 336 random_fortuna_genrandom(uint8_t *buf, u_int bytecount) 337 { 338 uint8_t temp[RANDOM_BLOCKSIZE * RANDOM_KEYS_PER_BLOCK]; 339 u_int blockcount; 340 341 RANDOM_RESEED_ASSERT_LOCK_OWNED(); 342 /*- 343 * FS&K - assert(n < 2^20 (== 1 MB) 344 * - r = first-n-bytes(GenerateBlocks(ceil(n/16))) 345 * - K = GenerateBlocks(2) 346 */ 347 KASSERT((bytecount <= RANDOM_FORTUNA_MAX_READ), ("invalid single read request to Fortuna of %d bytes", bytecount)); 348 blockcount = howmany(bytecount, RANDOM_BLOCKSIZE); 349 random_fortuna_genblocks(buf, blockcount); 350 random_fortuna_genblocks(temp, RANDOM_KEYS_PER_BLOCK); 351 randomdev_encrypt_init(&fortuna_state.fs_key, temp); 352 explicit_bzero(temp, sizeof(temp)); 353 } 354 355 /*- 356 * FS&K - RandomData() (Part 1) 357 * Used to return processed entropy from the PRNG. There is a pre_read 358 * required to be present (but it can be a stub) in order to allow 359 * specific actions at the begin of the read. 360 */ 361 void 362 random_fortuna_pre_read(void) 363 { 364 #ifdef _KERNEL 365 sbintime_t now; 366 #endif 367 struct randomdev_hash context; 368 uint32_t s[RANDOM_FORTUNA_NPOOLS*RANDOM_KEYSIZE_WORDS]; 369 uint8_t temp[RANDOM_KEYSIZE]; 370 u_int i; 371 372 KASSERT(fortuna_state.fs_minpoolsize > 0, ("random: Fortuna threshold must be > 0")); 373 RANDOM_RESEED_LOCK(); 374 #ifdef _KERNEL 375 /* FS&K - Use 'getsbinuptime()' to prevent reseed-spamming. */ 376 now = getsbinuptime(); 377 #endif 378 379 if (fortuna_state.fs_pool[0].fsp_length < fortuna_state.fs_minpoolsize 380 #ifdef _KERNEL 381 /* 382 * FS&K - Use 'getsbinuptime()' to prevent reseed-spamming, but do 383 * not block initial seeding (fs_lasttime == 0). 384 */ 385 || (__predict_true(fortuna_state.fs_lasttime != 0) && 386 now - fortuna_state.fs_lasttime <= SBT_1S/10) 387 #endif 388 ) { 389 RANDOM_RESEED_UNLOCK(); 390 return; 391 } 392 393 #ifdef _KERNEL 394 /* 395 * When set, pretend we do not have enough entropy to reseed yet. 396 */ 397 KFAIL_POINT_CODE(DEBUG_FP, random_fortuna_pre_read, { 398 if (RETURN_VALUE != 0) { 399 RANDOM_RESEED_UNLOCK(); 400 return; 401 } 402 }); 403 #endif 404 405 #ifdef _KERNEL 406 fortuna_state.fs_lasttime = now; 407 #endif 408 409 /* FS&K - ReseedCNT = ReseedCNT + 1 */ 410 fortuna_state.fs_reseedcount++; 411 /* s = \epsilon at start */ 412 for (i = 0; i < RANDOM_FORTUNA_NPOOLS; i++) { 413 /* FS&K - if Divides(ReseedCnt, 2^i) ... */ 414 if ((fortuna_state.fs_reseedcount % (1 << i)) == 0) { 415 /*- 416 * FS&K - temp = (P_i) 417 * - P_i = \epsilon 418 * - s = s|H(temp) 419 */ 420 randomdev_hash_finish(&fortuna_state.fs_pool[i].fsp_hash, temp); 421 randomdev_hash_init(&fortuna_state.fs_pool[i].fsp_hash); 422 fortuna_state.fs_pool[i].fsp_length = 0; 423 randomdev_hash_init(&context); 424 randomdev_hash_iterate(&context, temp, RANDOM_KEYSIZE); 425 randomdev_hash_finish(&context, s + i*RANDOM_KEYSIZE_WORDS); 426 } else 427 break; 428 } 429 #ifdef _KERNEL 430 SDT_PROBE2(random, fortuna, event_processor, debug, fortuna_state.fs_reseedcount, fortuna_state.fs_pool); 431 #endif 432 /* FS&K */ 433 random_fortuna_reseed_internal(s, i); 434 RANDOM_RESEED_UNLOCK(); 435 436 /* Clean up and secure */ 437 explicit_bzero(s, sizeof(s)); 438 explicit_bzero(temp, sizeof(temp)); 439 } 440 441 /*- 442 * FS&K - RandomData() (Part 2) 443 * Main read from Fortuna, continued. May be called multiple times after 444 * the random_fortuna_pre_read() above. 445 * The supplied buf MUST be a multiple of RANDOM_BLOCKSIZE in size. 446 * Lots of code presumes this for efficiency, both here and in other 447 * routines. You are NOT allowed to break this! 448 */ 449 void 450 random_fortuna_read(uint8_t *buf, u_int bytecount) 451 { 452 453 KASSERT((bytecount % RANDOM_BLOCKSIZE) == 0, ("%s(): bytecount (= %d) must be a multiple of %d", __func__, bytecount, RANDOM_BLOCKSIZE )); 454 RANDOM_RESEED_LOCK(); 455 random_fortuna_genrandom(buf, bytecount); 456 RANDOM_RESEED_UNLOCK(); 457 } 458 459 #ifdef _KERNEL 460 static bool block_seeded_status = false; 461 SYSCTL_BOOL(_kern_random, OID_AUTO, block_seeded_status, CTLFLAG_RWTUN, 462 &block_seeded_status, 0, 463 "If non-zero, pretend Fortuna is in an unseeded state. By setting " 464 "this as a tunable, boot can be tested as if the random device is " 465 "unavailable."); 466 #endif 467 468 static bool 469 random_fortuna_seeded_internal(void) 470 { 471 return (!uint128_is_zero(fortuna_state.fs_counter)); 472 } 473 474 static bool 475 random_fortuna_seeded(void) 476 { 477 478 #ifdef _KERNEL 479 if (block_seeded_status) 480 return (false); 481 #endif 482 483 if (__predict_true(random_fortuna_seeded_internal())) 484 return (true); 485 486 /* 487 * Maybe we have enough entropy in the zeroth pool but just haven't 488 * kicked the initial seed step. Do so now. 489 */ 490 random_fortuna_pre_read(); 491 492 return (random_fortuna_seeded_internal()); 493 } 494