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