From 91fcb532efe366d79b93a3c8c368b9dca6176a55 Mon Sep 17 00:00:00 2001 From: Theodore Ts'o Date: Tue, 10 Jun 2014 22:46:37 -0400 Subject: random: always update the entropy pool under the spinlock Instead of using lockless techniques introduced in commit 902c098a3663, use spin_trylock to try to grab entropy pool's lock. If we can't get the lock, then just try again on the next interrupt. Based on discussions with George Spelvin. Signed-off-by: Theodore Ts'o Cc: George Spelvin diff --git a/drivers/char/random.c b/drivers/char/random.c index 0a7ac0a..922a2e4 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -495,9 +495,8 @@ static void _mix_pool_bytes(struct entropy_store *r, const void *in, tap4 = r->poolinfo->tap4; tap5 = r->poolinfo->tap5; - smp_rmb(); - input_rotate = ACCESS_ONCE(r->input_rotate); - i = ACCESS_ONCE(r->add_ptr); + input_rotate = r->input_rotate; + i = r->add_ptr; /* mix one byte at a time to simplify size handling and churn faster */ while (nbytes--) { @@ -524,9 +523,8 @@ static void _mix_pool_bytes(struct entropy_store *r, const void *in, input_rotate = (input_rotate + (i ? 7 : 14)) & 31; } - ACCESS_ONCE(r->input_rotate) = input_rotate; - ACCESS_ONCE(r->add_ptr) = i; - smp_wmb(); + r->input_rotate = input_rotate; + r->add_ptr = i; if (out) for (j = 0; j < 16; j++) @@ -845,7 +843,7 @@ void add_interrupt_randomness(int irq, int irq_flags) __u32 input[4], c_high, j_high; __u64 ip; unsigned long seed; - int credit; + int credit = 0; c_high = (sizeof(cycles) > 4) ? cycles >> 32 : 0; j_high = (sizeof(now) > 4) ? now >> 32 : 0; @@ -860,36 +858,40 @@ void add_interrupt_randomness(int irq, int irq_flags) if ((fast_pool->count & 63) && !time_after(now, fast_pool->last + HZ)) return; - fast_pool->last = now; - r = nonblocking_pool.initialized ? &input_pool : &nonblocking_pool; + if (!spin_trylock(&r->lock)) { + fast_pool->count--; + return; + } + fast_pool->last = now; __mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool), NULL); /* + * If we have architectural seed generator, produce a seed and + * add it to the pool. For the sake of paranoia count it as + * 50% entropic. + */ + if (arch_get_random_seed_long(&seed)) { + __mix_pool_bytes(r, &seed, sizeof(seed), NULL); + credit += sizeof(seed) * 4; + } + spin_unlock(&r->lock); + + /* * If we don't have a valid cycle counter, and we see * back-to-back timer interrupts, then skip giving credit for * any entropy, otherwise credit 1 bit. */ - credit = 1; + credit++; if (cycles == 0) { if (irq_flags & __IRQF_TIMER) { if (fast_pool->last_timer_intr) - credit = 0; + credit--; fast_pool->last_timer_intr = 1; } else fast_pool->last_timer_intr = 0; } - /* - * If we have architectural seed generator, produce a seed and - * add it to the pool. For the sake of paranoia count it as - * 50% entropic. - */ - if (arch_get_random_seed_long(&seed)) { - __mix_pool_bytes(r, &seed, sizeof(seed), NULL); - credit += sizeof(seed) * 4; - } - credit_entropy_bits(r, credit); } -- cgit v0.10.2 From 85608f8e16c28f818f6bb9918958d231afa8bec2 Mon Sep 17 00:00:00 2001 From: Theodore Ts'o Date: Tue, 10 Jun 2014 23:09:20 -0400 Subject: random: remove unneeded hash of a portion of the entropy pool We previously extracted a portion of the entropy pool in mix_pool_bytes() and hashed it in to avoid racing CPU's from returning duplicate random values. Now that we are using a spinlock to prevent this from happening, this is no longer necessary. So remove it, to simplify the code a bit. Signed-off-by: Theodore Ts'o Cc: George Spelvin diff --git a/drivers/char/random.c b/drivers/char/random.c index 922a2e4..bc0de22 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -481,9 +481,9 @@ static __u32 const twist_table[8] = { * the entropy is concentrated in the low-order bits. */ static void _mix_pool_bytes(struct entropy_store *r, const void *in, - int nbytes, __u8 out[64]) + int nbytes) { - unsigned long i, j, tap1, tap2, tap3, tap4, tap5; + unsigned long i, tap1, tap2, tap3, tap4, tap5; int input_rotate; int wordmask = r->poolinfo->poolwords - 1; const char *bytes = in; @@ -525,27 +525,23 @@ static void _mix_pool_bytes(struct entropy_store *r, const void *in, r->input_rotate = input_rotate; r->add_ptr = i; - - if (out) - for (j = 0; j < 16; j++) - ((__u32 *)out)[j] = r->pool[(i - j) & wordmask]; } static void __mix_pool_bytes(struct entropy_store *r, const void *in, - int nbytes, __u8 out[64]) + int nbytes) { trace_mix_pool_bytes_nolock(r->name, nbytes, _RET_IP_); - _mix_pool_bytes(r, in, nbytes, out); + _mix_pool_bytes(r, in, nbytes); } static void mix_pool_bytes(struct entropy_store *r, const void *in, - int nbytes, __u8 out[64]) + int nbytes) { unsigned long flags; trace_mix_pool_bytes(r->name, nbytes, _RET_IP_); spin_lock_irqsave(&r->lock, flags); - _mix_pool_bytes(r, in, nbytes, out); + _mix_pool_bytes(r, in, nbytes); spin_unlock_irqrestore(&r->lock, flags); } @@ -737,13 +733,13 @@ void add_device_randomness(const void *buf, unsigned int size) trace_add_device_randomness(size, _RET_IP_); spin_lock_irqsave(&input_pool.lock, flags); - _mix_pool_bytes(&input_pool, buf, size, NULL); - _mix_pool_bytes(&input_pool, &time, sizeof(time), NULL); + _mix_pool_bytes(&input_pool, buf, size); + _mix_pool_bytes(&input_pool, &time, sizeof(time)); spin_unlock_irqrestore(&input_pool.lock, flags); spin_lock_irqsave(&nonblocking_pool.lock, flags); - _mix_pool_bytes(&nonblocking_pool, buf, size, NULL); - _mix_pool_bytes(&nonblocking_pool, &time, sizeof(time), NULL); + _mix_pool_bytes(&nonblocking_pool, buf, size); + _mix_pool_bytes(&nonblocking_pool, &time, sizeof(time)); spin_unlock_irqrestore(&nonblocking_pool.lock, flags); } EXPORT_SYMBOL(add_device_randomness); @@ -776,7 +772,7 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num) sample.cycles = random_get_entropy(); sample.num = num; r = nonblocking_pool.initialized ? &input_pool : &nonblocking_pool; - mix_pool_bytes(r, &sample, sizeof(sample), NULL); + mix_pool_bytes(r, &sample, sizeof(sample)); /* * Calculate number of bits of randomness we probably added. @@ -864,7 +860,7 @@ void add_interrupt_randomness(int irq, int irq_flags) return; } fast_pool->last = now; - __mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool), NULL); + __mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool)); /* * If we have architectural seed generator, produce a seed and @@ -872,7 +868,7 @@ void add_interrupt_randomness(int irq, int irq_flags) * 50% entropic. */ if (arch_get_random_seed_long(&seed)) { - __mix_pool_bytes(r, &seed, sizeof(seed), NULL); + __mix_pool_bytes(r, &seed, sizeof(seed)); credit += sizeof(seed) * 4; } spin_unlock(&r->lock); @@ -955,7 +951,7 @@ static void _xfer_secondary_pool(struct entropy_store *r, size_t nbytes) ENTROPY_BITS(r), ENTROPY_BITS(r->pull)); bytes = extract_entropy(r->pull, tmp, bytes, random_read_wakeup_bits / 8, rsvd_bytes); - mix_pool_bytes(r, tmp, bytes, NULL); + mix_pool_bytes(r, tmp, bytes); credit_entropy_bits(r, bytes*8); } @@ -1031,7 +1027,6 @@ static void extract_buf(struct entropy_store *r, __u8 *out) unsigned long l[LONGS(20)]; } hash; __u32 workspace[SHA_WORKSPACE_WORDS]; - __u8 extract[64]; unsigned long flags; /* @@ -1060,15 +1055,9 @@ static void extract_buf(struct entropy_store *r, __u8 *out) * brute-forcing the feedback as hard as brute-forcing the * hash. */ - __mix_pool_bytes(r, hash.w, sizeof(hash.w), extract); + __mix_pool_bytes(r, hash.w, sizeof(hash.w)); spin_unlock_irqrestore(&r->lock, flags); - /* - * To avoid duplicates, we atomically extract a portion of the - * pool while mixing, and hash one final time. - */ - sha_transform(hash.w, extract, workspace); - memset(extract, 0, sizeof(extract)); memset(workspace, 0, sizeof(workspace)); /* @@ -1255,14 +1244,14 @@ static void init_std_data(struct entropy_store *r) unsigned long rv; r->last_pulled = jiffies; - mix_pool_bytes(r, &now, sizeof(now), NULL); + mix_pool_bytes(r, &now, sizeof(now)); for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) { if (!arch_get_random_seed_long(&rv) && !arch_get_random_long(&rv)) rv = random_get_entropy(); - mix_pool_bytes(r, &rv, sizeof(rv), NULL); + mix_pool_bytes(r, &rv, sizeof(rv)); } - mix_pool_bytes(r, utsname(), sizeof(*(utsname())), NULL); + mix_pool_bytes(r, utsname(), sizeof(*(utsname()))); } /* @@ -1325,7 +1314,7 @@ static int arch_random_refill(void) if (n) { unsigned int rand_bytes = n * sizeof(unsigned long); - mix_pool_bytes(&input_pool, buf, rand_bytes, NULL); + mix_pool_bytes(&input_pool, buf, rand_bytes); credit_entropy_bits(&input_pool, rand_bytes*4); } @@ -1415,7 +1404,7 @@ write_pool(struct entropy_store *r, const char __user *buffer, size_t count) count -= bytes; p += bytes; - mix_pool_bytes(r, buf, bytes, NULL); + mix_pool_bytes(r, buf, bytes); cond_resched(); } -- cgit v0.10.2 From cff850312cc7c0e0b9fe8b573687812dea232031 Mon Sep 17 00:00:00 2001 From: Theodore Ts'o Date: Tue, 10 Jun 2014 23:18:16 -0400 Subject: random: only update the last_pulled time if we actually transferred entropy In xfer_secondary_pull(), check to make sure we need to pull from the secondary pool before checking and potentially updating the last_pulled time. Signed-off-by: Theodore Ts'o Cc: George Spelvin diff --git a/drivers/char/random.c b/drivers/char/random.c index bc0de22..364a800 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -920,6 +920,11 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf, static void _xfer_secondary_pool(struct entropy_store *r, size_t nbytes); static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes) { + if (!r->pull || + r->entropy_count >= (nbytes << (ENTROPY_SHIFT + 3)) || + r->entropy_count > r->poolinfo->poolfracbits) + return; + if (r->limit == 0 && random_min_urandom_seed) { unsigned long now = jiffies; @@ -928,10 +933,8 @@ static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes) return; r->last_pulled = now; } - if (r->pull && - r->entropy_count < (nbytes << (ENTROPY_SHIFT + 3)) && - r->entropy_count < r->poolinfo->poolfracbits) - _xfer_secondary_pool(r, nbytes); + + _xfer_secondary_pool(r, nbytes); } static void _xfer_secondary_pool(struct entropy_store *r, size_t nbytes) -- cgit v0.10.2 From 840f95077ffd640df9c74ad9796fa094a5c8075a Mon Sep 17 00:00:00 2001 From: Theodore Ts'o Date: Sat, 14 Jun 2014 03:06:57 -0400 Subject: random: clean up interrupt entropy accounting for archs w/o cycle counters For architectures that don't have cycle counters, the algorithm for deciding when to avoid giving entropy credit due to back-to-back timer interrupts didn't make any sense, since we were checking every 64 interrupts. Change it so that we only give an entropy credit if the majority of the interrupts are not based on the timer. Signed-off-by: Theodore Ts'o Cc: George Spelvin diff --git a/drivers/char/random.c b/drivers/char/random.c index 364a800..dfe918a 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -548,9 +548,9 @@ static void mix_pool_bytes(struct entropy_store *r, const void *in, struct fast_pool { __u32 pool[4]; unsigned long last; - unsigned short count; + unsigned char count; + unsigned char notimer_count; unsigned char rotate; - unsigned char last_timer_intr; }; /* @@ -850,15 +850,23 @@ void add_interrupt_randomness(int irq, int irq_flags) input[3] = ip >> 32; fast_mix(fast_pool, input); + if ((irq_flags & __IRQF_TIMER) == 0) + fast_pool->notimer_count++; - if ((fast_pool->count & 63) && !time_after(now, fast_pool->last + HZ)) - return; + if (cycles) { + if ((fast_pool->count < 64) && + !time_after(now, fast_pool->last + HZ)) + return; + } else { + /* CPU does not have a cycle counting register :-( */ + if (fast_pool->count < 64) + return; + } r = nonblocking_pool.initialized ? &input_pool : &nonblocking_pool; - if (!spin_trylock(&r->lock)) { - fast_pool->count--; + if (!spin_trylock(&r->lock)) return; - } + fast_pool->last = now; __mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool)); @@ -874,19 +882,15 @@ void add_interrupt_randomness(int irq, int irq_flags) spin_unlock(&r->lock); /* - * If we don't have a valid cycle counter, and we see - * back-to-back timer interrupts, then skip giving credit for - * any entropy, otherwise credit 1 bit. + * If we have a valid cycle counter or if the majority of + * interrupts collected were non-timer interrupts, then give + * an entropy credit of 1 bit. Yes, this is being very + * conservative. */ - credit++; - if (cycles == 0) { - if (irq_flags & __IRQF_TIMER) { - if (fast_pool->last_timer_intr) - credit--; - fast_pool->last_timer_intr = 1; - } else - fast_pool->last_timer_intr = 0; - } + if (cycles || (fast_pool->notimer_count >= 32)) + credit++; + + fast_pool->count = fast_pool->notimer_count = 0; credit_entropy_bits(r, credit); } -- cgit v0.10.2 From 43759d4f429c8d55fd56f863542e20f4e6e8f589 Mon Sep 17 00:00:00 2001 From: Theodore Ts'o Date: Sat, 14 Jun 2014 21:43:13 -0400 Subject: random: use an improved fast_mix() function Use more efficient fast_mix() function. Thanks to George Spelvin for doing the leg work to find a more efficient mixing function. Signed-off-by: Theodore Ts'o Cc: George Spelvin diff --git a/drivers/char/random.c b/drivers/char/random.c index dfe918a..d3bb792 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -267,6 +267,8 @@ #define CREATE_TRACE_POINTS #include +/* #define ADD_INTERRUPT_BENCH */ + /* * Configuration information */ @@ -558,25 +560,29 @@ struct fast_pool { * collector. It's hardcoded for an 128 bit pool and assumes that any * locks that might be needed are taken by the caller. */ -static void fast_mix(struct fast_pool *f, __u32 input[4]) +static void fast_mix(struct fast_pool *f) { - __u32 w; - unsigned input_rotate = f->rotate; - - w = rol32(input[0], input_rotate) ^ f->pool[0] ^ f->pool[3]; - f->pool[0] = (w >> 3) ^ twist_table[w & 7]; - input_rotate = (input_rotate + 14) & 31; - w = rol32(input[1], input_rotate) ^ f->pool[1] ^ f->pool[0]; - f->pool[1] = (w >> 3) ^ twist_table[w & 7]; - input_rotate = (input_rotate + 7) & 31; - w = rol32(input[2], input_rotate) ^ f->pool[2] ^ f->pool[1]; - f->pool[2] = (w >> 3) ^ twist_table[w & 7]; - input_rotate = (input_rotate + 7) & 31; - w = rol32(input[3], input_rotate) ^ f->pool[3] ^ f->pool[2]; - f->pool[3] = (w >> 3) ^ twist_table[w & 7]; - input_rotate = (input_rotate + 7) & 31; - - f->rotate = input_rotate; + __u32 a = f->pool[0], b = f->pool[1]; + __u32 c = f->pool[2], d = f->pool[3]; + + a += b; c += d; + b = rol32(a, 6); d = rol32(c, 27); + d ^= a; b ^= c; + + a += b; c += d; + b = rol32(a, 16); d = rol32(c, 14); + d ^= a; b ^= c; + + a += b; c += d; + b = rol32(a, 6); d = rol32(c, 27); + d ^= a; b ^= c; + + a += b; c += d; + b = rol32(a, 16); d = rol32(c, 14); + d ^= a; b ^= c; + + f->pool[0] = a; f->pool[1] = b; + f->pool[2] = c; f->pool[3] = d; f->count++; } @@ -829,6 +835,27 @@ EXPORT_SYMBOL_GPL(add_input_randomness); static DEFINE_PER_CPU(struct fast_pool, irq_randomness); +#ifdef ADD_INTERRUPT_BENCH +static unsigned long avg_cycles, avg_deviation; + +#define AVG_SHIFT 8 /* Exponential average factor k=1/256 */ +#define FIXED_1_2 (1 << (AVG_SHIFT-1)) + +static void add_interrupt_bench(cycles_t start) +{ + long delta = random_get_entropy() - start; + + /* Use a weighted moving average */ + delta = delta - ((avg_cycles + FIXED_1_2) >> AVG_SHIFT); + avg_cycles += delta; + /* And average deviation */ + delta = abs(delta) - ((avg_deviation + FIXED_1_2) >> AVG_SHIFT); + avg_deviation += delta; +} +#else +#define add_interrupt_bench(x) +#endif + void add_interrupt_randomness(int irq, int irq_flags) { struct entropy_store *r; @@ -836,22 +863,23 @@ void add_interrupt_randomness(int irq, int irq_flags) struct pt_regs *regs = get_irq_regs(); unsigned long now = jiffies; cycles_t cycles = random_get_entropy(); - __u32 input[4], c_high, j_high; + __u32 c_high, j_high; __u64 ip; unsigned long seed; int credit = 0; c_high = (sizeof(cycles) > 4) ? cycles >> 32 : 0; j_high = (sizeof(now) > 4) ? now >> 32 : 0; - input[0] = cycles ^ j_high ^ irq; - input[1] = now ^ c_high; + fast_pool->pool[0] ^= cycles ^ j_high ^ irq; + fast_pool->pool[1] ^= now ^ c_high; ip = regs ? instruction_pointer(regs) : _RET_IP_; - input[2] = ip; - input[3] = ip >> 32; + fast_pool->pool[2] ^= ip; + fast_pool->pool[3] ^= ip >> 32; - fast_mix(fast_pool, input); + fast_mix(fast_pool); if ((irq_flags & __IRQF_TIMER) == 0) fast_pool->notimer_count++; + add_interrupt_bench(cycles); if (cycles) { if ((fast_pool->count < 64) && @@ -1650,6 +1678,22 @@ struct ctl_table random_table[] = { .mode = 0444, .proc_handler = proc_do_uuid, }, +#ifdef ADD_INTERRUPT_BENCH + { + .procname = "add_interrupt_avg_cycles", + .data = &avg_cycles, + .maxlen = sizeof(avg_cycles), + .mode = 0444, + .proc_handler = proc_doulongvec_minmax, + }, + { + .procname = "add_interrupt_avg_deviation", + .data = &avg_deviation, + .maxlen = sizeof(avg_deviation), + .mode = 0444, + .proc_handler = proc_doulongvec_minmax, + }, +#endif { } }; #endif /* CONFIG_SYSCTL */ -- cgit v0.10.2 From c84dbf61a7b322188d2a7fddc0cc6317ac6713e2 Mon Sep 17 00:00:00 2001 From: Torsten Duwe Date: Sat, 14 Jun 2014 23:38:36 -0400 Subject: random: add_hwgenerator_randomness() for feeding entropy from devices This patch adds an interface to the random pool for feeding entropy in-kernel. Signed-off-by: Torsten Duwe Signed-off-by: Theodore Ts'o Acked-by: H. Peter Anvin diff --git a/drivers/char/random.c b/drivers/char/random.c index d3bb792..914b157 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -250,6 +250,7 @@ #include #include #include +#include #include #include #include @@ -1750,3 +1751,23 @@ randomize_range(unsigned long start, unsigned long end, unsigned long len) return 0; return PAGE_ALIGN(get_random_int() % range + start); } + +/* Interface for in-kernel drivers of true hardware RNGs. + * Those devices may produce endless random bits and will be throttled + * when our pool is full. + */ +void add_hwgenerator_randomness(const char *buffer, size_t count, + size_t entropy) +{ + struct entropy_store *poolp = &input_pool; + + /* Suspend writing if we're above the trickle threshold. + * We'll be woken up again once below random_write_wakeup_thresh, + * or when the calling thread is about to terminate. + */ + wait_event_interruptible(random_write_wait, kthread_should_stop() || + ENTROPY_BITS(&input_pool) <= random_write_wakeup_bits); + mix_pool_bytes(poolp, buffer, count); + credit_entropy_bits(poolp, entropy); +} +EXPORT_SYMBOL_GPL(add_hwgenerator_randomness); diff --git a/include/linux/hw_random.h b/include/linux/hw_random.h index b4b0eef..3f075ff 100644 --- a/include/linux/hw_random.h +++ b/include/linux/hw_random.h @@ -47,5 +47,7 @@ struct hwrng { extern int hwrng_register(struct hwrng *rng); /** Unregister a Hardware Random Number Generator driver. */ extern void hwrng_unregister(struct hwrng *rng); +/** Feed random bits into the pool. */ +extern void add_hwgenerator_randomness(const char *buffer, size_t count, size_t entropy); #endif /* LINUX_HWRANDOM_H_ */ -- cgit v0.10.2 From be4000bc4644d027c519b6361f5ae3bbfc52c347 Mon Sep 17 00:00:00 2001 From: Torsten Duwe Date: Sat, 14 Jun 2014 23:46:03 -0400 Subject: hwrng: create filler thread This can be viewed as the in-kernel equivalent of hwrngd; like FUSE it is a good thing to have a mechanism in user land, but for some reasons (simplicity, secrecy, integrity, speed) it may be better to have it in kernel space. This patch creates a thread once a hwrng registers, and uses the previously established add_hwgenerator_randomness() to feed its data to the input pool as long as needed. A derating factor is used to bias the entropy estimation and to disable this mechanism entirely when set to zero. Signed-off-by: Torsten Duwe Signed-off-by: Theodore Ts'o Acked-by: H. Peter Anvin diff --git a/drivers/char/hw_random/core.c b/drivers/char/hw_random/core.c index 334601c..48b3c81 100644 --- a/drivers/char/hw_random/core.c +++ b/drivers/char/hw_random/core.c @@ -38,6 +38,7 @@ #include #include #include +#include #include #include #include @@ -50,10 +51,18 @@ static struct hwrng *current_rng; +static struct task_struct *hwrng_fill; static LIST_HEAD(rng_list); static DEFINE_MUTEX(rng_mutex); static int data_avail; -static u8 *rng_buffer; +static u8 *rng_buffer, *rng_fillbuf; +static unsigned short current_quality = 700; /* an arbitrary 70% */ + +module_param(current_quality, ushort, 0644); +MODULE_PARM_DESC(current_quality, + "current hwrng entropy estimation per mill"); + +static void start_khwrngd(void); static size_t rng_buffer_size(void) { @@ -62,9 +71,18 @@ static size_t rng_buffer_size(void) static inline int hwrng_init(struct hwrng *rng) { - if (!rng->init) - return 0; - return rng->init(rng); + int err; + + if (rng->init) { + err = rng->init(rng); + if (err) + return err; + } + + if (current_quality > 0 && !hwrng_fill) + start_khwrngd(); + + return 0; } static inline void hwrng_cleanup(struct hwrng *rng) @@ -300,6 +318,36 @@ err_misc_dereg: goto out; } +static int hwrng_fillfn(void *unused) +{ + long rc; + + while (!kthread_should_stop()) { + if (!current_rng) + break; + rc = rng_get_data(current_rng, rng_fillbuf, + rng_buffer_size(), 1); + if (rc <= 0) { + pr_warn("hwrng: no data available\n"); + msleep_interruptible(10000); + continue; + } + add_hwgenerator_randomness((void *)rng_fillbuf, rc, + (rc*current_quality)>>10); + } + hwrng_fill = 0; + return 0; +} + +static void start_khwrngd(void) +{ + hwrng_fill = kthread_run(hwrng_fillfn, NULL, "hwrng"); + if (hwrng_fill == ERR_PTR(-ENOMEM)) { + pr_err("hwrng_fill thread creation failed"); + hwrng_fill = NULL; + } +} + int hwrng_register(struct hwrng *rng) { int err = -EINVAL; @@ -320,6 +368,13 @@ int hwrng_register(struct hwrng *rng) if (!rng_buffer) goto out_unlock; } + if (!rng_fillbuf) { + rng_fillbuf = kmalloc(rng_buffer_size(), GFP_KERNEL); + if (!rng_fillbuf) { + kfree(rng_buffer); + goto out_unlock; + } + } /* Must not register two RNGs with the same name. */ err = -EEXIST; @@ -375,8 +430,11 @@ void hwrng_unregister(struct hwrng *rng) current_rng = NULL; } } - if (list_empty(&rng_list)) + if (list_empty(&rng_list)) { unregister_miscdev(); + if (hwrng_fill) + kthread_stop(hwrng_fill); + } mutex_unlock(&rng_mutex); } @@ -387,6 +445,7 @@ static void __exit hwrng_exit(void) mutex_lock(&rng_mutex); BUG_ON(current_rng); kfree(rng_buffer); + kfree(rng_fillbuf); mutex_unlock(&rng_mutex); } -- cgit v0.10.2 From 0f734e6e768b4b66737b3d3e13f1769a12ecff86 Mon Sep 17 00:00:00 2001 From: Torsten Duwe Date: Sat, 14 Jun 2014 23:48:41 -0400 Subject: hwrng: add per-device entropy derating This patch introduces a derating factor to struct hwrng for the random bits going into the kernel input pool, and a common default derating for drivers which do not specify one. Signed-off-by: Torsten Duwe Signed-off-by: Theodore Ts'o Acked-by: H. Peter Anvin diff --git a/drivers/char/hw_random/core.c b/drivers/char/hw_random/core.c index 48b3c81..3aaf97c 100644 --- a/drivers/char/hw_random/core.c +++ b/drivers/char/hw_random/core.c @@ -56,11 +56,15 @@ static LIST_HEAD(rng_list); static DEFINE_MUTEX(rng_mutex); static int data_avail; static u8 *rng_buffer, *rng_fillbuf; -static unsigned short current_quality = 700; /* an arbitrary 70% */ +static unsigned short current_quality; +static unsigned short default_quality; /* = 0; default to "off" */ module_param(current_quality, ushort, 0644); MODULE_PARM_DESC(current_quality, "current hwrng entropy estimation per mill"); +module_param(default_quality, ushort, 0644); +MODULE_PARM_DESC(default_quality, + "default entropy content of hwrng per mill"); static void start_khwrngd(void); @@ -79,6 +83,11 @@ static inline int hwrng_init(struct hwrng *rng) return err; } + current_quality = rng->quality ? : default_quality; + current_quality &= 1023; + + if (current_quality == 0 && hwrng_fill) + kthread_stop(hwrng_fill); if (current_quality > 0 && !hwrng_fill) start_khwrngd(); diff --git a/include/linux/hw_random.h b/include/linux/hw_random.h index 3f075ff..914bb08 100644 --- a/include/linux/hw_random.h +++ b/include/linux/hw_random.h @@ -29,6 +29,8 @@ * @read: New API. drivers can fill up to max bytes of data * into the buffer. The buffer is aligned for any type. * @priv: Private data, for use by the RNG driver. + * @quality: Estimation of true entropy in RNG's bitstream + * (per mill). */ struct hwrng { const char *name; @@ -38,6 +40,7 @@ struct hwrng { int (*data_read)(struct hwrng *rng, u32 *data); int (*read)(struct hwrng *rng, void *data, size_t max, bool wait); unsigned long priv; + unsigned short quality; /* internal. */ struct list_head list; -- cgit v0.10.2 From ee3e00e9e7101c80a2ff2d5672d4b486bf001b88 Mon Sep 17 00:00:00 2001 From: Theodore Ts'o Date: Sun, 15 Jun 2014 16:59:24 -0400 Subject: random: use registers from interrupted code for CPU's w/o a cycle counter MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit For CPU's that don't have a cycle counter, or something equivalent which can be used for random_get_entropy(), random_get_entropy() will always return 0. In that case, substitute with the saved interrupt registers to add a bit more unpredictability. Some folks have suggested hashing all of the registers unconditionally, but this would increase the overhead of add_interrupt_randomness() by at least an order of magnitude, and this would very likely be unacceptable. The changes in this commit have been benchmarked as mostly unaffecting the overhead of add_interrupt_randomness() if the entropy counter is present, and doubling the overhead if it is not present. Signed-off-by: Theodore Ts'o Cc: Jörn Engel diff --git a/drivers/char/random.c b/drivers/char/random.c index 914b157..aa22fe5 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -551,9 +551,8 @@ static void mix_pool_bytes(struct entropy_store *r, const void *in, struct fast_pool { __u32 pool[4]; unsigned long last; + unsigned short reg_idx; unsigned char count; - unsigned char notimer_count; - unsigned char rotate; }; /* @@ -857,6 +856,17 @@ static void add_interrupt_bench(cycles_t start) #define add_interrupt_bench(x) #endif +static __u32 get_reg(struct fast_pool *f, struct pt_regs *regs) +{ + __u32 *ptr = (__u32 *) regs; + + if (regs == NULL) + return 0; + if (f->reg_idx >= sizeof(struct pt_regs) / sizeof(__u32)) + f->reg_idx = 0; + return *(ptr + f->reg_idx++); +} + void add_interrupt_randomness(int irq, int irq_flags) { struct entropy_store *r; @@ -869,28 +879,23 @@ void add_interrupt_randomness(int irq, int irq_flags) unsigned long seed; int credit = 0; + if (cycles == 0) + cycles = get_reg(fast_pool, regs); c_high = (sizeof(cycles) > 4) ? cycles >> 32 : 0; j_high = (sizeof(now) > 4) ? now >> 32 : 0; fast_pool->pool[0] ^= cycles ^ j_high ^ irq; fast_pool->pool[1] ^= now ^ c_high; ip = regs ? instruction_pointer(regs) : _RET_IP_; fast_pool->pool[2] ^= ip; - fast_pool->pool[3] ^= ip >> 32; + fast_pool->pool[3] ^= (sizeof(ip) > 4) ? ip >> 32 : + get_reg(fast_pool, regs); fast_mix(fast_pool); - if ((irq_flags & __IRQF_TIMER) == 0) - fast_pool->notimer_count++; add_interrupt_bench(cycles); - if (cycles) { - if ((fast_pool->count < 64) && - !time_after(now, fast_pool->last + HZ)) - return; - } else { - /* CPU does not have a cycle counting register :-( */ - if (fast_pool->count < 64) - return; - } + if ((fast_pool->count < 64) && + !time_after(now, fast_pool->last + HZ)) + return; r = nonblocking_pool.initialized ? &input_pool : &nonblocking_pool; if (!spin_trylock(&r->lock)) @@ -910,18 +915,10 @@ void add_interrupt_randomness(int irq, int irq_flags) } spin_unlock(&r->lock); - /* - * If we have a valid cycle counter or if the majority of - * interrupts collected were non-timer interrupts, then give - * an entropy credit of 1 bit. Yes, this is being very - * conservative. - */ - if (cycles || (fast_pool->notimer_count >= 32)) - credit++; - - fast_pool->count = fast_pool->notimer_count = 0; + fast_pool->count = 0; - credit_entropy_bits(r, credit); + /* award one bit for the contents of the fast pool */ + credit_entropy_bits(r, credit + 1); } #ifdef CONFIG_BLOCK -- cgit v0.10.2 From 9dda727d37ff6ce1628dd2b8557ad011c49db377 Mon Sep 17 00:00:00 2001 From: Torsten Duwe Date: Mon, 16 Jun 2014 10:24:09 -0400 Subject: hw_random: fix sparse warning (NULL vs 0 for pointer) Signed-off-by: Torsten Duwe Signed-off-by: Theodore Ts'o diff --git a/drivers/char/hw_random/core.c b/drivers/char/hw_random/core.c index 3aaf97c..349a3b8 100644 --- a/drivers/char/hw_random/core.c +++ b/drivers/char/hw_random/core.c @@ -344,7 +344,7 @@ static int hwrng_fillfn(void *unused) add_hwgenerator_randomness((void *)rng_fillbuf, rc, (rc*current_quality)>>10); } - hwrng_fill = 0; + hwrng_fill = NULL; return 0; } -- cgit v0.10.2 From c6e9d6f38894798696f23c8084ca7edbf16ee895 Mon Sep 17 00:00:00 2001 From: Theodore Ts'o Date: Thu, 17 Jul 2014 04:13:05 -0400 Subject: random: introduce getrandom(2) system call The getrandom(2) system call was requested by the LibreSSL Portable developers. It is analoguous to the getentropy(2) system call in OpenBSD. The rationale of this system call is to provide resiliance against file descriptor exhaustion attacks, where the attacker consumes all available file descriptors, forcing the use of the fallback code where /dev/[u]random is not available. Since the fallback code is often not well-tested, it is better to eliminate this potential failure mode entirely. The other feature provided by this new system call is the ability to request randomness from the /dev/urandom entropy pool, but to block until at least 128 bits of entropy has been accumulated in the /dev/urandom entropy pool. Historically, the emphasis in the /dev/urandom development has been to ensure that urandom pool is initialized as quickly as possible after system boot, and preferably before the init scripts start execution. This is because changing /dev/urandom reads to block represents an interface change that could potentially break userspace which is not acceptable. In practice, on most x86 desktop and server systems, in general the entropy pool can be initialized before it is needed (and in modern kernels, we will printk a warning message if not). However, on an embedded system, this may not be the case. And so with this new interface, we can provide the functionality of blocking until the urandom pool has been initialized. Any userspace program which uses this new functionality must take care to assure that if it is used during the boot process, that it will not cause the init scripts or other portions of the system startup to hang indefinitely. SYNOPSIS #include int getrandom(void *buf, size_t buflen, unsigned int flags); DESCRIPTION The system call getrandom() fills the buffer pointed to by buf with up to buflen random bytes which can be used to seed user space random number generators (i.e., DRBG's) or for other cryptographic uses. It should not be used for Monte Carlo simulations or other programs/algorithms which are doing probabilistic sampling. If the GRND_RANDOM flags bit is set, then draw from the /dev/random pool instead of the /dev/urandom pool. The /dev/random pool is limited based on the entropy that can be obtained from environmental noise, so if there is insufficient entropy, the requested number of bytes may not be returned. If there is no entropy available at all, getrandom(2) will either block, or return an error with errno set to EAGAIN if the GRND_NONBLOCK bit is set in flags. If the GRND_RANDOM bit is not set, then the /dev/urandom pool will be used. Unlike using read(2) to fetch data from /dev/urandom, if the urandom pool has not been sufficiently initialized, getrandom(2) will block (or return -1 with the errno set to EAGAIN if the GRND_NONBLOCK bit is set in flags). The getentropy(2) system call in OpenBSD can be emulated using the following function: int getentropy(void *buf, size_t buflen) { int ret; if (buflen > 256) goto failure; ret = getrandom(buf, buflen, 0); if (ret < 0) return ret; if (ret == buflen) return 0; failure: errno = EIO; return -1; } RETURN VALUE On success, the number of bytes that was filled in the buf is returned. This may not be all the bytes requested by the caller via buflen if insufficient entropy was present in the /dev/random pool, or if the system call was interrupted by a signal. On error, -1 is returned, and errno is set appropriately. ERRORS EINVAL An invalid flag was passed to getrandom(2) EFAULT buf is outside the accessible address space. EAGAIN The requested entropy was not available, and getentropy(2) would have blocked if the GRND_NONBLOCK flag was not set. EINTR While blocked waiting for entropy, the call was interrupted by a signal handler; see the description of how interrupted read(2) calls on "slow" devices are handled with and without the SA_RESTART flag in the signal(7) man page. NOTES For small requests (buflen <= 256) getrandom(2) will not return EINTR when reading from the urandom pool once the entropy pool has been initialized, and it will return all of the bytes that have been requested. This is the recommended way to use getrandom(2), and is designed for compatibility with OpenBSD's getentropy() system call. However, if you are using GRND_RANDOM, then getrandom(2) may block until the entropy accounting determines that sufficient environmental noise has been gathered such that getrandom(2) will be operating as a NRBG instead of a DRBG for those people who are working in the NIST SP 800-90 regime. Since it may block for a long time, these guarantees do *not* apply. The user may want to interrupt a hanging process using a signal, so blocking until all of the requested bytes are returned would be unfriendly. For this reason, the user of getrandom(2) MUST always check the return value, in case it returns some error, or if fewer bytes than requested was returned. In the case of !GRND_RANDOM and small request, the latter should never happen, but the careful userspace code (and all crypto code should be careful) should check for this anyway! Finally, unless you are doing long-term key generation (and perhaps not even then), you probably shouldn't be using GRND_RANDOM. The cryptographic algorithms used for /dev/urandom are quite conservative, and so should be sufficient for all purposes. The disadvantage of GRND_RANDOM is that it can block, and the increased complexity required to deal with partially fulfilled getrandom(2) requests. Signed-off-by: Theodore Ts'o Reviewed-by: Zach Brown diff --git a/arch/x86/syscalls/syscall_32.tbl b/arch/x86/syscalls/syscall_32.tbl index d6b8679..5b46a61 100644 --- a/arch/x86/syscalls/syscall_32.tbl +++ b/arch/x86/syscalls/syscall_32.tbl @@ -360,3 +360,4 @@ 351 i386 sched_setattr sys_sched_setattr 352 i386 sched_getattr sys_sched_getattr 353 i386 renameat2 sys_renameat2 +355 i386 getrandom sys_getrandom diff --git a/arch/x86/syscalls/syscall_64.tbl b/arch/x86/syscalls/syscall_64.tbl index ec255a1..0dc4bf8 100644 --- a/arch/x86/syscalls/syscall_64.tbl +++ b/arch/x86/syscalls/syscall_64.tbl @@ -323,6 +323,7 @@ 314 common sched_setattr sys_sched_setattr 315 common sched_getattr sys_sched_getattr 316 common renameat2 sys_renameat2 +318 common getrandom sys_getrandom # # x32-specific system call numbers start at 512 to avoid cache impact diff --git a/drivers/char/random.c b/drivers/char/random.c index aa22fe5..7d1682e 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -258,6 +258,8 @@ #include #include #include +#include +#include #include #include @@ -404,6 +406,7 @@ static struct poolinfo { */ static DECLARE_WAIT_QUEUE_HEAD(random_read_wait); static DECLARE_WAIT_QUEUE_HEAD(random_write_wait); +static DECLARE_WAIT_QUEUE_HEAD(urandom_init_wait); static struct fasync_struct *fasync; /********************************************************************** @@ -657,6 +660,7 @@ retry: r->entropy_total = 0; if (r == &nonblocking_pool) { prandom_reseed_late(); + wake_up_interruptible(&urandom_init_wait); pr_notice("random: %s pool is initialized\n", r->name); } } @@ -1174,13 +1178,14 @@ static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf, { ssize_t ret = 0, i; __u8 tmp[EXTRACT_SIZE]; + int large_request = (nbytes > 256); trace_extract_entropy_user(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_); xfer_secondary_pool(r, nbytes); nbytes = account(r, nbytes, 0, 0); while (nbytes) { - if (need_resched()) { + if (large_request && need_resched()) { if (signal_pending(current)) { if (ret == 0) ret = -ERESTARTSYS; @@ -1355,7 +1360,7 @@ static int arch_random_refill(void) } static ssize_t -random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) +_random_read(int nonblock, char __user *buf, size_t nbytes) { ssize_t n; @@ -1379,7 +1384,7 @@ random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) if (arch_random_refill()) continue; - if (file->f_flags & O_NONBLOCK) + if (nonblock) return -EAGAIN; wait_event_interruptible(random_read_wait, @@ -1391,6 +1396,12 @@ random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) } static ssize_t +random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) +{ + return _random_read(file->f_flags & O_NONBLOCK, buf, nbytes); +} + +static ssize_t urandom_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) { int ret; @@ -1533,6 +1544,29 @@ const struct file_operations urandom_fops = { .llseek = noop_llseek, }; +SYSCALL_DEFINE3(getrandom, char __user *, buf, size_t, count, + unsigned int, flags) +{ + if (flags & ~(GRND_NONBLOCK|GRND_RANDOM)) + return -EINVAL; + + if (count > INT_MAX) + count = INT_MAX; + + if (flags & GRND_RANDOM) + return _random_read(flags & GRND_NONBLOCK, buf, count); + + if (unlikely(nonblocking_pool.initialized == 0)) { + if (flags & GRND_NONBLOCK) + return -EAGAIN; + wait_event_interruptible(urandom_init_wait, + nonblocking_pool.initialized); + if (signal_pending(current)) + return -ERESTARTSYS; + } + return urandom_read(NULL, buf, count, NULL); +} + /*************************************************************** * Random UUID interface * diff --git a/include/linux/syscalls.h b/include/linux/syscalls.h index b0881a0..43324a8 100644 --- a/include/linux/syscalls.h +++ b/include/linux/syscalls.h @@ -866,4 +866,7 @@ asmlinkage long sys_process_vm_writev(pid_t pid, asmlinkage long sys_kcmp(pid_t pid1, pid_t pid2, int type, unsigned long idx1, unsigned long idx2); asmlinkage long sys_finit_module(int fd, const char __user *uargs, int flags); +asmlinkage long sys_getrandom(char __user *buf, size_t count, + unsigned int flags); + #endif diff --git a/include/uapi/asm-generic/unistd.h b/include/uapi/asm-generic/unistd.h index 3336406..1d104a2 100644 --- a/include/uapi/asm-generic/unistd.h +++ b/include/uapi/asm-generic/unistd.h @@ -699,9 +699,11 @@ __SYSCALL(__NR_sched_setattr, sys_sched_setattr) __SYSCALL(__NR_sched_getattr, sys_sched_getattr) #define __NR_renameat2 276 __SYSCALL(__NR_renameat2, sys_renameat2) +#define __NR_getrandom 278 +__SYSCALL(__NR_getrandom, sys_getrandom) #undef __NR_syscalls -#define __NR_syscalls 277 +#define __NR_syscalls 279 /* * All syscalls below here should go away really, diff --git a/include/uapi/linux/random.h b/include/uapi/linux/random.h index fff3528..3f93d16 100644 --- a/include/uapi/linux/random.h +++ b/include/uapi/linux/random.h @@ -40,4 +40,13 @@ struct rand_pool_info { __u32 buf[0]; }; +/* + * Flags for getrandom(2) + * + * GRND_NONBLOCK Don't block and return EAGAIN instead + * GRND_RANDOM Use the /dev/random pool instead of /dev/urandom + */ +#define GRND_NONBLOCK 0x0001 +#define GRND_RANDOM 0x0002 + #endif /* _UAPI_LINUX_RANDOM_H */ -- cgit v0.10.2 From 48d6be955a7167b0d0e025ae6c39e795e3544499 Mon Sep 17 00:00:00 2001 From: Theodore Ts'o Date: Thu, 17 Jul 2014 05:27:30 -0400 Subject: random: limit the contribution of the hw rng to at most half For people who don't trust a hardware RNG which can not be audited, the changes to add support for RDSEED can be troubling since 97% or more of the entropy will be contributed from the in-CPU hardware RNG. We now have a in-kernel khwrngd, so for those people who do want to implicitly trust the CPU-based system, we could create an arch-rng hw_random driver, and allow khwrng refill the entropy pool. This allows system administrator whether or not they trust the CPU (I assume the NSA will trust RDRAND/RDSEED implicitly :-), and if so, what level of entropy derating they want to use. The reason why this is a really good idea is that if different people use different levels of entropy derating, it will make it much more difficult to design a backdoor'ed hwrng that can be generally exploited in terms of the output of /dev/random when different attack targets are using differing levels of entropy derating. Signed-off-by: Theodore Ts'o diff --git a/drivers/char/random.c b/drivers/char/random.c index 7d1682e..6e455bc 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -910,12 +910,13 @@ void add_interrupt_randomness(int irq, int irq_flags) /* * If we have architectural seed generator, produce a seed and - * add it to the pool. For the sake of paranoia count it as - * 50% entropic. + * add it to the pool. For the sake of paranoia don't let the + * architectural seed generator dominate the input from the + * interrupt noise. */ if (arch_get_random_seed_long(&seed)) { __mix_pool_bytes(r, &seed, sizeof(seed)); - credit += sizeof(seed) * 4; + credit = 1; } spin_unlock(&r->lock); @@ -1328,37 +1329,6 @@ void rand_initialize_disk(struct gendisk *disk) } #endif -/* - * Attempt an emergency refill using arch_get_random_seed_long(). - * - * As with add_interrupt_randomness() be paranoid and only - * credit the output as 50% entropic. - */ -static int arch_random_refill(void) -{ - const unsigned int nlongs = 64; /* Arbitrary number */ - unsigned int n = 0; - unsigned int i; - unsigned long buf[nlongs]; - - if (!arch_has_random_seed()) - return 0; - - for (i = 0; i < nlongs; i++) { - if (arch_get_random_seed_long(&buf[n])) - n++; - } - - if (n) { - unsigned int rand_bytes = n * sizeof(unsigned long); - - mix_pool_bytes(&input_pool, buf, rand_bytes); - credit_entropy_bits(&input_pool, rand_bytes*4); - } - - return n; -} - static ssize_t _random_read(int nonblock, char __user *buf, size_t nbytes) { @@ -1379,11 +1349,6 @@ _random_read(int nonblock, char __user *buf, size_t nbytes) return n; /* Pool is (near) empty. Maybe wait and retry. */ - - /* First try an emergency refill */ - if (arch_random_refill()) - continue; - if (nonblock) return -EAGAIN; -- cgit v0.10.2 From e02b876597777ab26288dd2611a97b597d14d661 Mon Sep 17 00:00:00 2001 From: Stephen Boyd Date: Fri, 25 Jul 2014 15:19:18 -0700 Subject: hwrng: Pass entropy to add_hwgenerator_randomness() in bits, not bytes rng_get_data() returns the number of bytes read from the hardware. The entropy argument to add_hwgenerator_randomness() is passed directly to credit_entropy_bits() so we should be passing the number of bits, not bytes here. Fixes: be4000bc464 "hwrng: create filler thread" Acked-by: Torsten Duwe Signed-off-by: Stephen Boyd Signed-off-by: Theodore Ts'o diff --git a/drivers/char/hw_random/core.c b/drivers/char/hw_random/core.c index 349a3b8..33fd663 100644 --- a/drivers/char/hw_random/core.c +++ b/drivers/char/hw_random/core.c @@ -342,7 +342,7 @@ static int hwrng_fillfn(void *unused) continue; } add_hwgenerator_randomness((void *)rng_fillbuf, rc, - (rc*current_quality)>>10); + rc * current_quality * 8 >> 10); } hwrng_fill = NULL; return 0; -- cgit v0.10.2