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