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