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