More eyes requested (Re: Kernel entropy pool / cprng race fix)

Thor Lancelot Simon <[email protected]> Thu, 12 Apr 2012 18:29:39 -0400
Newsgroups gmane.os.netbsd.devel.kernel,gmane.os.netbsd.devel.crypto
Message-ID <[email protected]> 
On Fri, Apr 06, 2012 at 10:59:16AM -0400, Thor Lancelot Simon wrote:
> The attached patch should fix a race that exists when an entropy sink
> (such as a CPRNG instance that is being reseeded) is destroyed while
> it is currently being reseeded.
> 
> I've minimally tested it but since the problem is hard to reproduce
> I'd appreciate additional testers or additional eyes.
> 
> The diff is also at http://www.panix.com/~tls/seed-destroy.diff .

This is checked in, and has one bugfix courtesy of Matthias Drochner.

The attached patch is -- mostly -- an optimization for the odd case
where someone runs a program very frequently that opens /dev/urandom
and does a short read every time it's run (some versions of the perl
interpreter, invoked, let's say, on a busy CGI host, act like this).

It adds a per-CPU persistent cprng_strong that is used to service short
requests.  I don't use percpu(9) as I don't really care if occasionally
we switch away from the "home" CPU of a cprng before generating; there
is locking to make that safe.  This way avoids a lot of kpreempt_disable()s.

It also changes the rekeying strategy on pool full.  In the course of
testing that, I discovered a bug in the reseed / destroy race fix:
the reseed_pending variable on the cprng could get set but not cleared
if a reseed was skipped because the cprng's mutex was held.

The patch attached here tries to fix that, but now there is a LOCKDEBUG
problem: sometimes we seem to get to the uiomove() in rnd_read with
the reseed spin mutex held.  I don't see how this is possible but it
can be reproduced like this:

% sysctl -w ddb.onpanic=1
% dd if=/dev/urandom of=/dev/null bs=4 &
% dd if=/dev/sd0d of=/dev/null &

When the entropy pool fills and the per-cpu rng is rekeyed, the
LOCKDEBUG panic occurs.

I'd really appreciate help with this; I've just spent my whole
commute on it and I don't see how we get to that uiomove() with a
spin lock held!  The rekeying fix and short-read optimizations are
important, since they address real problems with real-world use cases,
so I really want to get this debugged and in the tree.

Diff is also at http://www.panix.com/~tls/rngpercpu.diff .

Thor
rngpercpu.diff (text/plain, 3.5 KB) 
? 1
? rh
? rngpercpu.diff
? seed-destroy.diff
? arch/amd64/conf/RNDVERBOSE
? arch/arm/xscale/.iopaau.c.swp
? dev/.rndpseudo.c.swp
? kern/1
? kern/lastbatch.txt
? sys/.cprng.h.swp
? sys/.cpu.h.swp
Index: dev/rndpseudo.c
===================================================================
RCS file: /cvsroot/src/sys/dev/rndpseudo.c,v
retrieving revision 1.6
diff -r1.6 rndpseudo.c
56a57
> #include <sys/cpu.h>
98a100,104
>  * The per-CPU RNGs used for short requests
>  */
> cprng_strong_t **rp_cpurngs;
> 
> /*
195a202,204
> 
> 	rp_cpurngs = kmem_zalloc(maxcpus * sizeof(cprng_strong_t *),
> 				 KM_SLEEP);
254a264
> 	cprng_strong_t *cprng;
256a267
> 	struct cpu_info *ci = curcpu();
265,268c276,278
< 	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);
269a280,299
> 		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;
272c302
< 	strength = cprng_strong_strength(ctx->cprng);
---
> 	strength = cprng_strong_strength(cprng);
288c318
< 		nread = cprng_strong(ctx->cprng, bf, n,
---
> 		nread = cprng_strong(cprng, bf, n,
306c336
< 		cprng_strong_deplete(ctx->cprng);
---
> 		cprng_strong_deplete(cprng);
308a339
> 
Index: kern/kern_rndpool.c
===================================================================
RCS file: /cvsroot/src/sys/kern/kern_rndpool.c,v
retrieving revision 1.1
diff -r1.1 kern_rndpool.c
55c55,56
< int rnd_full;
---
> int rnd_full = 0;			/* Flag: is the pool full? */
> int rnd_filled = 0;			/* Count: how many times filled? */
218a220
> 		rnd_filled++;
249c251,253
< 	rnd_full = 0;
---
> 	if (rp->stats.curentropy < RND_POOLBITS / 2) {
> 		rnd_full = 0;
> 	}
Index: kern/subr_cprng.c
===================================================================
RCS file: /cvsroot/src/sys/kern/subr_cprng.c,v
retrieving revision 1.7
diff -r1.7 subr_cprng.c
78,79c78,79
< 	if (!(c->reseed_pending) && mutex_tryenter(&c->reseed.mtx)) {
< 		c->reseed_pending = 1;
---
> 	if (mutex_tryenter(&c->reseed.mtx) && !c->reseed.pending) {
> 		c->reseed.pending = 1;
92a93,94
> 	KASSERT(mutex_owned(&c->reseed.mtx));
> 
105c107,108
< 	c->reseed_pending = 0;
---
> 	c->entropy_serial = rnd_filled;
> 	c->reseed.pending = 0;
127c130
< 	c->reseed_pending = 0;
---
> 	c->reseed.pending = 0;
129a133
> 	c->entropy_serial = rnd_filled;
256,260c260,261
< 	}
< 
< 	if (rnd_full) {
< 		if (!c->rekeyed_on_full) {
< 			c->rekeyed_on_full++;
---
> 	} else if (rnd_full) {
> 		if (c->entropy_serial != rnd_filled) {
263,264d263
< 	} else {
< 		c->rekeyed_on_full = 0;
283c282
< 	if (c->reseed_pending) {
---
> 	if (c->reseed.pending) {
Index: sys/cprng.h
===================================================================
RCS file: /cvsroot/src/sys/sys/cprng.h,v
retrieving revision 1.4
diff -r1.4 cprng.h
88c88
< 	int		rekeyed_on_full;
---
> 	int		entropy_serial;
Index: sys/rnd.h
===================================================================
RCS file: /cvsroot/src/sys/sys/rnd.h,v
retrieving revision 1.30
diff -r1.30 rnd.h
132a133
> 	int		pending;	/* currently in use */
180a182
> extern int	rnd_filled;