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