From cc743a3f097f6f634501b6229a25faa6086bd8af Mon Sep 17 00:00:00 2001 From: John Denker Date: Tue, 8 Oct 2013 22:29:39 -0700 Subject: fix some logic and math errors --- drivers/char/random.c | 122 +++++++++++++++++++++++++++++--------------------- 1 file changed, 70 insertions(+), 52 deletions(-) (limited to 'drivers') diff --git a/drivers/char/random.c b/drivers/char/random.c index e83f645..a93ea7e 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -840,51 +840,64 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf, size_t nbytes, int min, int rsvd); /* - * This utility inline function is responsible for transferring entropy - * from the primary pool to the secondary extraction pool. We make - * sure we pull enough for a 'catastrophic reseed'. + * This function is responsible for filling this pool (r) + * to an appropriate level, by pulling from the upstream + * pool (r->pull), if any, if necessary. + * + * We enforce (probably redundantly) the requirement that + * any pull be large enough to be "significant" to any attacker. + * + * In principle, this would cascade, pulling from other pools + * even farther upstream, but as it stands there are only two + * pools, so no cascade. */ -static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes) -{ +static void fill_pool( + struct entropy_store *r, + size_t want_level /* measured in bytes */ +){ __u32 tmp[OUTPUT_POOL_WORDS]; - - if (!r->pull) return; - if (r->entropy_count < nbytes * 8 && r->entropy_count < r->poolinfo->POOLBITS) { - int rsvd = 0; - int bytes = nbytes; - if (!r->limit) { + int rsvd = 0; /* measured in bits */ + int actual; /* measured in BYTES */ + int txbits = BYTE2BIT(want_level) - r->entropy_count; + if (txbits < 0) return; /* already have enough */ + if (r->entropy_count >= r->poolinfo->POOLBITS) return; /* already full */ + if (!r->pull) return; /* no upstream pool to pull from */ + if (!r->limit) { /* - * Here if we are non-limited i.e. non-blocking i.e. urandom. - * Reserve a suitable amount of entropy in the input pool, - * based on how desperate we are to be reseeded. - * - * The dilution factor ranges from 819 to 1 (at appetite=0) - * to 858,993,459 to 1 (at appetite=20) - */ - int appetite = fls64(r->extracted_subttl) - 18; - if (appetite < 0) return; /* 128k bits maps to appetite 0 */ -/* Max possible rsvd: */ - rsvd = W2BIT(r->pull->poolinfo->poolwords) - RESEED_BATCH; +* Here if we are non-limited i.e. non-blocking i.e. urandom. +* Reserve a suitable amount of entropy in the input pool, a +* sliding scale based on how desperately we need to be reseeded. +* +* The dilution factor ranges from 819 to 1 (at appetite=0) +* to 858,993,459 to 1 (at appetite=20) +*/ + int appetite = fls64(r->extracted_subttl) - 18; + if (appetite < 0) return; /* 128k bits maps to appetite 0 */ +/* The largest rsvd that makes any sense: */ + rsvd = W2BIT(r->pull->poolinfo->poolwords) - RESEED_BATCH; /* When the appetite gets to 20, rsvd goes to zero: */ - rsvd = rsvd - appetite*rsvd/20; - if (rsvd < 0) rsvd = 0; - } - - /* Make the request big enough to be "significant" to any attacker: */ - bytes = max_t(int, bytes, BIT2BYTE(RESEED_BATCH)); - /* but never more than our buffer size */ - bytes = min_t(int, bytes, sizeof(tmp)); - - DEBUG_ENT("Going to reseed %s with %d bits; " - "caller requested: %zu prev level: %d\n", - r->name, bytes * 8, nbytes * 8, r->entropy_count); - - bytes = extract_entropy(r->pull, tmp, bytes, - BIT2BYTE(RESEED_BATCH), BIT2BYTE(rsvd)); - mix_pool_bytes(r, tmp, bytes, NULL); - credit_entropy_bits(r, bytes*8); - } -// FIXME: return bytes; + rsvd = rsvd - appetite*rsvd/20; + if (rsvd < 0) rsvd = 0; + } + + /* Make the request big enough to be "significant" to any attacker: */ + txbits = max_t(int, txbits, RESEED_BATCH); + /* but never more than our buffer size */ + txbits = min_t(int, txbits, 8*sizeof(tmp)); + + DEBUG_ENT("Going to reseed %s with %d bits; " + "caller want_level: %zu prev level: %d\n", + r->name, txbits, + want_level * 8, r->entropy_count); + + actual = extract_entropy(r->pull, tmp, BIT2BYTE(txbits), + BIT2BYTE(RESEED_BATCH), BIT2BYTE(rsvd)); + mix_pool_bytes(r, tmp, actual, NULL); + credit_entropy_bits(r, actual*8); + if (BYTE2BIT(actual) > RESEED_BATCH) { + r->extracted_subttl = 0; + } +// FIXME: return actual; } /* @@ -1012,8 +1025,9 @@ static void extract_buf(struct entropy_store *r, __u8 *out) memset(&hash, 0, sizeof(hash)); } +/* returns actual number of bytes extracted */ static ssize_t extract_entropy(struct entropy_store *r, void *buf, - size_t nbytes, int min, int reserved) + size_t txbytes, int min, int reserved) { ssize_t ret = 0, i; __u8 tmp[EXTRACT_SIZE]; @@ -1027,7 +1041,7 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf, spin_unlock_irqrestore(&r->lock, flags); trace_extract_entropy(r->name, EXTRACT_SIZE, r->entropy_count, _RET_IP_); - xfer_secondary_pool(r, EXTRACT_SIZE); + fill_pool(r, EXTRACT_SIZE); extract_buf(r, tmp); spin_lock_irqsave(&r->lock, flags); memcpy(r->last_data, tmp, EXTRACT_SIZE); @@ -1035,11 +1049,15 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf, spin_unlock_irqrestore(&r->lock, flags); } - trace_extract_entropy(r->name, nbytes, r->entropy_count, _RET_IP_); - xfer_secondary_pool(r, nbytes); - nbytes = account(r, nbytes, min, reserved); + trace_extract_entropy(r->name, txbytes, r->entropy_count, _RET_IP_); +/* We want our pool (r) to have enough, if possible. + * So pull it up to a level (txbits) that will cover the + * extraction we are about to do. + */ + fill_pool(r, txbytes); + txbytes = account(r, txbytes, min, reserved); - while (nbytes) { + while (txbytes) { extract_buf(r, tmp); if (fips_enabled) { @@ -1049,9 +1067,9 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf, memcpy(r->last_data, tmp, EXTRACT_SIZE); spin_unlock_irqrestore(&r->lock, flags); } - i = min_t(int, nbytes, EXTRACT_SIZE); + i = min_t(int, txbytes, EXTRACT_SIZE); memcpy(buf, tmp, i); - nbytes -= i; + txbytes -= i; buf += i; ret += i; } @@ -1060,11 +1078,11 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf, memset(tmp, 0, sizeof(tmp)); if (ret > 0) { -/* Prevent overflow; saturate at a user-friendly round number: */ +/* Subttl does not overflow; it saturates at a user-friendly round number: */ r->extracted_subttl += BYTE2BIT(ret); if (r->extracted_subttl > 1000000000000000000LL) r->extracted_subttl = 1000000000000000000LL; +/* Total does not saturate; it just overflows and wraps around. */ r->extracted_total += BYTE2BIT(ret); - if (r->extracted_total > 1000000000000000000LL) r->extracted_total = 1000000000000000000LL; } return ret; } @@ -1076,7 +1094,7 @@ static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf, __u8 tmp[EXTRACT_SIZE]; trace_extract_entropy_user(r->name, nbytes, r->entropy_count, _RET_IP_); - xfer_secondary_pool(r, nbytes); + fill_pool(r, nbytes); nbytes = account(r, nbytes, 0, 0); while (nbytes) { -- cgit v1.2.3