diff options
Diffstat (limited to 'sys/dev/rnd.c')
| -rw-r--r-- | sys/dev/rnd.c | 846 |
1 files changed, 435 insertions, 411 deletions
diff --git a/sys/dev/rnd.c b/sys/dev/rnd.c index 15a5e0543f2..f4aa7ad2d4b 100644 --- a/sys/dev/rnd.c +++ b/sys/dev/rnd.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rnd.c,v 1.90 2008/06/09 23:03:16 djm Exp $ */ +/* $OpenBSD: rnd.c,v 1.91 2008/06/10 03:11:30 djm Exp $ */ /* * rnd.c -- A strong random number generator @@ -42,6 +42,7 @@ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED * OF THE POSSIBILITY OF SUCH DAMAGE. */ + /* * (now, with legal B.S. out of the way.....) * @@ -102,7 +103,7 @@ * =============================== * * There are three exported interfaces. - * The first one is designed to be used from within the kernel: + * The first set are designed to be used from within the kernel: * * void get_random_bytes(void *buf, int nbytes); * @@ -135,6 +136,7 @@ * void add_tty_randomness(int c); * void add_disk_randomness(int n); * void add_audio_randomness(int n); + * void add_video_randomness(int n); * * add_true_randomness() uses true random number generators present * on some cryptographic and system chipsets. Entropy accounting @@ -235,8 +237,6 @@ * Eastlake, Steve Crocker, and Jeff Schiller. */ -#undef RNDEBUG - #include <sys/param.h> #include <sys/endian.h> #include <sys/systm.h> @@ -266,70 +266,9 @@ int rnd_debug = 0x0000; #endif /* - * Maximum number of bytes to serve directly from the main arc4random - * pool. Larger requests are served from discrete arc4 instances keyed - * from the main pool. - */ -#define ARC4_MAIN_MAX_BYTES 2048 - -/* - * Key size (in bytes) for arc4 instances setup to serve requests larger - * than ARC4_MAIN_MAX_BYTES. + * Master random number pool functions + * ----------------------------------- */ -#define ARC4_SUB_KEY_BYTES (256 / 8) - -/* - * The pool is stirred with a primitive polynomial of degree 128 - * over GF(2), namely x^128 + x^99 + x^59 + x^31 + x^9 + x^7 + 1. - * For a pool of size 64, try x^64+x^62+x^38+x^10+x^6+x+1. - */ -#define POOLBITS (POOLWORDS*32) -#define POOLBYTES (POOLWORDS*4) -#if POOLWORDS == 2048 -#define TAP1 1638 -#define TAP2 1231 -#define TAP3 819 -#define TAP4 411 -#define TAP5 1 -#elif POOLWORDS == 1024 /* also (819, 616, 410, 207, 2) */ -#define TAP1 817 -#define TAP2 615 -#define TAP3 412 -#define TAP4 204 -#define TAP5 1 -#elif POOLWORDS == 512 /* also (409,307,206,102,2), (409,309,205,103,2) */ -#define TAP1 411 -#define TAP2 308 -#define TAP3 208 -#define TAP4 104 -#define TAP5 1 -#elif POOLWORDS == 256 -#define TAP1 205 -#define TAP2 155 -#define TAP3 101 -#define TAP4 52 -#define TAP5 1 -#elif POOLWORDS == 128 /* also (103, 78, 51, 27, 2) */ -#define TAP1 103 -#define TAP2 76 -#define TAP3 51 -#define TAP4 25 -#define TAP5 1 -#elif POOLWORDS == 64 -#define TAP1 52 -#define TAP2 39 -#define TAP3 26 -#define TAP4 14 -#define TAP5 1 -#elif POOLWORDS == 32 -#define TAP1 26 -#define TAP2 20 -#define TAP3 14 -#define TAP4 7 -#define TAP5 1 -#else -#error No primitive polynomial available for chosen POOLWORDS -#endif /* * For the purposes of better mixing, we use the CRC-32 polynomial as @@ -374,12 +313,64 @@ int rnd_debug = 0x0000; * hash; hash collisions will occur no more often than chance. */ -/* pIII/333 reported to have some drops w/ these numbers */ -#define QEVLEN (1024 / sizeof(struct rand_event)) -#define QEVSLOW (QEVLEN * 3 / 4) /* yet another 0.75 for 60-minutes hour /-; */ -#define QEVSBITS 10 +/* + * The pool is stirred with a primitive polynomial of degree 128 + * over GF(2), namely x^128 + x^99 + x^59 + x^31 + x^9 + x^7 + 1. + * For a pool of size 64, try x^64+x^62+x^38+x^10+x^6+x+1. + * XXX is this comment still accurate? + */ +#define POOLBITS (POOLWORDS*32) +#define POOLBYTES (POOLWORDS*4) +#define POOLMASK (POOLWORDS - 1) +#if POOLWORDS == 2048 +#define POOL_TAP1 1638 +#define POOL_TAP2 1231 +#define POOL_TAP3 819 +#define POOL_TAP4 411 +#define POOL_TAP5 1 +#elif POOLWORDS == 1024 /* also (819, 616, 410, 207, 2) */ +#define POOL_TAP1 817 +#define POOL_TAP2 615 +#define POOL_TAP3 412 +#define POOL_TAP4 204 +#define POOL_TAP5 1 +#elif POOLWORDS == 512 /* also (409,307,206,102,2), (409,309,205,103,2) */ +#define POOL_TAP1 411 +#define POOL_TAP2 308 +#define POOL_TAP3 208 +#define POOL_TAP4 104 +#define POOL_TAP5 1 +#elif POOLWORDS == 256 +#define POOL_TAP1 205 +#define POOL_TAP2 155 +#define POOL_TAP3 101 +#define POOL_TAP4 52 +#define POOL_TAP5 1 +#elif POOLWORDS == 128 /* also (103, 78, 51, 27, 2) */ +#define POOL_TAP1 103 +#define POOL_TAP2 76 +#define POOL_TAP3 51 +#define POOL_TAP4 25 +#define POOL_TAP5 1 +#elif POOLWORDS == 64 +#define POOL_TAP1 52 +#define POOL_TAP2 39 +#define POOL_TAP3 26 +#define POOL_TAP4 14 +#define POOL_TAP5 1 +#elif POOLWORDS == 32 +#define POOL_TAP1 26 +#define POOL_TAP2 20 +#define POOL_TAP3 14 +#define POOL_TAP4 7 +#define POOL_TAP5 1 +#else +#error No primitive polynomial available for chosen POOLWORDS +#endif + +static void dequeue_randomness(void *); -/* There is actually only one of these, globally. */ +/* Master kernel random number pool. */ struct random_bucket { u_int add_ptr; u_int entropy_count; @@ -388,6 +379,137 @@ struct random_bucket { u_int asleep; u_int tmo; }; +struct random_bucket random_state; +struct mutex rndlock; + +/* Rotate bits in word 'w' by 'i' positions */ +static __inline u_int32_t roll(u_int32_t w, int i) +{ +#ifdef i386 + __asm ("roll %%cl, %0" : "+r" (w) : "c" (i)); +#else + w = (w << i) | (w >> (32 - i)); +#endif + return w; +} + +/* + * This function adds a byte into the entropy pool. It does not + * update the entropy estimate. The caller must do this if appropriate. + * + * The pool is stirred with a primitive polynomial of degree 128 + * over GF(2), namely x^128 + x^99 + x^59 + x^31 + x^9 + x^7 + 1. + * For a pool of size 64, try x^64+x^62+x^38+x^10+x^6+x+1. + * XXX is this comment still accurate? + * + * We rotate the input word by a changing number of bits, to help + * assure that all bits in the entropy get toggled. Otherwise, if we + * consistently feed the entropy pool small numbers (like jiffies and + * scancodes, for example), the upper bits of the entropy pool don't + * get affected. --- TYT, 10/11/95 + */ +static void +add_entropy_words(const u_int32_t *buf, u_int n) +{ + static const u_int32_t twist_table[8] = { + 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158, + 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 + }; + + for (; n--; buf++) { + u_int32_t w = roll(*buf, random_state.input_rotate); + u_int i = random_state.add_ptr = + (random_state.add_ptr - 1) & POOLMASK; + /* + * Normally, we add 7 bits of rotation to the pool. + * At the beginning of the pool, add an extra 7 bits + * rotation, so that successive passes spread the + * input bits across the pool evenly. + */ + random_state.input_rotate = + (random_state.input_rotate + (i ? 7 : 14)) & 31; + + /* XOR in the various POOL_TAPs */ + w ^= random_state.pool[(i + POOL_TAP1) & POOLMASK] ^ + random_state.pool[(i + POOL_TAP2) & POOLMASK] ^ + random_state.pool[(i + POOL_TAP3) & POOLMASK] ^ + random_state.pool[(i + POOL_TAP4) & POOLMASK] ^ + random_state.pool[(i + POOL_TAP5) & POOLMASK] ^ + random_state.pool[i]; + random_state.pool[i] = (w >> 3) ^ twist_table[w & 7]; + } +} + +/* + * This function extracts randomness from the entropy pool, and + * returns it in a buffer. This function computes how many remaining + * bits of entropy are left in the pool, but it does not restrict the + * number of bytes that are actually obtained. + */ +static void +extract_entropy(u_int8_t *buf, int nbytes) +{ + struct random_bucket *rs = &random_state; + u_char buffer[16]; + MD5_CTX tmp; + u_int i; + + add_timer_randomness(nbytes); + + while (nbytes) { + if (nbytes < sizeof(buffer) / 2) + i = nbytes; + else + i = sizeof(buffer) / 2; + + /* Hash the pool to get the output */ + MD5Init(&tmp); + mtx_enter(&rndlock); + MD5Update(&tmp, (u_int8_t*)rs->pool, sizeof(rs->pool)); + if (rs->entropy_count / 8 > i) + rs->entropy_count -= i * 8; + else + rs->entropy_count = 0; + mtx_leave(&rndlock); + MD5Final(buffer, &tmp); + + /* + * In case the hash function has some recognizable + * output pattern, we fold it in half. + */ + buffer[0] ^= buffer[15]; + buffer[1] ^= buffer[14]; + buffer[2] ^= buffer[13]; + buffer[3] ^= buffer[12]; + buffer[4] ^= buffer[11]; + buffer[5] ^= buffer[10]; + buffer[6] ^= buffer[ 9]; + buffer[7] ^= buffer[ 8]; + + /* Copy data to destination buffer */ + bcopy(buffer, buf, i); + nbytes -= i; + buf += i; + + /* Modify pool so next hash will produce different results */ + add_timer_randomness(nbytes); + dequeue_randomness(&random_state); + } + + /* Wipe data from memory */ + bzero(&tmp, sizeof(tmp)); + bzero(buffer, sizeof(buffer)); +} + +/* + * Kernel-side entropy crediting API and handling of entropy-bearing events + * ------------------------------------------------------------------------ + */ + +/* pIII/333 reported to have some drops w/ these numbers */ +#define QEVLEN (1024 / sizeof(struct rand_event)) +#define QEVSLOW (QEVLEN * 3 / 4) /* yet another 0.75 for 60-minutes hour /-; */ +#define QEVSBITS 10 /* There is one of these per entropy source */ struct timer_rand_state { @@ -405,42 +527,14 @@ struct rand_event { u_int re_val; }; -struct timeout rnd_timeout, arc4_timeout; -struct random_bucket random_state; -struct rc4_ctx arc4random_state; -u_long arc4random_count = 0; struct timer_rand_state rnd_states[RND_SRC_NUM]; struct rand_event rnd_event_space[QEVLEN]; struct rand_event *rnd_event_head = rnd_event_space; struct rand_event *rnd_event_tail = rnd_event_space; -struct selinfo rnd_rsel, rnd_wsel; - -void filt_rndrdetach(struct knote *kn); -int filt_rndread(struct knote *kn, long hint); - -struct filterops rndread_filtops = - { 1, NULL, filt_rndrdetach, filt_rndread}; - -void filt_rndwdetach(struct knote *kn); -int filt_rndwrite(struct knote *kn, long hint); - -struct filterops rndwrite_filtops = - { 1, NULL, filt_rndwdetach, filt_rndwrite}; - -int rnd_attached; -int arc4random_initialized; +struct timeout rnd_timeout; +struct selinfo rnd_rsel; struct rndstats rndstats; -struct mutex rndlock; - -static __inline u_int32_t roll(u_int32_t w, int i) -{ -#ifdef i386 - __asm ("roll %%cl, %0" : "+r" (w) : "c" (i)); -#else - w = (w << i) | (w >> (32 - i)); -#endif - return w; -} +int rnd_attached; /* must be called at a proper spl, returns ptr to the next event */ static __inline struct rand_event * @@ -482,256 +576,6 @@ rnd_qlen(void) return (len < 0)? -len : len; } -void dequeue_randomness(void *); - -static void add_entropy_words(const u_int32_t *, u_int n); -void extract_entropy(u_int8_t *, int); - -void arc4_stir(void); -void arc4_reinit(void *v); -void arc4maybeinit(void); - -void -arc4_stir(void) -{ - u_int8_t buf[256]; - int len; - - nanotime((struct timespec *) buf); - len = random_state.entropy_count / 8; /* XXX maybe a half? */ - if (len > sizeof(buf) - sizeof(struct timeval)) - len = sizeof(buf) - sizeof(struct timeval); - get_random_bytes(buf + sizeof (struct timeval), len); - len += sizeof(struct timeval); - - mtx_enter(&rndlock); - if (rndstats.arc4_nstirs > 0) - rc4_crypt(&arc4random_state, buf, buf, sizeof(buf)); - - rc4_keysetup(&arc4random_state, buf, sizeof(buf)); - arc4random_count = 0; - rndstats.arc4_stirs += len; - rndstats.arc4_nstirs++; - - /* - * Throw away the first N words of output, as suggested in the - * paper "Weaknesses in the Key Scheduling Algorithm of RC4" - * by Fluher, Mantin, and Shamir. (N = 256 in our case.) - */ - rc4_skip(&arc4random_state, 256 * 4); - mtx_leave(&rndlock); -} - -void -arc4maybeinit(void) -{ - extern int hz; - - if (!arc4random_initialized) { -#ifdef DIAGNOSTIC - if (!rnd_attached) - panic("arc4maybeinit: premature"); -#endif - arc4random_initialized++; - arc4_stir(); - /* 10 minutes, per dm@'s suggestion */ - timeout_add(&arc4_timeout, 10 * 60 * hz); - } -} - -/* - * called by timeout to mark arc4 for stirring, - * actual stirring happens on any access attempt. - */ -void -arc4_reinit(void *v) -{ - arc4random_initialized = 0; -} - -u_int32_t -arc4random(void) -{ - u_int32_t ret; - - arc4maybeinit(); - mtx_enter(&rndlock); - rc4_getbytes(&arc4random_state, (u_char*)&ret, sizeof(ret)); - rndstats.arc4_reads += sizeof(ret); - arc4random_count += sizeof(ret); - mtx_leave(&rndlock); - return ret; -} - -static void -arc4random_buf_large(void *buf, size_t n) -{ - u_char lbuf[ARC4_SUB_KEY_BYTES]; - struct rc4_ctx lctx; - - mtx_enter(&rndlock); - rc4_getbytes(&arc4random_state, lbuf, sizeof(lbuf)); - rndstats.arc4_reads += n; - arc4random_count += sizeof(lbuf); - mtx_leave(&rndlock); - - rc4_keysetup(&lctx, lbuf, sizeof(lbuf)); - rc4_skip(&lctx, 256 * 4); - rc4_getbytes(&lctx, (u_char*)buf, n); - bzero(lbuf, sizeof(lbuf)); - bzero(&lctx, sizeof(lctx)); -} - -void -arc4random_buf(void *buf, size_t n) -{ - arc4maybeinit(); - - /* Satisfy large requests via an independent ARC4 instance */ - if (n > ARC4_MAIN_MAX_BYTES) { - arc4random_buf_large(buf, n); - return; - } - - mtx_enter(&rndlock); - rc4_getbytes(&arc4random_state, (u_char*)buf, n); - rndstats.arc4_reads += n; - arc4random_count += n; - mtx_leave(&rndlock); -} - -/* - * Calculate a uniformly distributed random number less than upper_bound - * avoiding "modulo bias". - * - * Uniformity is achieved by generating new random numbers until the one - * returned is outside the range [0, 2**32 % upper_bound). This - * guarantees the selected random number will be inside - * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) - * after reduction modulo upper_bound. - */ -u_int32_t -arc4random_uniform(u_int32_t upper_bound) -{ - u_int32_t r, min; - - if (upper_bound < 2) - return 0; - -#if (ULONG_MAX > 0xffffffffUL) - min = 0x100000000UL % upper_bound; -#else - /* Calculate (2**32 % upper_bound) avoiding 64-bit math */ - if (upper_bound > 0x80000000) - min = 1 + ~upper_bound; /* 2**32 - upper_bound */ - else { - /* (2**32 - x) % x == 2**32 % x when x <= 2**31 */ - min = ((0xffffffff - upper_bound) + 1) % upper_bound; - } -#endif - - /* - * This could theoretically loop forever but each retry has - * p > 0.5 (worst case, usually far better) of selecting a - * number inside the range we need, so it should rarely need - * to re-roll. - */ - for (;;) { - r = arc4random(); - if (r >= min) - break; - } - - return r % upper_bound; -} - -void -randomattach(void) -{ - if (rnd_attached) { -#ifdef RNDEBUG - printf("random: second attach\n"); -#endif - return; - } - - timeout_set(&rnd_timeout, dequeue_randomness, &random_state); - timeout_set(&arc4_timeout, arc4_reinit, NULL); - - random_state.add_ptr = 0; - random_state.entropy_count = 0; - rnd_states[RND_SRC_TIMER].dont_count_entropy = 1; - rnd_states[RND_SRC_TRUE].dont_count_entropy = 1; - rnd_states[RND_SRC_TRUE].max_entropy = 1; - - bzero(&rndstats, sizeof(rndstats)); - bzero(&rnd_event_space, sizeof(rnd_event_space)); - - bzero(&arc4random_state, sizeof(arc4random_state)); - mtx_init(&rndlock, IPL_HIGH); - arc4_reinit(NULL); - - rnd_attached = 1; -} - -int -randomopen(dev_t dev, int flag, int mode, struct proc *p) -{ - return (minor (dev) < RND_NODEV) ? 0 : ENXIO; -} - -int -randomclose(dev_t dev, int flag, int mode, struct proc *p) -{ - return 0; -} - -/* - * This function adds a byte into the entropy pool. It does not - * update the entropy estimate. The caller must do this if appropriate. - * - * The pool is stirred with a primitive polynomial of degree 128 - * over GF(2), namely x^128 + x^99 + x^59 + x^31 + x^9 + x^7 + 1. - * For a pool of size 64, try x^64+x^62+x^38+x^10+x^6+x+1. - * - * We rotate the input word by a changing number of bits, to help - * assure that all bits in the entropy get toggled. Otherwise, if we - * consistently feed the entropy pool small numbers (like jiffies and - * scancodes, for example), the upper bits of the entropy pool don't - * get affected. --- TYT, 10/11/95 - */ -static void -add_entropy_words(const u_int32_t *buf, u_int n) -{ - static const u_int32_t twist_table[8] = { - 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158, - 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 - }; - - for (; n--; buf++) { - u_int32_t w = roll(*buf, random_state.input_rotate); - u_int i = random_state.add_ptr = - (random_state.add_ptr - 1) & (POOLWORDS - 1); - /* - * Normally, we add 7 bits of rotation to the pool. - * At the beginning of the pool, add an extra 7 bits - * rotation, so that successive passes spread the - * input bits across the pool evenly. - */ - random_state.input_rotate = - (random_state.input_rotate + (i? 7 : 14)) & 31; - - /* XOR in the various taps */ - w ^= random_state.pool[(i+TAP1) & (POOLWORDS-1)] ^ - random_state.pool[(i+TAP2) & (POOLWORDS-1)] ^ - random_state.pool[(i+TAP3) & (POOLWORDS-1)] ^ - random_state.pool[(i+TAP4) & (POOLWORDS-1)] ^ - random_state.pool[(i+TAP5) & (POOLWORDS-1)] ^ - random_state.pool[i]; - random_state.pool[i] = (w >> 3) ^ twist_table[w & 7]; - } -} - /* * This function adds entropy to the entropy pool by using timing * delays. It uses the timer_rand_state structure to make an estimate @@ -742,7 +586,6 @@ add_entropy_words(const u_int32_t *buf, u_int n) * are for keyboard scan codes, 256 and upwards - for interrupts. * On the i386, this is assumed to be at most 16 bits, and the high bits * are used for a high-resolution timer. - * */ void enqueue_randomness(int state, int val) @@ -851,7 +694,7 @@ enqueue_randomness(int state, int val) mtx_leave(&rndlock); } -void +static void dequeue_randomness(void *v) { struct random_bucket *rs = v; @@ -897,81 +740,262 @@ dequeue_randomness(void *v) mtx_leave(&rndlock); } -#if POOLWORDS % 16 -#error extract_entropy() assumes that POOLWORDS is a multiple of 16 words. -#endif +/* + * Exported kernel CPRNG API: arc4random() and friends + * --------------------------------------------------- + */ /* - * This function extracts randomness from the entropy pool, and - * returns it in a buffer. This function computes how many remaining - * bits of entropy are left in the pool, but it does not restrict the - * number of bytes that are actually obtained. + * Maximum number of bytes to serve directly from the main arc4random + * pool. Larger requests are served from discrete arc4 instances keyed + * from the main pool. + */ +#define ARC4_MAIN_MAX_BYTES 2048 + +/* + * Key size (in bytes) for arc4 instances setup to serve requests larger + * than ARC4_MAIN_MAX_BYTES. + */ +#define ARC4_SUB_KEY_BYTES (256 / 8) + +struct timeout arc4_timeout; +struct rc4_ctx arc4random_state; +int arc4random_initialized; +u_long arc4random_count = 0; + +/* + * This function returns some number of good random numbers but is quite + * slow. Please use arc4random_buf() instead unless very high quality + * randomness is required. + * XXX: rename this */ void -extract_entropy(u_int8_t *buf, int nbytes) +get_random_bytes(void *buf, size_t nbytes) { - struct random_bucket *rs = &random_state; - u_char buffer[16]; - MD5_CTX tmp; - u_int i; + extract_entropy((u_int8_t *) buf, nbytes); + rndstats.rnd_used += nbytes * 8; +} - add_timer_randomness(nbytes); +static void +arc4_stir(void) +{ + u_int8_t buf[256]; + int len; - while (nbytes) { - if (nbytes < sizeof(buffer) / 2) - i = nbytes; - else - i = sizeof(buffer) / 2; + nanotime((struct timespec *) buf); + len = random_state.entropy_count / 8; /* XXX maybe a half? */ + if (len > sizeof(buf) - sizeof(struct timeval)) + len = sizeof(buf) - sizeof(struct timeval); + get_random_bytes(buf + sizeof (struct timeval), len); + len += sizeof(struct timeval); - /* Hash the pool to get the output */ - MD5Init(&tmp); - mtx_enter(&rndlock); - MD5Update(&tmp, (u_int8_t*)rs->pool, sizeof(rs->pool)); - if (rs->entropy_count / 8 > i) - rs->entropy_count -= i * 8; - else - rs->entropy_count = 0; - mtx_leave(&rndlock); - MD5Final(buffer, &tmp); + mtx_enter(&rndlock); + if (rndstats.arc4_nstirs > 0) + rc4_crypt(&arc4random_state, buf, buf, sizeof(buf)); - /* - * In case the hash function has some recognizable - * output pattern, we fold it in half. - */ - buffer[0] ^= buffer[15]; - buffer[1] ^= buffer[14]; - buffer[2] ^= buffer[13]; - buffer[3] ^= buffer[12]; - buffer[4] ^= buffer[11]; - buffer[5] ^= buffer[10]; - buffer[6] ^= buffer[ 9]; - buffer[7] ^= buffer[ 8]; + rc4_keysetup(&arc4random_state, buf, sizeof(buf)); + arc4random_count = 0; + rndstats.arc4_stirs += len; + rndstats.arc4_nstirs++; - /* Copy data to destination buffer */ - bcopy(buffer, buf, i); - nbytes -= i; - buf += i; + /* + * Throw away the first N words of output, as suggested in the + * paper "Weaknesses in the Key Scheduling Algorithm of RC4" + * by Fluher, Mantin, and Shamir. (N = 256 in our case.) + */ + rc4_skip(&arc4random_state, 256 * 4); + mtx_leave(&rndlock); +} - /* Modify pool so next hash will produce different results */ - add_timer_randomness(nbytes); - dequeue_randomness(&random_state); +/* + * called by timeout to mark arc4 for stirring, + * actual stirring happens on any access attempt. + */ +static void +arc4_reinit(void *v) +{ + arc4random_initialized = 0; +} + +static void +arc4maybeinit(void) +{ + extern int hz; + + if (!arc4random_initialized) { +#ifdef DIAGNOSTIC + if (!rnd_attached) + panic("arc4maybeinit: premature"); +#endif + arc4random_initialized++; + arc4_stir(); + /* 10 minutes, per dm@'s suggestion */ + timeout_add(&arc4_timeout, 10 * 60 * hz); } +} - /* Wipe data from memory */ - bzero(&tmp, sizeof(tmp)); - bzero(buffer, sizeof(buffer)); +void +randomattach(void) +{ + if (rnd_attached) { +#ifdef RNDEBUG + printf("random: second attach\n"); +#endif + return; + } + + timeout_set(&rnd_timeout, dequeue_randomness, &random_state); + timeout_set(&arc4_timeout, arc4_reinit, NULL); + + random_state.add_ptr = 0; + random_state.entropy_count = 0; + rnd_states[RND_SRC_TIMER].dont_count_entropy = 1; + rnd_states[RND_SRC_TRUE].dont_count_entropy = 1; + rnd_states[RND_SRC_TRUE].max_entropy = 1; + + bzero(&rndstats, sizeof(rndstats)); + bzero(&rnd_event_space, sizeof(rnd_event_space)); + + bzero(&arc4random_state, sizeof(arc4random_state)); + mtx_init(&rndlock, IPL_HIGH); + arc4_reinit(NULL); + + rnd_attached = 1; +} + +/* Return one word of randomness from an RC4 generator */ +u_int32_t +arc4random(void) +{ + u_int32_t ret; + + arc4maybeinit(); + mtx_enter(&rndlock); + rc4_getbytes(&arc4random_state, (u_char*)&ret, sizeof(ret)); + rndstats.arc4_reads += sizeof(ret); + arc4random_count += sizeof(ret); + mtx_leave(&rndlock); + return ret; +} + +/* + * Return a "large" buffer of randomness using an independantly-keyed RC4 + * generator. + */ +static void +arc4random_buf_large(void *buf, size_t n) +{ + u_char lbuf[ARC4_SUB_KEY_BYTES]; + struct rc4_ctx lctx; + + mtx_enter(&rndlock); + rc4_getbytes(&arc4random_state, lbuf, sizeof(lbuf)); + rndstats.arc4_reads += n; + arc4random_count += sizeof(lbuf); + mtx_leave(&rndlock); + + rc4_keysetup(&lctx, lbuf, sizeof(lbuf)); + rc4_skip(&lctx, 256 * 4); + rc4_getbytes(&lctx, (u_char*)buf, n); + bzero(lbuf, sizeof(lbuf)); + bzero(&lctx, sizeof(lctx)); } /* - * This function is the exported kernel interface. It returns some - * number of good random numbers, suitable for seeding TCP sequence - * numbers, etc. + * Fill a buffer of arbitrary length with RC4-derived randomness. */ void -get_random_bytes(void *buf, size_t nbytes) +arc4random_buf(void *buf, size_t n) { - extract_entropy((u_int8_t *) buf, nbytes); - rndstats.rnd_used += nbytes * 8; + arc4maybeinit(); + + /* Satisfy large requests via an independent ARC4 instance */ + if (n > ARC4_MAIN_MAX_BYTES) { + arc4random_buf_large(buf, n); + return; + } + + mtx_enter(&rndlock); + rc4_getbytes(&arc4random_state, (u_char*)buf, n); + rndstats.arc4_reads += n; + arc4random_count += n; + mtx_leave(&rndlock); +} + +/* + * Calculate a uniformly distributed random number less than upper_bound + * avoiding "modulo bias". + * + * Uniformity is achieved by generating new random numbers until the one + * returned is outside the range [0, 2**32 % upper_bound). This + * guarantees the selected random number will be inside + * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) + * after reduction modulo upper_bound. + */ +u_int32_t +arc4random_uniform(u_int32_t upper_bound) +{ + u_int32_t r, min; + + if (upper_bound < 2) + return 0; + +#if (ULONG_MAX > 0xffffffffUL) + min = 0x100000000UL % upper_bound; +#else + /* Calculate (2**32 % upper_bound) avoiding 64-bit math */ + if (upper_bound > 0x80000000) + min = 1 + ~upper_bound; /* 2**32 - upper_bound */ + else { + /* (2**32 - x) % x == 2**32 % x when x <= 2**31 */ + min = ((0xffffffff - upper_bound) + 1) % upper_bound; + } +#endif + + /* + * This could theoretically loop forever but each retry has + * p > 0.5 (worst case, usually far better) of selecting a + * number inside the range we need, so it should rarely need + * to re-roll. + */ + for (;;) { + r = arc4random(); + if (r >= min) + break; + } + + return r % upper_bound; +} + +/* + * random, srandom, urandom, prandom, arandom char devices + * ------------------------------------------------------- + */ + +void filt_rndrdetach(struct knote *kn); +int filt_rndread(struct knote *kn, long hint); + +struct filterops rndread_filtops = + { 1, NULL, filt_rndrdetach, filt_rndread}; + +void filt_rndwdetach(struct knote *kn); +int filt_rndwrite(struct knote *kn, long hint); + +struct filterops rndwrite_filtops = + { 1, NULL, filt_rndwdetach, filt_rndwrite}; + +struct selinfo rnd_wsel; + +int +randomopen(dev_t dev, int flag, int mode, struct proc *p) +{ + return (minor (dev) < RND_NODEV) ? 0 : ENXIO; +} + +int +randomclose(dev_t dev, int flag, int mode, struct proc *p) +{ + return 0; } int |