From 18684082fb953d52f0a86d854e4cc9ff9325767e Mon Sep 17 00:00:00 2001 From: John Denker Date: Tue, 8 Oct 2013 18:57:39 -0700 Subject: implement adaptive appetite --- drivers/char/random.c | 88 +++++++++++++++++++++++++++++++++++---------------- 1 file changed, 61 insertions(+), 27 deletions(-) (limited to 'drivers/char/random.c') diff --git a/drivers/char/random.c b/drivers/char/random.c index 57ec883..e83f645 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -286,6 +286,18 @@ */ #define FILL_FRAC(X) ((X)*3/4) +typedef unsigned long long int ulonglong; +#if defined __SIZEOF_LONG_LONG__ && __SIZEOF_LONG_LONG__ == 8 +/* This is how it should be using gcc + * on Intel x86_32 and also Intel 64 architectures. + * I don't know how to extrapolate to other architectures + * or other compilers ... + * but at least we are being properly defensive. + */ +#else +#error Broken assumption: __SIZEOF_LONG_LONG__ should be defined and equal to 8 +#endif + #define LONGS(x) (((x) + sizeof(unsigned long) - 1)/sizeof(unsigned long)) #define W2BYTE(X) ((X)*4) /* convert #words to #bytes */ #define W2BIT(X) ((X)*32) /* convert #words to #bits */ @@ -447,8 +459,8 @@ struct entropy_store { unsigned input_rotate; int entropy_count; int entropy_total; /* entropy input; used only during initialization */ - uint64_t extracted_subttl; - uint64_t extracted_total; + ulonglong extracted_subttl; + ulonglong extracted_total; unsigned int initialized:1; bool last_data_init; __u8 last_data[EXTRACT_SIZE]; @@ -458,10 +470,10 @@ static __u32 input_pool_data[INPUT_POOL_WORDS]; static __u32 blocking_pool_data[OUTPUT_POOL_WORDS]; static __u32 nonblocking_pool_data[OUTPUT_POOL_WORDS]; #ifdef NOTUSED - static uint64_t uint64_zero = 0; - static uint64_t uint64_max = ~((uint64_t)0); + static ulonglong uint64_zero = 0; + static ulonglong uint64_max = ~((ulonglong)0); #endif -static uint64_t play = sizeof(uint64_t)*10000 + sizeof(ulong)*100 + sizeof(int); +static ulonglong play = sizeof(ulonglong)*10000 + sizeof(ulong)*100 + sizeof(int); static struct entropy_store input_pool = { .poolinfo = &poolinfo_table[0], @@ -836,35 +848,54 @@ static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes) { __u32 tmp[OUTPUT_POOL_WORDS]; - if (r->pull && r->entropy_count < nbytes * 8 && - r->entropy_count < r->poolinfo->POOLBITS) { - /* If we're non-blocking, protect the reserved amount of entropy: */ - int rsvd = r->limit ? 0 : FILL_FRAC(W2BYTE(r->pull->poolinfo->poolwords)); + if (!r->pull) return; + if (r->entropy_count < nbytes * 8 && r->entropy_count < r->poolinfo->POOLBITS) { + int rsvd = 0; int bytes = nbytes; - - /* Request a big-enough batch: */ + 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; +/* 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 the buffer size */ + /* but never more than our buffer size */ bytes = min_t(int, bytes, sizeof(tmp)); - DEBUG_ENT("going to reseed %s with %d bits " - "(%zu of %d requested)\n", + 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), rsvd); + 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; } /* * These functions extracts randomness from the "entropy pool", and * returns it in a buffer. * - * The min parameter specifies the minimum amount we can pull before - * failing to avoid races that defeat catastrophic reseeding while the - * reserved parameter indicates how much entropy we must leave in the - * pool after each pull to avoid starving other readers. + * The /min/ parameter specifies the minimum amount we are allowed to pull; + * otherwise we pull nothing. This can be used to make sure the + * pull is "significant" to any attacker. + * The /reserved/ parameter indicates how much entropy we must leave + * in the pool after each pull to avoid starving other readers. * * Note: extract_entropy() assumes that .poolwords is a multiple of 16 words. */ @@ -1029,8 +1060,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: */ r->extracted_subttl += BYTE2BIT(ret); + if (r->extracted_subttl > 1000000000000000000LL) r->extracted_subttl = 1000000000000000000LL; r->extracted_total += BYTE2BIT(ret); + if (r->extracted_total > 1000000000000000000LL) r->extracted_total = 1000000000000000000LL; } return ret; } @@ -1473,56 +1507,56 @@ struct ctl_table random_table[] = { }, { .procname = "play_int", - .maxlen = sizeof(uint64_t), + .maxlen = sizeof(ulonglong), .mode = 0644, .proc_handler = proc_dointvec, .data = &play, }, { .procname = "play_long", - .maxlen = sizeof(uint64_t), + .maxlen = sizeof(ulonglong), .mode = 0644, .proc_handler = proc_doulonglongvec_minmax, .data = &play, }, { .procname = "extracted_total", - .maxlen = sizeof(uint64_t), + .maxlen = sizeof(ulonglong), .mode = 0644, .proc_handler = proc_doulonglongvec_minmax, .data = &input_pool.extracted_total, }, { .procname = "extracted_total_r", - .maxlen = sizeof(uint64_t), + .maxlen = sizeof(ulonglong), .mode = 0644, .proc_handler = proc_doulonglongvec_minmax, .data = &blocking_pool.extracted_total, }, { .procname = "extracted_total_ur", - .maxlen = sizeof(uint64_t), + .maxlen = sizeof(ulonglong), .mode = 0644, .proc_handler = proc_doulonglongvec_minmax, .data = &nonblocking_pool.extracted_total, }, { .procname = "extracted_subttl", - .maxlen = sizeof(uint64_t), + .maxlen = sizeof(ulonglong), .mode = 0644, .proc_handler = proc_doulonglongvec_minmax, .data = &input_pool.extracted_subttl, }, { .procname = "extracted_subttl_r", - .maxlen = sizeof(uint64_t), + .maxlen = sizeof(ulonglong), .mode = 0644, .proc_handler = proc_doulonglongvec_minmax, .data = &blocking_pool.extracted_subttl, }, { .procname = "extracted_subttl_ur", - .maxlen = sizeof(uint64_t), + .maxlen = sizeof(ulonglong), .mode = 0644, .proc_handler = proc_doulonglongvec_minmax, .data = &nonblocking_pool.extracted_subttl, -- cgit v1.2.3