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/limits.h> 39 40 #ifdef _KERNEL 41 #include <sys/param.h> 42 #include <sys/kernel.h> 43 #include <sys/lock.h> 44 #include <sys/malloc.h> 45 #include <sys/mutex.h> 46 #include <sys/random.h> 47 #include <sys/sdt.h> 48 #include <sys/sysctl.h> 49 #include <sys/systm.h> 50 51 #include <machine/cpu.h> 52 53 #include <crypto/rijndael/rijndael-api-fst.h> 54 #include <crypto/sha2/sha256.h> 55 56 #include <dev/random/hash.h> 57 #include <dev/random/randomdev.h> 58 #include <dev/random/random_harvestq.h> 59 #include <dev/random/uint128.h> 60 #include <dev/random/fortuna.h> 61 #else /* !_KERNEL */ 62 #include <sys/param.h> 63 #include <inttypes.h> 64 #include <stdbool.h> 65 #include <stdio.h> 66 #include <stdlib.h> 67 #include <string.h> 68 #include <threads.h> 69 70 #include "unit_test.h" 71 72 #include <crypto/rijndael/rijndael-api-fst.h> 73 #include <crypto/sha2/sha256.h> 74 75 #include <dev/random/hash.h> 76 #include <dev/random/randomdev.h> 77 #include <dev/random/uint128.h> 78 #include <dev/random/fortuna.h> 79 #endif /* _KERNEL */ 80 81 /* Defined in FS&K */ 82 #define RANDOM_FORTUNA_NPOOLS 32 /* The number of accumulation pools */ 83 #define RANDOM_FORTUNA_DEFPOOLSIZE 64 /* The default pool size/length for a (re)seed */ 84 #define RANDOM_FORTUNA_MAX_READ (1 << 20) /* Max bytes in a single read */ 85 86 /* 87 * The allowable range of RANDOM_FORTUNA_DEFPOOLSIZE. The default value is above. 88 * Making RANDOM_FORTUNA_DEFPOOLSIZE too large will mean a long time between reseeds, 89 * and too small may compromise initial security but get faster reseeds. 90 */ 91 #define RANDOM_FORTUNA_MINPOOLSIZE 16 92 #define RANDOM_FORTUNA_MAXPOOLSIZE INT_MAX 93 CTASSERT(RANDOM_FORTUNA_MINPOOLSIZE <= RANDOM_FORTUNA_DEFPOOLSIZE); 94 CTASSERT(RANDOM_FORTUNA_DEFPOOLSIZE <= RANDOM_FORTUNA_MAXPOOLSIZE); 95 96 /* This algorithm (and code) presumes that RANDOM_KEYSIZE is twice as large as RANDOM_BLOCKSIZE */ 97 CTASSERT(RANDOM_BLOCKSIZE == sizeof(uint128_t)); 98 CTASSERT(RANDOM_KEYSIZE == 2*RANDOM_BLOCKSIZE); 99 100 /* Probes for dtrace(1) */ 101 #ifdef _KERNEL 102 SDT_PROVIDER_DECLARE(random); 103 SDT_PROVIDER_DEFINE(random); 104 SDT_PROBE_DEFINE2(random, fortuna, event_processor, debug, "u_int", "struct fs_pool *"); 105 #endif /* _KERNEL */ 106 107 /* 108 * This is the beastie that needs protecting. It contains all of the 109 * state that we are excited about. Exactly one is instantiated. 110 */ 111 static struct fortuna_state { 112 struct fs_pool { /* P_i */ 113 u_int fsp_length; /* Only the first one is used by Fortuna */ 114 struct randomdev_hash fsp_hash; 115 } fs_pool[RANDOM_FORTUNA_NPOOLS]; 116 u_int fs_reseedcount; /* ReseedCnt */ 117 uint128_t fs_counter; /* C */ 118 struct randomdev_key fs_key; /* K */ 119 u_int fs_minpoolsize; /* Extras */ 120 /* Extras for the OS */ 121 #ifdef _KERNEL 122 /* For use when 'pacing' the reseeds */ 123 sbintime_t fs_lasttime; 124 #endif 125 /* Reseed lock */ 126 mtx_t fs_mtx; 127 } fortuna_state; 128 129 #ifdef _KERNEL 130 static struct sysctl_ctx_list random_clist; 131 RANDOM_CHECK_UINT(fs_minpoolsize, RANDOM_FORTUNA_MINPOOLSIZE, RANDOM_FORTUNA_MAXPOOLSIZE); 132 #else 133 static uint8_t zero_region[RANDOM_ZERO_BLOCKSIZE]; 134 #endif 135 136 static void random_fortuna_pre_read(void); 137 static void random_fortuna_read(uint8_t *, u_int); 138 static bool random_fortuna_seeded(void); 139 static void random_fortuna_process_event(struct harvest_event *); 140 static void random_fortuna_init_alg(void *); 141 static void random_fortuna_deinit_alg(void *); 142 143 static void random_fortuna_reseed_internal(uint32_t *entropy_data, u_int blockcount); 144 145 struct random_algorithm random_alg_context = { 146 .ra_ident = "Fortuna", 147 .ra_init_alg = random_fortuna_init_alg, 148 .ra_deinit_alg = random_fortuna_deinit_alg, 149 .ra_pre_read = random_fortuna_pre_read, 150 .ra_read = random_fortuna_read, 151 .ra_seeded = random_fortuna_seeded, 152 .ra_event_processor = random_fortuna_process_event, 153 .ra_poolcount = RANDOM_FORTUNA_NPOOLS, 154 }; 155 156 /* ARGSUSED */ 157 static void 158 random_fortuna_init_alg(void *unused __unused) 159 { 160 int i; 161 #ifdef _KERNEL 162 struct sysctl_oid *random_fortuna_o; 163 #endif 164 165 RANDOM_RESEED_INIT_LOCK(); 166 /* 167 * Fortuna parameters. Do not adjust these unless you have 168 * have a very good clue about what they do! 169 */ 170 fortuna_state.fs_minpoolsize = RANDOM_FORTUNA_DEFPOOLSIZE; 171 #ifdef _KERNEL 172 fortuna_state.fs_lasttime = 0; 173 random_fortuna_o = SYSCTL_ADD_NODE(&random_clist, 174 SYSCTL_STATIC_CHILDREN(_kern_random), 175 OID_AUTO, "fortuna", CTLFLAG_RW, 0, 176 "Fortuna Parameters"); 177 SYSCTL_ADD_PROC(&random_clist, 178 SYSCTL_CHILDREN(random_fortuna_o), OID_AUTO, 179 "minpoolsize", CTLTYPE_UINT | CTLFLAG_RWTUN, 180 &fortuna_state.fs_minpoolsize, RANDOM_FORTUNA_DEFPOOLSIZE, 181 random_check_uint_fs_minpoolsize, "IU", 182 "Minimum pool size necessary to cause a reseed"); 183 KASSERT(fortuna_state.fs_minpoolsize > 0, ("random: Fortuna threshold must be > 0 at startup")); 184 #endif 185 186 /*- 187 * FS&K - InitializePRNG() 188 * - P_i = \epsilon 189 * - ReseedCNT = 0 190 */ 191 for (i = 0; i < RANDOM_FORTUNA_NPOOLS; i++) { 192 randomdev_hash_init(&fortuna_state.fs_pool[i].fsp_hash); 193 fortuna_state.fs_pool[i].fsp_length = 0; 194 } 195 fortuna_state.fs_reseedcount = 0; 196 /*- 197 * FS&K - InitializeGenerator() 198 * - C = 0 199 * - K = 0 200 */ 201 fortuna_state.fs_counter = UINT128_ZERO; 202 explicit_bzero(&fortuna_state.fs_key, sizeof(fortuna_state.fs_key)); 203 } 204 205 /* ARGSUSED */ 206 static void 207 random_fortuna_deinit_alg(void *unused __unused) 208 { 209 210 RANDOM_RESEED_DEINIT_LOCK(); 211 explicit_bzero(&fortuna_state, sizeof(fortuna_state)); 212 #ifdef _KERNEL 213 sysctl_ctx_free(&random_clist); 214 #endif 215 } 216 217 /*- 218 * FS&K - AddRandomEvent() 219 * Process a single stochastic event off the harvest queue 220 */ 221 static void 222 random_fortuna_process_event(struct harvest_event *event) 223 { 224 u_int pl; 225 226 RANDOM_RESEED_LOCK(); 227 /*- 228 * FS&K - P_i = P_i|<harvested stuff> 229 * Accumulate the event into the appropriate pool 230 * where each event carries the destination information. 231 * 232 * The hash_init() and hash_finish() calls are done in 233 * random_fortuna_pre_read(). 234 * 235 * We must be locked against pool state modification which can happen 236 * during accumulation/reseeding and reading/regating. 237 */ 238 pl = event->he_destination % RANDOM_FORTUNA_NPOOLS; 239 /* 240 * We ignore low entropy static/counter fields towards the end of the 241 * he_event structure in order to increase measurable entropy when 242 * conducting SP800-90B entropy analysis measurements of seed material 243 * fed into PRNG. 244 * -- wdf 245 */ 246 KASSERT(event->he_size <= sizeof(event->he_entropy), 247 ("%s: event->he_size: %hhu > sizeof(event->he_entropy): %zu\n", 248 __func__, event->he_size, sizeof(event->he_entropy))); 249 randomdev_hash_iterate(&fortuna_state.fs_pool[pl].fsp_hash, 250 &event->he_somecounter, sizeof(event->he_somecounter)); 251 randomdev_hash_iterate(&fortuna_state.fs_pool[pl].fsp_hash, 252 event->he_entropy, event->he_size); 253 254 /*- 255 * Don't wrap the length. This is a "saturating" add. 256 * XXX: FIX!!: We don't actually need lengths for anything but fs_pool[0], 257 * but it's been useful debugging to see them all. 258 */ 259 fortuna_state.fs_pool[pl].fsp_length = MIN(RANDOM_FORTUNA_MAXPOOLSIZE, 260 fortuna_state.fs_pool[pl].fsp_length + 261 sizeof(event->he_somecounter) + event->he_size); 262 explicit_bzero(event, sizeof(*event)); 263 RANDOM_RESEED_UNLOCK(); 264 } 265 266 /*- 267 * FS&K - Reseed() 268 * This introduces new key material into the output generator. 269 * Additionally it increments the output generator's counter 270 * variable C. When C > 0, the output generator is seeded and 271 * will deliver output. 272 * The entropy_data buffer passed is a very specific size; the 273 * product of RANDOM_FORTUNA_NPOOLS and RANDOM_KEYSIZE. 274 */ 275 static void 276 random_fortuna_reseed_internal(uint32_t *entropy_data, u_int blockcount) 277 { 278 struct randomdev_hash context; 279 uint8_t hash[RANDOM_KEYSIZE]; 280 281 RANDOM_RESEED_ASSERT_LOCK_OWNED(); 282 /*- 283 * FS&K - K = Hd(K|s) where Hd(m) is H(H(0^512|m)) 284 * - C = C + 1 285 */ 286 randomdev_hash_init(&context); 287 randomdev_hash_iterate(&context, zero_region, RANDOM_ZERO_BLOCKSIZE); 288 randomdev_hash_iterate(&context, &fortuna_state.fs_key, sizeof(fortuna_state.fs_key)); 289 randomdev_hash_iterate(&context, entropy_data, RANDOM_KEYSIZE*blockcount); 290 randomdev_hash_finish(&context, hash); 291 randomdev_hash_init(&context); 292 randomdev_hash_iterate(&context, hash, RANDOM_KEYSIZE); 293 randomdev_hash_finish(&context, hash); 294 randomdev_encrypt_init(&fortuna_state.fs_key, hash); 295 explicit_bzero(hash, sizeof(hash)); 296 /* Unblock the device if this is the first time we are reseeding. */ 297 if (uint128_is_zero(fortuna_state.fs_counter)) 298 randomdev_unblock(); 299 uint128_increment(&fortuna_state.fs_counter); 300 } 301 302 /*- 303 * FS&K - GenerateBlocks() 304 * Generate a number of complete blocks of random output. 305 */ 306 static __inline void 307 random_fortuna_genblocks(uint8_t *buf, u_int blockcount) 308 { 309 u_int i; 310 311 RANDOM_RESEED_ASSERT_LOCK_OWNED(); 312 for (i = 0; i < blockcount; i++) { 313 /*- 314 * FS&K - r = r|E(K,C) 315 * - C = C + 1 316 */ 317 randomdev_encrypt(&fortuna_state.fs_key, &fortuna_state.fs_counter, buf, RANDOM_BLOCKSIZE); 318 buf += RANDOM_BLOCKSIZE; 319 uint128_increment(&fortuna_state.fs_counter); 320 } 321 } 322 323 /*- 324 * FS&K - PseudoRandomData() 325 * This generates no more than 2^20 bytes of data, and cleans up its 326 * internal state when finished. It is assumed that a whole number of 327 * blocks are available for writing; any excess generated will be 328 * ignored. 329 */ 330 static __inline void 331 random_fortuna_genrandom(uint8_t *buf, u_int bytecount) 332 { 333 static uint8_t temp[RANDOM_BLOCKSIZE*(RANDOM_KEYS_PER_BLOCK)]; 334 u_int blockcount; 335 336 RANDOM_RESEED_ASSERT_LOCK_OWNED(); 337 /*- 338 * FS&K - assert(n < 2^20 (== 1 MB) 339 * - r = first-n-bytes(GenerateBlocks(ceil(n/16))) 340 * - K = GenerateBlocks(2) 341 */ 342 KASSERT((bytecount <= RANDOM_FORTUNA_MAX_READ), ("invalid single read request to Fortuna of %d bytes", bytecount)); 343 blockcount = howmany(bytecount, RANDOM_BLOCKSIZE); 344 random_fortuna_genblocks(buf, blockcount); 345 random_fortuna_genblocks(temp, RANDOM_KEYS_PER_BLOCK); 346 randomdev_encrypt_init(&fortuna_state.fs_key, temp); 347 explicit_bzero(temp, sizeof(temp)); 348 } 349 350 /*- 351 * FS&K - RandomData() (Part 1) 352 * Used to return processed entropy from the PRNG. There is a pre_read 353 * required to be present (but it can be a stub) in order to allow 354 * specific actions at the begin of the read. 355 */ 356 void 357 random_fortuna_pre_read(void) 358 { 359 #ifdef _KERNEL 360 sbintime_t now; 361 #endif 362 struct randomdev_hash context; 363 uint32_t s[RANDOM_FORTUNA_NPOOLS*RANDOM_KEYSIZE_WORDS]; 364 uint8_t temp[RANDOM_KEYSIZE]; 365 u_int i; 366 367 KASSERT(fortuna_state.fs_minpoolsize > 0, ("random: Fortuna threshold must be > 0")); 368 #ifdef _KERNEL 369 /* FS&K - Use 'getsbinuptime()' to prevent reseed-spamming. */ 370 now = getsbinuptime(); 371 #endif 372 RANDOM_RESEED_LOCK(); 373 374 if (fortuna_state.fs_pool[0].fsp_length >= fortuna_state.fs_minpoolsize 375 #ifdef _KERNEL 376 /* FS&K - Use 'getsbinuptime()' to prevent reseed-spamming. */ 377 && (now - fortuna_state.fs_lasttime > SBT_1S/10) 378 #endif 379 ) { 380 #ifdef _KERNEL 381 fortuna_state.fs_lasttime = now; 382 #endif 383 384 /* FS&K - ReseedCNT = ReseedCNT + 1 */ 385 fortuna_state.fs_reseedcount++; 386 /* s = \epsilon at start */ 387 for (i = 0; i < RANDOM_FORTUNA_NPOOLS; i++) { 388 /* FS&K - if Divides(ReseedCnt, 2^i) ... */ 389 if ((fortuna_state.fs_reseedcount % (1 << i)) == 0) { 390 /*- 391 * FS&K - temp = (P_i) 392 * - P_i = \epsilon 393 * - s = s|H(temp) 394 */ 395 randomdev_hash_finish(&fortuna_state.fs_pool[i].fsp_hash, temp); 396 randomdev_hash_init(&fortuna_state.fs_pool[i].fsp_hash); 397 fortuna_state.fs_pool[i].fsp_length = 0; 398 randomdev_hash_init(&context); 399 randomdev_hash_iterate(&context, temp, RANDOM_KEYSIZE); 400 randomdev_hash_finish(&context, s + i*RANDOM_KEYSIZE_WORDS); 401 } else 402 break; 403 } 404 #ifdef _KERNEL 405 SDT_PROBE2(random, fortuna, event_processor, debug, fortuna_state.fs_reseedcount, fortuna_state.fs_pool); 406 #endif 407 /* FS&K */ 408 random_fortuna_reseed_internal(s, i < RANDOM_FORTUNA_NPOOLS ? i + 1 : RANDOM_FORTUNA_NPOOLS); 409 /* Clean up and secure */ 410 explicit_bzero(s, sizeof(s)); 411 explicit_bzero(temp, sizeof(temp)); 412 explicit_bzero(&context, sizeof(context)); 413 } 414 RANDOM_RESEED_UNLOCK(); 415 } 416 417 /*- 418 * FS&K - RandomData() (Part 2) 419 * Main read from Fortuna, continued. May be called multiple times after 420 * the random_fortuna_pre_read() above. 421 * The supplied buf MUST be a multiple of RANDOM_BLOCKSIZE in size. 422 * Lots of code presumes this for efficiency, both here and in other 423 * routines. You are NOT allowed to break this! 424 */ 425 void 426 random_fortuna_read(uint8_t *buf, u_int bytecount) 427 { 428 429 KASSERT((bytecount % RANDOM_BLOCKSIZE) == 0, ("%s(): bytecount (= %d) must be a multiple of %d", __func__, bytecount, RANDOM_BLOCKSIZE )); 430 RANDOM_RESEED_LOCK(); 431 random_fortuna_genrandom(buf, bytecount); 432 RANDOM_RESEED_UNLOCK(); 433 } 434 435 bool 436 random_fortuna_seeded(void) 437 { 438 439 return (!uint128_is_zero(fortuna_state.fs_counter)); 440 } 441