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