1 /* $OpenBSD: rnd.c,v 1.203 2020/03/02 22:27:50 deraadt 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 * enqueue_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 const struct filterops randomread_filtops = { 245 .f_flags = FILTEROP_ISFD, 246 .f_attach = NULL, 247 .f_detach = filt_randomdetach, 248 .f_event = filt_randomread, 249 }; 250 251 const struct filterops randomwrite_filtops = { 252 .f_flags = FILTEROP_ISFD, 253 .f_attach = NULL, 254 .f_detach = filt_randomdetach, 255 .f_event = filt_randomwrite, 256 }; 257 258 static inline struct rand_event * 259 rnd_get(void) 260 { 261 u_int idx; 262 263 /* nothing to do if queue is empty */ 264 if (rnd_event_prod == rnd_event_cons) 265 return NULL; 266 267 if (rnd_event_prod - rnd_event_cons > QEVLEN) 268 rnd_event_cons = rnd_event_prod - QEVLEN; 269 idx = rnd_event_cons++; 270 return &rnd_event_space[idx & (QEVLEN - 1)]; 271 } 272 273 static inline struct rand_event * 274 rnd_put(void) 275 { 276 u_int idx = rnd_event_prod++; 277 278 /* allow wrapping. caller will mix it in. */ 279 return &rnd_event_space[idx & (QEVLEN - 1)]; 280 } 281 282 static inline u_int 283 rnd_qlen(void) 284 { 285 return rnd_event_prod - rnd_event_cons; 286 } 287 288 /* 289 * This function adds entropy to the entropy pool by using timing delays. 290 * 291 * The number "val" is also added to the pool - it should somehow describe 292 * the type of event which just happened. Currently the values of 0-255 293 * are for keyboard scan codes, 256 and upwards - for interrupts. 294 */ 295 void 296 enqueue_randomness(u_int val) 297 { 298 struct rand_event *rep; 299 struct timespec ts; 300 u_int qlen; 301 302 if (timeout_initialized(&rnd_timeout)) 303 nanotime(&ts); 304 305 mtx_enter(&rnd_enqlck); 306 rep = rnd_put(); 307 rep->re_time += ts.tv_nsec ^ (ts.tv_sec << 20); 308 rep->re_val += val; 309 qlen = rnd_qlen(); 310 mtx_leave(&rnd_enqlck); 311 312 if (qlen > QEVSLOW/2 && timeout_initialized(&rnd_timeout) && 313 !timeout_pending(&rnd_timeout)) 314 timeout_add(&rnd_timeout, 1); 315 } 316 317 /* 318 * This function adds a byte into the entropy pool. It does not 319 * update the entropy estimate. The caller must do this if appropriate. 320 * 321 * The pool is stirred with a polynomial of degree POOLWORDS over GF(2); 322 * see POOL_TAP[1-4] above 323 * 324 * Rotate the input word by a changing number of bits, to help assure 325 * that all bits in the entropy get toggled. Otherwise, if the pool 326 * is consistently fed small numbers (such as keyboard scan codes) 327 * then the upper bits of the entropy pool will frequently remain 328 * untouched. 329 */ 330 void 331 add_entropy_words(const u_int32_t *buf, u_int n) 332 { 333 /* derived from IEEE 802.3 CRC-32 */ 334 static const u_int32_t twist_table[8] = { 335 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158, 336 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 337 }; 338 339 for (; n--; buf++) { 340 u_int32_t w = (*buf << entropy_input_rotate) | 341 (*buf >> ((32 - entropy_input_rotate) & 31)); 342 u_int i = entropy_add_ptr = 343 (entropy_add_ptr - 1) & POOLMASK; 344 /* 345 * Normally, we add 7 bits of rotation to the pool. 346 * At the beginning of the pool, add an extra 7 bits 347 * rotation, so that successive passes spread the 348 * input bits across the pool evenly. 349 */ 350 entropy_input_rotate = 351 (entropy_input_rotate + (i ? 7 : 14)) & 31; 352 353 /* XOR pool contents corresponding to polynomial terms */ 354 w ^= entropy_pool[(i + POOL_TAP1) & POOLMASK] ^ 355 entropy_pool[(i + POOL_TAP2) & POOLMASK] ^ 356 entropy_pool[(i + POOL_TAP3) & POOLMASK] ^ 357 entropy_pool[(i + POOL_TAP4) & POOLMASK] ^ 358 entropy_pool[(i + 1) & POOLMASK] ^ 359 entropy_pool[i]; /* + 2^POOLWORDS */ 360 361 entropy_pool[i] = (w >> 3) ^ twist_table[w & 7]; 362 } 363 } 364 365 /* 366 * Pulls entropy out of the queue and merges it into the pool 367 * with the CRC. 368 */ 369 /* ARGSUSED */ 370 void 371 dequeue_randomness(void *v) 372 { 373 struct rand_event *rep; 374 u_int32_t buf[2]; 375 376 if (timeout_initialized(&rnd_timeout)) 377 timeout_del(&rnd_timeout); 378 379 mtx_enter(&rnd_deqlck); 380 while ((rep = rnd_get())) { 381 buf[0] = rep->re_time; 382 buf[1] = rep->re_val; 383 mtx_leave(&rnd_deqlck); 384 add_entropy_words(buf, 2); 385 mtx_enter(&rnd_deqlck); 386 } 387 mtx_leave(&rnd_deqlck); 388 } 389 390 /* 391 * Grabs a chunk from the entropy_pool[] and slams it through SHA512 when 392 * requested. 393 */ 394 void 395 extract_entropy(u_int8_t *buf) 396 { 397 static u_int32_t extract_pool[POOLWORDS]; 398 u_char digest[SHA512_DIGEST_LENGTH]; 399 SHA2_CTX shactx; 400 401 #if SHA512_DIGEST_LENGTH < EBUFSIZE 402 #error "need more bigger hash output" 403 #endif 404 405 /* 406 * INTENTIONALLY not protected by any lock. Races during 407 * memcpy() result in acceptable input data; races during 408 * SHA512Update() would create nasty data dependencies. We 409 * do not rely on this as a benefit, but if it happens, cool. 410 */ 411 memcpy(extract_pool, entropy_pool, sizeof(extract_pool)); 412 413 /* Hash the pool to get the output */ 414 SHA512Init(&shactx); 415 SHA512Update(&shactx, (u_int8_t *)extract_pool, sizeof(extract_pool)); 416 SHA512Final(digest, &shactx); 417 418 /* Copy data to destination buffer */ 419 memcpy(buf, digest, EBUFSIZE); 420 421 /* Modify pool so next hash will produce different results */ 422 enqueue_randomness(EBUFSIZE); 423 dequeue_randomness(NULL); 424 425 /* Wipe data from memory */ 426 explicit_bzero(extract_pool, sizeof(extract_pool)); 427 explicit_bzero(digest, sizeof(digest)); 428 } 429 430 /* random keystream by ChaCha */ 431 432 void rnd_reinit(void *v); /* timeout to start reinit */ 433 void rnd_init(void *); /* actually do the reinit */ 434 435 struct mutex rndlock = MUTEX_INITIALIZER(IPL_HIGH); 436 struct timeout rndreinit_timeout; 437 struct task rnd_task = TASK_INITIALIZER(rnd_init, NULL); 438 439 static chacha_ctx rs; /* chacha context for random keystream */ 440 /* keystream blocks (also chacha seed from boot) */ 441 static u_char rs_buf[RSBUFSZ]; 442 u_char rs_buf0[RSBUFSZ] __attribute__((section(".openbsd.randomdata"))); 443 static size_t rs_have; /* valid bytes at end of rs_buf */ 444 static size_t rs_count; /* bytes till reseed */ 445 446 void 447 suspend_randomness(void) 448 { 449 struct timespec ts; 450 451 getnanotime(&ts); 452 enqueue_randomness(ts.tv_sec); 453 enqueue_randomness(ts.tv_nsec); 454 455 dequeue_randomness(NULL); 456 rs_count = 0; 457 arc4random_buf(entropy_pool, sizeof(entropy_pool)); 458 } 459 460 void 461 resume_randomness(char *buf, size_t buflen) 462 { 463 struct timespec ts; 464 465 if (buf && buflen) 466 _rs_seed(buf, buflen); 467 getnanotime(&ts); 468 enqueue_randomness(ts.tv_sec); 469 enqueue_randomness(ts.tv_nsec); 470 471 dequeue_randomness(NULL); 472 rs_count = 0; 473 } 474 475 static inline void _rs_rekey(u_char *dat, size_t datlen); 476 477 static inline void 478 _rs_init(u_char *buf, size_t n) 479 { 480 KASSERT(n >= KEYSZ + IVSZ); 481 chacha_keysetup(&rs, buf, KEYSZ * 8); 482 chacha_ivsetup(&rs, buf + KEYSZ, NULL); 483 } 484 485 static void 486 _rs_seed(u_char *buf, size_t n) 487 { 488 _rs_rekey(buf, n); 489 490 /* invalidate rs_buf */ 491 rs_have = 0; 492 memset(rs_buf, 0, RSBUFSZ); 493 494 rs_count = 1600000; 495 } 496 497 static void 498 _rs_stir(int do_lock) 499 { 500 struct timespec ts; 501 u_int8_t buf[EBUFSIZE], *p; 502 int i; 503 504 /* 505 * Use SHA512 PRNG data and a system timespec; early in the boot 506 * process this is the best we can do -- some architectures do 507 * not collect entropy very well during this time, but may have 508 * clock information which is better than nothing. 509 */ 510 extract_entropy(buf); 511 512 nanotime(&ts); 513 for (p = (u_int8_t *)&ts, i = 0; i < sizeof(ts); i++) 514 buf[i] ^= p[i]; 515 516 if (do_lock) 517 mtx_enter(&rndlock); 518 _rs_seed(buf, sizeof(buf)); 519 if (do_lock) 520 mtx_leave(&rndlock); 521 522 explicit_bzero(buf, sizeof(buf)); 523 } 524 525 static inline void 526 _rs_stir_if_needed(size_t len) 527 { 528 static int rs_initialized; 529 530 if (!rs_initialized) { 531 memcpy(entropy_pool, entropy_pool0, sizeof entropy_pool); 532 memcpy(rs_buf, rs_buf0, sizeof rs_buf); 533 /* seeds cannot be cleaned yet, random_start() will do so */ 534 _rs_init(rs_buf, KEYSZ + IVSZ); 535 rs_count = 1024 * 1024 * 1024; /* until main() runs */ 536 rs_initialized = 1; 537 } else if (rs_count <= len) 538 _rs_stir(0); 539 else 540 rs_count -= len; 541 } 542 543 static void 544 _rs_clearseed(const void *p, size_t s) 545 { 546 struct kmem_dyn_mode kd_avoidalias; 547 vaddr_t va = trunc_page((vaddr_t)p); 548 vsize_t off = (vaddr_t)p - va; 549 vsize_t len; 550 vaddr_t rwva; 551 paddr_t pa; 552 553 while (s > 0) { 554 pmap_extract(pmap_kernel(), va, &pa); 555 556 memset(&kd_avoidalias, 0, sizeof kd_avoidalias); 557 kd_avoidalias.kd_prefer = pa; 558 kd_avoidalias.kd_waitok = 1; 559 rwva = (vaddr_t)km_alloc(PAGE_SIZE, &kv_any, &kp_none, 560 &kd_avoidalias); 561 if (!rwva) 562 panic("_rs_clearseed"); 563 564 pmap_kenter_pa(rwva, pa, PROT_READ | PROT_WRITE); 565 pmap_update(pmap_kernel()); 566 567 len = MIN(s, PAGE_SIZE - off); 568 explicit_bzero((void *)(rwva + off), len); 569 570 pmap_kremove(rwva, PAGE_SIZE); 571 km_free((void *)rwva, PAGE_SIZE, &kv_any, &kp_none); 572 573 va += PAGE_SIZE; 574 s -= len; 575 off = 0; 576 } 577 } 578 579 static inline void 580 _rs_rekey(u_char *dat, size_t datlen) 581 { 582 #ifndef KEYSTREAM_ONLY 583 memset(rs_buf, 0, RSBUFSZ); 584 #endif 585 /* fill rs_buf with the keystream */ 586 chacha_encrypt_bytes(&rs, rs_buf, rs_buf, RSBUFSZ); 587 /* mix in optional user provided data */ 588 if (dat) { 589 size_t i, m; 590 591 m = MIN(datlen, KEYSZ + IVSZ); 592 for (i = 0; i < m; i++) 593 rs_buf[i] ^= dat[i]; 594 } 595 /* immediately reinit for backtracking resistance */ 596 _rs_init(rs_buf, KEYSZ + IVSZ); 597 memset(rs_buf, 0, KEYSZ + IVSZ); 598 rs_have = RSBUFSZ - KEYSZ - IVSZ; 599 } 600 601 static inline void 602 _rs_random_buf(void *_buf, size_t n) 603 { 604 u_char *buf = (u_char *)_buf; 605 size_t m; 606 607 _rs_stir_if_needed(n); 608 while (n > 0) { 609 if (rs_have > 0) { 610 m = MIN(n, rs_have); 611 memcpy(buf, rs_buf + RSBUFSZ - rs_have, m); 612 memset(rs_buf + RSBUFSZ - rs_have, 0, m); 613 buf += m; 614 n -= m; 615 rs_have -= m; 616 } 617 if (rs_have == 0) 618 _rs_rekey(NULL, 0); 619 } 620 } 621 622 static inline void 623 _rs_random_u32(u_int32_t *val) 624 { 625 _rs_stir_if_needed(sizeof(*val)); 626 if (rs_have < sizeof(*val)) 627 _rs_rekey(NULL, 0); 628 memcpy(val, rs_buf + RSBUFSZ - rs_have, sizeof(*val)); 629 memset(rs_buf + RSBUFSZ - rs_have, 0, sizeof(*val)); 630 rs_have -= sizeof(*val); 631 } 632 633 /* Return one word of randomness from a ChaCha20 generator */ 634 u_int32_t 635 arc4random(void) 636 { 637 u_int32_t ret; 638 639 mtx_enter(&rndlock); 640 _rs_random_u32(&ret); 641 mtx_leave(&rndlock); 642 return ret; 643 } 644 645 /* 646 * Fill a buffer of arbitrary length with ChaCha20-derived randomness. 647 */ 648 void 649 arc4random_buf(void *buf, size_t n) 650 { 651 mtx_enter(&rndlock); 652 _rs_random_buf(buf, n); 653 mtx_leave(&rndlock); 654 } 655 656 /* 657 * Allocate a new ChaCha20 context for the caller to use. 658 */ 659 struct arc4random_ctx * 660 arc4random_ctx_new() 661 { 662 char keybuf[KEYSZ + IVSZ]; 663 664 chacha_ctx *ctx = malloc(sizeof(chacha_ctx), M_TEMP, M_WAITOK); 665 arc4random_buf(keybuf, KEYSZ + IVSZ); 666 chacha_keysetup(ctx, keybuf, KEYSZ * 8); 667 chacha_ivsetup(ctx, keybuf + KEYSZ, NULL); 668 explicit_bzero(keybuf, sizeof(keybuf)); 669 return (struct arc4random_ctx *)ctx; 670 } 671 672 /* 673 * Free a ChaCha20 context created by arc4random_ctx_new() 674 */ 675 void 676 arc4random_ctx_free(struct arc4random_ctx *ctx) 677 { 678 explicit_bzero(ctx, sizeof(chacha_ctx)); 679 free(ctx, M_TEMP, sizeof(chacha_ctx)); 680 } 681 682 /* 683 * Use a given ChaCha20 context to fill a buffer 684 */ 685 void 686 arc4random_ctx_buf(struct arc4random_ctx *ctx, void *buf, size_t n) 687 { 688 chacha_encrypt_bytes((chacha_ctx *)ctx, buf, buf, n); 689 } 690 691 /* 692 * Calculate a uniformly distributed random number less than upper_bound 693 * avoiding "modulo bias". 694 * 695 * Uniformity is achieved by generating new random numbers until the one 696 * returned is outside the range [0, 2**32 % upper_bound). This 697 * guarantees the selected random number will be inside 698 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 699 * after reduction modulo upper_bound. 700 */ 701 u_int32_t 702 arc4random_uniform(u_int32_t upper_bound) 703 { 704 u_int32_t r, min; 705 706 if (upper_bound < 2) 707 return 0; 708 709 /* 2**32 % x == (2**32 - x) % x */ 710 min = -upper_bound % upper_bound; 711 712 /* 713 * This could theoretically loop forever but each retry has 714 * p > 0.5 (worst case, usually far better) of selecting a 715 * number inside the range we need, so it should rarely need 716 * to re-roll. 717 */ 718 for (;;) { 719 r = arc4random(); 720 if (r >= min) 721 break; 722 } 723 724 return r % upper_bound; 725 } 726 727 /* ARGSUSED */ 728 void 729 rnd_init(void *null) 730 { 731 _rs_stir(1); 732 } 733 734 /* 735 * Called by timeout to mark arc4 for stirring, 736 */ 737 void 738 rnd_reinit(void *v) 739 { 740 task_add(systq, &rnd_task); 741 /* 10 minutes, per dm@'s suggestion */ 742 timeout_add_sec(&rndreinit_timeout, 10 * 60); 743 } 744 745 /* 746 * Start periodic services inside the random subsystem, which pull 747 * entropy forward, hash it, and re-seed the random stream as needed. 748 */ 749 void 750 random_start(void) 751 { 752 extern char etext[]; 753 754 #if !defined(NO_PROPOLICE) 755 extern long __guard_local; 756 757 if (__guard_local == 0) 758 printf("warning: no entropy supplied by boot loader\n"); 759 #endif 760 761 _rs_clearseed(entropy_pool0, sizeof entropy_pool0); 762 _rs_clearseed(rs_buf0, sizeof rs_buf0); 763 764 /* Message buffer may contain data from previous boot */ 765 if (msgbufp->msg_magic == MSG_MAGIC) 766 add_entropy_words((u_int32_t *)msgbufp->msg_bufc, 767 msgbufp->msg_bufs / sizeof(u_int32_t)); 768 add_entropy_words((u_int32_t *)etext - 32*1024, 769 8192/sizeof(u_int32_t)); 770 771 dequeue_randomness(NULL); 772 rnd_init(NULL); 773 timeout_set(&rndreinit_timeout, rnd_reinit, NULL); 774 rnd_reinit(NULL); 775 timeout_set(&rnd_timeout, dequeue_randomness, NULL); 776 } 777 778 int 779 randomopen(dev_t dev, int flag, int mode, struct proc *p) 780 { 781 return 0; 782 } 783 784 int 785 randomclose(dev_t dev, int flag, int mode, struct proc *p) 786 { 787 return 0; 788 } 789 790 /* 791 * Maximum number of bytes to serve directly from the main ChaCha 792 * pool. Larger requests are served from a discrete ChaCha instance keyed 793 * from the main pool. 794 */ 795 #define RND_MAIN_MAX_BYTES 2048 796 797 int 798 randomread(dev_t dev, struct uio *uio, int ioflag) 799 { 800 u_char lbuf[KEYSZ+IVSZ]; 801 chacha_ctx lctx; 802 size_t total = uio->uio_resid; 803 u_char *buf; 804 int myctx = 0, ret = 0; 805 806 if (uio->uio_resid == 0) 807 return 0; 808 809 buf = malloc(POOLBYTES, M_TEMP, M_WAITOK); 810 if (total > RND_MAIN_MAX_BYTES) { 811 arc4random_buf(lbuf, sizeof(lbuf)); 812 chacha_keysetup(&lctx, lbuf, KEYSZ * 8); 813 chacha_ivsetup(&lctx, lbuf + KEYSZ, NULL); 814 explicit_bzero(lbuf, sizeof(lbuf)); 815 myctx = 1; 816 } 817 818 while (ret == 0 && uio->uio_resid > 0) { 819 size_t n = ulmin(POOLBYTES, uio->uio_resid); 820 821 if (myctx) { 822 #ifndef KEYSTREAM_ONLY 823 memset(buf, 0, n); 824 #endif 825 chacha_encrypt_bytes(&lctx, buf, buf, n); 826 } else 827 arc4random_buf(buf, n); 828 ret = uiomove(buf, n, uio); 829 if (ret == 0 && uio->uio_resid > 0) 830 yield(); 831 } 832 if (myctx) 833 explicit_bzero(&lctx, sizeof(lctx)); 834 explicit_bzero(buf, POOLBYTES); 835 free(buf, M_TEMP, POOLBYTES); 836 return ret; 837 } 838 839 int 840 randomwrite(dev_t dev, struct uio *uio, int flags) 841 { 842 int ret = 0, newdata = 0; 843 u_int32_t *buf; 844 845 if (uio->uio_resid == 0) 846 return 0; 847 848 buf = malloc(POOLBYTES, M_TEMP, M_WAITOK); 849 850 while (ret == 0 && uio->uio_resid > 0) { 851 size_t n = ulmin(POOLBYTES, uio->uio_resid); 852 853 ret = uiomove(buf, n, uio); 854 if (ret != 0) 855 break; 856 while (n % sizeof(u_int32_t)) 857 ((u_int8_t *)buf)[n++] = 0; 858 add_entropy_words(buf, n / 4); 859 if (uio->uio_resid > 0) 860 yield(); 861 newdata = 1; 862 } 863 864 if (newdata) 865 rnd_init(NULL); 866 867 explicit_bzero(buf, POOLBYTES); 868 free(buf, M_TEMP, POOLBYTES); 869 return ret; 870 } 871 872 int 873 randomkqfilter(dev_t dev, struct knote *kn) 874 { 875 switch (kn->kn_filter) { 876 case EVFILT_READ: 877 kn->kn_fop = &randomread_filtops; 878 break; 879 case EVFILT_WRITE: 880 kn->kn_fop = &randomwrite_filtops; 881 break; 882 default: 883 return (EINVAL); 884 } 885 886 return (0); 887 } 888 889 void 890 filt_randomdetach(struct knote *kn) 891 { 892 } 893 894 int 895 filt_randomread(struct knote *kn, long hint) 896 { 897 kn->kn_data = RND_MAIN_MAX_BYTES; 898 return (1); 899 } 900 901 int 902 filt_randomwrite(struct knote *kn, long hint) 903 { 904 kn->kn_data = POOLBYTES; 905 return (1); 906 } 907 908 int 909 randomioctl(dev_t dev, u_long cmd, caddr_t data, int flag, struct proc *p) 910 { 911 switch (cmd) { 912 case FIOASYNC: 913 /* No async flag in softc so this is a no-op. */ 914 break; 915 case FIONBIO: 916 /* Handled in the upper FS layer. */ 917 break; 918 default: 919 return ENOTTY; 920 } 921 return 0; 922 } 923 924 int 925 sys_getentropy(struct proc *p, void *v, register_t *retval) 926 { 927 struct sys_getentropy_args /* { 928 syscallarg(void *) buf; 929 syscallarg(size_t) nbyte; 930 } */ *uap = v; 931 char buf[256]; 932 int error; 933 934 if (SCARG(uap, nbyte) > sizeof(buf)) 935 return (EIO); 936 arc4random_buf(buf, SCARG(uap, nbyte)); 937 if ((error = copyout(buf, SCARG(uap, buf), SCARG(uap, nbyte))) != 0) 938 return (error); 939 explicit_bzero(buf, sizeof(buf)); 940 retval[0] = 0; 941 return (0); 942 } 943