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