1 /* $OpenBSD: rnd.c,v 1.195 2017/11/26 17:06:46 mikeb Exp $ */ 2 3 /* 4 * Copyright (c) 2011 Theo de Raadt. 5 * Copyright (c) 2008 Damien Miller. 6 * Copyright (c) 1996, 1997, 2000-2002 Michael Shalayeff. 7 * Copyright (c) 2013 Markus Friedl. 8 * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999. 9 * All rights reserved. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, and the entire permission notice in its entirety, 16 * including the disclaimer of warranties. 17 * 2. Redistributions in binary form must reproduce the above copyright 18 * notice, this list of conditions and the following disclaimer in the 19 * documentation and/or other materials provided with the distribution. 20 * 3. The name of the author may not be used to endorse or promote 21 * products derived from this software without specific prior 22 * written permission. 23 * 24 * ALTERNATIVELY, this product may be distributed under the terms of 25 * the GNU Public License, in which case the provisions of the GPL are 26 * required INSTEAD OF the above restrictions. (This clause is 27 * necessary due to a potential bad interaction between the GPL and 28 * the restrictions contained in a BSD-style copyright.) 29 * 30 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED 31 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 32 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 33 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, 34 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 35 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 36 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 37 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 38 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 39 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 40 * OF THE POSSIBILITY OF SUCH DAMAGE. 41 */ 42 43 /* 44 * Computers are very predictable devices. Hence it is extremely hard 45 * to produce truly random numbers on a computer --- as opposed to 46 * pseudo-random numbers, which can be easily generated by using an 47 * algorithm. Unfortunately, it is very easy for attackers to guess 48 * the sequence of pseudo-random number generators, and for some 49 * applications this is not acceptable. Instead, we must try to 50 * gather "environmental noise" from the computer's environment, which 51 * must be hard for outside attackers to observe and use to 52 * generate random numbers. In a Unix environment, this is best done 53 * from inside the kernel. 54 * 55 * Sources of randomness from the environment include inter-keyboard 56 * timings, inter-interrupt timings from some interrupts, and other 57 * events which are both (a) non-deterministic and (b) hard for an 58 * outside observer to measure. Randomness from these sources is 59 * added to the "rnd states" queue; this is used as much of the 60 * source material which is mixed on occasion using a CRC-like function 61 * into the "entropy pool". This is not cryptographically strong, but 62 * it is adequate assuming the randomness is not chosen maliciously, 63 * and it is very fast because the interrupt-time event is only to add 64 * a small random token to the "rnd states" queue. 65 * 66 * When random bytes are desired, they are obtained by pulling from 67 * the entropy pool and running a SHA512 hash. The SHA512 hash avoids 68 * exposing the internal state of the entropy pool. Even if it is 69 * possible to analyze SHA512 in some clever way, as long as the amount 70 * of data returned from the generator is less than the inherent 71 * entropy in the pool, the output data is totally unpredictable. For 72 * this reason, the routine decreases its internal estimate of how many 73 * bits of "true randomness" are contained in the entropy pool as it 74 * outputs random numbers. 75 * 76 * If this estimate goes to zero, the SHA512 hash will continue to generate 77 * output since there is no true risk because the SHA512 output is not 78 * exported outside this subsystem. It is next used as input to seed a 79 * ChaCha20 stream cipher, which is re-seeded from time to time. This 80 * design provides very high amounts of output data from a potentially 81 * small entropy base, at high enough speeds to encourage use of random 82 * numbers in nearly any situation. Before OpenBSD 5.5, the RC4 stream 83 * cipher (also known as ARC4) was used instead of ChaCha20. 84 * 85 * The output of this single ChaCha20 engine is then shared amongst many 86 * consumers in the kernel and userland via a few interfaces: 87 * arc4random_buf(), arc4random(), arc4random_uniform(), randomread() 88 * for the set of /dev/random nodes and the system call getentropy(), 89 * which provides seeds for process-context pseudorandom generators. 90 * 91 * Acknowledgements: 92 * ================= 93 * 94 * Ideas for constructing this random number generator were derived 95 * from Pretty Good Privacy's random number generator, and from private 96 * discussions with Phil Karn. Colin Plumb provided a faster random 97 * number generator, which speeds up the mixing function of the entropy 98 * pool, taken from PGPfone. Dale Worley has also contributed many 99 * useful ideas and suggestions to improve this driver. 100 * 101 * Any flaws in the design are solely my responsibility, and should 102 * not be attributed to the Phil, Colin, or any of the authors of PGP. 103 * 104 * Further background information on this topic may be obtained from 105 * RFC 1750, "Randomness Recommendations for Security", by Donald 106 * Eastlake, Steve Crocker, and Jeff Schiller. 107 * 108 * Using a RC4 stream cipher as 2nd stage after the MD5 (now SHA512) output 109 * is the result of work by David Mazieres. 110 */ 111 112 #include <sys/param.h> 113 #include <sys/systm.h> 114 #include <sys/disk.h> 115 #include <sys/event.h> 116 #include <sys/limits.h> 117 #include <sys/time.h> 118 #include <sys/ioctl.h> 119 #include <sys/malloc.h> 120 #include <sys/fcntl.h> 121 #include <sys/timeout.h> 122 #include <sys/mutex.h> 123 #include <sys/task.h> 124 #include <sys/msgbuf.h> 125 #include <sys/mount.h> 126 #include <sys/syscallargs.h> 127 128 #include <crypto/sha2.h> 129 130 #define KEYSTREAM_ONLY 131 #include <crypto/chacha_private.h> 132 133 #include <dev/rndvar.h> 134 135 #include <uvm/uvm_param.h> 136 #include <uvm/uvm_extern.h> 137 138 /* 139 * For the purposes of better mixing, we use the CRC-32 polynomial as 140 * well to make a twisted Generalized Feedback Shift Register 141 * 142 * (See M. Matsumoto & Y. Kurita, 1992. Twisted GFSR generators. ACM 143 * Transactions on Modeling and Computer Simulation 2(3):179-194. 144 * Also see M. Matsumoto & Y. Kurita, 1994. Twisted GFSR generators 145 * II. ACM Transactions on Modeling and Computer Simulation 4:254-266) 146 * 147 * Thanks to Colin Plumb for suggesting this. 148 * 149 * We have not analyzed the resultant polynomial to prove it primitive; 150 * in fact it almost certainly isn't. Nonetheless, the irreducible factors 151 * of a random large-degree polynomial over GF(2) are more than large enough 152 * that periodicity is not a concern. 153 * 154 * The input hash is much less sensitive than the output hash. All 155 * we want from it is to be a good non-cryptographic hash - 156 * i.e. to not produce collisions when fed "random" data of the sort 157 * we expect to see. As long as the pool state differs for different 158 * inputs, we have preserved the input entropy and done a good job. 159 * The fact that an intelligent attacker can construct inputs that 160 * will produce controlled alterations to the pool's state is not 161 * important because we don't consider such inputs to contribute any 162 * randomness. The only property we need with respect to them is that 163 * the attacker can't increase his/her knowledge of the pool's state. 164 * Since all additions are reversible (knowing the final state and the 165 * input, you can reconstruct the initial state), if an attacker has 166 * any uncertainty about the initial state, he/she can only shuffle 167 * that uncertainty about, but never cause any collisions (which would 168 * decrease the uncertainty). 169 * 170 * The chosen system lets the state of the pool be (essentially) the input 171 * modulo the generator polynomial. Now, for random primitive polynomials, 172 * this is a universal class of hash functions, meaning that the chance 173 * of a collision is limited by the attacker's knowledge of the generator 174 * polynomial, so if it is chosen at random, an attacker can never force 175 * a collision. Here, we use a fixed polynomial, but we *can* assume that 176 * ###--> it is unknown to the processes generating the input entropy. <-### 177 * Because of this important property, this is a good, collision-resistant 178 * hash; hash collisions will occur no more often than chance. 179 */ 180 181 /* 182 * Stirring polynomials over GF(2) for various pool sizes. Used in 183 * add_entropy_words() below. 184 * 185 * The polynomial terms are chosen to be evenly spaced (minimum RMS 186 * distance from evenly spaced; except for the last tap, which is 1 to 187 * get the twisting happening as fast as possible. 188 * 189 * The resultant polynomial is: 190 * 2^POOLWORDS + 2^POOL_TAP1 + 2^POOL_TAP2 + 2^POOL_TAP3 + 2^POOL_TAP4 + 1 191 */ 192 #define POOLWORDS 2048 193 #define POOLBYTES (POOLWORDS*4) 194 #define POOLMASK (POOLWORDS - 1) 195 #define POOL_TAP1 1638 196 #define POOL_TAP2 1231 197 #define POOL_TAP3 819 198 #define POOL_TAP4 411 199 200 /* 201 * Raw entropy collection from device drivers; at interrupt context or not. 202 * add_*_randomness() provide data which is put into the entropy queue. 203 */ 204 205 #define QEVLEN 128 /* must be a power of 2 */ 206 #define QEVSLOW (QEVLEN * 3 / 4) /* yet another 0.75 for 60-minutes hour /-; */ 207 208 #define KEYSZ 32 209 #define IVSZ 8 210 #define BLOCKSZ 64 211 #define RSBUFSZ (16*BLOCKSZ) 212 #define EBUFSIZE KEYSZ + IVSZ 213 214 struct rand_event { 215 u_int re_time; 216 u_int re_val; 217 } rnd_event_space[QEVLEN]; 218 219 u_int rnd_event_cons; 220 u_int rnd_event_prod; 221 222 struct mutex rnd_enqlck = MUTEX_INITIALIZER(IPL_HIGH); 223 struct mutex rnd_deqlck = MUTEX_INITIALIZER(IPL_HIGH); 224 225 struct timeout rnd_timeout; 226 227 static u_int32_t entropy_pool[POOLWORDS]; 228 u_int32_t entropy_pool0[POOLWORDS] __attribute__((section(".openbsd.randomdata"))); 229 u_int entropy_add_ptr; 230 u_char entropy_input_rotate; 231 232 void dequeue_randomness(void *); 233 void add_entropy_words(const u_int32_t *, u_int); 234 void extract_entropy(u_int8_t *) 235 __attribute__((__bounded__(__minbytes__,1,EBUFSIZE))); 236 237 int filt_randomread(struct knote *, long); 238 void filt_randomdetach(struct knote *); 239 int filt_randomwrite(struct knote *, long); 240 241 static void _rs_seed(u_char *, size_t); 242 static void _rs_clearseed(const void *p, size_t s); 243 244 struct filterops randomread_filtops = 245 { 1, NULL, filt_randomdetach, filt_randomread }; 246 struct filterops randomwrite_filtops = 247 { 1, NULL, filt_randomdetach, filt_randomwrite }; 248 249 static inline struct rand_event * 250 rnd_get(void) 251 { 252 u_int idx; 253 254 /* nothing to do if queue is empty */ 255 if (rnd_event_prod == rnd_event_cons) 256 return NULL; 257 258 if (rnd_event_prod - rnd_event_cons > QEVLEN) 259 rnd_event_cons = rnd_event_prod - QEVLEN; 260 idx = rnd_event_cons++; 261 return &rnd_event_space[idx & (QEVLEN - 1)]; 262 } 263 264 static inline struct rand_event * 265 rnd_put(void) 266 { 267 u_int idx = rnd_event_prod++; 268 269 /* allow wrapping. caller will mix it in. */ 270 return &rnd_event_space[idx & (QEVLEN - 1)]; 271 } 272 273 static inline u_int 274 rnd_qlen(void) 275 { 276 return rnd_event_prod - rnd_event_cons; 277 } 278 279 /* 280 * This function adds entropy to the entropy pool by using timing delays. 281 * 282 * The number "val" is also added to the pool - it should somehow describe 283 * the type of event which just happened. Currently the values of 0-255 284 * are for keyboard scan codes, 256 and upwards - for interrupts. 285 */ 286 void 287 enqueue_randomness(u_int state, u_int val) 288 { 289 struct rand_event *rep; 290 struct timespec ts; 291 u_int qlen; 292 293 #ifdef DIAGNOSTIC 294 if (state >= RND_SRC_NUM) 295 return; 296 #endif 297 298 if (timeout_initialized(&rnd_timeout)) 299 nanotime(&ts); 300 301 val += state << 13; 302 303 mtx_enter(&rnd_enqlck); 304 rep = rnd_put(); 305 rep->re_time += ts.tv_nsec ^ (ts.tv_sec << 20); 306 rep->re_val += val; 307 qlen = rnd_qlen(); 308 mtx_leave(&rnd_enqlck); 309 310 if (qlen > QEVSLOW/2 && timeout_initialized(&rnd_timeout) && 311 !timeout_pending(&rnd_timeout)) 312 timeout_add(&rnd_timeout, 1); 313 } 314 315 /* 316 * This function adds a byte into the entropy pool. It does not 317 * update the entropy estimate. The caller must do this if appropriate. 318 * 319 * The pool is stirred with a polynomial of degree POOLWORDS over GF(2); 320 * see POOL_TAP[1-4] above 321 * 322 * Rotate the input word by a changing number of bits, to help assure 323 * that all bits in the entropy get toggled. Otherwise, if the pool 324 * is consistently fed small numbers (such as keyboard scan codes) 325 * then the upper bits of the entropy pool will frequently remain 326 * untouched. 327 */ 328 void 329 add_entropy_words(const u_int32_t *buf, u_int n) 330 { 331 /* derived from IEEE 802.3 CRC-32 */ 332 static const u_int32_t twist_table[8] = { 333 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158, 334 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 335 }; 336 337 for (; n--; buf++) { 338 u_int32_t w = (*buf << entropy_input_rotate) | 339 (*buf >> ((32 - entropy_input_rotate) & 31)); 340 u_int i = entropy_add_ptr = 341 (entropy_add_ptr - 1) & POOLMASK; 342 /* 343 * Normally, we add 7 bits of rotation to the pool. 344 * At the beginning of the pool, add an extra 7 bits 345 * rotation, so that successive passes spread the 346 * input bits across the pool evenly. 347 */ 348 entropy_input_rotate = 349 (entropy_input_rotate + (i ? 7 : 14)) & 31; 350 351 /* XOR pool contents corresponding to polynomial terms */ 352 w ^= entropy_pool[(i + POOL_TAP1) & POOLMASK] ^ 353 entropy_pool[(i + POOL_TAP2) & POOLMASK] ^ 354 entropy_pool[(i + POOL_TAP3) & POOLMASK] ^ 355 entropy_pool[(i + POOL_TAP4) & POOLMASK] ^ 356 entropy_pool[(i + 1) & POOLMASK] ^ 357 entropy_pool[i]; /* + 2^POOLWORDS */ 358 359 entropy_pool[i] = (w >> 3) ^ twist_table[w & 7]; 360 } 361 } 362 363 /* 364 * Pulls entropy out of the queue and merges it into the pool 365 * with the CRC. 366 */ 367 /* ARGSUSED */ 368 void 369 dequeue_randomness(void *v) 370 { 371 struct rand_event *rep; 372 u_int32_t buf[2]; 373 374 if (timeout_initialized(&rnd_timeout)) 375 timeout_del(&rnd_timeout); 376 377 mtx_enter(&rnd_deqlck); 378 while ((rep = rnd_get())) { 379 buf[0] = rep->re_time; 380 buf[1] = rep->re_val; 381 mtx_leave(&rnd_deqlck); 382 add_entropy_words(buf, 2); 383 mtx_enter(&rnd_deqlck); 384 } 385 mtx_leave(&rnd_deqlck); 386 } 387 388 /* 389 * Grabs a chunk from the entropy_pool[] and slams it through SHA512 when 390 * requested. 391 */ 392 void 393 extract_entropy(u_int8_t *buf) 394 { 395 static u_int32_t extract_pool[POOLWORDS]; 396 u_char digest[SHA512_DIGEST_LENGTH]; 397 SHA2_CTX shactx; 398 399 #if SHA512_DIGEST_LENGTH < EBUFSIZE 400 #error "need more bigger hash output" 401 #endif 402 403 /* 404 * INTENTIONALLY not protected by any lock. Races during 405 * memcpy() result in acceptable input data; races during 406 * SHA512Update() would create nasty data dependencies. We 407 * do not rely on this as a benefit, but if it happens, cool. 408 */ 409 memcpy(extract_pool, entropy_pool, sizeof(extract_pool)); 410 411 /* Hash the pool to get the output */ 412 SHA512Init(&shactx); 413 SHA512Update(&shactx, (u_int8_t *)extract_pool, sizeof(extract_pool)); 414 SHA512Final(digest, &shactx); 415 416 /* Copy data to destination buffer */ 417 memcpy(buf, digest, EBUFSIZE); 418 419 /* Modify pool so next hash will produce different results */ 420 add_timer_randomness(EBUFSIZE); 421 dequeue_randomness(NULL); 422 423 /* Wipe data from memory */ 424 explicit_bzero(extract_pool, sizeof(extract_pool)); 425 explicit_bzero(digest, sizeof(digest)); 426 } 427 428 /* random keystream by ChaCha */ 429 430 void arc4_reinit(void *v); /* timeout to start reinit */ 431 void arc4_init(void *); /* actually do the reinit */ 432 433 struct mutex rndlock = MUTEX_INITIALIZER(IPL_HIGH); 434 struct timeout arc4_timeout; 435 struct task arc4_task = TASK_INITIALIZER(arc4_init, NULL); 436 437 static chacha_ctx rs; /* chacha context for random keystream */ 438 /* keystream blocks (also chacha seed from boot) */ 439 static u_char rs_buf[RSBUFSZ]; 440 u_char rs_buf0[RSBUFSZ] __attribute__((section(".openbsd.randomdata"))); 441 static size_t rs_have; /* valid bytes at end of rs_buf */ 442 static size_t rs_count; /* bytes till reseed */ 443 444 void 445 suspend_randomness(void) 446 { 447 struct timespec ts; 448 449 getnanotime(&ts); 450 add_true_randomness(ts.tv_sec); 451 add_true_randomness(ts.tv_nsec); 452 453 dequeue_randomness(NULL); 454 rs_count = 0; 455 arc4random_buf(entropy_pool, sizeof(entropy_pool)); 456 } 457 458 void 459 resume_randomness(char *buf, size_t buflen) 460 { 461 struct timespec ts; 462 463 if (buf && buflen) 464 _rs_seed(buf, buflen); 465 getnanotime(&ts); 466 add_true_randomness(ts.tv_sec); 467 add_true_randomness(ts.tv_nsec); 468 469 dequeue_randomness(NULL); 470 rs_count = 0; 471 } 472 473 static inline void _rs_rekey(u_char *dat, size_t datlen); 474 475 static inline void 476 _rs_init(u_char *buf, size_t n) 477 { 478 KASSERT(n >= KEYSZ + IVSZ); 479 chacha_keysetup(&rs, buf, KEYSZ * 8); 480 chacha_ivsetup(&rs, buf + KEYSZ, NULL); 481 } 482 483 static void 484 _rs_seed(u_char *buf, size_t n) 485 { 486 _rs_rekey(buf, n); 487 488 /* invalidate rs_buf */ 489 rs_have = 0; 490 memset(rs_buf, 0, RSBUFSZ); 491 492 rs_count = 1600000; 493 } 494 495 static void 496 _rs_stir(int do_lock) 497 { 498 struct timespec ts; 499 u_int8_t buf[EBUFSIZE], *p; 500 int i; 501 502 /* 503 * Use SHA512 PRNG data and a system timespec; early in the boot 504 * process this is the best we can do -- some architectures do 505 * not collect entropy very well during this time, but may have 506 * clock information which is better than nothing. 507 */ 508 extract_entropy(buf); 509 510 nanotime(&ts); 511 for (p = (u_int8_t *)&ts, i = 0; i < sizeof(ts); i++) 512 buf[i] ^= p[i]; 513 514 if (do_lock) 515 mtx_enter(&rndlock); 516 _rs_seed(buf, sizeof(buf)); 517 if (do_lock) 518 mtx_leave(&rndlock); 519 520 explicit_bzero(buf, sizeof(buf)); 521 } 522 523 static inline void 524 _rs_stir_if_needed(size_t len) 525 { 526 static int rs_initialized; 527 528 if (!rs_initialized) { 529 memcpy(entropy_pool, entropy_pool0, sizeof entropy_pool); 530 memcpy(rs_buf, rs_buf0, sizeof rs_buf); 531 /* seeds cannot be cleaned yet, random_start() will do so */ 532 _rs_init(rs_buf, KEYSZ + IVSZ); 533 rs_count = 1024 * 1024 * 1024; /* until main() runs */ 534 rs_initialized = 1; 535 } else if (rs_count <= len) 536 _rs_stir(0); 537 else 538 rs_count -= len; 539 } 540 541 static void 542 _rs_clearseed(const void *p, size_t s) 543 { 544 struct kmem_dyn_mode kd_avoidalias; 545 vaddr_t va = trunc_page((vaddr_t)p); 546 vsize_t off = (vaddr_t)p - va; 547 vsize_t len; 548 vaddr_t rwva; 549 paddr_t pa; 550 551 while (s > 0) { 552 pmap_extract(pmap_kernel(), va, &pa); 553 554 memset(&kd_avoidalias, 0, sizeof kd_avoidalias); 555 kd_avoidalias.kd_prefer = pa; 556 kd_avoidalias.kd_waitok = 1; 557 rwva = (vaddr_t)km_alloc(PAGE_SIZE, &kv_any, &kp_none, 558 &kd_avoidalias); 559 if (!rwva) 560 panic("_rs_clearseed"); 561 562 pmap_kenter_pa(rwva, pa, PROT_READ | PROT_WRITE); 563 pmap_update(pmap_kernel()); 564 565 len = MIN(s, PAGE_SIZE - off); 566 explicit_bzero((void *)(rwva + off), len); 567 568 pmap_kremove(rwva, PAGE_SIZE); 569 km_free((void *)rwva, PAGE_SIZE, &kv_any, &kp_none); 570 571 va += PAGE_SIZE; 572 s -= len; 573 off = 0; 574 } 575 } 576 577 static inline void 578 _rs_rekey(u_char *dat, size_t datlen) 579 { 580 #ifndef KEYSTREAM_ONLY 581 memset(rs_buf, 0, RSBUFSZ); 582 #endif 583 /* fill rs_buf with the keystream */ 584 chacha_encrypt_bytes(&rs, rs_buf, rs_buf, RSBUFSZ); 585 /* mix in optional user provided data */ 586 if (dat) { 587 size_t i, m; 588 589 m = MIN(datlen, KEYSZ + IVSZ); 590 for (i = 0; i < m; i++) 591 rs_buf[i] ^= dat[i]; 592 } 593 /* immediately reinit for backtracking resistance */ 594 _rs_init(rs_buf, KEYSZ + IVSZ); 595 memset(rs_buf, 0, KEYSZ + IVSZ); 596 rs_have = RSBUFSZ - KEYSZ - IVSZ; 597 } 598 599 static inline void 600 _rs_random_buf(void *_buf, size_t n) 601 { 602 u_char *buf = (u_char *)_buf; 603 size_t m; 604 605 _rs_stir_if_needed(n); 606 while (n > 0) { 607 if (rs_have > 0) { 608 m = MIN(n, rs_have); 609 memcpy(buf, rs_buf + RSBUFSZ - rs_have, m); 610 memset(rs_buf + RSBUFSZ - rs_have, 0, m); 611 buf += m; 612 n -= m; 613 rs_have -= m; 614 } 615 if (rs_have == 0) 616 _rs_rekey(NULL, 0); 617 } 618 } 619 620 static inline void 621 _rs_random_u32(u_int32_t *val) 622 { 623 _rs_stir_if_needed(sizeof(*val)); 624 if (rs_have < sizeof(*val)) 625 _rs_rekey(NULL, 0); 626 memcpy(val, rs_buf + RSBUFSZ - rs_have, sizeof(*val)); 627 memset(rs_buf + RSBUFSZ - rs_have, 0, sizeof(*val)); 628 rs_have -= sizeof(*val); 629 } 630 631 /* Return one word of randomness from a ChaCha20 generator */ 632 u_int32_t 633 arc4random(void) 634 { 635 u_int32_t ret; 636 637 mtx_enter(&rndlock); 638 _rs_random_u32(&ret); 639 mtx_leave(&rndlock); 640 return ret; 641 } 642 643 /* 644 * Fill a buffer of arbitrary length with ChaCha20-derived randomness. 645 */ 646 void 647 arc4random_buf(void *buf, size_t n) 648 { 649 mtx_enter(&rndlock); 650 _rs_random_buf(buf, n); 651 mtx_leave(&rndlock); 652 } 653 654 /* 655 * Calculate a uniformly distributed random number less than upper_bound 656 * avoiding "modulo bias". 657 * 658 * Uniformity is achieved by generating new random numbers until the one 659 * returned is outside the range [0, 2**32 % upper_bound). This 660 * guarantees the selected random number will be inside 661 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 662 * after reduction modulo upper_bound. 663 */ 664 u_int32_t 665 arc4random_uniform(u_int32_t upper_bound) 666 { 667 u_int32_t r, min; 668 669 if (upper_bound < 2) 670 return 0; 671 672 /* 2**32 % x == (2**32 - x) % x */ 673 min = -upper_bound % upper_bound; 674 675 /* 676 * This could theoretically loop forever but each retry has 677 * p > 0.5 (worst case, usually far better) of selecting a 678 * number inside the range we need, so it should rarely need 679 * to re-roll. 680 */ 681 for (;;) { 682 r = arc4random(); 683 if (r >= min) 684 break; 685 } 686 687 return r % upper_bound; 688 } 689 690 /* ARGSUSED */ 691 void 692 arc4_init(void *null) 693 { 694 _rs_stir(1); 695 } 696 697 /* 698 * Called by timeout to mark arc4 for stirring, 699 */ 700 void 701 arc4_reinit(void *v) 702 { 703 task_add(systq, &arc4_task); 704 /* 10 minutes, per dm@'s suggestion */ 705 timeout_add_sec(&arc4_timeout, 10 * 60); 706 } 707 708 /* 709 * Start periodic services inside the random subsystem, which pull 710 * entropy forward, hash it, and re-seed the random stream as needed. 711 */ 712 void 713 random_start(void) 714 { 715 #if !defined(NO_PROPOLICE) 716 extern long __guard_local; 717 718 if (__guard_local == 0) 719 printf("warning: no entropy supplied by boot loader\n"); 720 #endif 721 722 _rs_clearseed(entropy_pool0, sizeof entropy_pool0); 723 _rs_clearseed(rs_buf0, sizeof rs_buf0); 724 725 /* Message buffer may contain data from previous boot */ 726 if (msgbufp->msg_magic == MSG_MAGIC) 727 add_entropy_words((u_int32_t *)msgbufp->msg_bufc, 728 msgbufp->msg_bufs / sizeof(u_int32_t)); 729 730 dequeue_randomness(NULL); 731 arc4_init(NULL); 732 timeout_set(&arc4_timeout, arc4_reinit, NULL); 733 arc4_reinit(NULL); 734 timeout_set(&rnd_timeout, dequeue_randomness, NULL); 735 } 736 737 int 738 randomopen(dev_t dev, int flag, int mode, struct proc *p) 739 { 740 return 0; 741 } 742 743 int 744 randomclose(dev_t dev, int flag, int mode, struct proc *p) 745 { 746 return 0; 747 } 748 749 /* 750 * Maximum number of bytes to serve directly from the main ChaCha 751 * pool. Larger requests are served from a discrete ChaCha instance keyed 752 * from the main pool. 753 */ 754 #define ARC4_MAIN_MAX_BYTES 2048 755 756 int 757 randomread(dev_t dev, struct uio *uio, int ioflag) 758 { 759 u_char lbuf[KEYSZ+IVSZ]; 760 chacha_ctx lctx; 761 size_t total = uio->uio_resid; 762 u_char *buf; 763 int myctx = 0, ret = 0; 764 765 if (uio->uio_resid == 0) 766 return 0; 767 768 buf = malloc(POOLBYTES, M_TEMP, M_WAITOK); 769 if (total > ARC4_MAIN_MAX_BYTES) { 770 arc4random_buf(lbuf, sizeof(lbuf)); 771 chacha_keysetup(&lctx, lbuf, KEYSZ * 8); 772 chacha_ivsetup(&lctx, lbuf + KEYSZ, NULL); 773 explicit_bzero(lbuf, sizeof(lbuf)); 774 myctx = 1; 775 } 776 777 while (ret == 0 && uio->uio_resid > 0) { 778 size_t n = ulmin(POOLBYTES, uio->uio_resid); 779 780 if (myctx) { 781 #ifndef KEYSTREAM_ONLY 782 memset(buf, 0, n); 783 #endif 784 chacha_encrypt_bytes(&lctx, buf, buf, n); 785 } else 786 arc4random_buf(buf, n); 787 ret = uiomove(buf, n, uio); 788 if (ret == 0 && uio->uio_resid > 0) 789 yield(); 790 } 791 if (myctx) 792 explicit_bzero(&lctx, sizeof(lctx)); 793 explicit_bzero(buf, POOLBYTES); 794 free(buf, M_TEMP, POOLBYTES); 795 return ret; 796 } 797 798 int 799 randomwrite(dev_t dev, struct uio *uio, int flags) 800 { 801 int ret = 0, newdata = 0; 802 u_int32_t *buf; 803 804 if (uio->uio_resid == 0) 805 return 0; 806 807 buf = malloc(POOLBYTES, M_TEMP, M_WAITOK); 808 809 while (ret == 0 && uio->uio_resid > 0) { 810 size_t n = ulmin(POOLBYTES, uio->uio_resid); 811 812 ret = uiomove(buf, n, uio); 813 if (ret != 0) 814 break; 815 while (n % sizeof(u_int32_t)) 816 ((u_int8_t *)buf)[n++] = 0; 817 add_entropy_words(buf, n / 4); 818 if (uio->uio_resid > 0) 819 yield(); 820 newdata = 1; 821 } 822 823 if (newdata) 824 arc4_init(NULL); 825 826 explicit_bzero(buf, POOLBYTES); 827 free(buf, M_TEMP, POOLBYTES); 828 return ret; 829 } 830 831 int 832 randomkqfilter(dev_t dev, struct knote *kn) 833 { 834 switch (kn->kn_filter) { 835 case EVFILT_READ: 836 kn->kn_fop = &randomread_filtops; 837 break; 838 case EVFILT_WRITE: 839 kn->kn_fop = &randomwrite_filtops; 840 break; 841 default: 842 return (EINVAL); 843 } 844 845 return (0); 846 } 847 848 void 849 filt_randomdetach(struct knote *kn) 850 { 851 } 852 853 int 854 filt_randomread(struct knote *kn, long hint) 855 { 856 kn->kn_data = ARC4_MAIN_MAX_BYTES; 857 return (1); 858 } 859 860 int 861 filt_randomwrite(struct knote *kn, long hint) 862 { 863 kn->kn_data = POOLBYTES; 864 return (1); 865 } 866 867 int 868 randomioctl(dev_t dev, u_long cmd, caddr_t data, int flag, struct proc *p) 869 { 870 switch (cmd) { 871 case FIOASYNC: 872 /* No async flag in softc so this is a no-op. */ 873 break; 874 case FIONBIO: 875 /* Handled in the upper FS layer. */ 876 break; 877 default: 878 return ENOTTY; 879 } 880 return 0; 881 } 882 883 int 884 sys_getentropy(struct proc *p, void *v, register_t *retval) 885 { 886 struct sys_getentropy_args /* { 887 syscallarg(void *) buf; 888 syscallarg(size_t) nbyte; 889 } */ *uap = v; 890 char buf[256]; 891 int error; 892 893 if (SCARG(uap, nbyte) > sizeof(buf)) 894 return (EIO); 895 arc4random_buf(buf, SCARG(uap, nbyte)); 896 if ((error = copyout(buf, SCARG(uap, buf), SCARG(uap, nbyte))) != 0) 897 return (error); 898 explicit_bzero(buf, sizeof(buf)); 899 retval[0] = 0; 900 return (0); 901 } 902