Module Name: src Committed By: tls Date: Tue Apr 17 02:50:39 UTC 2012
Modified Files: src/share/man/man4: rnd.4 src/sys/dev: rndpseudo.c src/sys/kern: kern_rndpool.c kern_rndq.c subr_cprng.c src/sys/sys: cprng.h rnd.h Log Message: Address multiple problems with rnd(4)/cprng(9): 1) Add a per-cpu CPRNG to handle short reads from /dev/urandom so that programs like perl don't drain the entropy pool dry by repeatedly opening, reading 4 bytes, closing. 2) Really fix the locking around reseeds and destroys. 3) Fix the opportunistic-reseed strategy so it actually works, reseeding existing RNGs once each (as they are used, so idle RNGs don't get reseeded) until the pool is half empty or newly full again. To generate a diff of this commit: cvs rdiff -u -r1.18 -r1.19 src/share/man/man4/rnd.4 cvs rdiff -u -r1.7 -r1.8 src/sys/dev/rndpseudo.c cvs rdiff -u -r1.1 -r1.2 src/sys/kern/kern_rndpool.c cvs rdiff -u -r1.2 -r1.3 src/sys/kern/kern_rndq.c cvs rdiff -u -r1.7 -r1.8 src/sys/kern/subr_cprng.c cvs rdiff -u -r1.4 -r1.5 src/sys/sys/cprng.h cvs rdiff -u -r1.30 -r1.31 src/sys/sys/rnd.h Please note that diffs are not public domain; they are subject to the copyright notices on the relevant files.
Modified files: Index: src/share/man/man4/rnd.4 diff -u src/share/man/man4/rnd.4:1.18 src/share/man/man4/rnd.4:1.19 --- src/share/man/man4/rnd.4:1.18 Sat Dec 17 21:21:59 2011 +++ src/share/man/man4/rnd.4 Tue Apr 17 02:50:39 2012 @@ -1,4 +1,4 @@ -.\" $NetBSD: rnd.4,v 1.18 2011/12/17 21:21:59 wiz Exp $ +.\" $NetBSD: rnd.4,v 1.19 2012/04/17 02:50:39 tls Exp $ .\" .\" Copyright (c) 1997 Michael Graff .\" All rights reserved. @@ -52,13 +52,32 @@ SP 800-90) which is used to generate val the pseudo-device is read. .Pp The pseudodevice is cloning, which means that each time it is opened, -a new instance of the stream generator is created. +a new instance of the stream generator may be created. Interposing a stream generator between the entropy pool and readers in this manner protects readers from each other (each reader's random stream is generated from a unique key) and protects all users of the entropy pool from any attack which might correlate its successive outputs to each other, such as iterative guessing attacks. +.Pp +Certain programs make very short reads from +.Pa /dev/urandom +each time they begin execution. One program with this behavior is +.Xr perl 1 . +If such a program is run repeatedly (for example from a network +service or shell script), the resulting repeated keying of the stream +generator can quickly drain the entropy pool dry. As an optimization +for such cases, a separate per-CPU instance of the stream generator +is used to handle reads from +.Pa /dev/urandom +which are smaller than the key length of the underlying cipher. Any +read of a larger size causes an immediate allocation of a private +instance of the stream generator for the reader. Since all stream +generators are automatically rekeyed upon use when sufficient entropy +is available, the shared short-request generators do still offer +some protection against other consumers of +.Pa /dev/urandom , +though less than is provided for consumers making larger requests. .Sh USER ACCESS User code can obtain random values from the kernel in two ways. .Pp @@ -190,6 +209,20 @@ The device is a tape device. The device is a terminal, mouse, or other user input device. .It Dv RND_TYPE_RNG The device is a random number generator. +.It Dv RND_TYPE_SKEW +The "device" is a measurement of the skew between two clocks, such as a +periodic device interrupt and the system timecounter, a timecounter and +an audio codec, or some other source of pairs of events where each +member of each pair is derived from a different instance of some +recurring physical process. +.It Dv RND_TYPE_ENV +The device is an environmental sensor such as a temperature sensor or +a fan speed sensor. +.It Dv RND_TYPE_VM +The "device" consists of timings of virtual memory system events. +.It Dv RND_TYPE_POWER +The device is a sensor returning changes in the power state of the +system, such as battery charge state or A/C adapter state. .El .Pp .Va flags Index: src/sys/dev/rndpseudo.c diff -u src/sys/dev/rndpseudo.c:1.7 src/sys/dev/rndpseudo.c:1.8 --- src/sys/dev/rndpseudo.c:1.7 Fri Mar 30 20:15:18 2012 +++ src/sys/dev/rndpseudo.c Tue Apr 17 02:50:38 2012 @@ -1,4 +1,4 @@ -/* $NetBSD: rndpseudo.c,v 1.7 2012/03/30 20:15:18 drochner Exp $ */ +/* $NetBSD: rndpseudo.c,v 1.8 2012/04/17 02:50:38 tls Exp $ */ /*- * Copyright (c) 1997-2011 The NetBSD Foundation, Inc. @@ -30,7 +30,7 @@ */ #include <sys/cdefs.h> -__KERNEL_RCSID(0, "$NetBSD: rndpseudo.c,v 1.7 2012/03/30 20:15:18 drochner Exp $"); +__KERNEL_RCSID(0, "$NetBSD: rndpseudo.c,v 1.8 2012/04/17 02:50:38 tls Exp $"); #if defined(_KERNEL_OPT) #include "opt_compat_netbsd.h" @@ -54,6 +54,7 @@ __KERNEL_RCSID(0, "$NetBSD: rndpseudo.c, #include <sys/pool.h> #include <sys/kauth.h> #include <sys/cprng.h> +#include <sys/cpu.h> #include <sys/stat.h> #include <sys/rnd.h> @@ -96,6 +97,11 @@ static pool_cache_t rp_pc; static pool_cache_t rp_cpc; /* + * The per-CPU RNGs used for short requests + */ +cprng_strong_t **rp_cpurngs; + +/* * A context. cprng plus a smidge. */ typedef struct { @@ -193,6 +199,9 @@ rndattach(int num) mutex_spin_enter(&rndpool_mtx); rndpool_add_data(&rnd_pool, &c, sizeof(u_int32_t), 1); mutex_spin_exit(&rndpool_mtx); + + rp_cpurngs = kmem_zalloc(maxcpus * sizeof(cprng_strong_t *), + KM_SLEEP); } int @@ -251,8 +260,10 @@ rnd_read(struct file * fp, off_t *offp, kauth_cred_t cred, int flags) { rp_ctx_t *ctx = fp->f_data; + cprng_strong_t *cprng; u_int8_t *bf; int strength, ret; + struct cpu_info *ci = curcpu(); DPRINTF(RND_DEBUG_READ, ("Random: Read of %zu requested, flags 0x%08x\n", @@ -261,14 +272,35 @@ rnd_read(struct file * fp, off_t *offp, if (uio->uio_resid == 0) return (0); - if (ctx->cprng == NULL) { - rnd_alloc_cprng(ctx); - if (__predict_false(ctx->cprng == NULL)) { - return EIO; + if (ctx->hard || uio->uio_resid > NIST_BLOCK_KEYLEN_BYTES) { + if (ctx->cprng == NULL) { + rnd_alloc_cprng(ctx); } + cprng = ctx->cprng; + } else { + int index = cpu_index(ci); + + if (__predict_false(rp_cpurngs[index] == NULL)) { + char rngname[32]; + + snprintf(rngname, sizeof(rngname), + "%s-short", cpu_name(ci)); + rp_cpurngs[index] = + cprng_strong_create(rngname, IPL_NONE, + CPRNG_INIT_ANY | + CPRNG_REKEY_ANY); + } + cprng = rp_cpurngs[index]; + } + + if (__predict_false(cprng == NULL)) { + printf("NULL rng!\n"); + return EIO; } - strength = cprng_strong_strength(ctx->cprng); + KASSERT(!mutex_owned(&cprng->reseed.mtx)); + + strength = cprng_strong_strength(cprng); ret = 0; bf = pool_cache_get(rp_pc, PR_WAITOK); while (uio->uio_resid > 0) { @@ -284,7 +316,7 @@ rnd_read(struct file * fp, off_t *offp, n = want; } - nread = cprng_strong(ctx->cprng, bf, n, + nread = cprng_strong(cprng, bf, n, (fp->f_flag & FNONBLOCK) ? FNONBLOCK : 0); if (nread != n) { if (fp->f_flag & FNONBLOCK) { @@ -294,6 +326,7 @@ rnd_read(struct file * fp, off_t *offp, } goto out; } + /* KASSERT(!mutex_owned(&cprng->reseed.mtx)); */ ret = uiomove((void *)bf, nread, uio); if (ret != 0 || n < want) { goto out; @@ -302,9 +335,10 @@ rnd_read(struct file * fp, off_t *offp, out: if (ctx->bytesonkey >= strength) { /* Force reseed of underlying DRBG (prediction resistance) */ - cprng_strong_deplete(ctx->cprng); + cprng_strong_deplete(cprng); ctx->bytesonkey = 0; } + pool_cache_put(rp_pc, bf); return (ret); } Index: src/sys/kern/kern_rndpool.c diff -u src/sys/kern/kern_rndpool.c:1.1 src/sys/kern/kern_rndpool.c:1.2 --- src/sys/kern/kern_rndpool.c:1.1 Thu Feb 2 19:43:07 2012 +++ src/sys/kern/kern_rndpool.c Tue Apr 17 02:50:38 2012 @@ -1,4 +1,4 @@ -/* $NetBSD: kern_rndpool.c,v 1.1 2012/02/02 19:43:07 tls Exp $ */ +/* $NetBSD: kern_rndpool.c,v 1.2 2012/04/17 02:50:38 tls Exp $ */ /*- * Copyright (c) 1997 The NetBSD Foundation, Inc. @@ -31,7 +31,7 @@ */ #include <sys/cdefs.h> -__KERNEL_RCSID(0, "$NetBSD: kern_rndpool.c,v 1.1 2012/02/02 19:43:07 tls Exp $"); +__KERNEL_RCSID(0, "$NetBSD: kern_rndpool.c,v 1.2 2012/04/17 02:50:38 tls Exp $"); #include <sys/param.h> #include <sys/systm.h> @@ -52,7 +52,8 @@ __KERNEL_RCSID(0, "$NetBSD: kern_rndpool /* * Let others know: the pool is full. */ -int rnd_full; +int rnd_full = 0; /* Flag: is the pool full? */ +int rnd_filled = 0; /* Count: how many times filled? */ static inline void rndpool_add_one_word(rndpool_t *, u_int32_t); @@ -216,6 +217,7 @@ rndpool_add_data(rndpool_t *rp, void *p, if (rp->stats.curentropy > RND_POOLBITS) { rp->stats.discarded += (rp->stats.curentropy - RND_POOLBITS); rp->stats.curentropy = RND_POOLBITS; + rnd_filled++; rnd_full = 1; } } @@ -246,7 +248,9 @@ rndpool_extract_data(rndpool_t *rp, void buf = p; remain = len; - rnd_full = 0; + if (rp->stats.curentropy < RND_POOLBITS / 2) { + rnd_full = 0; + } if (mode == RND_EXTRACT_ANY) good = 1; Index: src/sys/kern/kern_rndq.c diff -u src/sys/kern/kern_rndq.c:1.2 src/sys/kern/kern_rndq.c:1.3 --- src/sys/kern/kern_rndq.c:1.2 Tue Apr 10 14:02:27 2012 +++ src/sys/kern/kern_rndq.c Tue Apr 17 02:50:38 2012 @@ -1,4 +1,4 @@ -/* $NetBSD: kern_rndq.c,v 1.2 2012/04/10 14:02:27 tls Exp $ */ +/* $NetBSD: kern_rndq.c,v 1.3 2012/04/17 02:50:38 tls Exp $ */ /*- * Copyright (c) 1997-2011 The NetBSD Foundation, Inc. @@ -32,7 +32,7 @@ */ #include <sys/cdefs.h> -__KERNEL_RCSID(0, "$NetBSD: kern_rndq.c,v 1.2 2012/04/10 14:02:27 tls Exp $"); +__KERNEL_RCSID(0, "$NetBSD: kern_rndq.c,v 1.3 2012/04/17 02:50:38 tls Exp $"); #include <sys/param.h> #include <sys/ioctl.h> @@ -221,6 +221,16 @@ rnd_wakeup_readers(void) */ mutex_spin_enter(&rndsink_mtx); TAILQ_FOREACH_SAFE(sink, &rnd_sinks, tailq, tsink) { + if (!mutex_tryenter(&sink->mtx)) { +#ifdef RND_VERBOSE + printf("rnd_wakeup_readers: " + "skipping busy rndsink\n"); +#endif + continue; + } + + KASSERT(RSTATE_PENDING == sink->state); + if ((sink->len + RND_ENTROPY_THRESHOLD) * 8 < rndpool_get_entropy_count(&rnd_pool)) { /* We have enough entropy to sink some here. */ @@ -230,13 +240,12 @@ rnd_wakeup_readers(void) panic("could not extract estimated " "entropy from pool"); } - /* Skip if busy, else mark in-progress */ - if (!mutex_tryenter(&sink->mtx)) { - continue; - } + sink->state = RSTATE_HASBITS; /* Move this sink to the list of pending callbacks */ TAILQ_REMOVE(&rnd_sinks, sink, tailq); TAILQ_INSERT_HEAD(&sunk, sink, tailq); + } else { + mutex_exit(&sink->mtx); } } mutex_spin_exit(&rndsink_mtx); @@ -269,6 +278,7 @@ rnd_wakeup_readers(void) " (cb %p, arg %p).\n", (int)sink->len, sink->name, sink->cb, sink->arg); #endif + sink->state = RSTATE_HASBITS; sink->cb(sink->arg); TAILQ_REMOVE(&sunk, sink, tailq); mutex_spin_exit(&sink->mtx); @@ -976,16 +986,19 @@ rndsink_attach(rndsink_t *rs) #endif KASSERT(mutex_owned(&rs->mtx)); + KASSERT(rs->state = RSTATE_PENDING); mutex_spin_enter(&rndsink_mtx); TAILQ_INSERT_TAIL(&rnd_sinks, rs, tailq); mutex_spin_exit(&rndsink_mtx); + mutex_spin_enter(&rnd_mtx); if (rnd_timeout_pending == 0) { rnd_timeout_pending = 1; callout_schedule(&rnd_callout, 1); } mutex_spin_exit(&rnd_mtx); + } void @@ -995,7 +1008,6 @@ rndsink_detach(rndsink_t *rs) #ifdef RND_VERBOSE printf("rnd: entropy sink \"%s\" no longer wants data.\n", rs->name); #endif - KASSERT(mutex_owned(&rs->mtx)); mutex_spin_enter(&rndsink_mtx); Index: src/sys/kern/subr_cprng.c diff -u src/sys/kern/subr_cprng.c:1.7 src/sys/kern/subr_cprng.c:1.8 --- src/sys/kern/subr_cprng.c:1.7 Tue Apr 10 15:12:40 2012 +++ src/sys/kern/subr_cprng.c Tue Apr 17 02:50:39 2012 @@ -1,4 +1,4 @@ -/* $NetBSD: subr_cprng.c,v 1.7 2012/04/10 15:12:40 tls Exp $ */ +/* $NetBSD: subr_cprng.c,v 1.8 2012/04/17 02:50:39 tls Exp $ */ /*- * Copyright (c) 2011 The NetBSD Foundation, Inc. @@ -46,7 +46,7 @@ #include <sys/cprng.h> -__KERNEL_RCSID(0, "$NetBSD: subr_cprng.c,v 1.7 2012/04/10 15:12:40 tls Exp $"); +__KERNEL_RCSID(0, "$NetBSD: subr_cprng.c,v 1.8 2012/04/17 02:50:39 tls Exp $"); void cprng_init(void) @@ -72,41 +72,82 @@ cprng_counter(void) } static void +cprng_strong_doreseed(cprng_strong_t *const c) +{ + uint32_t cc = cprng_counter(); + + KASSERT(mutex_owned(&c->mtx)); + KASSERT(mutex_owned(&c->reseed.mtx)); + KASSERT(c->reseed.len == NIST_BLOCK_KEYLEN_BYTES); + + if (nist_ctr_drbg_reseed(&c->drbg, c->reseed.data, c->reseed.len, + &cc, sizeof(cc))) { + panic("cprng %s: nist_ctr_drbg_reseed failed.", c->name); + } +#ifdef RND_VERBOSE + printf("cprng %s: reseeded with rnd_filled = %d\n", c->name, + rnd_filled); +#endif + c->entropy_serial = rnd_filled; + c->reseed.state = RSTATE_IDLE; + if (c->flags & CPRNG_USE_CV) { + cv_broadcast(&c->cv); + } + selnotify(&c->selq, 0, 0); +} + +static void cprng_strong_sched_reseed(cprng_strong_t *const c) { KASSERT(mutex_owned(&c->mtx)); - if (!(c->reseed_pending) && mutex_tryenter(&c->reseed.mtx)) { - c->reseed_pending = 1; - c->reseed.len = NIST_BLOCK_KEYLEN_BYTES; - rndsink_attach(&c->reseed); + if (mutex_tryenter(&c->reseed.mtx)) { + switch (c->reseed.state) { + case RSTATE_IDLE: + c->reseed.state = RSTATE_PENDING; + c->reseed.len = NIST_BLOCK_KEYLEN_BYTES; + rndsink_attach(&c->reseed); + break; + case RSTATE_HASBITS: + /* Just rekey the underlying generator now. */ + cprng_strong_doreseed(c); + break; + case RSTATE_PENDING: + if (c->entropy_serial != rnd_filled) { + rndsink_detach(&c->reseed); + rndsink_attach(&c->reseed); + } + break; + default: + panic("cprng %s: bad reseed state %d", + c->name, c->reseed.state); + break; + } mutex_spin_exit(&c->reseed.mtx); } +#ifdef RND_VERBOSE + else { + printf("cprng %s: skipping sched_reseed, sink busy\n", + c->name); + } +#endif } static void cprng_strong_reseed(void *const arg) { cprng_strong_t *c = arg; - uint8_t key[NIST_BLOCK_KEYLEN_BYTES]; - uint32_t cc = cprng_counter(); + + KASSERT(mutex_owned(&c->reseed.mtx)); + KASSERT(RSTATE_HASBITS == c->reseed.state); if (!mutex_tryenter(&c->mtx)) { +#ifdef RND_VERBOSE + printf("cprng: sink %s cprng busy, no reseed\n", c->reseed.name); +#endif return; } - if (c->reseed.len != sizeof(key)) { - panic("cprng_strong_reseed: bad entropy length %d " - " (expected %d)", (int)c->reseed.len, (int)sizeof(key)); - } - if (nist_ctr_drbg_reseed(&c->drbg, c->reseed.data, c->reseed.len, - &cc, sizeof(cc))) { - panic("cprng %s: nist_ctr_drbg_reseed failed.", c->name); - } - c->reseed_pending = 0; - if (c->flags & CPRNG_USE_CV) { - cv_broadcast(&c->cv); - } - selnotify(&c->selq, 0, 0); + cprng_strong_doreseed(c); mutex_exit(&c->mtx); } @@ -124,9 +165,10 @@ cprng_strong_create(const char *const na } c->flags = flags; strlcpy(c->name, name, sizeof(c->name)); - c->reseed_pending = 0; + c->reseed.state = RSTATE_IDLE; c->reseed.cb = cprng_strong_reseed; c->reseed.arg = c; + c->entropy_serial = rnd_filled; mutex_init(&c->reseed.mtx, MUTEX_DEFAULT, IPL_VM); strlcpy(c->reseed.name, name, sizeof(c->reseed.name)); @@ -253,15 +295,15 @@ cprng_strong(cprng_strong_t *const c, vo if (__predict_false(c->drbg.reseed_counter > (NIST_CTR_DRBG_RESEED_INTERVAL / 2))) { cprng_strong_sched_reseed(c); - } - - if (rnd_full) { - if (!c->rekeyed_on_full) { - c->rekeyed_on_full++; + } else if (rnd_full) { + if (c->entropy_serial != rnd_filled) { +#ifdef RND_VERBOSE + printf("cprng %s: reseeding from full pool " + "(serial %d vs pool %d)\n", c->name, + c->entropy_serial, rnd_filled); +#endif cprng_strong_sched_reseed(c); } - } else { - c->rekeyed_on_full = 0; } mutex_exit(&c->mtx); @@ -280,7 +322,7 @@ cprng_strong_destroy(cprng_strong_t *c) } seldestroy(&c->selq); - if (c->reseed_pending) { + if (RSTATE_PENDING == c->reseed.state) { rndsink_detach(&c->reseed); } mutex_spin_exit(&c->reseed.mtx); Index: src/sys/sys/cprng.h diff -u src/sys/sys/cprng.h:1.4 src/sys/sys/cprng.h:1.5 --- src/sys/sys/cprng.h:1.4 Sat Dec 17 20:05:40 2011 +++ src/sys/sys/cprng.h Tue Apr 17 02:50:39 2012 @@ -1,4 +1,4 @@ -/* $NetBSD: cprng.h,v 1.4 2011/12/17 20:05:40 tls Exp $ */ +/* $NetBSD: cprng.h,v 1.5 2012/04/17 02:50:39 tls Exp $ */ /*- * Copyright (c) 2011 The NetBSD Foundation, Inc. @@ -85,7 +85,7 @@ typedef struct _cprng_strong { int flags; char name[16]; int reseed_pending; - int rekeyed_on_full; + int entropy_serial; rndsink_t reseed; } cprng_strong_t; Index: src/sys/sys/rnd.h diff -u src/sys/sys/rnd.h:1.30 src/sys/sys/rnd.h:1.31 --- src/sys/sys/rnd.h:1.30 Tue Apr 10 14:02:28 2012 +++ src/sys/sys/rnd.h Tue Apr 17 02:50:39 2012 @@ -1,4 +1,4 @@ -/* $NetBSD: rnd.h,v 1.30 2012/04/10 14:02:28 tls Exp $ */ +/* $NetBSD: rnd.h,v 1.31 2012/04/17 02:50:39 tls Exp $ */ /*- * Copyright (c) 1997 The NetBSD Foundation, Inc. @@ -127,9 +127,16 @@ typedef struct krndsource { rngtest_t *test; /* test data for RNG type sources */ } krndsource_t; +enum rsink_st { + RSTATE_IDLE = 0, + RSTATE_PENDING, + RSTATE_HASBITS +}; + typedef struct rndsink { TAILQ_ENTRY(rndsink) tailq; /* the queue */ kmutex_t mtx; /* lock to seed or unregister */ + enum rsink_st state; /* in-use? filled? */ void (*cb)(void *); /* callback function when ready */ void *arg; /* callback function argument */ char name[16]; /* sink name */ @@ -178,6 +185,7 @@ rnd_add_uint32(krndsource_t *kr, uint32_ } extern int rnd_full; +extern int rnd_filled; #endif /* _KERNEL */