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