1 /* $OpenBSD: rnd.c,v 1.155 2014/02/05 05:54:58 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 127 #include <crypto/md5.h> 128 129 #define KEYSTREAM_ONLY 130 #include <crypto/chacha_private.h> 131 132 #include <dev/rndvar.h> 133 134 /* 135 * For the purposes of better mixing, we use the CRC-32 polynomial as 136 * well to make a twisted Generalized Feedback Shift Register 137 * 138 * (See M. Matsumoto & Y. Kurita, 1992. Twisted GFSR generators. ACM 139 * Transactions on Modeling and Computer Simulation 2(3):179-194. 140 * Also see M. Matsumoto & Y. Kurita, 1994. Twisted GFSR generators 141 * II. ACM Transactions on Mdeling and Computer Simulation 4:254-266) 142 * 143 * Thanks to Colin Plumb for suggesting this. 144 * 145 * We have not analyzed the resultant polynomial to prove it primitive; 146 * in fact it almost certainly isn't. Nonetheless, the irreducible factors 147 * of a random large-degree polynomial over GF(2) are more than large enough 148 * that periodicity is not a concern. 149 * 150 * The input hash is much less sensitive than the output hash. All 151 * we want from it is to be a good non-cryptographic hash - 152 * i.e. to not produce collisions when fed "random" data of the sort 153 * we expect to see. As long as the pool state differs for different 154 * inputs, we have preserved the input entropy and done a good job. 155 * The fact that an intelligent attacker can construct inputs that 156 * will produce controlled alterations to the pool's state is not 157 * important because we don't consider such inputs to contribute any 158 * randomness. The only property we need with respect to them is that 159 * the attacker can't increase his/her knowledge of the pool's state. 160 * Since all additions are reversible (knowing the final state and the 161 * input, you can reconstruct the initial state), if an attacker has 162 * any uncertainty about the initial state, he/she can only shuffle 163 * that uncertainty about, but never cause any collisions (which would 164 * decrease the uncertainty). 165 * 166 * The chosen system lets the state of the pool be (essentially) the input 167 * modulo the generator polynomial. Now, for random primitive polynomials, 168 * this is a universal class of hash functions, meaning that the chance 169 * of a collision is limited by the attacker's knowledge of the generator 170 * polynomial, so if it is chosen at random, an attacker can never force 171 * a collision. Here, we use a fixed polynomial, but we *can* assume that 172 * ###--> it is unknown to the processes generating the input entropy. <-### 173 * Because of this important property, this is a good, collision-resistant 174 * hash; hash collisions will occur no more often than chance. 175 */ 176 177 /* 178 * Stirring polynomials over GF(2) for various pool sizes. Used in 179 * add_entropy_words() below. 180 * 181 * The polynomial terms are chosen to be evenly spaced (minimum RMS 182 * distance from evenly spaced; except for the last tap, which is 1 to 183 * get the twisting happening as fast as possible. 184 * 185 * The reultant polynomial is: 186 * 2^POOLWORDS + 2^POOL_TAP1 + 2^POOL_TAP2 + 2^POOL_TAP3 + 2^POOL_TAP4 + 1 187 */ 188 #define POOLWORDS 2048 189 #define POOLBYTES (POOLWORDS*4) 190 #define POOLMASK (POOLWORDS - 1) 191 #define POOL_TAP1 1638 192 #define POOL_TAP2 1231 193 #define POOL_TAP3 819 194 #define POOL_TAP4 411 195 196 struct mutex entropylock = MUTEX_INITIALIZER(IPL_HIGH); 197 198 /* 199 * Raw entropy collection from device drivers; at interrupt context or not. 200 * add_*_randomness() provide data which is put into the entropy queue. 201 * Almost completely under the entropylock. 202 */ 203 struct timer_rand_state { /* There is one of these per entropy source */ 204 u_int last_time; 205 u_int last_delta; 206 u_int last_delta2; 207 u_int dont_count_entropy : 1; 208 u_int max_entropy : 1; 209 } rnd_states[RND_SRC_NUM]; 210 211 #define QEVLEN (1024 / sizeof(struct rand_event)) 212 #define QEVSLOW (QEVLEN * 3 / 4) /* yet another 0.75 for 60-minutes hour /-; */ 213 #define QEVSBITS 10 214 215 struct rand_event { 216 struct timer_rand_state *re_state; 217 u_int re_nbits; 218 u_int re_time; 219 u_int re_val; 220 } rnd_event_space[QEVLEN]; 221 struct rand_event *rnd_event_head = rnd_event_space; 222 struct rand_event *rnd_event_tail = rnd_event_space; 223 224 struct timeout rnd_timeout; 225 struct rndstats rndstats; 226 227 u_int32_t entropy_pool[POOLWORDS] __attribute__((section(".openbsd.randomdata"))); 228 u_int entropy_add_ptr; 229 u_char entropy_input_rotate; 230 231 void dequeue_randomness(void *); 232 void add_entropy_words(const u_int32_t *, u_int); 233 void extract_entropy(u_int8_t *, int); 234 235 int filt_randomread(struct knote *, long); 236 void filt_randomdetach(struct knote *); 237 int filt_randomwrite(struct knote *, long); 238 239 struct filterops randomread_filtops = 240 { 1, NULL, filt_randomdetach, filt_randomread }; 241 struct filterops randomwrite_filtops = 242 { 1, NULL, filt_randomdetach, filt_randomwrite }; 243 244 static __inline struct rand_event * 245 rnd_get(void) 246 { 247 struct rand_event *p = rnd_event_tail; 248 249 if (p == rnd_event_head) 250 return NULL; 251 252 if (p + 1 >= &rnd_event_space[QEVLEN]) 253 rnd_event_tail = rnd_event_space; 254 else 255 rnd_event_tail++; 256 257 return p; 258 } 259 260 static __inline struct rand_event * 261 rnd_put(void) 262 { 263 struct rand_event *p = rnd_event_head + 1; 264 265 if (p >= &rnd_event_space[QEVLEN]) 266 p = rnd_event_space; 267 268 if (p == rnd_event_tail) 269 return NULL; 270 271 return rnd_event_head = p; 272 } 273 274 static __inline int 275 rnd_qlen(void) 276 { 277 int len = rnd_event_head - rnd_event_tail; 278 return (len < 0)? -len : len; 279 } 280 281 /* 282 * This function adds entropy to the entropy pool by using timing 283 * delays. It uses the timer_rand_state structure to make an estimate 284 * of how many bits of entropy this call has added to the pool. 285 * 286 * The number "val" is also added to the pool - it should somehow describe 287 * the type of event which just happened. Currently the values of 0-255 288 * are for keyboard scan codes, 256 and upwards - for interrupts. 289 * On the i386, this is assumed to be at most 16 bits, and the high bits 290 * are used for a high-resolution timer. 291 */ 292 void 293 enqueue_randomness(int state, 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 < 0 || 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 /* 368 * the logic is to drop low-entropy entries, 369 * in hope for dequeuing to be more randomfull 370 */ 371 if (rnd_qlen() > QEVSLOW && nbits < QEVSBITS) { 372 rndstats.rnd_drople++; 373 goto done; 374 } 375 p->last_time = time; 376 p->last_delta = delta3; 377 p->last_delta2 = delta2; 378 } 379 380 if ((rep = rnd_put()) == NULL) { 381 rndstats.rnd_drops++; 382 goto done; 383 } 384 385 rep->re_state = p; 386 rep->re_nbits = nbits; 387 rep->re_time = ts.tv_nsec ^ (ts.tv_sec << 20); 388 rep->re_val = val; 389 390 rndstats.rnd_enqs++; 391 rndstats.rnd_ed[nbits]++; 392 rndstats.rnd_sc[state]++; 393 rndstats.rnd_sb[state] += nbits; 394 395 if (rnd_qlen() > QEVSLOW/2 && timeout_initialized(&rnd_timeout) && 396 !timeout_pending(&rnd_timeout)) 397 timeout_add(&rnd_timeout, 1); 398 done: 399 mtx_leave(&entropylock); 400 } 401 402 /* 403 * This function adds a byte into the entropy pool. It does not 404 * update the entropy estimate. The caller must do this if appropriate. 405 * 406 * The pool is stirred with a polynomial of degree POOLWORDS over GF(2); 407 * see POOL_TAP[1-4] above 408 * 409 * Rotate the input word by a changing number of bits, to help assure 410 * that all bits in the entropy get toggled. Otherwise, if the pool 411 * is consistently fed small numbers (such as keyboard scan codes) 412 * then the upper bits of the entropy pool will frequently remain 413 * untouched. 414 */ 415 void 416 add_entropy_words(const u_int32_t *buf, u_int n) 417 { 418 /* derived from IEEE 802.3 CRC-32 */ 419 static const u_int32_t twist_table[8] = { 420 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158, 421 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 422 }; 423 424 for (; n--; buf++) { 425 u_int32_t w = (*buf << entropy_input_rotate) | 426 (*buf >> (32 - entropy_input_rotate)); 427 u_int i = entropy_add_ptr = 428 (entropy_add_ptr - 1) & POOLMASK; 429 /* 430 * Normally, we add 7 bits of rotation to the pool. 431 * At the beginning of the pool, add an extra 7 bits 432 * rotation, so that successive passes spread the 433 * input bits across the pool evenly. 434 */ 435 entropy_input_rotate = 436 (entropy_input_rotate + (i ? 7 : 14)) & 31; 437 438 /* XOR pool contents corresponding to polynomial terms */ 439 w ^= entropy_pool[(i + POOL_TAP1) & POOLMASK] ^ 440 entropy_pool[(i + POOL_TAP2) & POOLMASK] ^ 441 entropy_pool[(i + POOL_TAP3) & POOLMASK] ^ 442 entropy_pool[(i + POOL_TAP4) & POOLMASK] ^ 443 entropy_pool[(i + 1) & POOLMASK] ^ 444 entropy_pool[i]; /* + 2^POOLWORDS */ 445 446 entropy_pool[i] = (w >> 3) ^ twist_table[w & 7]; 447 } 448 } 449 450 /* 451 * Pulls entropy out of the queue and throws merges it into the pool 452 * with the CRC. 453 */ 454 /* ARGSUSED */ 455 void 456 dequeue_randomness(void *v) 457 { 458 struct rand_event *rep; 459 u_int32_t buf[2]; 460 u_int nbits; 461 462 mtx_enter(&entropylock); 463 464 if (timeout_initialized(&rnd_timeout)) 465 timeout_del(&rnd_timeout); 466 467 rndstats.rnd_deqs++; 468 while ((rep = rnd_get())) { 469 buf[0] = rep->re_time; 470 buf[1] = rep->re_val; 471 nbits = rep->re_nbits; 472 mtx_leave(&entropylock); 473 474 add_entropy_words(buf, 2); 475 476 mtx_enter(&entropylock); 477 rndstats.rnd_total += nbits; 478 } 479 mtx_leave(&entropylock); 480 } 481 482 /* 483 * Grabs a chunk from the entropy_pool[] and slams it through MD5 when 484 * requested. 485 */ 486 void 487 extract_entropy(u_int8_t *buf, int nbytes) 488 { 489 static u_int32_t extract_pool[POOLWORDS]; 490 u_char buffer[MD5_DIGEST_LENGTH]; 491 MD5_CTX tmp; 492 u_int i; 493 494 add_timer_randomness(nbytes); 495 496 while (nbytes) { 497 i = MIN(nbytes, sizeof(buffer)); 498 499 /* 500 * INTENTIONALLY not protected by entropylock. Races 501 * during bcopy() result in acceptable input data; races 502 * during MD5Update() would create nasty data dependencies. 503 */ 504 bcopy(entropy_pool, extract_pool, 505 sizeof(extract_pool)); 506 507 /* Hash the pool to get the output */ 508 MD5Init(&tmp); 509 MD5Update(&tmp, (u_int8_t *)extract_pool, sizeof(extract_pool)); 510 MD5Final(buffer, &tmp); 511 512 /* Copy data to destination buffer */ 513 bcopy(buffer, buf, i); 514 nbytes -= i; 515 buf += i; 516 517 /* Modify pool so next hash will produce different results */ 518 add_timer_randomness(nbytes); 519 dequeue_randomness(NULL); 520 } 521 522 /* Wipe data from memory */ 523 explicit_bzero(extract_pool, sizeof(extract_pool)); 524 explicit_bzero(&tmp, sizeof(tmp)); 525 explicit_bzero(buffer, sizeof(buffer)); 526 } 527 528 /* random keystream by ChaCha */ 529 530 struct mutex rndlock = MUTEX_INITIALIZER(IPL_HIGH); 531 struct timeout arc4_timeout; 532 struct task arc4_task; 533 534 void arc4_reinit(void *v); /* timeout to start reinit */ 535 void arc4_init(void *, void *); /* actually do the reinit */ 536 537 #define KEYSZ 32 538 #define IVSZ 8 539 #define BLOCKSZ 64 540 #define RSBUFSZ (16*BLOCKSZ) 541 static int rs_initialized; 542 static chacha_ctx rs; /* chacha context for random keystream */ 543 /* keystream blocks (also chacha seed from boot) */ 544 static u_char rs_buf[RSBUFSZ] __attribute__((section(".openbsd.randomdata"))); 545 static size_t rs_have; /* valid bytes at end of rs_buf */ 546 static size_t rs_count; /* bytes till reseed */ 547 548 static inline void _rs_rekey(u_char *dat, size_t datlen); 549 550 static inline void 551 _rs_init(u_char *buf, size_t n) 552 { 553 KASSERT(n >= KEYSZ + IVSZ); 554 chacha_keysetup(&rs, buf, KEYSZ * 8, 0); 555 chacha_ivsetup(&rs, buf + KEYSZ); 556 } 557 558 static void 559 _rs_seed(u_char *buf, size_t n) 560 { 561 _rs_rekey(buf, n); 562 563 /* invalidate rs_buf */ 564 rs_have = 0; 565 memset(rs_buf, 0, RSBUFSZ); 566 567 rs_count = 1600000; 568 } 569 570 static void 571 _rs_stir(int do_lock) 572 { 573 struct timespec ts; 574 u_int8_t buf[KEYSZ + IVSZ], *p; 575 int i; 576 577 /* 578 * Use MD5 PRNG data and a system timespec; early in the boot 579 * process this is the best we can do -- some architectures do 580 * not collect entropy very well during this time, but may have 581 * clock information which is better than nothing. 582 */ 583 extract_entropy((u_int8_t *)buf, sizeof buf); 584 585 nanotime(&ts); 586 for (p = (u_int8_t *)&ts, i = 0; i < sizeof(ts); i++) 587 buf[i] ^= p[i]; 588 589 if (do_lock) 590 mtx_enter(&rndlock); 591 _rs_seed(buf, sizeof(buf)); 592 rndstats.arc4_nstirs++; 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 an RC4 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 rndstats.arc4_reads += sizeof(ret); 676 mtx_leave(&rndlock); 677 return ret; 678 } 679 680 /* 681 * Fill a buffer of arbitrary length with RC4-derived randomness. 682 */ 683 void 684 arc4random_buf(void *buf, size_t n) 685 { 686 mtx_enter(&rndlock); 687 _rs_random_buf(buf, n); 688 rndstats.arc4_reads += n; 689 mtx_leave(&rndlock); 690 } 691 692 /* 693 * Calculate a uniformly distributed random number less than upper_bound 694 * avoiding "modulo bias". 695 * 696 * Uniformity is achieved by generating new random numbers until the one 697 * returned is outside the range [0, 2**32 % upper_bound). This 698 * guarantees the selected random number will be inside 699 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 700 * after reduction modulo upper_bound. 701 */ 702 u_int32_t 703 arc4random_uniform(u_int32_t upper_bound) 704 { 705 u_int32_t r, min; 706 707 if (upper_bound < 2) 708 return 0; 709 710 /* 2**32 % x == (2**32 - x) % x */ 711 min = -upper_bound % upper_bound; 712 713 /* 714 * This could theoretically loop forever but each retry has 715 * p > 0.5 (worst case, usually far better) of selecting a 716 * number inside the range we need, so it should rarely need 717 * to re-roll. 718 */ 719 for (;;) { 720 r = arc4random(); 721 if (r >= min) 722 break; 723 } 724 725 return r % upper_bound; 726 } 727 728 /* ARGSUSED */ 729 void 730 arc4_init(void *v, void *w) 731 { 732 _rs_stir(1); 733 } 734 735 /* 736 * Called by timeout to mark arc4 for stirring, 737 */ 738 void 739 arc4_reinit(void *v) 740 { 741 task_add(systq, &arc4_task); 742 /* 10 minutes, per dm@'s suggestion */ 743 timeout_add_sec(&arc4_timeout, 10 * 60); 744 } 745 746 /* 747 * Start periodic services inside the random subsystem, which pull 748 * entropy forward, hash it, and re-seed the random stream as needed. 749 */ 750 void 751 random_start(void) 752 { 753 #if !defined(NO_PROPOLICE) 754 extern long __guard_local; 755 756 if (__guard_local == 0) 757 printf("warning: no entropy supplied by boot loader\n"); 758 #endif 759 760 rnd_states[RND_SRC_TIMER].dont_count_entropy = 1; 761 rnd_states[RND_SRC_TRUE].dont_count_entropy = 1; 762 rnd_states[RND_SRC_TRUE].max_entropy = 1; 763 764 /* Provide some data from this kernel */ 765 add_entropy_words((u_int32_t *)version, 766 strlen(version) / sizeof(u_int32_t)); 767 768 /* Provide some data from this kernel */ 769 add_entropy_words((u_int32_t *)cfdata, 770 8192 / sizeof(u_int32_t)); 771 772 /* Message buffer may contain data from previous boot */ 773 if (msgbufp->msg_magic == MSG_MAGIC) 774 add_entropy_words((u_int32_t *)msgbufp->msg_bufc, 775 msgbufp->msg_bufs / sizeof(u_int32_t)); 776 777 rs_initialized = 1; 778 dequeue_randomness(NULL); 779 arc4_init(NULL, NULL); 780 task_set(&arc4_task, arc4_init, NULL, NULL); 781 timeout_set(&arc4_timeout, arc4_reinit, NULL); 782 arc4_reinit(NULL); 783 timeout_set(&rnd_timeout, dequeue_randomness, NULL); 784 } 785 786 int 787 randomopen(dev_t dev, int flag, int mode, struct proc *p) 788 { 789 return 0; 790 } 791 792 int 793 randomclose(dev_t dev, int flag, int mode, struct proc *p) 794 { 795 return 0; 796 } 797 798 /* 799 * Maximum number of bytes to serve directly from the main ChaCha 800 * pool. Larger requests are served from a discrete ChaCha instance keyed 801 * from the main pool. 802 */ 803 #define ARC4_MAIN_MAX_BYTES 2048 804 805 int 806 randomread(dev_t dev, struct uio *uio, int ioflag) 807 { 808 u_char lbuf[KEYSZ+IVSZ]; 809 chacha_ctx lctx; 810 size_t total = uio->uio_resid; 811 u_char *buf; 812 int myctx = 0, ret = 0; 813 814 if (uio->uio_resid == 0) 815 return 0; 816 817 buf = malloc(POOLBYTES, M_TEMP, M_WAITOK); 818 if (total > ARC4_MAIN_MAX_BYTES) { 819 arc4random_buf(lbuf, sizeof(lbuf)); 820 chacha_keysetup(&lctx, lbuf, KEYSZ * 8, 0); 821 chacha_ivsetup(&lctx, lbuf + KEYSZ); 822 explicit_bzero(lbuf, sizeof(lbuf)); 823 myctx = 1; 824 } 825 826 while (ret == 0 && uio->uio_resid > 0) { 827 int n = min(POOLBYTES, uio->uio_resid); 828 829 if (myctx) { 830 #ifndef KEYSTREAM_ONLY 831 memset(buf, 0, n); 832 #endif 833 chacha_encrypt_bytes(&lctx, buf, buf, n); 834 } else 835 arc4random_buf(buf, n); 836 ret = uiomove(buf, n, uio); 837 if (ret == 0 && uio->uio_resid > 0) 838 yield(); 839 } 840 if (myctx) 841 explicit_bzero(&lctx, sizeof(lctx)); 842 explicit_bzero(buf, POOLBYTES); 843 free(buf, M_TEMP); 844 return ret; 845 } 846 847 int 848 randomwrite(dev_t dev, struct uio *uio, int flags) 849 { 850 int ret = 0, newdata = 0; 851 u_int32_t *buf; 852 853 if (uio->uio_resid == 0) 854 return 0; 855 856 buf = malloc(POOLBYTES, M_TEMP, M_WAITOK); 857 858 while (ret == 0 && uio->uio_resid > 0) { 859 int n = min(POOLBYTES, uio->uio_resid); 860 861 ret = uiomove(buf, n, uio); 862 if (ret != 0) 863 break; 864 while (n % sizeof(u_int32_t)) 865 ((u_int8_t *)buf)[n++] = 0; 866 add_entropy_words(buf, n / 4); 867 if (uio->uio_resid > 0) 868 yield(); 869 newdata = 1; 870 } 871 872 if (newdata) 873 arc4_init(NULL, NULL); 874 875 explicit_bzero(buf, POOLBYTES); 876 free(buf, M_TEMP); 877 return ret; 878 } 879 880 int 881 randomkqfilter(dev_t dev, struct knote *kn) 882 { 883 switch (kn->kn_filter) { 884 case EVFILT_READ: 885 kn->kn_fop = &randomread_filtops; 886 break; 887 case EVFILT_WRITE: 888 kn->kn_fop = &randomwrite_filtops; 889 break; 890 default: 891 return (EINVAL); 892 } 893 894 return (0); 895 } 896 897 void 898 filt_randomdetach(struct knote *kn) 899 { 900 } 901 902 int 903 filt_randomread(struct knote *kn, long hint) 904 { 905 kn->kn_data = ARC4_MAIN_MAX_BYTES; 906 return (1); 907 } 908 909 int 910 filt_randomwrite(struct knote *kn, long hint) 911 { 912 kn->kn_data = POOLBYTES; 913 return (1); 914 } 915 916 int 917 randomioctl(dev_t dev, u_long cmd, caddr_t data, int flag, struct proc *p) 918 { 919 switch (cmd) { 920 case FIOASYNC: 921 /* No async flag in softc so this is a no-op. */ 922 break; 923 case FIONBIO: 924 /* Handled in the upper FS layer. */ 925 break; 926 default: 927 return ENOTTY; 928 } 929 return 0; 930 } 931