1 /* $OpenBSD: rnd.c,v 1.181 2016/05/23 15:48:59 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, the sysctl kern.arandom, and the 89 * system call getentropy(), which provides seeds for process-context 90 * pseudorandom generators. 91 * 92 * Acknowledgements: 93 * ================= 94 * 95 * Ideas for constructing this random number generator were derived 96 * from Pretty Good Privacy's random number generator, and from private 97 * discussions with Phil Karn. Colin Plumb provided a faster random 98 * number generator, which speeds up the mixing function of the entropy 99 * pool, taken from PGPfone. Dale Worley has also contributed many 100 * useful ideas and suggestions to improve this driver. 101 * 102 * Any flaws in the design are solely my responsibility, and should 103 * not be attributed to the Phil, Colin, or any of the authors of PGP. 104 * 105 * Further background information on this topic may be obtained from 106 * RFC 1750, "Randomness Recommendations for Security", by Donald 107 * Eastlake, Steve Crocker, and Jeff Schiller. 108 * 109 * Using a RC4 stream cipher as 2nd stage after the MD5 (now SHA512) output 110 * is the result of work by David Mazieres. 111 */ 112 113 #include <sys/param.h> 114 #include <sys/systm.h> 115 #include <sys/disk.h> 116 #include <sys/event.h> 117 #include <sys/limits.h> 118 #include <sys/time.h> 119 #include <sys/ioctl.h> 120 #include <sys/malloc.h> 121 #include <sys/fcntl.h> 122 #include <sys/timeout.h> 123 #include <sys/mutex.h> 124 #include <sys/task.h> 125 #include <sys/msgbuf.h> 126 #include <sys/mount.h> 127 #include <sys/syscallargs.h> 128 129 #include <crypto/sha2.h> 130 131 #define KEYSTREAM_ONLY 132 #include <crypto/chacha_private.h> 133 134 #include <dev/rndvar.h> 135 136 /* 137 * For the purposes of better mixing, we use the CRC-32 polynomial as 138 * well to make a twisted Generalized Feedback Shift Register 139 * 140 * (See M. Matsumoto & Y. Kurita, 1992. Twisted GFSR generators. ACM 141 * Transactions on Modeling and Computer Simulation 2(3):179-194. 142 * Also see M. Matsumoto & Y. Kurita, 1994. Twisted GFSR generators 143 * II. ACM Transactions on Mdeling and Computer Simulation 4:254-266) 144 * 145 * Thanks to Colin Plumb for suggesting this. 146 * 147 * We have not analyzed the resultant polynomial to prove it primitive; 148 * in fact it almost certainly isn't. Nonetheless, the irreducible factors 149 * of a random large-degree polynomial over GF(2) are more than large enough 150 * that periodicity is not a concern. 151 * 152 * The input hash is much less sensitive than the output hash. All 153 * we want from it is to be a good non-cryptographic hash - 154 * i.e. to not produce collisions when fed "random" data of the sort 155 * we expect to see. As long as the pool state differs for different 156 * inputs, we have preserved the input entropy and done a good job. 157 * The fact that an intelligent attacker can construct inputs that 158 * will produce controlled alterations to the pool's state is not 159 * important because we don't consider such inputs to contribute any 160 * randomness. The only property we need with respect to them is that 161 * the attacker can't increase his/her knowledge of the pool's state. 162 * Since all additions are reversible (knowing the final state and the 163 * input, you can reconstruct the initial state), if an attacker has 164 * any uncertainty about the initial state, he/she can only shuffle 165 * that uncertainty about, but never cause any collisions (which would 166 * decrease the uncertainty). 167 * 168 * The chosen system lets the state of the pool be (essentially) the input 169 * modulo the generator polynomial. Now, for random primitive polynomials, 170 * this is a universal class of hash functions, meaning that the chance 171 * of a collision is limited by the attacker's knowledge of the generator 172 * polynomial, so if it is chosen at random, an attacker can never force 173 * a collision. Here, we use a fixed polynomial, but we *can* assume that 174 * ###--> it is unknown to the processes generating the input entropy. <-### 175 * Because of this important property, this is a good, collision-resistant 176 * hash; hash collisions will occur no more often than chance. 177 */ 178 179 /* 180 * Stirring polynomials over GF(2) for various pool sizes. Used in 181 * add_entropy_words() below. 182 * 183 * The polynomial terms are chosen to be evenly spaced (minimum RMS 184 * distance from evenly spaced; except for the last tap, which is 1 to 185 * get the twisting happening as fast as possible. 186 * 187 * The reultant polynomial is: 188 * 2^POOLWORDS + 2^POOL_TAP1 + 2^POOL_TAP2 + 2^POOL_TAP3 + 2^POOL_TAP4 + 1 189 */ 190 #define POOLWORDS 2048 191 #define POOLBYTES (POOLWORDS*4) 192 #define POOLMASK (POOLWORDS - 1) 193 #define POOL_TAP1 1638 194 #define POOL_TAP2 1231 195 #define POOL_TAP3 819 196 #define POOL_TAP4 411 197 198 struct mutex entropylock = MUTEX_INITIALIZER(IPL_HIGH); 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 * Almost completely under the entropylock. 204 */ 205 struct timer_rand_state { /* There is one of these per entropy source */ 206 u_int last_time; 207 u_int last_delta; 208 u_int last_delta2; 209 u_int dont_count_entropy : 1; 210 u_int max_entropy : 1; 211 } rnd_states[RND_SRC_NUM]; 212 213 #define QEVLEN (1024 / sizeof(struct rand_event)) 214 #define QEVSLOW (QEVLEN * 3 / 4) /* yet another 0.75 for 60-minutes hour /-; */ 215 #define QEVSBITS 10 216 217 #define KEYSZ 32 218 #define IVSZ 8 219 #define BLOCKSZ 64 220 #define RSBUFSZ (16*BLOCKSZ) 221 #define EBUFSIZE KEYSZ + IVSZ 222 223 struct rand_event { 224 struct timer_rand_state *re_state; 225 u_int re_nbits; 226 u_int re_time; 227 u_int re_val; 228 } rnd_event_space[QEVLEN]; 229 /* index of next free slot */ 230 u_int rnd_event_idx; 231 232 struct timeout rnd_timeout; 233 234 u_int32_t entropy_pool[POOLWORDS] __attribute__((section(".openbsd.randomdata"))); 235 u_int entropy_add_ptr; 236 u_char entropy_input_rotate; 237 238 void dequeue_randomness(void *); 239 void add_entropy_words(const u_int32_t *, u_int); 240 void extract_entropy(u_int8_t *) 241 __attribute__((__bounded__(__minbytes__,1,EBUFSIZE))); 242 243 int filt_randomread(struct knote *, long); 244 void filt_randomdetach(struct knote *); 245 int filt_randomwrite(struct knote *, long); 246 247 static void _rs_seed(u_char *, size_t); 248 249 struct filterops randomread_filtops = 250 { 1, NULL, filt_randomdetach, filt_randomread }; 251 struct filterops randomwrite_filtops = 252 { 1, NULL, filt_randomdetach, filt_randomwrite }; 253 254 static __inline struct rand_event * 255 rnd_get(void) 256 { 257 if (rnd_event_idx == 0) 258 return NULL; 259 /* if it wrapped around, start dequeuing at the end */ 260 if (rnd_event_idx > QEVLEN) 261 rnd_event_idx = QEVLEN; 262 263 return &rnd_event_space[--rnd_event_idx]; 264 } 265 266 static __inline struct rand_event * 267 rnd_put(void) 268 { 269 u_int idx = rnd_event_idx++; 270 271 /* allow wrapping. caller will use xor. */ 272 idx = idx % QEVLEN; 273 274 return &rnd_event_space[idx]; 275 } 276 277 static __inline u_int 278 rnd_qlen(void) 279 { 280 return rnd_event_idx; 281 } 282 283 /* 284 * This function adds entropy to the entropy pool by using timing 285 * delays. It uses the timer_rand_state structure to make an estimate 286 * of how many bits of entropy this call has added to the pool. 287 * 288 * The number "val" is also added to the pool - it should somehow describe 289 * the type of event which just happened. Currently the values of 0-255 290 * are for keyboard scan codes, 256 and upwards - for interrupts. 291 */ 292 void 293 enqueue_randomness(u_int state, u_int val) 294 { 295 int delta, delta2, delta3; 296 struct timer_rand_state *p; 297 struct rand_event *rep; 298 struct timespec ts; 299 u_int time, nbits; 300 301 #ifdef DIAGNOSTIC 302 if (state >= RND_SRC_NUM) 303 return; 304 #endif 305 306 if (timeout_initialized(&rnd_timeout)) 307 nanotime(&ts); 308 309 p = &rnd_states[state]; 310 val += state << 13; 311 312 time = (ts.tv_nsec >> 10) + (ts.tv_sec << 20); 313 nbits = 0; 314 315 /* 316 * Calculate the number of bits of randomness that we probably 317 * added. We take into account the first and second order 318 * deltas in order to make our estimate. 319 */ 320 if (!p->dont_count_entropy) { 321 delta = time - p->last_time; 322 delta2 = delta - p->last_delta; 323 delta3 = delta2 - p->last_delta2; 324 325 if (delta < 0) delta = -delta; 326 if (delta2 < 0) delta2 = -delta2; 327 if (delta3 < 0) delta3 = -delta3; 328 if (delta > delta2) delta = delta2; 329 if (delta > delta3) delta = delta3; 330 delta3 = delta >>= 1; 331 /* 332 * delta &= 0xfff; 333 * we don't do it since our time sheet is different from linux 334 */ 335 336 if (delta & 0xffff0000) { 337 nbits = 16; 338 delta >>= 16; 339 } 340 if (delta & 0xff00) { 341 nbits += 8; 342 delta >>= 8; 343 } 344 if (delta & 0xf0) { 345 nbits += 4; 346 delta >>= 4; 347 } 348 if (delta & 0xc) { 349 nbits += 2; 350 delta >>= 2; 351 } 352 if (delta & 2) { 353 nbits += 1; 354 delta >>= 1; 355 } 356 if (delta & 1) 357 nbits++; 358 } else if (p->max_entropy) 359 nbits = 8 * sizeof(val) - 1; 360 361 /* given the multi-order delta logic above, this should never happen */ 362 if (nbits >= 32) 363 return; 364 365 mtx_enter(&entropylock); 366 if (!p->dont_count_entropy) { 367 p->last_time = time; 368 p->last_delta = delta3; 369 p->last_delta2 = delta2; 370 } 371 372 rep = rnd_put(); 373 374 rep->re_state = p; 375 rep->re_nbits = nbits; 376 rep->re_time += ts.tv_nsec ^ (ts.tv_sec << 20); 377 rep->re_val += val; 378 379 if (rnd_qlen() > QEVSLOW/2 && timeout_initialized(&rnd_timeout) && 380 !timeout_pending(&rnd_timeout)) 381 timeout_add(&rnd_timeout, 1); 382 383 mtx_leave(&entropylock); 384 } 385 386 /* 387 * This function adds a byte into the entropy pool. It does not 388 * update the entropy estimate. The caller must do this if appropriate. 389 * 390 * The pool is stirred with a polynomial of degree POOLWORDS over GF(2); 391 * see POOL_TAP[1-4] above 392 * 393 * Rotate the input word by a changing number of bits, to help assure 394 * that all bits in the entropy get toggled. Otherwise, if the pool 395 * is consistently fed small numbers (such as keyboard scan codes) 396 * then the upper bits of the entropy pool will frequently remain 397 * untouched. 398 */ 399 void 400 add_entropy_words(const u_int32_t *buf, u_int n) 401 { 402 /* derived from IEEE 802.3 CRC-32 */ 403 static const u_int32_t twist_table[8] = { 404 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158, 405 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 406 }; 407 408 for (; n--; buf++) { 409 u_int32_t w = (*buf << entropy_input_rotate) | 410 (*buf >> ((32 - entropy_input_rotate) & 31)); 411 u_int i = entropy_add_ptr = 412 (entropy_add_ptr - 1) & POOLMASK; 413 /* 414 * Normally, we add 7 bits of rotation to the pool. 415 * At the beginning of the pool, add an extra 7 bits 416 * rotation, so that successive passes spread the 417 * input bits across the pool evenly. 418 */ 419 entropy_input_rotate = 420 (entropy_input_rotate + (i ? 7 : 14)) & 31; 421 422 /* XOR pool contents corresponding to polynomial terms */ 423 w ^= entropy_pool[(i + POOL_TAP1) & POOLMASK] ^ 424 entropy_pool[(i + POOL_TAP2) & POOLMASK] ^ 425 entropy_pool[(i + POOL_TAP3) & POOLMASK] ^ 426 entropy_pool[(i + POOL_TAP4) & POOLMASK] ^ 427 entropy_pool[(i + 1) & POOLMASK] ^ 428 entropy_pool[i]; /* + 2^POOLWORDS */ 429 430 entropy_pool[i] = (w >> 3) ^ twist_table[w & 7]; 431 } 432 } 433 434 /* 435 * Pulls entropy out of the queue and throws merges it into the pool 436 * with the CRC. 437 */ 438 /* ARGSUSED */ 439 void 440 dequeue_randomness(void *v) 441 { 442 struct rand_event *rep; 443 u_int32_t buf[2]; 444 u_int nbits; 445 446 mtx_enter(&entropylock); 447 448 if (timeout_initialized(&rnd_timeout)) 449 timeout_del(&rnd_timeout); 450 451 while ((rep = rnd_get())) { 452 buf[0] = rep->re_time; 453 buf[1] = rep->re_val; 454 nbits = rep->re_nbits; 455 mtx_leave(&entropylock); 456 457 add_entropy_words(buf, 2); 458 459 mtx_enter(&entropylock); 460 } 461 mtx_leave(&entropylock); 462 } 463 464 /* 465 * Grabs a chunk from the entropy_pool[] and slams it through SHA512 when 466 * requested. 467 */ 468 void 469 extract_entropy(u_int8_t *buf) 470 { 471 static u_int32_t extract_pool[POOLWORDS]; 472 u_char digest[SHA512_DIGEST_LENGTH]; 473 SHA2_CTX shactx; 474 475 #if SHA512_DIGEST_LENGTH < EBUFSIZE 476 #error "need more bigger hash output" 477 #endif 478 479 /* 480 * INTENTIONALLY not protected by entropylock. Races during 481 * memcpy() result in acceptable input data; races during 482 * SHA512Update() would create nasty data dependencies. We 483 * do not rely on this as a benefit, but if it happens, cool. 484 */ 485 memcpy(extract_pool, entropy_pool, sizeof(extract_pool)); 486 487 /* Hash the pool to get the output */ 488 SHA512Init(&shactx); 489 SHA512Update(&shactx, (u_int8_t *)extract_pool, sizeof(extract_pool)); 490 SHA512Final(digest, &shactx); 491 492 /* Copy data to destination buffer */ 493 memcpy(buf, digest, EBUFSIZE); 494 495 /* Modify pool so next hash will produce different results */ 496 add_timer_randomness(EBUFSIZE); 497 dequeue_randomness(NULL); 498 499 /* Wipe data from memory */ 500 explicit_bzero(extract_pool, sizeof(extract_pool)); 501 explicit_bzero(digest, sizeof(digest)); 502 } 503 504 /* random keystream by ChaCha */ 505 506 void arc4_reinit(void *v); /* timeout to start reinit */ 507 void arc4_init(void *); /* actually do the reinit */ 508 509 struct mutex rndlock = MUTEX_INITIALIZER(IPL_HIGH); 510 struct timeout arc4_timeout; 511 struct task arc4_task = TASK_INITIALIZER(arc4_init, NULL); 512 513 static int rs_initialized; 514 static chacha_ctx rs; /* chacha context for random keystream */ 515 /* keystream blocks (also chacha seed from boot) */ 516 static u_char rs_buf[RSBUFSZ] __attribute__((section(".openbsd.randomdata"))); 517 static size_t rs_have; /* valid bytes at end of rs_buf */ 518 static size_t rs_count; /* bytes till reseed */ 519 520 void 521 suspend_randomness(void) 522 { 523 struct timespec ts; 524 525 getnanotime(&ts); 526 add_true_randomness(ts.tv_sec); 527 add_true_randomness(ts.tv_nsec); 528 529 dequeue_randomness(NULL); 530 rs_count = 0; 531 arc4random_buf(entropy_pool, sizeof(entropy_pool)); 532 } 533 534 void 535 resume_randomness(char *buf, size_t buflen) 536 { 537 struct timespec ts; 538 539 if (buf && buflen) 540 _rs_seed(buf, buflen); 541 getnanotime(&ts); 542 add_true_randomness(ts.tv_sec); 543 add_true_randomness(ts.tv_nsec); 544 545 dequeue_randomness(NULL); 546 rs_count = 0; 547 } 548 549 static inline void _rs_rekey(u_char *dat, size_t datlen); 550 551 static inline void 552 _rs_init(u_char *buf, size_t n) 553 { 554 KASSERT(n >= KEYSZ + IVSZ); 555 chacha_keysetup(&rs, buf, KEYSZ * 8); 556 chacha_ivsetup(&rs, buf + KEYSZ, NULL); 557 } 558 559 static void 560 _rs_seed(u_char *buf, size_t n) 561 { 562 _rs_rekey(buf, n); 563 564 /* invalidate rs_buf */ 565 rs_have = 0; 566 memset(rs_buf, 0, RSBUFSZ); 567 568 rs_count = 1600000; 569 } 570 571 static void 572 _rs_stir(int do_lock) 573 { 574 struct timespec ts; 575 u_int8_t buf[EBUFSIZE], *p; 576 int i; 577 578 /* 579 * Use SHA512 PRNG data and a system timespec; early in the boot 580 * process this is the best we can do -- some architectures do 581 * not collect entropy very well during this time, but may have 582 * clock information which is better than nothing. 583 */ 584 extract_entropy(buf); 585 586 nanotime(&ts); 587 for (p = (u_int8_t *)&ts, i = 0; i < sizeof(ts); i++) 588 buf[i] ^= p[i]; 589 590 if (do_lock) 591 mtx_enter(&rndlock); 592 _rs_seed(buf, sizeof(buf)); 593 if (do_lock) 594 mtx_leave(&rndlock); 595 596 explicit_bzero(buf, sizeof(buf)); 597 } 598 599 static inline void 600 _rs_stir_if_needed(size_t len) 601 { 602 if (!rs_initialized) { 603 _rs_init(rs_buf, KEYSZ + IVSZ); 604 rs_count = 1024 * 1024 * 1024; /* until main() runs */ 605 rs_initialized = 1; 606 } else if (rs_count <= len) 607 _rs_stir(0); 608 else 609 rs_count -= len; 610 } 611 612 static inline void 613 _rs_rekey(u_char *dat, size_t datlen) 614 { 615 #ifndef KEYSTREAM_ONLY 616 memset(rs_buf, 0, RSBUFSZ); 617 #endif 618 /* fill rs_buf with the keystream */ 619 chacha_encrypt_bytes(&rs, rs_buf, rs_buf, RSBUFSZ); 620 /* mix in optional user provided data */ 621 if (dat) { 622 size_t i, m; 623 624 m = MIN(datlen, KEYSZ + IVSZ); 625 for (i = 0; i < m; i++) 626 rs_buf[i] ^= dat[i]; 627 } 628 /* immediately reinit for backtracking resistance */ 629 _rs_init(rs_buf, KEYSZ + IVSZ); 630 memset(rs_buf, 0, KEYSZ + IVSZ); 631 rs_have = RSBUFSZ - KEYSZ - IVSZ; 632 } 633 634 static inline void 635 _rs_random_buf(void *_buf, size_t n) 636 { 637 u_char *buf = (u_char *)_buf; 638 size_t m; 639 640 _rs_stir_if_needed(n); 641 while (n > 0) { 642 if (rs_have > 0) { 643 m = MIN(n, rs_have); 644 memcpy(buf, rs_buf + RSBUFSZ - rs_have, m); 645 memset(rs_buf + RSBUFSZ - rs_have, 0, m); 646 buf += m; 647 n -= m; 648 rs_have -= m; 649 } 650 if (rs_have == 0) 651 _rs_rekey(NULL, 0); 652 } 653 } 654 655 static inline void 656 _rs_random_u32(u_int32_t *val) 657 { 658 _rs_stir_if_needed(sizeof(*val)); 659 if (rs_have < sizeof(*val)) 660 _rs_rekey(NULL, 0); 661 memcpy(val, rs_buf + RSBUFSZ - rs_have, sizeof(*val)); 662 memset(rs_buf + RSBUFSZ - rs_have, 0, sizeof(*val)); 663 rs_have -= sizeof(*val); 664 return; 665 } 666 667 /* Return one word of randomness from a ChaCha20 generator */ 668 u_int32_t 669 arc4random(void) 670 { 671 u_int32_t ret; 672 673 mtx_enter(&rndlock); 674 _rs_random_u32(&ret); 675 mtx_leave(&rndlock); 676 return ret; 677 } 678 679 /* 680 * Fill a buffer of arbitrary length with ChaCha20-derived randomness. 681 */ 682 void 683 arc4random_buf(void *buf, size_t n) 684 { 685 mtx_enter(&rndlock); 686 _rs_random_buf(buf, n); 687 mtx_leave(&rndlock); 688 } 689 690 /* 691 * Calculate a uniformly distributed random number less than upper_bound 692 * avoiding "modulo bias". 693 * 694 * Uniformity is achieved by generating new random numbers until the one 695 * returned is outside the range [0, 2**32 % upper_bound). This 696 * guarantees the selected random number will be inside 697 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 698 * after reduction modulo upper_bound. 699 */ 700 u_int32_t 701 arc4random_uniform(u_int32_t upper_bound) 702 { 703 u_int32_t r, min; 704 705 if (upper_bound < 2) 706 return 0; 707 708 /* 2**32 % x == (2**32 - x) % x */ 709 min = -upper_bound % upper_bound; 710 711 /* 712 * This could theoretically loop forever but each retry has 713 * p > 0.5 (worst case, usually far better) of selecting a 714 * number inside the range we need, so it should rarely need 715 * to re-roll. 716 */ 717 for (;;) { 718 r = arc4random(); 719 if (r >= min) 720 break; 721 } 722 723 return r % upper_bound; 724 } 725 726 /* ARGSUSED */ 727 void 728 arc4_init(void *null) 729 { 730 _rs_stir(1); 731 } 732 733 /* 734 * Called by timeout to mark arc4 for stirring, 735 */ 736 void 737 arc4_reinit(void *v) 738 { 739 task_add(systq, &arc4_task); 740 /* 10 minutes, per dm@'s suggestion */ 741 timeout_add_sec(&arc4_timeout, 10 * 60); 742 } 743 744 /* 745 * Start periodic services inside the random subsystem, which pull 746 * entropy forward, hash it, and re-seed the random stream as needed. 747 */ 748 void 749 random_start(void) 750 { 751 #if !defined(NO_PROPOLICE) 752 extern long __guard_local; 753 754 if (__guard_local == 0) 755 printf("warning: no entropy supplied by boot loader\n"); 756 #endif 757 758 rnd_states[RND_SRC_TIMER].dont_count_entropy = 1; 759 rnd_states[RND_SRC_TRUE].dont_count_entropy = 1; 760 rnd_states[RND_SRC_TRUE].max_entropy = 1; 761 762 /* Provide some data from this kernel */ 763 add_entropy_words((u_int32_t *)version, 764 strlen(version) / sizeof(u_int32_t)); 765 766 /* Provide some data from this kernel */ 767 add_entropy_words((u_int32_t *)cfdata, 768 8192 / sizeof(u_int32_t)); 769 770 /* Message buffer may contain data from previous boot */ 771 if (msgbufp->msg_magic == MSG_MAGIC) 772 add_entropy_words((u_int32_t *)msgbufp->msg_bufc, 773 msgbufp->msg_bufs / sizeof(u_int32_t)); 774 775 rs_initialized = 1; 776 dequeue_randomness(NULL); 777 arc4_init(NULL); 778 timeout_set(&arc4_timeout, arc4_reinit, NULL); 779 arc4_reinit(NULL); 780 timeout_set(&rnd_timeout, dequeue_randomness, NULL); 781 } 782 783 int 784 randomopen(dev_t dev, int flag, int mode, struct proc *p) 785 { 786 return 0; 787 } 788 789 int 790 randomclose(dev_t dev, int flag, int mode, struct proc *p) 791 { 792 return 0; 793 } 794 795 /* 796 * Maximum number of bytes to serve directly from the main ChaCha 797 * pool. Larger requests are served from a discrete ChaCha instance keyed 798 * from the main pool. 799 */ 800 #define ARC4_MAIN_MAX_BYTES 2048 801 802 int 803 randomread(dev_t dev, struct uio *uio, int ioflag) 804 { 805 u_char lbuf[KEYSZ+IVSZ]; 806 chacha_ctx lctx; 807 size_t total = uio->uio_resid; 808 u_char *buf; 809 int myctx = 0, ret = 0; 810 811 if (uio->uio_resid == 0) 812 return 0; 813 814 buf = malloc(POOLBYTES, M_TEMP, M_WAITOK); 815 if (total > ARC4_MAIN_MAX_BYTES) { 816 arc4random_buf(lbuf, sizeof(lbuf)); 817 chacha_keysetup(&lctx, lbuf, KEYSZ * 8); 818 chacha_ivsetup(&lctx, lbuf + KEYSZ, NULL); 819 explicit_bzero(lbuf, sizeof(lbuf)); 820 myctx = 1; 821 } 822 823 while (ret == 0 && uio->uio_resid > 0) { 824 size_t n = ulmin(POOLBYTES, uio->uio_resid); 825 826 if (myctx) { 827 #ifndef KEYSTREAM_ONLY 828 memset(buf, 0, n); 829 #endif 830 chacha_encrypt_bytes(&lctx, buf, buf, n); 831 } else 832 arc4random_buf(buf, n); 833 ret = uiomove(buf, n, uio); 834 if (ret == 0 && uio->uio_resid > 0) 835 yield(); 836 } 837 if (myctx) 838 explicit_bzero(&lctx, sizeof(lctx)); 839 explicit_bzero(buf, POOLBYTES); 840 free(buf, M_TEMP, POOLBYTES); 841 return ret; 842 } 843 844 int 845 randomwrite(dev_t dev, struct uio *uio, int flags) 846 { 847 int ret = 0, newdata = 0; 848 u_int32_t *buf; 849 850 if (uio->uio_resid == 0) 851 return 0; 852 853 buf = malloc(POOLBYTES, M_TEMP, M_WAITOK); 854 855 while (ret == 0 && uio->uio_resid > 0) { 856 size_t n = ulmin(POOLBYTES, uio->uio_resid); 857 858 ret = uiomove(buf, n, uio); 859 if (ret != 0) 860 break; 861 while (n % sizeof(u_int32_t)) 862 ((u_int8_t *)buf)[n++] = 0; 863 add_entropy_words(buf, n / 4); 864 if (uio->uio_resid > 0) 865 yield(); 866 newdata = 1; 867 } 868 869 if (newdata) 870 arc4_init(NULL); 871 872 explicit_bzero(buf, POOLBYTES); 873 free(buf, M_TEMP, POOLBYTES); 874 return ret; 875 } 876 877 int 878 randomkqfilter(dev_t dev, struct knote *kn) 879 { 880 switch (kn->kn_filter) { 881 case EVFILT_READ: 882 kn->kn_fop = &randomread_filtops; 883 break; 884 case EVFILT_WRITE: 885 kn->kn_fop = &randomwrite_filtops; 886 break; 887 default: 888 return (EINVAL); 889 } 890 891 return (0); 892 } 893 894 void 895 filt_randomdetach(struct knote *kn) 896 { 897 } 898 899 int 900 filt_randomread(struct knote *kn, long hint) 901 { 902 kn->kn_data = ARC4_MAIN_MAX_BYTES; 903 return (1); 904 } 905 906 int 907 filt_randomwrite(struct knote *kn, long hint) 908 { 909 kn->kn_data = POOLBYTES; 910 return (1); 911 } 912 913 int 914 randomioctl(dev_t dev, u_long cmd, caddr_t data, int flag, struct proc *p) 915 { 916 switch (cmd) { 917 case FIOASYNC: 918 /* No async flag in softc so this is a no-op. */ 919 break; 920 case FIONBIO: 921 /* Handled in the upper FS layer. */ 922 break; 923 default: 924 return ENOTTY; 925 } 926 return 0; 927 } 928 929 int 930 sys_getentropy(struct proc *p, void *v, register_t *retval) 931 { 932 struct sys_getentropy_args /* { 933 syscallarg(void *) buf; 934 syscallarg(size_t) nbyte; 935 } */ *uap = v; 936 char buf[256]; 937 int error; 938 939 if (SCARG(uap, nbyte) > sizeof(buf)) 940 return (EIO); 941 arc4random_buf(buf, SCARG(uap, nbyte)); 942 if ((error = copyout(buf, SCARG(uap, buf), SCARG(uap, nbyte))) != 0) 943 return (error); 944 explicit_bzero(buf, sizeof(buf)); 945 retval[0] = 0; 946 return (0); 947 } 948