1 /* $OpenBSD: rnd.c,v 1.50 2001/09/24 02:23:44 mickey Exp $ */ 2 3 /* 4 * random.c -- A strong random number generator 5 * 6 * Copyright (c) 1996, 1997, 2000, 2001 Michael Shalayeff. 7 * 8 * Version 1.89, last modified 19-Sep-99 9 * 10 * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999. 11 * All rights reserved. 12 * 13 * Redistribution and use in source and binary forms, with or without 14 * modification, are permitted provided that the following conditions 15 * are met: 16 * 1. Redistributions of source code must retain the above copyright 17 * notice, and the entire permission notice in its entirety, 18 * including the disclaimer of warranties. 19 * 2. Redistributions in binary form must reproduce the above copyright 20 * notice, this list of conditions and the following disclaimer in the 21 * documentation and/or other materials provided with the distribution. 22 * 3. The name of the author may not be used to endorse or promote 23 * products derived from this software without specific prior 24 * written permission. 25 * 26 * ALTERNATIVELY, this product may be distributed under the terms of 27 * the GNU Public License, in which case the provisions of the GPL are 28 * required INSTEAD OF the above restrictions. (This clause is 29 * necessary due to a potential bad interaction between the GPL and 30 * the restrictions contained in a BSD-style copyright.) 31 * 32 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED 33 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 34 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 35 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, 36 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 37 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 38 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 39 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 40 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 41 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 42 * OF THE POSSIBILITY OF SUCH DAMAGE. 43 */ 44 45 /* 46 * (now, with legal B.S. out of the way.....) 47 * 48 * This routine gathers environmental noise from device drivers, etc., 49 * and returns good random numbers, suitable for cryptographic use. 50 * Besides the obvious cryptographic uses, these numbers are also good 51 * for seeding TCP sequence numbers, and other places where it is 52 * desirable to have numbers which are not only random, but hard to 53 * predict by an attacker. 54 * 55 * Theory of operation 56 * =================== 57 * 58 * Computers are very predictable devices. Hence it is extremely hard 59 * to produce truly random numbers on a computer --- as opposed to 60 * pseudo-random numbers, which can easily generated by using a 61 * algorithm. Unfortunately, it is very easy for attackers to guess 62 * the sequence of pseudo-random number generators, and for some 63 * applications this is not acceptable. So instead, we must try to 64 * gather "environmental noise" from the computer's environment, which 65 * must be hard for outside attackers to observe, and use that to 66 * generate random numbers. In a Unix environment, this is best done 67 * from inside the kernel. 68 * 69 * Sources of randomness from the environment include inter-keyboard 70 * timings, inter-interrupt timings from some interrupts, and other 71 * events which are both (a) non-deterministic and (b) hard for an 72 * outside observer to measure. Randomness from these sources are 73 * added to an "entropy pool", which is mixed using a CRC-like function. 74 * This is not cryptographically strong, but it is adequate assuming 75 * the randomness is not chosen maliciously, and it is fast enough that 76 * the overhead of doing it on every interrupt is very reasonable. 77 * As random bytes are mixed into the entropy pool, the routines keep 78 * an *estimate* of how many bits of randomness have been stored into 79 * the random number generator's internal state. 80 * 81 * When random bytes are desired, they are obtained by taking the MD5 82 * hash of the contents of the "entropy pool". The MD5 hash avoids 83 * exposing the internal state of the entropy pool. It is believed to 84 * be computationally infeasible to derive any useful information 85 * about the input of MD5 from its output. Even if it is possible to 86 * analyze MD5 in some clever way, as long as the amount of data 87 * returned from the generator is less than the inherent entropy in 88 * the pool, the output data is totally unpredictable. For this 89 * reason, the routine decreases its internal estimate of how many 90 * bits of "true randomness" are contained in the entropy pool as it 91 * outputs random numbers. 92 * 93 * If this estimate goes to zero, the routine can still generate 94 * random numbers; however, an attacker may (at least in theory) be 95 * able to infer the future output of the generator from prior 96 * outputs. This requires successful cryptanalysis of MD5, which is 97 * not believed to be feasible, but there is a remote possibility. 98 * Nonetheless, these numbers should be useful for the vast majority 99 * of purposes. 100 * 101 * Exported interfaces ---- output 102 * =============================== 103 * 104 * There are three exported interfaces; the first is one designed to 105 * be used from within the kernel: 106 * 107 * void get_random_bytes(void *buf, int nbytes); 108 * 109 * This interface will return the requested number of random bytes, 110 * and place it in the requested buffer. 111 * 112 * The two other interfaces are two character devices /dev/random and 113 * /dev/urandom. /dev/random is suitable for use when very high 114 * quality randomness is desired (for example, for key generation or 115 * one-time pads), as it will only return a maximum of the number of 116 * bits of randomness (as estimated by the random number generator) 117 * contained in the entropy pool. 118 * 119 * The /dev/urandom device does not have this limit, and will return 120 * as many bytes as are requested. As more and more random bytes are 121 * requested without giving time for the entropy pool to recharge, 122 * this will result in random numbers that are merely cryptographically 123 * strong. For many applications, however, this is acceptable. 124 * 125 * Exported interfaces ---- input 126 * ============================== 127 * 128 * The current exported interfaces for gathering environmental noise 129 * from the devices are: 130 * 131 * void add_true_randomness(int data); 132 * void add_timer_randomness(int data); 133 * void add_mouse_randomness(int mouse_data); 134 * void add_net_randomness(int isr); 135 * void add_tty_randomness(int c); 136 * void add_disk_randomness(int n); 137 * void add_audio_randomness(int n); 138 * 139 * add_true_randomness() uses true random number generators present 140 * on some cryptographic and system chipsets. entropy accounting 141 * is not quitable, no timing is done, supplied 32 bits of pure entropy 142 * are hashed into the pool plain and blindly, increasing the counter. 143 * 144 * add_timer_randomness() uses the random driver itselves timing, 145 * measuring extract_entropy() and rndioctl() execution times. 146 * 147 * add_mouse_randomness() uses the mouse interrupt timing, as well as 148 * the reported position of the mouse from the hardware. 149 * 150 * add_net_randomness() times the finishing time of net input. 151 * 152 * add_tty_randomness() uses the inter-keypress timing, as well as the 153 * character as random inputs into the "entropy pool". 154 * 155 * add_disk_randomness() times the finishing time of disk requests as well 156 * as feeding both xfer size & time into the entropy pool. 157 * 158 * add_audio_randomness() times the finishing of audio codec dma 159 * requests for both recording and playback, apparently supplies quite 160 * a lot of entropy, i'd blame on low resolution audio clock generators. 161 * 162 * All of these routines (except for add_true_randomness() of course) 163 * try to estimate how many bits of randomness a particular randomness 164 * source. They do this by keeping track of the first and second order 165 * deltas of the event timings. 166 * 167 * Ensuring unpredictability at system startup 168 * ============================================ 169 * 170 * When any operating system starts up, it will go through a sequence 171 * of actions that are fairly predictable by an adversary, especially 172 * if the start-up does not involve interaction with a human operator. 173 * This reduces the actual number of bits of unpredictability in the 174 * entropy pool below the value in entropy_count. In order to 175 * counteract this effect, it helps to carry information in the 176 * entropy pool across shut-downs and start-ups. To do this, put the 177 * following lines an appropriate script which is run during the boot 178 * sequence: 179 * 180 * echo "Initializing random number generator..." 181 * # Carry a random seed from start-up to start-up 182 * # Load and then save 512 bytes, which is the size of the entropy pool 183 * if [ -f /etc/random-seed ]; then 184 * cat /etc/random-seed >/dev/urandom 185 * fi 186 * dd if=/dev/urandom of=/etc/random-seed count=1 187 * 188 * and the following lines in an appropriate script which is run as 189 * the system is shutdown: 190 * 191 * # Carry a random seed from shut-down to start-up 192 * # Save 512 bytes, which is the size of the entropy pool 193 * echo "Saving random seed..." 194 * dd if=/dev/urandom of=/etc/random-seed count=1 195 * 196 * For example, on many Linux systems, the appropriate scripts are 197 * usually /etc/rc.d/rc.local and /etc/rc.d/rc.0, respectively. 198 * 199 * Effectively, these commands cause the contents of the entropy pool 200 * to be saved at shut-down time and reloaded into the entropy pool at 201 * start-up. (The 'dd' in the addition to the bootup script is to 202 * make sure that /etc/random-seed is different for every start-up, 203 * even if the system crashes without executing rc.0.) Even with 204 * complete knowledge of the start-up activities, predicting the state 205 * of the entropy pool requires knowledge of the previous history of 206 * the system. 207 * 208 * Configuring the /dev/random driver under Linux 209 * ============================================== 210 * 211 * The /dev/random driver under Linux uses minor numbers 8 and 9 of 212 * the /dev/mem major number (#1). So if your system does not have 213 * /dev/random and /dev/urandom created already, they can be created 214 * by using the commands: 215 * 216 * mknod /dev/random c 1 8 217 * mknod /dev/urandom c 1 9 218 * 219 * Acknowledgements: 220 * ================= 221 * 222 * Ideas for constructing this random number generator were derived 223 * from Pretty Good Privacy's random number generator, and from private 224 * discussions with Phil Karn. Colin Plumb provided a faster random 225 * number generator, which speed up the mixing function of the entropy 226 * pool, taken from PGPfone. Dale Worley has also contributed many 227 * useful ideas and suggestions to improve this driver. 228 * 229 * Any flaws in the design are solely my responsibility, and should 230 * not be attributed to the Phil, Colin, or any of authors of PGP. 231 * 232 * Further background information on this topic may be obtained from 233 * RFC 1750, "Randomness Recommendations for Security", by Donald 234 * Eastlake, Steve Crocker, and Jeff Schiller. 235 */ 236 237 #undef RNDEBUG 238 239 #include <sys/param.h> 240 #include <sys/systm.h> 241 #include <sys/conf.h> 242 #include <sys/disk.h> 243 #include <sys/ioctl.h> 244 #include <sys/malloc.h> 245 #include <sys/fcntl.h> 246 #include <sys/vnode.h> 247 #include <sys/md5k.h> 248 #include <sys/sysctl.h> 249 #include <sys/timeout.h> 250 251 #include <dev/rndvar.h> 252 #include <dev/rndioctl.h> 253 254 #ifdef RNDEBUG 255 int rnd_debug = 0x0000; 256 #define RD_INPUT 0x000f /* input data */ 257 #define RD_OUTPUT 0x00f0 /* output data */ 258 #define RD_WAIT 0x0100 /* sleep/wakeup for good data */ 259 #endif 260 261 /* 262 * The pool is stirred with a primitive polynomial of degree 128 263 * over GF(2), namely x^128 + x^99 + x^59 + x^31 + x^9 + x^7 + 1. 264 * For a pool of size 64, try x^64+x^62+x^38+x^10+x^6+x+1. 265 */ 266 #define POOLBITS (POOLWORDS*32) 267 #if POOLWORDS == 2048 268 #define TAP1 1638 269 #define TAP2 1231 270 #define TAP3 819 271 #define TAP4 411 272 #define TAP5 1 273 #elif POOLWORDS == 1024 /* also (819, 616, 410, 207, 2) */ 274 #define TAP1 817 275 #define TAP2 615 276 #define TAP3 412 277 #define TAP4 204 278 #define TAP5 1 279 #elif POOLWORDS == 512 /* also (409,307,206,102,2), (409,309,205,103,2) */ 280 #define TAP1 411 281 #define TAP2 308 282 #define TAP3 208 283 #define TAP4 104 284 #define TAP5 1 285 #elif POOLWORDS == 256 286 #define TAP1 205 287 #define TAP2 155 288 #define TAP3 101 289 #define TAP4 52 290 #define TAP5 1 291 #elif POOLWORDS == 128 /* also (103, 78, 51, 27, 2) */ 292 #define TAP1 103 293 #define TAP2 76 294 #define TAP3 51 295 #define TAP4 25 296 #define TAP5 1 297 #elif POOLWORDS == 64 298 #define TAP1 52 299 #define TAP2 39 300 #define TAP3 26 301 #define TAP4 14 302 #define TAP5 1 303 #elif POOLWORDS == 32 304 #define TAP1 26 305 #define TAP2 20 306 #define TAP3 14 307 #define TAP4 7 308 #define TAP5 1 309 #else 310 #error No primitive polynomial available for chosen POOLWORDS 311 #endif 312 313 /* 314 * For the purposes of better mixing, we use the CRC-32 polynomial as 315 * well to make a twisted Generalized Feedback Shift Reigster 316 * 317 * (See M. Matsumoto & Y. Kurita, 1992. Twisted GFSR generators. ACM 318 * Transactions on Modeling and Computer Simulation 2(3):179-194. 319 * Also see M. Matsumoto & Y. Kurita, 1994. Twisted GFSR generators 320 * II. ACM Transactions on Mdeling and Computer Simulation 4:254-266) 321 * 322 * Thanks to Colin Plumb for suggesting this. 323 * 324 * We have not analyzed the resultant polynomial to prove it primitive; 325 * in fact it almost certainly isn't. Nonetheless, the irreducible factors 326 * of a random large-degree polynomial over GF(2) are more than large enough 327 * that periodicity is not a concern. 328 * 329 * The input hash is much less sensitive than the output hash. All 330 * that we want of it is that it be a good non-cryptographic hash; 331 * i.e. it not produce collisions when fed "random" data of the sort 332 * we expect to see. As long as the pool state differs for different 333 * inputs, we have preserved the input entropy and done a good job. 334 * The fact that an intelligent attacker can construct inputs that 335 * will produce controlled alterations to the pool's state is not 336 * important because we don't consider such inputs to contribute any 337 * randomness. The only property we need with respect to them is that 338 * the attacker can't increase his/her knowledge of the pool's state. 339 * Since all additions are reversible (knowing the final state and the 340 * input, you can reconstruct the initial state), if an attacker has 341 * any uncertainty about the initial state, he/she can only shuffle 342 * that uncertainty about, but never cause any collisions (which would 343 * decrease the uncertainty). 344 * 345 * The chosen system lets the state of the pool be (essentially) the input 346 * modulo the generator polymnomial. Now, for random primitive polynomials, 347 * this is a universal class of hash functions, meaning that the chance 348 * of a collision is limited by the attacker's knowledge of the generator 349 * polynomail, so if it is chosen at random, an attacker can never force 350 * a collision. Here, we use a fixed polynomial, but we *can* assume that 351 * ###--> it is unknown to the processes generating the input entropy. <-### 352 * Because of this important property, this is a good, collision-resistant 353 * hash; hash collisions will occur no more often than chance. 354 */ 355 356 /* pIII/333 reported to have some drops w/ these numbers */ 357 #define QEVLEN (1024 / sizeof(struct rand_event)) 358 #define QEVSLOW (QEVLEN * 3 / 4) /* yet another 0.75 for 60-minutes hour /-; */ 359 #define QEVSBITS 12 360 361 /* There is actually only one of these, globally. */ 362 struct random_bucket { 363 u_int add_ptr; 364 u_int entropy_count; 365 u_char input_rotate; 366 u_int32_t pool[POOLWORDS]; 367 u_int asleep; 368 u_int tmo; 369 }; 370 371 /* There is one of these per entropy source */ 372 struct timer_rand_state { 373 u_int last_time; 374 u_int last_delta; 375 u_int last_delta2; 376 u_int dont_count_entropy : 1; 377 u_int max_entropy : 1; 378 }; 379 380 struct arc4_stream { 381 u_int8_t s[256]; 382 u_int cnt; 383 u_int8_t i; 384 u_int8_t j; 385 }; 386 387 struct rand_event { 388 struct timer_rand_state *re_state; 389 u_int re_nbits; 390 u_int re_time; 391 u_int re_val; 392 }; 393 394 struct timeout rnd_timeout, arc4_timeout; 395 struct random_bucket random_state; 396 struct arc4_stream arc4random_state; 397 struct timer_rand_state rnd_states[RND_SRC_NUM]; 398 struct rand_event rnd_event_space[QEVLEN]; 399 struct rand_event *rnd_event_head = rnd_event_space; 400 struct rand_event *rnd_event_tail = rnd_event_space; 401 402 int rnd_attached; 403 int arc4random_initialized; 404 struct rndstats rndstats; 405 406 static __inline u_int32_t roll(u_int32_t w, int i) 407 { 408 #ifdef i386 409 __asm ("roll %%cl, %0" : "+r" (w) : "c" (i)); 410 #else 411 w = (w << i) | (w >> (32 - i)); 412 #endif 413 return w; 414 } 415 416 /* must be called at a proper spl, returns ptr to the next event */ 417 static __inline struct rand_event * 418 rnd_get(void) 419 { 420 struct rand_event *p = rnd_event_tail; 421 422 if (p == rnd_event_head) 423 return NULL; 424 425 if (p + 1 >= &rnd_event_space[QEVLEN]) 426 rnd_event_tail = rnd_event_space; 427 else 428 rnd_event_tail++; 429 430 return p; 431 } 432 433 /* must be called at a proper spl, returns next available item */ 434 static __inline struct rand_event * 435 rnd_put(void) 436 { 437 struct rand_event *p = rnd_event_head + 1; 438 439 if (p >= &rnd_event_space[QEVLEN]) 440 p = rnd_event_space; 441 442 if (p == rnd_event_tail) 443 return NULL; 444 445 return rnd_event_head = p; 446 } 447 448 /* must be called at a proper spl, returns number of items in the queue */ 449 static __inline int 450 rnd_qlen(void) 451 { 452 int len = rnd_event_head - rnd_event_tail; 453 return (len < 0)? -len : len; 454 } 455 456 void dequeue_randomness __P((void *)); 457 458 static __inline void add_entropy_words __P((const u_int32_t *, u_int n)); 459 static __inline void extract_entropy __P((register u_int8_t *, int)); 460 461 static __inline u_int8_t arc4_getbyte __P((void)); 462 static __inline void arc4_stir __P((void)); 463 void arc4_reinit __P((void *v)); 464 void arc4maybeinit __P((void)); 465 466 /* Arcfour random stream generator. This code is derived from section 467 * 17.1 of Applied Cryptography, second edition, which describes a 468 * stream cipher allegedly compatible with RSA Labs "RC4" cipher (the 469 * actual description of which is a trade secret). The same algorithm 470 * is used as a stream cipher called "arcfour" in Tatu Ylonen's ssh 471 * package. 472 * 473 * The initialization function here has been modified not to discard 474 * old state, and its input always includes the time of day in 475 * microseconds. Moreover, bytes from the stream may at any point be 476 * diverted to multiple processes or even kernel functions desiring 477 * random numbers. This increases the strenght of the random stream, 478 * but makes it impossible to use this code for encryption--There is 479 * no way ever to reproduce the same stream of random bytes. 480 * 481 * RC4 is a registered trademark of RSA Laboratories. 482 */ 483 484 static __inline void 485 arc4_stir(void) 486 { 487 u_int8_t buf[256]; 488 register u_int8_t si; 489 register int n, s; 490 int len; 491 492 microtime((struct timeval *) buf); 493 len = random_state.entropy_count / 8; /* XXX maybe a half? */ 494 if (len > sizeof(buf) - sizeof(struct timeval)) 495 len = sizeof(buf) - sizeof(struct timeval); 496 get_random_bytes(buf + sizeof (struct timeval), len); 497 len += sizeof(struct timeval); 498 499 s = splhigh(); 500 arc4random_state.i--; 501 for (n = 0; n < 256; n++) { 502 arc4random_state.i++; 503 si = arc4random_state.s[arc4random_state.i]; 504 arc4random_state.j += si + buf[n % len]; 505 arc4random_state.s[arc4random_state.i] = 506 arc4random_state.s[arc4random_state.j]; 507 arc4random_state.s[arc4random_state.j] = si; 508 } 509 arc4random_state.j = arc4random_state.i; 510 arc4random_state.cnt = 0; 511 rndstats.arc4_stirs += len; 512 rndstats.arc4_nstirs++; 513 splx(s); 514 } 515 516 static __inline u_int8_t 517 arc4_getbyte(void) 518 { 519 register u_int8_t si, sj; 520 521 rndstats.arc4_reads++; 522 arc4random_state.cnt++; 523 arc4random_state.i++; 524 si = arc4random_state.s[arc4random_state.i]; 525 arc4random_state.j += si; 526 sj = arc4random_state.s[arc4random_state.j]; 527 arc4random_state.s[arc4random_state.i] = sj; 528 arc4random_state.s[arc4random_state.j] = si; 529 return arc4random_state.s[(si + sj) & 0xff]; 530 } 531 532 void 533 arc4maybeinit(void) 534 { 535 extern int hz; 536 537 if (!arc4random_initialized) { 538 arc4random_initialized++; 539 arc4_stir(); 540 /* 10 minutes, per dm@'s suggestion */ 541 timeout_add(&arc4_timeout, 10 * 60 * hz); 542 } 543 } 544 545 /* 546 * called by timeout to mark arc4 for stirring, 547 * actuall stirring happens on any access attempt. 548 */ 549 void 550 arc4_reinit(v) 551 void *v; 552 { 553 arc4random_initialized = 0; 554 } 555 556 int 557 arc4random_8(void) 558 { 559 arc4maybeinit(); 560 return arc4_getbyte(); 561 } 562 563 u_int32_t 564 arc4random(void) 565 { 566 arc4maybeinit(); 567 return ((arc4_getbyte() << 24) | (arc4_getbyte() << 16) 568 | (arc4_getbyte() << 8) | arc4_getbyte()); 569 } 570 571 void 572 randomattach(void) 573 { 574 int i; 575 576 if (rnd_attached) { 577 #ifdef RNDEBUG 578 printf("random: second attach\n"); 579 #endif 580 return; 581 } 582 583 timeout_set(&rnd_timeout, dequeue_randomness, &random_state); 584 timeout_set(&arc4_timeout, arc4_reinit, NULL); 585 586 random_state.add_ptr = 0; 587 random_state.entropy_count = 0; 588 rnd_states[RND_SRC_TIMER].dont_count_entropy = 1; 589 rnd_states[RND_SRC_TRUE].dont_count_entropy = 1; 590 rnd_states[RND_SRC_TRUE].max_entropy = 1; 591 592 bzero(&rndstats, sizeof(rndstats)); 593 bzero(&rnd_event_space, sizeof(rnd_event_space)); 594 595 for (i = 0; i < 256; i++) 596 arc4random_state.s[i] = i; 597 arc4_reinit(NULL); 598 599 rnd_attached = 1; 600 } 601 602 int 603 randomopen(dev, flag, mode, p) 604 dev_t dev; 605 int flag; 606 int mode; 607 struct proc *p; 608 { 609 return (minor (dev) < RND_NODEV) ? 0 : ENXIO; 610 } 611 612 int 613 randomclose(dev, flag, mode, p) 614 dev_t dev; 615 int flag; 616 int mode; 617 struct proc *p; 618 { 619 return 0; 620 } 621 622 /* 623 * This function adds a byte into the entropy "pool". It does not 624 * update the entropy estimate. The caller must do this if appropriate. 625 * 626 * The pool is stirred with a primitive polynomial of degree 128 627 * over GF(2), namely x^128 + x^99 + x^59 + x^31 + x^9 + x^7 + 1. 628 * For a pool of size 64, try x^64+x^62+x^38+x^10+x^6+x+1. 629 * 630 * We rotate the input word by a changing number of bits, to help 631 * assure that all bits in the entropy get toggled. Otherwise, if we 632 * consistently feed the entropy pool small numbers (like jiffies and 633 * scancodes, for example), the upper bits of the entropy pool don't 634 * get affected. --- TYT, 10/11/95 635 */ 636 static __inline void 637 add_entropy_words(buf, n) 638 const u_int32_t *buf; 639 u_int n; 640 { 641 static const u_int32_t twist_table[8] = { 642 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158, 643 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 644 }; 645 646 for (; n--; buf++) { 647 register u_int32_t w = roll(*buf, random_state.input_rotate); 648 register u_int i = random_state.add_ptr = 649 (random_state.add_ptr - 1) & (POOLWORDS - 1); 650 /* 651 * Normally, we add 7 bits of rotation to the pool. 652 * At the beginning of the pool, add an extra 7 bits 653 * rotation, so that successive passes spread the 654 * input bits across the pool evenly. 655 */ 656 random_state.input_rotate = 657 (random_state.input_rotate + (i? 7 : 14)) & 31; 658 659 /* XOR in the various taps */ 660 w ^= random_state.pool[(i+TAP1) & (POOLWORDS-1)] ^ 661 random_state.pool[(i+TAP2) & (POOLWORDS-1)] ^ 662 random_state.pool[(i+TAP3) & (POOLWORDS-1)] ^ 663 random_state.pool[(i+TAP4) & (POOLWORDS-1)] ^ 664 random_state.pool[(i+TAP5) & (POOLWORDS-1)] ^ 665 random_state.pool[i]; 666 random_state.pool[i] = (w >> 3) ^ twist_table[w & 7]; 667 } 668 } 669 670 /* 671 * This function adds entropy to the entropy "pool" by using timing 672 * delays. It uses the timer_rand_state structure to make an estimate 673 * of how many bits of entropy this call has added to the pool. 674 * 675 * The number "num" is also added to the pool - it should somehow describe 676 * the type of event which just happened. This is currently 0-255 for 677 * keyboard scan codes, and 256 upwards for interrupts. 678 * On the i386, this is assumed to be at most 16 bits, and the high bits 679 * are used for a high-resolution timer. 680 * 681 */ 682 void 683 enqueue_randomness(state, val) 684 int state, val; 685 { 686 register struct timer_rand_state *p; 687 register struct rand_event *rep; 688 struct timeval tv; 689 u_int time, nbits; 690 int s; 691 692 /* XXX on sparc we get here before randomattach() */ 693 if (!rnd_attached) 694 return; 695 696 #ifdef DIAGNOSTIC 697 if (state < 0 || state >= RND_SRC_NUM) 698 return; 699 #endif 700 701 p = &rnd_states[state]; 702 val += state << 13; 703 704 microtime(&tv); 705 time = tv.tv_usec ^ tv.tv_sec; 706 nbits = 0; 707 708 /* 709 * Calculate number of bits of randomness we probably 710 * added. We take into account the first and second order 711 * deltas in order to make our estimate. 712 */ 713 if (!p->dont_count_entropy) { 714 register int delta, delta2, delta3; 715 delta = time - p->last_time; 716 delta2 = delta - p->last_delta; 717 delta3 = delta2 - p->last_delta2; 718 719 if (delta < 0) delta = -delta; 720 if (delta2 < 0) delta2 = -delta2; 721 if (delta3 < 0) delta3 = -delta3; 722 if (delta > delta2) delta = delta2; 723 if (delta > delta3) delta = delta3; 724 delta3 = delta >>= 1; 725 /* 726 * delta &= 0xfff; 727 * we don't do it since our time sheet is different from linux 728 */ 729 730 if (delta & 0xffff0000) { 731 nbits = 16; 732 delta >>= 16; 733 } 734 if (delta & 0xff00) { 735 nbits += 8; 736 delta >>= 8; 737 } 738 if (delta & 0xf0) { 739 nbits += 4; 740 delta >>= 4; 741 } 742 if (delta & 0xc) { 743 nbits += 2; 744 delta >>= 2; 745 } 746 if (delta & 2) { 747 nbits += 1; 748 delta >>= 1; 749 } 750 if (delta & 1) 751 nbits++; 752 753 /* 754 * the logic is to drop low-entropy entries, 755 * in hope for dequeuing to be more randomfull 756 */ 757 if (rnd_qlen() > QEVSLOW && nbits < QEVSBITS) { 758 rndstats.rnd_drople++; 759 return; 760 } 761 p->last_time = time; 762 p->last_delta = delta3; 763 p->last_delta2 = delta2; 764 } else if (p->max_entropy) 765 nbits = 8 * sizeof(val) - 1; 766 767 s = splhigh(); 768 if ((rep = rnd_put()) == NULL) { 769 rndstats.rnd_drops++; 770 splx(s); 771 return; 772 } 773 774 rep->re_state = p; 775 rep->re_nbits = nbits; 776 rep->re_time = time; 777 rep->re_val = val; 778 779 rndstats.rnd_enqs++; 780 rndstats.rnd_ed[nbits]++; 781 rndstats.rnd_sc[state]++; 782 rndstats.rnd_sb[state] += nbits; 783 784 if (rnd_qlen() > QEVSLOW/2 && !random_state.tmo) { 785 random_state.tmo++; 786 timeout_add(&rnd_timeout, 1); 787 } 788 splx(s); 789 } 790 791 void 792 dequeue_randomness(v) 793 void *v; 794 { 795 struct random_bucket *rs = v; 796 register struct rand_event *rep; 797 u_int32_t buf[2]; 798 u_int nbits; 799 int s; 800 801 timeout_del(&rnd_timeout); 802 rndstats.rnd_deqs++; 803 804 s = splhigh(); 805 while ((rep = rnd_get())) { 806 807 buf[0] = rep->re_time; 808 buf[1] = rep->re_val; 809 nbits = rep->re_nbits; 810 splx(s); 811 812 add_entropy_words(buf, 2); 813 814 rndstats.rnd_total += nbits; 815 rs->entropy_count += nbits; 816 if (rs->entropy_count > POOLBITS) 817 rs->entropy_count = POOLBITS; 818 819 if (rs->asleep && rs->entropy_count > 8) { 820 #ifdef RNDEBUG 821 if (rnd_debug & RD_WAIT) 822 printf("rnd: wakeup[%u]{%u}\n", 823 rs->asleep, 824 rs->entropy_count); 825 #endif 826 rs->asleep--; 827 wakeup((void *)&rs->asleep); 828 } 829 830 s = splhigh(); 831 } 832 833 rs->tmo = 0; 834 splx(s); 835 } 836 837 #if POOLWORDS % 16 838 #error extract_entropy() assumes that POOLWORDS is a multiple of 16 words. 839 #endif 840 841 /* 842 * This function extracts randomness from the "entropy pool", and 843 * returns it in a buffer. This function computes how many remaining 844 * bits of entropy are left in the pool, but it does not restrict the 845 * number of bytes that are actually obtained. 846 */ 847 static __inline void 848 extract_entropy(buf, nbytes) 849 register u_int8_t *buf; 850 int nbytes; 851 { 852 struct random_bucket *rs = &random_state; 853 MD5_CTX tmp; 854 u_char buffer[16]; 855 856 add_timer_randomness(nbytes); 857 858 if (rs->entropy_count / 8 > nbytes) 859 rs->entropy_count -= nbytes*8; 860 else 861 rs->entropy_count = 0; 862 863 while (nbytes) { 864 int i; 865 866 /* Hash the pool to get the output */ 867 MD5Init(&tmp); 868 MD5Update(&tmp, (u_int8_t*)rs->pool, sizeof(rs->pool)); 869 MD5Final(buffer, &tmp); 870 871 /* 872 * In case the hash function has some recognizable 873 * output pattern, we fold it in half. 874 */ 875 buffer[0] ^= buffer[15]; 876 buffer[1] ^= buffer[14]; 877 buffer[2] ^= buffer[13]; 878 buffer[3] ^= buffer[12]; 879 buffer[4] ^= buffer[11]; 880 buffer[5] ^= buffer[10]; 881 buffer[6] ^= buffer[ 9]; 882 buffer[7] ^= buffer[ 8]; 883 884 /* Modify pool so next hash will produce different results */ 885 add_entropy_words((u_int32_t*)buffer, sizeof(buffer)/8); 886 887 /* Copy data to destination buffer */ 888 if (nbytes < sizeof(buffer) / 2) 889 bcopy(buffer, buf, i = nbytes); 890 else 891 bcopy(buffer, buf, i = sizeof(buffer) / 2); 892 nbytes -= i; 893 buf += i; 894 add_timer_randomness(nbytes); 895 } 896 897 /* Wipe data from memory */ 898 bzero(&tmp, sizeof(tmp)); 899 bzero(&buffer, sizeof(buffer)); 900 } 901 902 /* 903 * This function is the exported kernel interface. It returns some 904 * number of good random numbers, suitable for seeding TCP sequence 905 * numbers, etc. 906 */ 907 void 908 get_random_bytes(buf, nbytes) 909 void *buf; 910 size_t nbytes; 911 { 912 extract_entropy((u_int8_t *) buf, nbytes); 913 rndstats.rnd_used += nbytes * 8; 914 } 915 916 int 917 randomread(dev, uio, ioflag) 918 dev_t dev; 919 struct uio *uio; 920 int ioflag; 921 { 922 int ret = 0; 923 int s, i; 924 925 if (uio->uio_resid == 0) 926 return 0; 927 928 while (!ret && uio->uio_resid > 0) { 929 u_int32_t buf[ POOLWORDS ]; 930 int n = min(sizeof(buf), uio->uio_resid); 931 932 s = splhigh(); 933 switch(minor(dev)) { 934 case RND_RND: 935 ret = EIO; /* no chip -- error */ 936 break; 937 case RND_SRND: 938 if (random_state.entropy_count < 16 * 8) { 939 if (ioflag & IO_NDELAY) { 940 ret = EWOULDBLOCK; 941 break; 942 } 943 #ifdef RNDEBUG 944 if (rnd_debug & RD_WAIT) 945 printf("rnd: sleep[%u]\n", 946 random_state.asleep); 947 #endif 948 random_state.asleep++; 949 rndstats.rnd_waits++; 950 ret = tsleep(&random_state.asleep, 951 PWAIT | PCATCH, "rndrd", 0); 952 #ifdef RNDEBUG 953 if (rnd_debug & RD_WAIT) 954 printf("rnd: awakened(%d)\n", ret); 955 #endif 956 if (ret) 957 break; 958 } 959 if (n > random_state.entropy_count / 8) 960 n = random_state.entropy_count / 8; 961 rndstats.rnd_reads++; 962 #ifdef RNDEBUG 963 if (rnd_debug & RD_OUTPUT) 964 printf("rnd: %u possible output\n", n); 965 #endif 966 case RND_URND: 967 get_random_bytes((char *)buf, n); 968 #ifdef RNDEBUG 969 if (rnd_debug & RD_OUTPUT) 970 printf("rnd: %u bytes for output\n", n); 971 #endif 972 break; 973 case RND_PRND: 974 i = (n + 3) / 4; 975 while (i--) 976 buf[i] = random() << 16 | (random() & 0xFFFF); 977 break; 978 case RND_ARND: 979 { 980 u_int8_t *cp = (u_int8_t *) buf; 981 u_int8_t *end = cp + n; 982 while (cp < end) 983 *cp++ = arc4random_8(); 984 break; 985 } 986 default: 987 ret = ENXIO; 988 } 989 splx(s); 990 if (n != 0 && ret == 0) 991 ret = uiomove((caddr_t)buf, n, uio); 992 } 993 return ret; 994 } 995 996 int 997 randomselect(dev, rw, p) 998 dev_t dev; 999 int rw; 1000 struct proc *p; 1001 { 1002 switch (rw) { 1003 case FREAD: 1004 return random_state.entropy_count > 0; 1005 case FWRITE: 1006 return 1; 1007 } 1008 return 0; 1009 } 1010 1011 int 1012 randomwrite(dev, uio, flags) 1013 dev_t dev; 1014 struct uio *uio; 1015 int flags; 1016 { 1017 int ret = 0; 1018 1019 if (minor(dev) == RND_RND || minor(dev) == RND_PRND) 1020 return ENXIO; 1021 1022 if (uio->uio_resid == 0) 1023 return 0; 1024 1025 while (!ret && uio->uio_resid > 0) { 1026 u_int32_t buf[ POOLWORDS ]; 1027 u_short n = min(sizeof(buf),uio->uio_resid); 1028 1029 ret = uiomove((caddr_t)buf, n, uio); 1030 if (!ret) { 1031 while (n % sizeof(u_int32_t)) 1032 ((u_int8_t *) buf)[n++] = 0; 1033 add_entropy_words(buf, n / 4); 1034 } 1035 } 1036 1037 if (minor(dev) == RND_ARND && !ret) 1038 arc4random_initialized = 0; 1039 1040 return ret; 1041 } 1042 1043 int 1044 randomioctl(dev, cmd, data, flag, p) 1045 dev_t dev; 1046 u_long cmd; 1047 caddr_t data; 1048 int flag; 1049 struct proc *p; 1050 { 1051 int s, ret = 0; 1052 u_int cnt; 1053 1054 add_timer_randomness((u_long)p ^ (u_long)data ^ cmd); 1055 1056 switch (cmd) { 1057 case FIOASYNC: 1058 /* rnd has no async flag in softc so this is really a no-op. */ 1059 break; 1060 1061 case FIONBIO: 1062 /* Handled in the upper FS layer. */ 1063 break; 1064 1065 case RNDGETENTCNT: 1066 s = splhigh(); 1067 *(u_int *)data = random_state.entropy_count; 1068 splx(s); 1069 break; 1070 case RNDADDTOENTCNT: 1071 if (suser(p->p_ucred, &p->p_acflag) != 0) 1072 ret = EPERM; 1073 else { 1074 cnt = *(u_int *)data; 1075 s = splhigh(); 1076 random_state.entropy_count += cnt; 1077 if (random_state.entropy_count > POOLBITS) 1078 random_state.entropy_count = POOLBITS; 1079 splx(s); 1080 } 1081 break; 1082 case RNDZAPENTCNT: 1083 if (suser(p->p_ucred, &p->p_acflag) != 0) 1084 ret = EPERM; 1085 else { 1086 s = splhigh(); 1087 random_state.entropy_count = 0; 1088 splx(s); 1089 } 1090 break; 1091 case RNDSTIRARC4: 1092 if (suser(p->p_ucred, &p->p_acflag) != 0) 1093 ret = EPERM; 1094 else if (random_state.entropy_count < 64) 1095 ret = EAGAIN; 1096 else { 1097 s = splhigh(); 1098 arc4random_initialized = 0; 1099 splx(s); 1100 } 1101 break; 1102 case RNDCLRSTATS: 1103 if (suser(p->p_ucred, &p->p_acflag) != 0) 1104 ret = EPERM; 1105 else { 1106 s = splhigh(); 1107 bzero(&rndstats, sizeof(rndstats)); 1108 splx(s); 1109 } 1110 break; 1111 default: 1112 ret = EINVAL; 1113 } 1114 1115 add_timer_randomness((u_long)p ^ (u_long)data ^ cmd); 1116 return ret; 1117 } 1118