1 /* $OpenBSD: rnd.c,v 1.159 2014/07/17 13:38:22 tedu 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 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 MD5 hash. The MD5 hash avoids 68 * exposing the internal state of the entropy pool. Even if it is 69 * possible to analyze MD5 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 MD5 hash will continue to generate 77 * output since there is no true risk because the MD5 output is not 78 * exported outside this subsystem. It is next used as input to seed a 79 * RC4 stream cipher. Attempts are made to follow best practice 80 * regarding this stream cipher - the first chunk of output is discarded 81 * and the cipher is re-seeded from time to time. This design provides 82 * very high amounts of output data from a potentially small entropy 83 * base, at high enough speeds to encourage use of random numbers in 84 * nearly any situation. 85 * 86 * The output of this single RC4 engine is then shared amongst many 87 * consumers in the kernel and userland via a few interfaces: 88 * arc4random_buf(), arc4random(), arc4random_uniform(), randomread() 89 * for the set of /dev/random nodes, and the sysctl kern.arandom. 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 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/conf.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/md5.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 struct rand_event { 218 struct timer_rand_state *re_state; 219 u_int re_nbits; 220 u_int re_time; 221 u_int re_val; 222 } rnd_event_space[QEVLEN]; 223 struct rand_event *rnd_event_head = rnd_event_space; 224 struct rand_event *rnd_event_tail = rnd_event_space; 225 226 struct timeout rnd_timeout; 227 struct rndstats rndstats; 228 229 u_int32_t entropy_pool[POOLWORDS] __attribute__((section(".openbsd.randomdata"))); 230 u_int entropy_add_ptr; 231 u_char entropy_input_rotate; 232 233 void dequeue_randomness(void *); 234 void add_entropy_words(const u_int32_t *, u_int); 235 void extract_entropy(u_int8_t *, int); 236 237 int filt_randomread(struct knote *, long); 238 void filt_randomdetach(struct knote *); 239 int filt_randomwrite(struct knote *, long); 240 241 struct filterops randomread_filtops = 242 { 1, NULL, filt_randomdetach, filt_randomread }; 243 struct filterops randomwrite_filtops = 244 { 1, NULL, filt_randomdetach, filt_randomwrite }; 245 246 static __inline struct rand_event * 247 rnd_get(void) 248 { 249 struct rand_event *p = rnd_event_tail; 250 251 if (p == rnd_event_head) 252 return NULL; 253 254 if (p + 1 >= &rnd_event_space[QEVLEN]) 255 rnd_event_tail = rnd_event_space; 256 else 257 rnd_event_tail++; 258 259 return p; 260 } 261 262 static __inline struct rand_event * 263 rnd_put(void) 264 { 265 struct rand_event *p = rnd_event_head + 1; 266 267 if (p >= &rnd_event_space[QEVLEN]) 268 p = rnd_event_space; 269 270 if (p == rnd_event_tail) 271 return NULL; 272 273 return rnd_event_head = p; 274 } 275 276 static __inline int 277 rnd_qlen(void) 278 { 279 int len = rnd_event_head - rnd_event_tail; 280 return (len < 0)? -len : len; 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 * On the i386, this is assumed to be at most 16 bits, and the high bits 292 * are used for a high-resolution timer. 293 */ 294 void 295 enqueue_randomness(int state, int val) 296 { 297 int delta, delta2, delta3; 298 struct timer_rand_state *p; 299 struct rand_event *rep; 300 struct timespec ts; 301 u_int time, nbits; 302 303 #ifdef DIAGNOSTIC 304 if (state < 0 || state >= RND_SRC_NUM) 305 return; 306 #endif 307 308 if (timeout_initialized(&rnd_timeout)) 309 nanotime(&ts); 310 311 p = &rnd_states[state]; 312 val += state << 13; 313 314 time = (ts.tv_nsec >> 10) + (ts.tv_sec << 20); 315 nbits = 0; 316 317 /* 318 * Calculate the number of bits of randomness that we probably 319 * added. We take into account the first and second order 320 * deltas in order to make our estimate. 321 */ 322 if (!p->dont_count_entropy) { 323 delta = time - p->last_time; 324 delta2 = delta - p->last_delta; 325 delta3 = delta2 - p->last_delta2; 326 327 if (delta < 0) delta = -delta; 328 if (delta2 < 0) delta2 = -delta2; 329 if (delta3 < 0) delta3 = -delta3; 330 if (delta > delta2) delta = delta2; 331 if (delta > delta3) delta = delta3; 332 delta3 = delta >>= 1; 333 /* 334 * delta &= 0xfff; 335 * we don't do it since our time sheet is different from linux 336 */ 337 338 if (delta & 0xffff0000) { 339 nbits = 16; 340 delta >>= 16; 341 } 342 if (delta & 0xff00) { 343 nbits += 8; 344 delta >>= 8; 345 } 346 if (delta & 0xf0) { 347 nbits += 4; 348 delta >>= 4; 349 } 350 if (delta & 0xc) { 351 nbits += 2; 352 delta >>= 2; 353 } 354 if (delta & 2) { 355 nbits += 1; 356 delta >>= 1; 357 } 358 if (delta & 1) 359 nbits++; 360 } else if (p->max_entropy) 361 nbits = 8 * sizeof(val) - 1; 362 363 /* given the multi-order delta logic above, this should never happen */ 364 if (nbits >= 32) 365 return; 366 367 mtx_enter(&entropylock); 368 if (!p->dont_count_entropy) { 369 /* 370 * the logic is to drop low-entropy entries, 371 * in hope for dequeuing to be more randomfull 372 */ 373 if (rnd_qlen() > QEVSLOW && nbits < QEVSBITS) { 374 rndstats.rnd_drople++; 375 goto done; 376 } 377 p->last_time = time; 378 p->last_delta = delta3; 379 p->last_delta2 = delta2; 380 } 381 382 if ((rep = rnd_put()) == NULL) { 383 rndstats.rnd_drops++; 384 goto done; 385 } 386 387 rep->re_state = p; 388 rep->re_nbits = nbits; 389 rep->re_time = ts.tv_nsec ^ (ts.tv_sec << 20); 390 rep->re_val = val; 391 392 rndstats.rnd_enqs++; 393 rndstats.rnd_ed[nbits]++; 394 rndstats.rnd_sc[state]++; 395 rndstats.rnd_sb[state] += nbits; 396 397 if (rnd_qlen() > QEVSLOW/2 && timeout_initialized(&rnd_timeout) && 398 !timeout_pending(&rnd_timeout)) 399 timeout_add(&rnd_timeout, 1); 400 done: 401 mtx_leave(&entropylock); 402 } 403 404 /* 405 * This function adds a byte into the entropy pool. It does not 406 * update the entropy estimate. The caller must do this if appropriate. 407 * 408 * The pool is stirred with a polynomial of degree POOLWORDS over GF(2); 409 * see POOL_TAP[1-4] above 410 * 411 * Rotate the input word by a changing number of bits, to help assure 412 * that all bits in the entropy get toggled. Otherwise, if the pool 413 * is consistently fed small numbers (such as keyboard scan codes) 414 * then the upper bits of the entropy pool will frequently remain 415 * untouched. 416 */ 417 void 418 add_entropy_words(const u_int32_t *buf, u_int n) 419 { 420 /* derived from IEEE 802.3 CRC-32 */ 421 static const u_int32_t twist_table[8] = { 422 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158, 423 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 424 }; 425 426 for (; n--; buf++) { 427 u_int32_t w = (*buf << entropy_input_rotate) | 428 (*buf >> (32 - entropy_input_rotate)); 429 u_int i = entropy_add_ptr = 430 (entropy_add_ptr - 1) & POOLMASK; 431 /* 432 * Normally, we add 7 bits of rotation to the pool. 433 * At the beginning of the pool, add an extra 7 bits 434 * rotation, so that successive passes spread the 435 * input bits across the pool evenly. 436 */ 437 entropy_input_rotate = 438 (entropy_input_rotate + (i ? 7 : 14)) & 31; 439 440 /* XOR pool contents corresponding to polynomial terms */ 441 w ^= entropy_pool[(i + POOL_TAP1) & POOLMASK] ^ 442 entropy_pool[(i + POOL_TAP2) & POOLMASK] ^ 443 entropy_pool[(i + POOL_TAP3) & POOLMASK] ^ 444 entropy_pool[(i + POOL_TAP4) & POOLMASK] ^ 445 entropy_pool[(i + 1) & POOLMASK] ^ 446 entropy_pool[i]; /* + 2^POOLWORDS */ 447 448 entropy_pool[i] = (w >> 3) ^ twist_table[w & 7]; 449 } 450 } 451 452 /* 453 * Pulls entropy out of the queue and throws merges it into the pool 454 * with the CRC. 455 */ 456 /* ARGSUSED */ 457 void 458 dequeue_randomness(void *v) 459 { 460 struct rand_event *rep; 461 u_int32_t buf[2]; 462 u_int nbits; 463 464 mtx_enter(&entropylock); 465 466 if (timeout_initialized(&rnd_timeout)) 467 timeout_del(&rnd_timeout); 468 469 rndstats.rnd_deqs++; 470 while ((rep = rnd_get())) { 471 buf[0] = rep->re_time; 472 buf[1] = rep->re_val; 473 nbits = rep->re_nbits; 474 mtx_leave(&entropylock); 475 476 add_entropy_words(buf, 2); 477 478 mtx_enter(&entropylock); 479 rndstats.rnd_total += nbits; 480 } 481 mtx_leave(&entropylock); 482 } 483 484 /* 485 * Grabs a chunk from the entropy_pool[] and slams it through MD5 when 486 * requested. 487 */ 488 void 489 extract_entropy(u_int8_t *buf, int nbytes) 490 { 491 static u_int32_t extract_pool[POOLWORDS]; 492 u_char buffer[MD5_DIGEST_LENGTH]; 493 MD5_CTX tmp; 494 u_int i; 495 496 add_timer_randomness(nbytes); 497 498 while (nbytes) { 499 i = MIN(nbytes, sizeof(buffer)); 500 501 /* 502 * INTENTIONALLY not protected by entropylock. Races 503 * during bcopy() result in acceptable input data; races 504 * during MD5Update() would create nasty data dependencies. 505 */ 506 bcopy(entropy_pool, extract_pool, 507 sizeof(extract_pool)); 508 509 /* Hash the pool to get the output */ 510 MD5Init(&tmp); 511 MD5Update(&tmp, (u_int8_t *)extract_pool, sizeof(extract_pool)); 512 MD5Final(buffer, &tmp); 513 514 /* Copy data to destination buffer */ 515 bcopy(buffer, buf, i); 516 nbytes -= i; 517 buf += i; 518 519 /* Modify pool so next hash will produce different results */ 520 add_timer_randomness(nbytes); 521 dequeue_randomness(NULL); 522 } 523 524 /* Wipe data from memory */ 525 explicit_bzero(extract_pool, sizeof(extract_pool)); 526 explicit_bzero(&tmp, sizeof(tmp)); 527 explicit_bzero(buffer, sizeof(buffer)); 528 } 529 530 /* random keystream by ChaCha */ 531 532 struct mutex rndlock = MUTEX_INITIALIZER(IPL_HIGH); 533 struct timeout arc4_timeout; 534 struct task arc4_task; 535 536 void arc4_reinit(void *v); /* timeout to start reinit */ 537 void arc4_init(void *, void *); /* actually do the reinit */ 538 539 #define KEYSZ 32 540 #define IVSZ 8 541 #define BLOCKSZ 64 542 #define RSBUFSZ (16*BLOCKSZ) 543 static int rs_initialized; 544 static chacha_ctx rs; /* chacha context for random keystream */ 545 /* keystream blocks (also chacha seed from boot) */ 546 static u_char rs_buf[RSBUFSZ] __attribute__((section(".openbsd.randomdata"))); 547 static size_t rs_have; /* valid bytes at end of rs_buf */ 548 static size_t rs_count; /* bytes till reseed */ 549 550 static inline void _rs_rekey(u_char *dat, size_t datlen); 551 552 static inline void 553 _rs_init(u_char *buf, size_t n) 554 { 555 KASSERT(n >= KEYSZ + IVSZ); 556 chacha_keysetup(&rs, buf, KEYSZ * 8, 0); 557 chacha_ivsetup(&rs, buf + KEYSZ); 558 } 559 560 static void 561 _rs_seed(u_char *buf, size_t n) 562 { 563 _rs_rekey(buf, n); 564 565 /* invalidate rs_buf */ 566 rs_have = 0; 567 memset(rs_buf, 0, RSBUFSZ); 568 569 rs_count = 1600000; 570 } 571 572 static void 573 _rs_stir(int do_lock) 574 { 575 struct timespec ts; 576 u_int8_t buf[KEYSZ + IVSZ], *p; 577 int i; 578 579 /* 580 * Use MD5 PRNG data and a system timespec; early in the boot 581 * process this is the best we can do -- some architectures do 582 * not collect entropy very well during this time, but may have 583 * clock information which is better than nothing. 584 */ 585 extract_entropy((u_int8_t *)buf, sizeof buf); 586 587 nanotime(&ts); 588 for (p = (u_int8_t *)&ts, i = 0; i < sizeof(ts); i++) 589 buf[i] ^= p[i]; 590 591 if (do_lock) 592 mtx_enter(&rndlock); 593 _rs_seed(buf, sizeof(buf)); 594 rndstats.arc4_nstirs++; 595 if (do_lock) 596 mtx_leave(&rndlock); 597 598 explicit_bzero(buf, sizeof(buf)); 599 } 600 601 static inline void 602 _rs_stir_if_needed(size_t len) 603 { 604 if (!rs_initialized) { 605 _rs_init(rs_buf, KEYSZ + IVSZ); 606 rs_count = 1024 * 1024 * 1024; /* until main() runs */ 607 rs_initialized = 1; 608 } else if (rs_count <= len) 609 _rs_stir(0); 610 else 611 rs_count -= len; 612 } 613 614 static inline void 615 _rs_rekey(u_char *dat, size_t datlen) 616 { 617 #ifndef KEYSTREAM_ONLY 618 memset(rs_buf, 0, RSBUFSZ); 619 #endif 620 /* fill rs_buf with the keystream */ 621 chacha_encrypt_bytes(&rs, rs_buf, rs_buf, RSBUFSZ); 622 /* mix in optional user provided data */ 623 if (dat) { 624 size_t i, m; 625 626 m = MIN(datlen, KEYSZ + IVSZ); 627 for (i = 0; i < m; i++) 628 rs_buf[i] ^= dat[i]; 629 } 630 /* immediately reinit for backtracking resistance */ 631 _rs_init(rs_buf, KEYSZ + IVSZ); 632 memset(rs_buf, 0, KEYSZ + IVSZ); 633 rs_have = RSBUFSZ - KEYSZ - IVSZ; 634 } 635 636 static inline void 637 _rs_random_buf(void *_buf, size_t n) 638 { 639 u_char *buf = (u_char *)_buf; 640 size_t m; 641 642 _rs_stir_if_needed(n); 643 while (n > 0) { 644 if (rs_have > 0) { 645 m = MIN(n, rs_have); 646 memcpy(buf, rs_buf + RSBUFSZ - rs_have, m); 647 memset(rs_buf + RSBUFSZ - rs_have, 0, m); 648 buf += m; 649 n -= m; 650 rs_have -= m; 651 } 652 if (rs_have == 0) 653 _rs_rekey(NULL, 0); 654 } 655 } 656 657 static inline void 658 _rs_random_u32(u_int32_t *val) 659 { 660 _rs_stir_if_needed(sizeof(*val)); 661 if (rs_have < sizeof(*val)) 662 _rs_rekey(NULL, 0); 663 memcpy(val, rs_buf + RSBUFSZ - rs_have, sizeof(*val)); 664 memset(rs_buf + RSBUFSZ - rs_have, 0, sizeof(*val)); 665 rs_have -= sizeof(*val); 666 return; 667 } 668 669 /* Return one word of randomness from an RC4 generator */ 670 u_int32_t 671 arc4random(void) 672 { 673 u_int32_t ret; 674 675 mtx_enter(&rndlock); 676 _rs_random_u32(&ret); 677 rndstats.arc4_reads += sizeof(ret); 678 mtx_leave(&rndlock); 679 return ret; 680 } 681 682 /* 683 * Fill a buffer of arbitrary length with RC4-derived randomness. 684 */ 685 void 686 arc4random_buf(void *buf, size_t n) 687 { 688 mtx_enter(&rndlock); 689 _rs_random_buf(buf, n); 690 rndstats.arc4_reads += n; 691 mtx_leave(&rndlock); 692 } 693 694 /* 695 * Calculate a uniformly distributed random number less than upper_bound 696 * avoiding "modulo bias". 697 * 698 * Uniformity is achieved by generating new random numbers until the one 699 * returned is outside the range [0, 2**32 % upper_bound). This 700 * guarantees the selected random number will be inside 701 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 702 * after reduction modulo upper_bound. 703 */ 704 u_int32_t 705 arc4random_uniform(u_int32_t upper_bound) 706 { 707 u_int32_t r, min; 708 709 if (upper_bound < 2) 710 return 0; 711 712 /* 2**32 % x == (2**32 - x) % x */ 713 min = -upper_bound % upper_bound; 714 715 /* 716 * This could theoretically loop forever but each retry has 717 * p > 0.5 (worst case, usually far better) of selecting a 718 * number inside the range we need, so it should rarely need 719 * to re-roll. 720 */ 721 for (;;) { 722 r = arc4random(); 723 if (r >= min) 724 break; 725 } 726 727 return r % upper_bound; 728 } 729 730 /* ARGSUSED */ 731 void 732 arc4_init(void *v, void *w) 733 { 734 _rs_stir(1); 735 } 736 737 /* 738 * Called by timeout to mark arc4 for stirring, 739 */ 740 void 741 arc4_reinit(void *v) 742 { 743 task_add(systq, &arc4_task); 744 /* 10 minutes, per dm@'s suggestion */ 745 timeout_add_sec(&arc4_timeout, 10 * 60); 746 } 747 748 /* 749 * Start periodic services inside the random subsystem, which pull 750 * entropy forward, hash it, and re-seed the random stream as needed. 751 */ 752 void 753 random_start(void) 754 { 755 #if !defined(NO_PROPOLICE) 756 extern long __guard_local; 757 758 if (__guard_local == 0) 759 printf("warning: no entropy supplied by boot loader\n"); 760 #endif 761 762 rnd_states[RND_SRC_TIMER].dont_count_entropy = 1; 763 rnd_states[RND_SRC_TRUE].dont_count_entropy = 1; 764 rnd_states[RND_SRC_TRUE].max_entropy = 1; 765 766 /* Provide some data from this kernel */ 767 add_entropy_words((u_int32_t *)version, 768 strlen(version) / sizeof(u_int32_t)); 769 770 /* Provide some data from this kernel */ 771 add_entropy_words((u_int32_t *)cfdata, 772 8192 / sizeof(u_int32_t)); 773 774 /* Message buffer may contain data from previous boot */ 775 if (msgbufp->msg_magic == MSG_MAGIC) 776 add_entropy_words((u_int32_t *)msgbufp->msg_bufc, 777 msgbufp->msg_bufs / sizeof(u_int32_t)); 778 779 rs_initialized = 1; 780 dequeue_randomness(NULL); 781 arc4_init(NULL, NULL); 782 task_set(&arc4_task, arc4_init, NULL, NULL); 783 timeout_set(&arc4_timeout, arc4_reinit, NULL); 784 arc4_reinit(NULL); 785 timeout_set(&rnd_timeout, dequeue_randomness, NULL); 786 } 787 788 int 789 randomopen(dev_t dev, int flag, int mode, struct proc *p) 790 { 791 return 0; 792 } 793 794 int 795 randomclose(dev_t dev, int flag, int mode, struct proc *p) 796 { 797 return 0; 798 } 799 800 /* 801 * Maximum number of bytes to serve directly from the main ChaCha 802 * pool. Larger requests are served from a discrete ChaCha instance keyed 803 * from the main pool. 804 */ 805 #define ARC4_MAIN_MAX_BYTES 2048 806 807 int 808 randomread(dev_t dev, struct uio *uio, int ioflag) 809 { 810 u_char lbuf[KEYSZ+IVSZ]; 811 chacha_ctx lctx; 812 size_t total = uio->uio_resid; 813 u_char *buf; 814 int myctx = 0, ret = 0; 815 816 if (uio->uio_resid == 0) 817 return 0; 818 819 buf = malloc(POOLBYTES, M_TEMP, M_WAITOK); 820 if (total > ARC4_MAIN_MAX_BYTES) { 821 arc4random_buf(lbuf, sizeof(lbuf)); 822 chacha_keysetup(&lctx, lbuf, KEYSZ * 8, 0); 823 chacha_ivsetup(&lctx, lbuf + KEYSZ); 824 explicit_bzero(lbuf, sizeof(lbuf)); 825 myctx = 1; 826 } 827 828 while (ret == 0 && uio->uio_resid > 0) { 829 int n = min(POOLBYTES, uio->uio_resid); 830 831 if (myctx) { 832 #ifndef KEYSTREAM_ONLY 833 memset(buf, 0, n); 834 #endif 835 chacha_encrypt_bytes(&lctx, buf, buf, n); 836 } else 837 arc4random_buf(buf, n); 838 ret = uiomove(buf, n, uio); 839 if (ret == 0 && uio->uio_resid > 0) 840 yield(); 841 } 842 if (myctx) 843 explicit_bzero(&lctx, sizeof(lctx)); 844 explicit_bzero(buf, POOLBYTES); 845 free(buf, M_TEMP, 0); 846 return ret; 847 } 848 849 int 850 randomwrite(dev_t dev, struct uio *uio, int flags) 851 { 852 int ret = 0, newdata = 0; 853 u_int32_t *buf; 854 855 if (uio->uio_resid == 0) 856 return 0; 857 858 buf = malloc(POOLBYTES, M_TEMP, M_WAITOK); 859 860 while (ret == 0 && uio->uio_resid > 0) { 861 int n = min(POOLBYTES, uio->uio_resid); 862 863 ret = uiomove(buf, n, uio); 864 if (ret != 0) 865 break; 866 while (n % sizeof(u_int32_t)) 867 ((u_int8_t *)buf)[n++] = 0; 868 add_entropy_words(buf, n / 4); 869 if (uio->uio_resid > 0) 870 yield(); 871 newdata = 1; 872 } 873 874 if (newdata) 875 arc4_init(NULL, NULL); 876 877 explicit_bzero(buf, POOLBYTES); 878 free(buf, M_TEMP, 0); 879 return ret; 880 } 881 882 int 883 randomkqfilter(dev_t dev, struct knote *kn) 884 { 885 switch (kn->kn_filter) { 886 case EVFILT_READ: 887 kn->kn_fop = &randomread_filtops; 888 break; 889 case EVFILT_WRITE: 890 kn->kn_fop = &randomwrite_filtops; 891 break; 892 default: 893 return (EINVAL); 894 } 895 896 return (0); 897 } 898 899 void 900 filt_randomdetach(struct knote *kn) 901 { 902 } 903 904 int 905 filt_randomread(struct knote *kn, long hint) 906 { 907 kn->kn_data = ARC4_MAIN_MAX_BYTES; 908 return (1); 909 } 910 911 int 912 filt_randomwrite(struct knote *kn, long hint) 913 { 914 kn->kn_data = POOLBYTES; 915 return (1); 916 } 917 918 int 919 randomioctl(dev_t dev, u_long cmd, caddr_t data, int flag, struct proc *p) 920 { 921 switch (cmd) { 922 case FIOASYNC: 923 /* No async flag in softc so this is a no-op. */ 924 break; 925 case FIONBIO: 926 /* Handled in the upper FS layer. */ 927 break; 928 default: 929 return ENOTTY; 930 } 931 return 0; 932 } 933 934 int 935 sys_getentropy(struct proc *p, void *v, register_t *retval) 936 { 937 struct sys_getentropy_args /* { 938 syscallarg(void *) buf; 939 syscallarg(size_t) nbyte; 940 } */ *uap = v; 941 char buf[256]; 942 int error; 943 944 if (SCARG(uap, nbyte) > sizeof(buf)) 945 return (EIO); 946 arc4random_buf(buf, SCARG(uap, nbyte)); 947 if ((error = copyout(buf, SCARG(uap, buf), SCARG(uap, nbyte))) != 0) 948 return (error); 949 explicit_bzero(buf, sizeof(buf)); 950 retval[0] = 0; 951 return (0); 952 } 953