Messages in this thread | | | Date | Sat, 29 Sep 2012 12:47:04 -0700 | From | "H. Peter Anvin" <> | Subject | Re: [PATCH RFC] random: Account for entropy loss due to overwrites |
| |
Ping on this patch?
-hpa
On 08/13/2012 10:26 AM, H. Peter Anvin wrote: > From: "H. Peter Anvin" <hpa@linux.intel.com> > > When we write entropy into a non-empty pool, we currently don't > account at all for the fact that we will probabilistically overwrite > some of the entropy in that pool. This means that unless the pool is > fully empty, we are currently *guaranteed* to overestimate the amount > of entropy in the pool! > > Assuming Shannon entropy with zero correlations we end up with an > exponentally decaying value of new entropy added: > > entropy <- entropy + (pool_size - entropy) * > (1 - exp(-add_entropy/pool_size)) > > However, calculations involving fractional exponentials are not > practical in the kernel, so apply a piecewise linearization: > > For add_entropy <= pool_size then > > (1 - exp(-add_entropy/pool_size)) >= (add_entropy/pool_size)*0.632... > > ... so we can approximate the exponential with > add_entropy/(pool_size*2) and still be on the > safe side by adding at most one pool_size at a time. > > In order for the loop not to take arbitrary amounts of time if a bad > ioctl is received, terminate if we are within one bit of full. This > way the loop is guaranteed to terminate after no more than > log2(poolsize) iterations, no matter what the input value is. The > vast majority of the time the loop will be executed exactly once. > > The piecewise linearization is very conservative, approaching 1/2 of > the usable input value for small inputs, however, our entropy > estimation is pretty weak at best, especially for small values; we > have no handle on correlation; and the Shannon entropy measure (Rényi > entropy of order 1) is not the correct one to use in the first place, > but rather the correct entropy measure is the min-entropy, the Rényi > entropy of infinite order. > > As such, this conservatism seems more than justified. Note, however, > that attempting to add one bit of entropy will never succeed; nor will > two bits unless the pool is completely empty. These roundoff > artifacts could be improved by using fixed-point arithmetic and adding > some number of fractional entropy bits. > > Signed-off-by: H. Peter Anvin <hpa@linux.intel.com> > Cc: DJ Johnston <dj.johnston@intel.com> > Cc: <stable@vger.kernel.org> > --- > drivers/char/random.c | 104 ++++++++++++++++++++++++++++++++++---------------- > 1 file changed, 72 insertions(+), 32 deletions(-) > > diff --git a/drivers/char/random.c b/drivers/char/random.c > index b86eae9..5d870ad 100644 > --- a/drivers/char/random.c > +++ b/drivers/char/random.c > @@ -272,10 +272,12 @@ > /* > * Configuration information > */ > -#define INPUT_POOL_WORDS 128 > -#define OUTPUT_POOL_WORDS 32 > -#define SEC_XFER_SIZE 512 > -#define EXTRACT_SIZE 10 > +#define INPUT_POOL_SHIFT 12 > +#define INPUT_POOL_WORDS (1 << (INPUT_POOL_SHIFT-5)) > +#define OUTPUT_POOL_SHIFT 10 > +#define OUTPUT_POOL_WORDS (1 << (OUTPUT_POOL_SHIFT-5)) > +#define SEC_XFER_SIZE 512 > +#define EXTRACT_SIZE 10 > > #define LONGS(x) (((x) + sizeof(unsigned long) - 1)/sizeof(unsigned long)) > > @@ -309,40 +311,41 @@ static DEFINE_PER_CPU(int, trickle_count); > * scaled squared error sum) except for the last tap, which is 1 to > * get the twisting happening as fast as possible. > */ > -static struct poolinfo { > +static const struct poolinfo { > + int poolshift; /* log2(POOLBITS) */ > int poolwords; > int tap1, tap2, tap3, tap4, tap5; > } poolinfo_table[] = { > - /* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */ > - { 128, 103, 76, 51, 25, 1 }, > - /* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */ > - { 32, 26, 20, 14, 7, 1 }, > + /* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */ > + { 12, 128, 103, 76, 51, 25, 1 }, > + /* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */ > + { 10, 32, 26, 20, 14, 7, 1 }, > #if 0 > - /* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1 -- 115 */ > - { 2048, 1638, 1231, 819, 411, 1 }, > + /* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1 -- 115 */ > + { 16, 2048, 1638, 1231, 819, 411, 1 }, > > - /* x^1024 + x^817 + x^615 + x^412 + x^204 + x + 1 -- 290 */ > - { 1024, 817, 615, 412, 204, 1 }, > + /* x^1024 + x^817 + x^615 + x^412 + x^204 + x + 1 -- 290 */ > + { 15, 1024, 817, 615, 412, 204, 1 }, > > - /* x^1024 + x^819 + x^616 + x^410 + x^207 + x^2 + 1 -- 115 */ > - { 1024, 819, 616, 410, 207, 2 }, > + /* x^1024 + x^819 + x^616 + x^410 + x^207 + x^2 + 1 -- 115 */ > + { 15, 1024, 819, 616, 410, 207, 2 }, > > - /* x^512 + x^411 + x^308 + x^208 + x^104 + x + 1 -- 225 */ > - { 512, 411, 308, 208, 104, 1 }, > + /* x^512 + x^411 + x^308 + x^208 + x^104 + x + 1 -- 225 */ > + { 14, 512, 411, 308, 208, 104, 1 }, > > - /* x^512 + x^409 + x^307 + x^206 + x^102 + x^2 + 1 -- 95 */ > - { 512, 409, 307, 206, 102, 2 }, > - /* x^512 + x^409 + x^309 + x^205 + x^103 + x^2 + 1 -- 95 */ > - { 512, 409, 309, 205, 103, 2 }, > + /* x^512 + x^409 + x^307 + x^206 + x^102 + x^2 + 1 -- 95 */ > + { 14, 512, 409, 307, 206, 102, 2 }, > + /* x^512 + x^409 + x^309 + x^205 + x^103 + x^2 + 1 -- 95 */ > + { 14, 512, 409, 309, 205, 103, 2 }, > > - /* x^256 + x^205 + x^155 + x^101 + x^52 + x + 1 -- 125 */ > - { 256, 205, 155, 101, 52, 1 }, > + /* x^256 + x^205 + x^155 + x^101 + x^52 + x + 1 -- 125 */ > + { 13, 256, 205, 155, 101, 52, 1 }, > > - /* x^128 + x^103 + x^78 + x^51 + x^27 + x^2 + 1 -- 70 */ > - { 128, 103, 78, 51, 27, 2 }, > + /* x^128 + x^103 + x^78 + x^51 + x^27 + x^2 + 1 -- 70 */ > + { 12, 128, 103, 78, 51, 27, 2 }, > > - /* x^64 + x^52 + x^39 + x^26 + x^14 + x + 1 -- 15 */ > - { 64, 52, 39, 26, 14, 1 }, > + /* x^64 + x^52 + x^39 + x^26 + x^14 + x + 1 -- 15 */ > + { 11, 64, 52, 39, 26, 14, 1 }, > #endif > }; > > @@ -424,7 +427,7 @@ module_param(debug, bool, 0644); > struct entropy_store; > struct entropy_store { > /* read-only data: */ > - struct poolinfo *poolinfo; > + const struct poolinfo *poolinfo; > __u32 *pool; > const char *name; > struct entropy_store *pull; > @@ -585,11 +588,13 @@ static void fast_mix(struct fast_pool *f, const void *in, int nbytes) > } > > /* > - * Credit (or debit) the entropy store with n bits of entropy > + * Credit (or debit) the entropy store with n bits of entropy. > + * The nbits value is given in units of 2^-16 bits, i.e. 0x10000 == 1 bit. > */ > static void credit_entropy_bits(struct entropy_store *r, int nbits) > { > int entropy_count, orig; > + int pool_size = r->poolinfo->POOLBITS; > > if (!nbits) > return; > @@ -597,13 +602,48 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits) > DEBUG_ENT("added %d entropy credits to %s\n", nbits, r->name); > retry: > entropy_count = orig = ACCESS_ONCE(r->entropy_count); > - entropy_count += nbits; > + if (nbits < 0) { > + /* Debit. */ > + entropy_count += nbits; > + } else { > + /* > + * Credit: we have to account for the possibility of > + * overwriting already present entropy. Even in the > + * ideal case of pure Shannon entropy, new contributions > + * approach the full value asymptotically: > + * > + * entropy <- entropy + (pool_size - entropy) * > + * (1 - exp(-add_entropy/pool_size)) > + * > + * For add_entropy <= pool_size then > + * (1 - exp(-add_entropy/pool_size)) >= > + * (add_entropy/pool_size)*0.632... > + * so we can approximate the exponential with > + * add_entropy/(pool_size*2) and still be on the > + * safe side by adding at most one pool_size at a time. > + * > + * The use of pool_size-1 in the while statement is to > + * prevent rounding artifacts from making the loop > + * arbitrarily long; this limits the loop to poolshift > + * turns no matter how large nbits is. > + */ > + int pnbits = nbits; > + int s = r->poolinfo->poolshift + 1; > + > + do { > + int anbits = min(pnbits, pool_size); > + > + entropy_count += > + ((pool_size - entropy_count)*anbits) >> s; > + pnbits -= anbits; > + } while (unlikely(entropy_count < pool_size-1 && pnbits)); > + } > > if (entropy_count < 0) { > DEBUG_ENT("negative entropy/overflow\n"); > entropy_count = 0; > - } else if (entropy_count > r->poolinfo->POOLBITS) > - entropy_count = r->poolinfo->POOLBITS; > + } else if (entropy_count > pool_size) > + entropy_count = pool_size; > if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig) > goto retry; > >
-- H. Peter Anvin, Intel Open Source Technology Center I work for Intel. I don't speak on their behalf.
-- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |