[PATCH, RFC 00/12] random driver changes

[PATCH, RFC 00/12] random driver changes

[Theodore Ts'o]

Recent events have inspired me to take a closer look at the /dev/random
driver and make a number of changes to improve it.  The changes reflect
relatively minor changes across the entire /dev/random architecture,
including:

* how we collect entropy on non-x86 architectures
* optimizing the CPU overhead when we collect entropy
* improving our entropy accumulation estimates
* small changes to the mixing function suggested by researchers who have
	been analyzing the /dev/random driver

I would appreciate folks taking a look at the changes and making any
comments, asking questions, etc.

Cheers!

						- Ted

H. Peter Anvin (3):
  random: Statically compute poolbitshift, poolbytes, poolbits
  random: Allow fractional bits to be tracked
  random: Account for entropy loss due to overwrites

Theodore Ts'o (9):
  random: run random_int_secret_init() run after all late_initcalls
  random: fix the tracepoint for get_random_bytes(_arch)
  random: optimize spinlock use in add_device_randomness()
  random: allow architectures to optionally define random_get_entropy()
  random: mix in architectural randomness earlier in extract_buf()
  random: optimize the entropy_store structure
  random: cap the rate which the /dev/urandom pool gets reseeded
  random: speed up the fast_mix function by a factor of four
  random: adjust the generator polynomials in the mixing function
    slightly

 drivers/char/random.c         | 419 +++++++++++++++++++++++++++---------------
 include/linux/random.h        |   1 +
 include/linux/timex.h         |  17 ++
 include/trace/events/random.h |  33 +++-
 init/main.c                   |   2 +
 5 files changed, 321 insertions(+), 151 deletions(-)

-- 
1.7.12.rc0.22.gcdd159b

[PATCH, RFC 01/12] random: run random_int_secret_init() run after all late_initcalls

[Theodore Ts'o]

The some platforms (e.g., ARM) initializes their clocks as
late_initcalls for some unknown reason.  So make sure
random_int_secret_init() is run all of the late_initcalls are run.

Cc: stable@vger.kernel.org
Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 drivers/char/random.c  | 3 +--
 include/linux/random.h | 1 +
 init/main.c            | 2 ++
 3 files changed, 4 insertions(+), 2 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 0d91fe5..92e6c67 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1462,12 +1462,11 @@ struct ctl_table random_table[] = {
 
 static u32 random_int_secret[MD5_MESSAGE_BYTES / 4] ____cacheline_aligned;
 
-static int __init random_int_secret_init(void)
+int random_int_secret_init(void)
 {
 	get_random_bytes(random_int_secret, sizeof(random_int_secret));
 	return 0;
 }
-late_initcall(random_int_secret_init);
 
 /*
  * Get a random word for internal kernel use only. Similar to urandom but
diff --git a/include/linux/random.h b/include/linux/random.h
index 3b9377d..6312dd9 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -17,6 +17,7 @@ extern void add_interrupt_randomness(int irq, int irq_flags);
 extern void get_random_bytes(void *buf, int nbytes);
 extern void get_random_bytes_arch(void *buf, int nbytes);
 void generate_random_uuid(unsigned char uuid_out[16]);
+extern int random_int_secret_init(void);
 
 #ifndef MODULE
 extern const struct file_operations random_fops, urandom_fops;
diff --git a/init/main.c b/init/main.c
index d03d2ec..586cd33 100644
--- a/init/main.c
+++ b/init/main.c
@@ -75,6 +75,7 @@
 #include <linux/blkdev.h>
 #include <linux/elevator.h>
 #include <linux/sched_clock.h>
+#include <linux/random.h>
 
 #include <asm/io.h>
 #include <asm/bugs.h>
@@ -778,6 +779,7 @@ static void __init do_basic_setup(void)
 	do_ctors();
 	usermodehelper_enable();
 	do_initcalls();
+	random_int_secret_init();
 }
 
 static void __init do_pre_smp_initcalls(void)
-- 
1.7.12.rc0.22.gcdd159b

[PATCH, RFC 02/12] random: Statically compute poolbitshift, poolbytes, poolbits

[Theodore Ts'o]

From: "H. Peter Anvin" <hpa@linux.intel.com>

Use a macro to statically compute poolbitshift (will be used in a
subsequent patch), poolbytes, and poolbits.  On virtually all
architectures the cost of a memory load with an offset is the same as
the one of a memory load.

It is still possible for this to generate worse code since the C
compiler doesn't know the fixed relationship between these fields, but
that is somewhat unlikely.

Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>
Cc: <stable@vger.kernel.org>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
---
 drivers/char/random.c | 39 +++++++++++++++++++--------------------
 1 file changed, 19 insertions(+), 20 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 92e6c67..e973658 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -309,46 +309,45 @@ 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 {
-	int poolwords;
+	int poolbitshift, poolwords, poolbytes, poolbits;
+#define S(x) ilog2(x)+5, (x), (x)*4, (x)*32
 	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 },
+	{ S(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 },
+	{ S(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 },
+	{ S(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 },
+	{ S(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 },
+	{ S(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 },
+	{ S(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 },
+	{ S(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 },
+	{ S(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 },
+	{ S(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 },
+	{ S(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 },
+	{ S(64),	52,	39,	26,	14,	1 },
 #endif
 };
 
-#define POOLBITS	poolwords*32
-#define POOLBYTES	poolwords*4
-
 /*
  * For the purposes of better mixing, we use the CRC-32 polynomial as
  * well to make a twisted Generalized Feedback Shift Reigster
@@ -599,8 +598,8 @@ retry:
 	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 > r->poolinfo->poolbits)
+		entropy_count = r->poolinfo->poolbits;
 	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
 		goto retry;
 
@@ -815,7 +814,7 @@ 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) {
+	    r->entropy_count < r->poolinfo->poolbits) {
 		/* If we're limited, always leave two wakeup worth's BITS */
 		int rsvd = r->limit ? 0 : random_read_wakeup_thresh/4;
 		int bytes = nbytes;
@@ -857,7 +856,7 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min,
 	/* Hold lock while accounting */
 	spin_lock_irqsave(&r->lock, flags);
 
-	BUG_ON(r->entropy_count > r->poolinfo->POOLBITS);
+	BUG_ON(r->entropy_count > r->poolinfo->poolbits);
 	DEBUG_ENT("trying to extract %zu bits from %s\n",
 		  nbytes * 8, r->name);
 
@@ -1112,7 +1111,7 @@ static void init_std_data(struct entropy_store *r)
 	r->entropy_total = 0;
 	r->last_data_init = false;
 	mix_pool_bytes(r, &now, sizeof(now), NULL);
-	for (i = r->poolinfo->POOLBYTES; i > 0; i -= sizeof(rv)) {
+	for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) {
 		if (!arch_get_random_long(&rv))
 			break;
 		mix_pool_bytes(r, &rv, sizeof(rv), NULL);
-- 
1.7.12.rc0.22.gcdd159b

[PATCH, RFC 03/12] random: Allow fractional bits to be tracked

[Theodore Ts'o]

From: "H. Peter Anvin" <hpa@zytor.com>

Allow fractional bits of entropy to be tracked by scaling the entropy
counter (fixed point).  This will be used in a subsequent patch that
accounts for entropy lost due to overwrites.

Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>
Cc: <stable@vger.kernel.org>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
---
 drivers/char/random.c | 118 ++++++++++++++++++++++++++++++++++----------------
 1 file changed, 81 insertions(+), 37 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index e973658..1547338 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -280,6 +280,14 @@
 #define LONGS(x) (((x) + sizeof(unsigned long) - 1)/sizeof(unsigned long))
 
 /*
+ * To allow fractional bits to be tracked, the following fields contain
+ * this many fractional bits:
+ *
+ * entropy_count, trickle_thresh
+ */
+#define ENTROPY_SHIFT 3
+
+/*
  * The minimum number of bits of entropy before we wake up a read on
  * /dev/random.  Should be enough to do a significant reseed.
  */
@@ -296,8 +304,7 @@ static int random_write_wakeup_thresh = 128;
  * When the input pool goes over trickle_thresh, start dropping most
  * samples to avoid wasting CPU time and reduce lock contention.
  */
-
-static int trickle_thresh __read_mostly = INPUT_POOL_WORDS * 28;
+static const int trickle_thresh = (INPUT_POOL_WORDS * 28) << ENTROPY_SHIFT;
 
 static DEFINE_PER_CPU(int, trickle_count);
 
@@ -311,8 +318,8 @@ static DEFINE_PER_CPU(int, trickle_count);
  */
 
 static struct poolinfo {
-	int poolbitshift, poolwords, poolbytes, poolbits;
-#define S(x) ilog2(x)+5, (x), (x)*4, (x)*32
+	int poolbitshift, poolwords, poolbytes, poolbits, poolfracbits;
+#define S(x) ilog2(x)+5, (x), (x)*4, (x)*32, (x) << (ENTROPY_SHIFT+5)
 	int tap1, tap2, tap3, tap4, tap5;
 } poolinfo_table[] = {
 	/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
@@ -581,7 +588,9 @@ 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.
+ * Use credit_entropy_bits_safe() if the value comes from userspace
+ * or otherwise should be checked for extreme values.
  */
 static void credit_entropy_bits(struct entropy_store *r, int nbits)
 {
@@ -593,13 +602,13 @@ 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;
+	entropy_count += nbits << ENTROPY_SHIFT;
 
 	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 > r->poolinfo->poolfracbits)
+		entropy_count = r->poolinfo->poolfracbits;
 	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
 		goto retry;
 
@@ -613,12 +622,24 @@ retry:
 				  r->entropy_total, _RET_IP_);
 
 	/* should we wake readers? */
-	if (r == &input_pool && entropy_count >= random_read_wakeup_thresh) {
+	if (r == &input_pool &&
+	    (entropy_count >> ENTROPY_SHIFT) >= random_read_wakeup_thresh) {
 		wake_up_interruptible(&random_read_wait);
 		kill_fasync(&fasync, SIGIO, POLL_IN);
 	}
 }
 
+static void credit_entropy_bits_safe(struct entropy_store *r, int nbits)
+{
+	const int nbits_max = (int)(~0U >> (ENTROPY_SHIFT + 1));
+
+	/* Cap the value to avoid overflows */
+	nbits = min(nbits,  nbits_max);
+	nbits = max(nbits, -nbits_max);
+
+	credit_entropy_bits(r, nbits);
+}
+
 /*********************************************************************
  *
  * Entropy input management
@@ -813,8 +834,9 @@ 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 (r->pull &&
+	    r->entropy_count < (nbytes << (ENTROPY_SHIFT + 3)) &&
+	    r->entropy_count < r->poolinfo->poolfracbits) {
 		/* If we're limited, always leave two wakeup worth's BITS */
 		int rsvd = r->limit ? 0 : random_read_wakeup_thresh/4;
 		int bytes = nbytes;
@@ -826,7 +848,8 @@ static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
 
 		DEBUG_ENT("going to reseed %s with %d bits "
 			  "(%zu of %d requested)\n",
-			  r->name, bytes * 8, nbytes * 8, r->entropy_count);
+			  r->name, bytes * 8, nbytes * 8,
+			  r->entropy_count >> ENTROPY_SHIFT);
 
 		bytes = extract_entropy(r->pull, tmp, bytes,
 					random_read_wakeup_thresh / 8, rsvd);
@@ -852,41 +875,44 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min,
 {
 	unsigned long flags;
 	int wakeup_write = 0;
+	int have_bytes;
+	int entropy_count, orig;
+	size_t ibytes;
 
 	/* Hold lock while accounting */
 	spin_lock_irqsave(&r->lock, flags);
 
-	BUG_ON(r->entropy_count > r->poolinfo->poolbits);
+	BUG_ON(r->entropy_count > r->poolinfo->poolfracbits);
 	DEBUG_ENT("trying to extract %zu bits from %s\n",
 		  nbytes * 8, r->name);
 
 	/* Can we pull enough? */
-	if (r->entropy_count / 8 < min + reserved) {
-		nbytes = 0;
-	} else {
-		int entropy_count, orig;
 retry:
-		entropy_count = orig = ACCESS_ONCE(r->entropy_count);
+	entropy_count = orig = ACCESS_ONCE(r->entropy_count);
+	have_bytes = entropy_count >> (ENTROPY_SHIFT + 3);
+	ibytes = nbytes;
+	if (have_bytes < min + reserved) {
+		ibytes = 0;
+	} else {
 		/* If limited, never pull more than available */
-		if (r->limit && nbytes + reserved >= entropy_count / 8)
-			nbytes = entropy_count/8 - reserved;
-
-		if (entropy_count / 8 >= nbytes + reserved) {
-			entropy_count -= nbytes*8;
-			if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
-				goto retry;
-		} else {
-			entropy_count = reserved;
-			if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
-				goto retry;
-		}
+		if (r->limit && ibytes + reserved >= have_bytes)
+			ibytes = have_bytes - reserved;
+
+		if (have_bytes >= ibytes + reserved)
+			entropy_count -= ibytes << (ENTROPY_SHIFT + 3);
+		else
+			entropy_count = reserved << (ENTROPY_SHIFT + 3);
 
-		if (entropy_count < random_write_wakeup_thresh)
+		if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
+			goto retry;
+
+		if ((r->entropy_count >> ENTROPY_SHIFT)
+		    < random_write_wakeup_thresh)
 			wakeup_write = 1;
 	}
 
 	DEBUG_ENT("debiting %zu entropy credits from %s%s\n",
-		  nbytes * 8, r->name, r->limit ? "" : " (unlimited)");
+		  ibytes * 8, r->name, r->limit ? "" : " (unlimited)");
 
 	spin_unlock_irqrestore(&r->lock, flags);
 
@@ -895,7 +921,7 @@ retry:
 		kill_fasync(&fasync, SIGIO, POLL_OUT);
 	}
 
-	return nbytes;
+	return ibytes;
 }
 
 static void extract_buf(struct entropy_store *r, __u8 *out)
@@ -1277,7 +1303,8 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
 	switch (cmd) {
 	case RNDGETENTCNT:
 		/* inherently racy, no point locking */
-		if (put_user(input_pool.entropy_count, p))
+		ent_count = input_pool.entropy_count >> ENTROPY_SHIFT;
+		if (put_user(ent_count, p))
 			return -EFAULT;
 		return 0;
 	case RNDADDTOENTCNT:
@@ -1285,7 +1312,7 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
 			return -EPERM;
 		if (get_user(ent_count, p))
 			return -EFAULT;
-		credit_entropy_bits(&input_pool, ent_count);
+		credit_entropy_bits_safe(&input_pool, ent_count);
 		return 0;
 	case RNDADDENTROPY:
 		if (!capable(CAP_SYS_ADMIN))
@@ -1300,7 +1327,7 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
 				    size);
 		if (retval < 0)
 			return retval;
-		credit_entropy_bits(&input_pool, ent_count);
+		credit_entropy_bits_safe(&input_pool, ent_count);
 		return 0;
 	case RNDZAPENTCNT:
 	case RNDCLEARPOOL:
@@ -1407,6 +1434,23 @@ static int proc_do_uuid(struct ctl_table *table, int write,
 	return proc_dostring(&fake_table, write, buffer, lenp, ppos);
 }
 
+/*
+ * Return entropy available scaled to integral bits
+ */
+static int proc_do_entropy(ctl_table *table, int write,
+			   void __user *buffer, size_t *lenp, loff_t *ppos)
+{
+	ctl_table fake_table;
+	int entropy_count;
+
+	entropy_count = *(int *)table->data >> ENTROPY_SHIFT;
+
+	fake_table.data = &entropy_count;
+	fake_table.maxlen = sizeof(entropy_count);
+
+	return proc_dointvec(&fake_table, write, buffer, lenp, ppos);
+}
+
 static int sysctl_poolsize = INPUT_POOL_WORDS * 32;
 extern struct ctl_table random_table[];
 struct ctl_table random_table[] = {
@@ -1421,7 +1465,7 @@ struct ctl_table random_table[] = {
 		.procname	= "entropy_avail",
 		.maxlen		= sizeof(int),
 		.mode		= 0444,
-		.proc_handler	= proc_dointvec,
+		.proc_handler	= proc_do_entropy,
 		.data		= &input_pool.entropy_count,
 	},
 	{
-- 
1.7.12.rc0.22.gcdd159b

Re: [PATCH, RFC 03/12] random: Allow fractional bits to be tracked

[Theodore Ts'o]

I've added the following changes to this patch since upon testing,
there were some uses of r->entropy_count that were not properly
converted from using fractional bits to bits.

					- Ted

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 1547338..8654b7e 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -286,6 +286,7 @@
  * entropy_count, trickle_thresh
  */
 #define ENTROPY_SHIFT 3
+#define ENTROPY_BITS(r) ((r)->entropy_count >> ENTROPY_SHIFT)
 
 /*
  * The minimum number of bits of entropy before we wake up a read on
@@ -618,7 +619,8 @@ retry:
 			r->initialized = 1;
 	}
 
-	trace_credit_entropy_bits(r->name, nbits, entropy_count,
+	trace_credit_entropy_bits(r->name, nbits,
+				  entropy_count >> ENTROPY_SHIFT,
 				  r->entropy_total, _RET_IP_);
 
 	/* should we wake readers? */
@@ -695,7 +697,7 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
 
 	preempt_disable();
 	/* if over the trickle threshold, use only 1 in 4096 samples */
-	if (input_pool.entropy_count > trickle_thresh &&
+	if (ENTROPY_BITS(&input_pool) > trickle_thresh &&
 	    ((__this_cpu_inc_return(trickle_count) - 1) & 0xfff))
 		goto out;
 
@@ -999,7 +1001,7 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 			r->last_data_init = true;
 			spin_unlock_irqrestore(&r->lock, flags);
 			trace_extract_entropy(r->name, EXTRACT_SIZE,
-					      r->entropy_count, _RET_IP_);
+					      ENTROPY_BITS(r), _RET_IP_);
 			xfer_secondary_pool(r, EXTRACT_SIZE);
 			extract_buf(r, tmp);
 			spin_lock_irqsave(&r->lock, flags);
@@ -1008,7 +1010,7 @@ 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_);
+	trace_extract_entropy(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_);
 	xfer_secondary_pool(r, nbytes);
 	nbytes = account(r, nbytes, min, reserved);
 
@@ -1041,7 +1043,7 @@ static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf,
 	ssize_t ret = 0, i;
 	__u8 tmp[EXTRACT_SIZE];
 
-	trace_extract_entropy_user(r->name, nbytes, r->entropy_count, _RET_IP_);
+	trace_extract_entropy_user(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_);
 	xfer_secondary_pool(r, nbytes);
 	nbytes = account(r, nbytes, 0, 0);
 
@@ -1213,8 +1215,8 @@ random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
 			DEBUG_ENT("sleeping?\n");
 
 			wait_event_interruptible(random_read_wait,
-				input_pool.entropy_count >=
-						 random_read_wakeup_thresh);
+				ENTROPY_BITS(&input_pool) >=
+				random_read_wakeup_thresh);
 
 			DEBUG_ENT("awake\n");
 
@@ -1250,9 +1252,9 @@ random_poll(struct file *file, poll_table * wait)
 	poll_wait(file, &random_read_wait, wait);
 	poll_wait(file, &random_write_wait, wait);
 	mask = 0;
-	if (input_pool.entropy_count >= random_read_wakeup_thresh)
+	if (ENTROPY_BITS(&input_pool) >= random_read_wakeup_thresh)
 		mask |= POLLIN | POLLRDNORM;
-	if (input_pool.entropy_count < random_write_wakeup_thresh)
+	if (ENTROPY_BITS(&input_pool) < random_write_wakeup_thresh)
 		mask |= POLLOUT | POLLWRNORM;
 	return mask;
 }
@@ -1303,7 +1305,7 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
 	switch (cmd) {
 	case RNDGETENTCNT:
 		/* inherently racy, no point locking */
-		ent_count = input_pool.entropy_count >> ENTROPY_SHIFT;
+		ent_count = ENTROPY_BITS(&input_pool);
 		if (put_user(ent_count, p))
 			return -EFAULT;
 		return 0;

Re: [PATCH, RFC 03/12] random: Allow fractional bits to be tracked

[H. Peter Anvin]

On 09/22/2013 09:01 PM, Theodore Ts'o wrote:
> I've added the following changes to this patch since upon testing,
> there were some uses of r->entropy_count that were not properly
> converted from using fractional bits to bits.
> 

Thanks for catching that.

	-hpa

[PATCH, RFC 04/12] random: Account for entropy loss due to overwrites

[Theodore Ts'o]

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/2 then

	  (1 - exp(-add_entropy/pool_size)) >= (add_entropy/pool_size)*0.7869...

	  ... so we can approximate the exponential with
	  3/4*add_entropy/pool_size and still be on the
	  safe side by adding at most pool_size/2 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 3/4 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.

This does introduce fractional bit values.  I have left it to have 3
bits of fraction, so that with a pool of 2^12 bits the multiply in
credit_entropy_bits() can still fit into an int, as 2*(3+12) < 31.  It
is definitely possible to allow for more fractional accounting, but
that multiply then would have to be turned into a 32*32 -> 64 multiply.

Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>
Cc: DJ Johnston <dj.johnston@intel.com>
Cc: <stable@vger.kernel.org>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
---
 drivers/char/random.c | 60 ++++++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 52 insertions(+), 8 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 1547338..75f04d5 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))
 
@@ -284,6 +286,9 @@
  * this many fractional bits:
  *
  * entropy_count, trickle_thresh
+ *
+ * 2*(ENTROPY_SHIFT + log2(poolbits)) must <= 31, or the multiply in
+ * credit_entropy_bits() needs to be 64 bits wide.
  */
 #define ENTROPY_SHIFT 3
 
@@ -426,7 +431,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;
@@ -595,6 +600,8 @@ static void fast_mix(struct fast_pool *f, const void *in, int nbytes)
 static void credit_entropy_bits(struct entropy_store *r, int nbits)
 {
 	int entropy_count, orig;
+	const int pool_size = r->poolinfo->poolfracbits;
+	int nfrac = nbits << ENTROPY_SHIFT;
 
 	if (!nbits)
 		return;
@@ -602,13 +609,50 @@ 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 << ENTROPY_SHIFT;
+	if (nfrac < 0) {
+		/* Debit */
+		entropy_count += nfrac;
+	} 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/2 then
+		 * (1 - exp(-add_entropy/pool_size)) >=
+		 *    (add_entropy/pool_size)*0.7869...
+		 * so we can approximate the exponential with
+		 * 3/4*add_entropy/pool_size and still be on the
+		 * safe side by adding at most pool_size/2 at a time.
+		 *
+		 * The use of pool_size-2 in the while statement is to
+		 * prevent rounding artifacts from making the loop
+		 * arbitrarily long; this limits the loop to log2(pool_size)*2
+		 * turns no matter how large nbits is.
+		 */
+		int pnfrac = nfrac;
+		const int s = r->poolinfo->poolbitshift + ENTROPY_SHIFT + 2;
+		/* The +2 corresponds to the /4 in the denominator */
+
+		do {
+			unsigned int anfrac = min(pnfrac, pool_size/2);
+			unsigned int add =
+				((pool_size - entropy_count)*anfrac*3) >> s;
+
+			entropy_count += add;
+			pnfrac -= anfrac;
+		} while (unlikely(entropy_count < pool_size-2 && pnfrac));
+	}
 
 	if (entropy_count < 0) {
 		DEBUG_ENT("negative entropy/overflow\n");
 		entropy_count = 0;
-	} else if (entropy_count > r->poolinfo->poolfracbits)
-		entropy_count = r->poolinfo->poolfracbits;
+	} else if (entropy_count > pool_size)
+		entropy_count = pool_size;
 	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
 		goto retry;
 
-- 
1.7.12.rc0.22.gcdd159b

[PATCH, RFC 05/12] random: fix the tracepoint for get_random_bytes(_arch)

[Theodore Ts'o]

Fix a problem where get_random_bytes_arch() was calling the tracepoint
get_random_bytes().  So add a new tracepoint for
get_random_bytes_arch(), and make get_random_bytes() and
get_random_bytes_arch() call their correct tracepoint.

Also, add a new tracepoint for add_device_randomness()

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 drivers/char/random.c         |  5 ++++-
 include/trace/events/random.h | 33 ++++++++++++++++++++++++++++++++-
 2 files changed, 36 insertions(+), 2 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 75f04d5..391b05a 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -708,7 +708,9 @@ struct timer_rand_state {
 void add_device_randomness(const void *buf, unsigned int size)
 {
 	unsigned long time = get_cycles() ^ jiffies;
+	unsigned long flags;
 
+	trace_add_device_randomness(size, _RET_IP_);
 	mix_pool_bytes(&input_pool, buf, size, NULL);
 	mix_pool_bytes(&input_pool, &time, sizeof(time), NULL);
 	mix_pool_bytes(&nonblocking_pool, buf, size, NULL);
@@ -1125,6 +1127,7 @@ static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf,
  */
 void get_random_bytes(void *buf, int nbytes)
 {
+	trace_get_random_bytes(nbytes, _RET_IP_);
 	extract_entropy(&nonblocking_pool, buf, nbytes, 0, 0);
 }
 EXPORT_SYMBOL(get_random_bytes);
@@ -1143,7 +1146,7 @@ void get_random_bytes_arch(void *buf, int nbytes)
 {
 	char *p = buf;
 
-	trace_get_random_bytes(nbytes, _RET_IP_);
+	trace_get_random_bytes_arch(nbytes, _RET_IP_);
 	while (nbytes) {
 		unsigned long v;
 		int chunk = min(nbytes, (int)sizeof(unsigned long));
diff --git a/include/trace/events/random.h b/include/trace/events/random.h
index 422df19..2ffcaec 100644
--- a/include/trace/events/random.h
+++ b/include/trace/events/random.h
@@ -7,6 +7,25 @@
 #include <linux/writeback.h>
 #include <linux/tracepoint.h>
 
+TRACE_EVENT(add_device_randomness,
+	TP_PROTO(int bytes, unsigned long IP),
+
+	TP_ARGS(bytes, IP),
+
+	TP_STRUCT__entry(
+		__field(	  int,	bytes			)
+		__field(unsigned long,	IP			)
+	),
+
+	TP_fast_assign(
+		__entry->bytes		= bytes;
+		__entry->IP		= IP;
+	),
+
+	TP_printk("bytes %d caller %pF",
+		__entry->bytes, (void *)__entry->IP)
+);
+
 DECLARE_EVENT_CLASS(random__mix_pool_bytes,
 	TP_PROTO(const char *pool_name, int bytes, unsigned long IP),
 
@@ -68,7 +87,7 @@ TRACE_EVENT(credit_entropy_bits,
 		  (void *)__entry->IP)
 );
 
-TRACE_EVENT(get_random_bytes,
+DECLARE_EVENT_CLASS(random__get_random_bytes,
 	TP_PROTO(int nbytes, unsigned long IP),
 
 	TP_ARGS(nbytes, IP),
@@ -86,6 +105,18 @@ TRACE_EVENT(get_random_bytes,
 	TP_printk("nbytes %d caller %pF", __entry->nbytes, (void *)__entry->IP)
 );
 
+DEFINE_EVENT(random__get_random_bytes, get_random_bytes,
+	TP_PROTO(int nbytes, unsigned long IP),
+
+	TP_ARGS(nbytes, IP)
+);
+
+DEFINE_EVENT(random__get_random_bytes, get_random_bytes_arch,
+	TP_PROTO(int nbytes, unsigned long IP),
+
+	TP_ARGS(nbytes, IP)
+);
+
 DECLARE_EVENT_CLASS(random__extract_entropy,
 	TP_PROTO(const char *pool_name, int nbytes, int entropy_count,
 		 unsigned long IP),
-- 
1.7.12.rc0.22.gcdd159b

[PATCH, RFC 06/12] random: optimize spinlock use in add_device_randomness()

[Theodore Ts'o]

No point taking the spinlock twice for each call to mix_pool_bytes();
better to take it once for each pool where we add entropy.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 drivers/char/random.c | 13 +++++++++----
 1 file changed, 9 insertions(+), 4 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 391b05a..9564144 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -711,10 +711,15 @@ void add_device_randomness(const void *buf, unsigned int size)
 	unsigned long flags;
 
 	trace_add_device_randomness(size, _RET_IP_);
-	mix_pool_bytes(&input_pool, buf, size, NULL);
-	mix_pool_bytes(&input_pool, &time, sizeof(time), NULL);
-	mix_pool_bytes(&nonblocking_pool, buf, size, NULL);
-	mix_pool_bytes(&nonblocking_pool, &time, sizeof(time), NULL);
+	spin_lock_irqsave(&input_pool.lock, flags);
+	_mix_pool_bytes(&input_pool, buf, size, NULL);
+	_mix_pool_bytes(&input_pool, &time, sizeof(time), NULL);
+	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);
+	spin_unlock_irqrestore(&nonblocking_pool.lock, flags);
 }
 EXPORT_SYMBOL(add_device_randomness);
 
-- 
1.7.12.rc0.22.gcdd159b

[PATCH, RFC 07/12] random: allow architectures to optionally define random_get_entropy()

[Theodore Ts'o]

Allow architectures which have a disabled get_cycles() function to
provide a random_get_entropy() function which provides a fine-grained,
rapidly changing counter that can be used by the /dev/random driver.

For example, an architecture might have a rapidly changing register
used to control random TLB cache eviction, or DRAM refresh that
doesn't meet the requirements of get_cycles(), but which is good
enough for the needs of the random driver.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 drivers/char/random.c |  8 ++++----
 include/linux/timex.h | 17 +++++++++++++++++
 2 files changed, 21 insertions(+), 4 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 9564144..ba23d5c 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -707,7 +707,7 @@ struct timer_rand_state {
  */
 void add_device_randomness(const void *buf, unsigned int size)
 {
-	unsigned long time = get_cycles() ^ jiffies;
+	unsigned long time = random_get_entropy() ^ jiffies;
 	unsigned long flags;
 
 	trace_add_device_randomness(size, _RET_IP_);
@@ -751,7 +751,7 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
 		goto out;
 
 	sample.jiffies = jiffies;
-	sample.cycles = get_cycles();
+	sample.cycles = random_get_entropy();
 	sample.num = num;
 	mix_pool_bytes(&input_pool, &sample, sizeof(sample), NULL);
 
@@ -818,7 +818,7 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	struct fast_pool	*fast_pool = &__get_cpu_var(irq_randomness);
 	struct pt_regs		*regs = get_irq_regs();
 	unsigned long		now = jiffies;
-	__u32			input[4], cycles = get_cycles();
+	__u32			input[4], cycles = random_get_entropy();
 
 	input[0] = cycles ^ jiffies;
 	input[1] = irq;
@@ -1580,7 +1580,7 @@ unsigned int get_random_int(void)
 
 	hash = get_cpu_var(get_random_int_hash);
 
-	hash[0] += current->pid + jiffies + get_cycles();
+	hash[0] += current->pid + jiffies + random_get_entropy();
 	md5_transform(hash, random_int_secret);
 	ret = hash[0];
 	put_cpu_var(get_random_int_hash);
diff --git a/include/linux/timex.h b/include/linux/timex.h
index b3726e6..f9780cc 100644
--- a/include/linux/timex.h
+++ b/include/linux/timex.h
@@ -64,6 +64,23 @@
 
 #include <asm/timex.h>
 
+#ifndef random_get_entropy
+/*
+ * The random_get_entropy() function is used by the /dev/random driver
+ * in order to extract entropy via the relative unpredictability of
+ * when an interrupt takes places versus a high speed, fine-grained
+ * timing source or cycle counter.  Since it will be occurred on every
+ * single interrupt, it must have a very low cost/overhead.
+ *
+ * By default we use get_cycles() for this purpose, but individual
+ * architectures may override this in their asm/timex.h header file.
+ */
+static inline cycles_t random_get_entropy(void)
+{
+	return get_cycles();
+}
+#endif
+
 /*
  * SHIFT_PLL is used as a dampening factor to define how much we
  * adjust the frequency correction for a given offset in PLL mode.
-- 
1.7.12.rc0.22.gcdd159b

Re: [PATCH, RFC 07/12] random: allow architectures to optionally define random_get_entropy()

[Stephan Mueller]

Am Sonntag, 22. September 2013, 16:38:53 schrieb Theodore Ts'o:

Hi Theodore,

>Allow architectures which have a disabled get_cycles() function to
>provide a random_get_entropy() function which provides a fine-grained,
>rapidly changing counter that can be used by the /dev/random driver.

Are there any plans to get such function implemented on large list of 
architectures without a get_cycles function?

Thanks
>
>For example, an architecture might have a rapidly changing register
>used to control random TLB cache eviction, or DRAM refresh that
>doesn't meet the requirements of get_cycles(), but which is good
>enough for the needs of the random driver.
>
>Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
>---
> drivers/char/random.c |  8 ++++----
> include/linux/timex.h | 17 +++++++++++++++++
> 2 files changed, 21 insertions(+), 4 deletions(-)
>
>diff --git a/drivers/char/random.c b/drivers/char/random.c
>index 9564144..ba23d5c 100644
>--- a/drivers/char/random.c
>+++ b/drivers/char/random.c
>@@ -707,7 +707,7 @@ struct timer_rand_state {
>  */
> void add_device_randomness(const void *buf, unsigned int size)
> {
>-	unsigned long time = get_cycles() ^ jiffies;
>+	unsigned long time = random_get_entropy() ^ jiffies;
> 	unsigned long flags;
>
> 	trace_add_device_randomness(size, _RET_IP_);
>@@ -751,7 +751,7 @@ static void add_timer_randomness(struct
>timer_rand_state *state, unsigned num) goto out;
>
> 	sample.jiffies = jiffies;
>-	sample.cycles = get_cycles();
>+	sample.cycles = random_get_entropy();
> 	sample.num = num;
> 	mix_pool_bytes(&input_pool, &sample, sizeof(sample), NULL);
>
>@@ -818,7 +818,7 @@ void add_interrupt_randomness(int irq, int
>irq_flags) struct fast_pool	*fast_pool =
>&__get_cpu_var(irq_randomness); struct pt_regs		*regs =
>get_irq_regs();
> 	unsigned long		now = jiffies;
>-	__u32			input[4], cycles = get_cycles();
>+	__u32			input[4], cycles = random_get_entropy();
>
> 	input[0] = cycles ^ jiffies;
> 	input[1] = irq;
>@@ -1580,7 +1580,7 @@ unsigned int get_random_int(void)
>
> 	hash = get_cpu_var(get_random_int_hash);
>
>-	hash[0] += current->pid + jiffies + get_cycles();
>+	hash[0] += current->pid + jiffies + random_get_entropy();
> 	md5_transform(hash, random_int_secret);
> 	ret = hash[0];
> 	put_cpu_var(get_random_int_hash);
>diff --git a/include/linux/timex.h b/include/linux/timex.h
>index b3726e6..f9780cc 100644
>--- a/include/linux/timex.h
>+++ b/include/linux/timex.h
>@@ -64,6 +64,23 @@
>
> #include <asm/timex.h>
>
>+#ifndef random_get_entropy
>+/*
>+ * The random_get_entropy() function is used by the /dev/random driver
>+ * in order to extract entropy via the relative unpredictability of +
>* when an interrupt takes places versus a high speed, fine-grained + *
>timing source or cycle counter.  Since it will be occurred on every +
>* single interrupt, it must have a very low cost/overhead.
>+ *
>+ * By default we use get_cycles() for this purpose, but individual
>+ * architectures may override this in their asm/timex.h header file.
>+ */
>+static inline cycles_t random_get_entropy(void)
>+{
>+	return get_cycles();
>+}
>+#endif
>+
> /*
>  * SHIFT_PLL is used as a dampening factor to define how much we
>  * adjust the frequency correction for a given offset in PLL mode.


Ciao
Stephan

Re: [PATCH, RFC 07/12] random: allow architectures to optionally define random_get_entropy()

[Theodore Ts'o]

On Mon, Sep 23, 2013 at 12:38:26PM +0200, Stephan Mueller wrote:
> 
> Are there any plans to get such function implemented on large list of 
> architectures without a get_cycles function?

For some architectures, yes.  As John Stultz pointed out, on many of
the older embedded platforms (which are many of the ones with out a
get_cycles function), the only clocksource they have is the jiffies
time source anyway.  So I'd much rather take each architecture one at
a time, and fix them right.

						- Ted

[PATCH, RFC 08/12] random: mix in architectural randomness earlier in extract_buf()

[Theodore Ts'o]

Previously if CPU chip had a built-in random number generator (i.e.,
RDRAND on newer x86 chips), we mixed it in at the very end of
extract_buf() using an XOR operation.

We now mix it in right after the calculate a hash across the entire
pool.  This has the advantage that any contribution of entropy from
the CPU's HWRNG will get mixed back into the pool.  In addition, it
means that if the HWRNG has any defects (either accidentally or
maliciously introduced), this will be mitigated via the non-linear
transform of the SHA-1 hash function before we hand out generated
output.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 drivers/char/random.c | 22 +++++++++++-----------
 1 file changed, 11 insertions(+), 11 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index ba23d5c..6d5e8e6 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -993,6 +993,17 @@ static void extract_buf(struct entropy_store *r, __u8 *out)
 		sha_transform(hash.w, (__u8 *)(r->pool + i), workspace);
 
 	/*
+	 * If we have a architectural hardware random number
+	 * generator, mix that in, too.
+	 */
+	for (i = 0; i < LONGS(EXTRACT_SIZE); i++) {
+		unsigned long v;
+		if (!arch_get_random_long(&v))
+			break;
+		hash.l[i] ^= v;
+	}
+
+	/*
 	 * We mix the hash back into the pool to prevent backtracking
 	 * attacks (where the attacker knows the state of the pool
 	 * plus the current outputs, and attempts to find previous
@@ -1021,17 +1032,6 @@ static void extract_buf(struct entropy_store *r, __u8 *out)
 	hash.w[1] ^= hash.w[4];
 	hash.w[2] ^= rol32(hash.w[2], 16);
 
-	/*
-	 * If we have a architectural hardware random number
-	 * generator, mix that in, too.
-	 */
-	for (i = 0; i < LONGS(EXTRACT_SIZE); i++) {
-		unsigned long v;
-		if (!arch_get_random_long(&v))
-			break;
-		hash.l[i] ^= v;
-	}
-
 	memcpy(out, &hash, EXTRACT_SIZE);
 	memset(&hash, 0, sizeof(hash));
 }
-- 
1.7.12.rc0.22.gcdd159b

Re: [PATCH, RFC 08/12] random: mix in architectural randomness earlier in extract_buf()

[H. Peter Anvin]

On 09/22/2013 01:38 PM, Theodore Ts'o wrote:
> Previously if CPU chip had a built-in random number generator (i.e.,
> RDRAND on newer x86 chips), we mixed it in at the very end of
> extract_buf() using an XOR operation.
> 
> We now mix it in right after the calculate a hash across the entire
> pool.  This has the advantage that any contribution of entropy from
> the CPU's HWRNG will get mixed back into the pool.  In addition, it
> means that if the HWRNG has any defects (either accidentally or
> maliciously introduced), this will be mitigated via the non-linear
> transform of the SHA-1 hash function before we hand out generated
> output.
> 
> Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>


This doesn't mix in across the entire width of the hash (my original
motivation for putting this at the end was to do it after the hash is
folded in half -- which is still believe is cryptographically dubious,
but please don't take my word for it, as I'm not a professional
cryptographer.)  As such, this change should *probably* have
EXTRACT_SIZE changed to 2*EXTRACT_SIZE (or simply "20") both in the for
loop and in the declaration of the union.

	-hpa

>  drivers/char/random.c | 22 +++++++++++-----------
>  1 file changed, 11 insertions(+), 11 deletions(-)
> 
> diff --git a/drivers/char/random.c b/drivers/char/random.c
> index ba23d5c..6d5e8e6 100644
> --- a/drivers/char/random.c
> +++ b/drivers/char/random.c
> @@ -993,6 +993,17 @@ static void extract_buf(struct entropy_store *r, __u8 *out)
>  		sha_transform(hash.w, (__u8 *)(r->pool + i), workspace);
>  
>  	/*
> +	 * If we have a architectural hardware random number
> +	 * generator, mix that in, too.
> +	 */
> +	for (i = 0; i < LONGS(EXTRACT_SIZE); i++) {
> +		unsigned long v;
> +		if (!arch_get_random_long(&v))
> +			break;
> +		hash.l[i] ^= v;
> +	}
> +
> +	/*
>  	 * We mix the hash back into the pool to prevent backtracking
>  	 * attacks (where the attacker knows the state of the pool
>  	 * plus the current outputs, and attempts to find previous
> @@ -1021,17 +1032,6 @@ static void extract_buf(struct entropy_store *r, __u8 *out)
>  	hash.w[1] ^= hash.w[4];
>  	hash.w[2] ^= rol32(hash.w[2], 16);
>  
> -	/*
> -	 * If we have a architectural hardware random number
> -	 * generator, mix that in, too.
> -	 */
> -	for (i = 0; i < LONGS(EXTRACT_SIZE); i++) {
> -		unsigned long v;
> -		if (!arch_get_random_long(&v))
> -			break;
> -		hash.l[i] ^= v;
> -	}
> -
>  	memcpy(out, &hash, EXTRACT_SIZE);
>  	memset(&hash, 0, sizeof(hash));
>  }
> 

Re: [PATCH, RFC 08/12] random: mix in architectural randomness earlier in extract_buf()

[Theodore Ts'o]

On Sun, Sep 22, 2013 at 09:11:58PM -0700, H. Peter Anvin wrote:
> 
> This doesn't mix in across the entire width of the hash (my original
> motivation for putting this at the end was to do it after the hash is
> folded in half -- which is still believe is cryptographically dubious,
> but please don't take my word for it, as I'm not a professional
> cryptographer.)  As such, this change should *probably* have
> EXTRACT_SIZE changed to 2*EXTRACT_SIZE (or simply "20") both in the for
> loop and in the declaration of the union.

Agreed, I'll make the change to "20" instead of EXTRACT_SIZE.

As far as whether or not folding the hash is cryptographically
dubious, we're not using the hash as part of a digital signature,
which is normally where cryptographers get antsy about truncating a
cryptographic hash value (since it effectively halves the length of
the hash, which thanks to the birthday paradox, makes it much easier
to find collisions).

However, in this case, we are reducing the amount of information which
is available to an attacker to infer the state of the pool.  The
"Linux Random Pool Revisited" paper had the following to say about it
in section 4.3:

    "In addition, the folding operation helps in avoiding recognizable
    patterns: the output of the hash function is not directly
    recognizable from the output data.  For an optimal hash function,
    this step would not be necessary and could be replaced by a simple
    truncation."

If they had thought it was cryptographically dubious, they could have
said so --- but they didn't.

It's true that if we know for sure that SHA-1 is a perfect one-way
hash function (which is believed to be true, although there is no
proof of this, and the recent work by Xiaoyun Wang, Yiquin Lisa Yin,
and Hungbo Yu does not lead to any evidence for or against SHA-1's
status as a one-way function), the folding operation wouldn't be
necessary.  But the folding operation shouldn't hurt (except for
reducing the speed of generating random numbers, and it's currently
not a bottleneck), and in the case where it might not be a perfect
one-way function, it could help.

					- Ted

[PATCH, RFC 09/12] random: optimize the entropy_store structure

[Theodore Ts'o]

Use smaller types to slightly shrink the size of the entropy store
structure.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 drivers/char/random.c | 16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 6d5e8e6..292e717 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -435,16 +435,16 @@ struct entropy_store {
 	__u32 *pool;
 	const char *name;
 	struct entropy_store *pull;
-	int limit;
 
 	/* read-write data: */
 	spinlock_t lock;
-	unsigned add_ptr;
-	unsigned input_rotate;
+	unsigned short add_ptr;
+	unsigned short input_rotate;
 	int entropy_count;
 	int entropy_total;
 	unsigned int initialized:1;
-	bool last_data_init;
+	unsigned int limit:1;
+	unsigned int last_data_init:1;
 	__u8 last_data[EXTRACT_SIZE];
 };
 
@@ -512,7 +512,7 @@ static void _mix_pool_bytes(struct entropy_store *r, const void *in,
 
 	/* mix one byte at a time to simplify size handling and churn faster */
 	while (nbytes--) {
-		w = rol32(*bytes++, input_rotate & 31);
+		w = rol32(*bytes++, input_rotate);
 		i = (i - 1) & wordmask;
 
 		/* XOR in the various taps */
@@ -532,7 +532,7 @@ static void _mix_pool_bytes(struct entropy_store *r, const void *in,
 		 * rotation, so that successive passes spread the
 		 * input bits across the pool evenly.
 		 */
-		input_rotate += i ? 7 : 14;
+		input_rotate = (input_rotate + (i ? 7 : 14)) & 31;
 	}
 
 	ACCESS_ONCE(r->input_rotate) = input_rotate;
@@ -1047,7 +1047,7 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 	if (fips_enabled) {
 		spin_lock_irqsave(&r->lock, flags);
 		if (!r->last_data_init) {
-			r->last_data_init = true;
+			r->last_data_init = 1;
 			spin_unlock_irqrestore(&r->lock, flags);
 			trace_extract_entropy(r->name, EXTRACT_SIZE,
 					      r->entropy_count, _RET_IP_);
@@ -1187,7 +1187,7 @@ static void init_std_data(struct entropy_store *r)
 
 	r->entropy_count = 0;
 	r->entropy_total = 0;
-	r->last_data_init = false;
+	r->last_data_init = 0;
 	mix_pool_bytes(r, &now, sizeof(now), NULL);
 	for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) {
 		if (!arch_get_random_long(&rv))
-- 
1.7.12.rc0.22.gcdd159b

[PATCH, RFC 10/12] random: cap the rate which the /dev/urandom pool gets reseeded

[Theodore Ts'o]

In order to avoid draining the input pool of its entropy at too high
of a rate, enforce a minimum time interval between reseedings of the
urandom pool.  This is set to 60 seconds by default.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 drivers/char/random.c | 25 +++++++++++++++++++++++++
 1 file changed, 25 insertions(+)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 292e717..3439b1c 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -306,6 +306,13 @@ static int random_read_wakeup_thresh = 64;
 static int random_write_wakeup_thresh = 128;
 
 /*
+ * The minimum number of seconds between urandom pool resending.  We
+ * do this to limit the amount of entropy that can be drained from the
+ * input pool even if there are heavy demands on /dev/urandom.
+ */
+static int random_min_urandom_seed = 60;
+
+/*
  * When the input pool goes over trickle_thresh, start dropping most
  * samples to avoid wasting CPU time and reduce lock contention.
  */
@@ -437,6 +444,7 @@ struct entropy_store {
 	struct entropy_store *pull;
 
 	/* read-write data: */
+	unsigned long last_pulled;
 	spinlock_t lock;
 	unsigned short add_ptr;
 	unsigned short input_rotate;
@@ -885,6 +893,15 @@ static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
 {
 	__u32	tmp[OUTPUT_POOL_WORDS];
 
+	if (r->limit == 0 && random_min_urandom_seed) {
+		unsigned long now = jiffies;
+
+		if (time_before(now,
+				r->last_pulled + random_min_urandom_seed * HZ)) {
+			return;
+		}
+		r->last_pulled = now;
+	}
 	if (r->pull &&
 	    r->entropy_count < (nbytes << (ENTROPY_SHIFT + 3)) &&
 	    r->entropy_count < r->poolinfo->poolfracbits) {
@@ -1188,6 +1205,7 @@ static void init_std_data(struct entropy_store *r)
 	r->entropy_count = 0;
 	r->entropy_total = 0;
 	r->last_data_init = 0;
+	r->last_pulled = jiffies;
 	mix_pool_bytes(r, &now, sizeof(now), NULL);
 	for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) {
 		if (!arch_get_random_long(&rv))
@@ -1539,6 +1557,13 @@ struct ctl_table random_table[] = {
 		.extra2		= &max_write_thresh,
 	},
 	{
+		.procname	= "urandom_min_reseed_secs",
+		.data		= &random_min_urandom_seed,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= proc_dointvec,
+	},
+	{
 		.procname	= "boot_id",
 		.data		= &sysctl_bootid,
 		.maxlen		= 16,
-- 
1.7.12.rc0.22.gcdd159b

Re: [PATCH, RFC 10/12] random: cap the rate which the /dev/urandom pool gets reseeded

[H. Peter Anvin]

Is this really an improvement on a system with plenty of entropy? Would it not make more sense to modulate this bad on entropy production rates?

Also, the urandom pool is only reseeded once per read, no matter how large...

Theodore Ts'o <tytso@mit.edu> wrote:
>In order to avoid draining the input pool of its entropy at too high
>of a rate, enforce a minimum time interval between reseedings of the
>urandom pool.  This is set to 60 seconds by default.
>
>Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
>---
> drivers/char/random.c | 25 +++++++++++++++++++++++++
> 1 file changed, 25 insertions(+)
>
>diff --git a/drivers/char/random.c b/drivers/char/random.c
>index 292e717..3439b1c 100644
>--- a/drivers/char/random.c
>+++ b/drivers/char/random.c
>@@ -306,6 +306,13 @@ static int random_read_wakeup_thresh = 64;
> static int random_write_wakeup_thresh = 128;
> 
> /*
>+ * The minimum number of seconds between urandom pool resending.  We
>+ * do this to limit the amount of entropy that can be drained from the
>+ * input pool even if there are heavy demands on /dev/urandom.
>+ */
>+static int random_min_urandom_seed = 60;
>+
>+/*
>  * When the input pool goes over trickle_thresh, start dropping most
>  * samples to avoid wasting CPU time and reduce lock contention.
>  */
>@@ -437,6 +444,7 @@ struct entropy_store {
> 	struct entropy_store *pull;
> 
> 	/* read-write data: */
>+	unsigned long last_pulled;
> 	spinlock_t lock;
> 	unsigned short add_ptr;
> 	unsigned short input_rotate;
>@@ -885,6 +893,15 @@ static void xfer_secondary_pool(struct
>entropy_store *r, size_t nbytes)
> {
> 	__u32	tmp[OUTPUT_POOL_WORDS];
> 
>+	if (r->limit == 0 && random_min_urandom_seed) {
>+		unsigned long now = jiffies;
>+
>+		if (time_before(now,
>+				r->last_pulled + random_min_urandom_seed * HZ)) {
>+			return;
>+		}
>+		r->last_pulled = now;
>+	}
> 	if (r->pull &&
> 	    r->entropy_count < (nbytes << (ENTROPY_SHIFT + 3)) &&
> 	    r->entropy_count < r->poolinfo->poolfracbits) {
>@@ -1188,6 +1205,7 @@ static void init_std_data(struct entropy_store
>*r)
> 	r->entropy_count = 0;
> 	r->entropy_total = 0;
> 	r->last_data_init = 0;
>+	r->last_pulled = jiffies;
> 	mix_pool_bytes(r, &now, sizeof(now), NULL);
> 	for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) {
> 		if (!arch_get_random_long(&rv))
>@@ -1539,6 +1557,13 @@ struct ctl_table random_table[] = {
> 		.extra2		= &max_write_thresh,
> 	},
> 	{
>+		.procname	= "urandom_min_reseed_secs",
>+		.data		= &random_min_urandom_seed,
>+		.maxlen		= sizeof(int),
>+		.mode		= 0644,
>+		.proc_handler	= proc_dointvec,
>+	},
>+	{
> 		.procname	= "boot_id",
> 		.data		= &sysctl_bootid,
> 		.maxlen		= 16,

-- 
Sent from my mobile phone.  Please pardon brevity and lack of formatting.

Re: [PATCH, RFC 10/12] random: cap the rate which the /dev/urandom pool gets reseeded

[Theodore Ts'o]

On Sun, Sep 22, 2013 at 02:21:48PM -0700, H. Peter Anvin wrote:
> Is this really an improvement on a system with plenty of entropy? Would it not make more sense to modulate this bad on entropy production rates?
> 
> Also, the urandom pool is only reseeded once per read, no matter how large...

I added this after observing using the random driver's tracepoints to
measure how the entropy pool behaves on a desktop system.  It turns
outs the Chrome browser requests a truly amazing amount of entropy
using /dev/urandom.  Enough so that while you are reading GMail or
using G+, the available entropy in the input pool is always running at
minimum levels.  (i.e., it never gets above 192 bits before we do a
catatrophic reseed and it drops down to 128 bits.)

I'm not sure what the heck it is doing --- maybe it is using
/dev/urandom to generate random padding values?  I can't believe it is
opening new SSL connetions that quickly.  So this might be a Chrome
bug, and I can talk to some Chrome developers when I get into work
tomorrow.  But in the case of badly behaved applications, this is
useful.

It results in more entropy building up in the input pool before we do
a reseed, so it should result in better "catastrophic reseeding", and
it means that there is more entropy available in the input pool for
use by the /dev/random pool, even if /dev/urandom is being used in
what might be arguably considered an abusive fashion.

You can test this by applying the patch, and observing the value of
/proc/sys/kernel/random/entropy_avail over time while running a Chrome
browser (and there may be other userspace applications which are as
aggressive in the use of /dev/urandom).  The compare it after running
the command "echo 0 > /proc/sys/kernel/random/urandom_min_reseed_secs",
which will restore the original pre-patch behaviour.

						- Ted

Re: [PATCH, RFC 10/12] random: cap the rate which the /dev/urandom pool gets reseeded

[H. Peter Anvin]

I understand the motivation, but I question basing it in a fixed amount of time.

Theodore Ts'o <tytso@mit.edu> wrote:
>On Sun, Sep 22, 2013 at 02:21:48PM -0700, H. Peter Anvin wrote:
>> Is this really an improvement on a system with plenty of entropy?
>Would it not make more sense to modulate this bad on entropy production
>rates?
>> 
>> Also, the urandom pool is only reseeded once per read, no matter how
>large...
>
>I added this after observing using the random driver's tracepoints to
>measure how the entropy pool behaves on a desktop system.  It turns
>outs the Chrome browser requests a truly amazing amount of entropy
>using /dev/urandom.  Enough so that while you are reading GMail or
>using G+, the available entropy in the input pool is always running at
>minimum levels.  (i.e., it never gets above 192 bits before we do a
>catatrophic reseed and it drops down to 128 bits.)
>
>I'm not sure what the heck it is doing --- maybe it is using
>/dev/urandom to generate random padding values?  I can't believe it is
>opening new SSL connetions that quickly.  So this might be a Chrome
>bug, and I can talk to some Chrome developers when I get into work
>tomorrow.  But in the case of badly behaved applications, this is
>useful.
>
>It results in more entropy building up in the input pool before we do
>a reseed, so it should result in better "catastrophic reseeding", and
>it means that there is more entropy available in the input pool for
>use by the /dev/random pool, even if /dev/urandom is being used in
>what might be arguably considered an abusive fashion.
>
>You can test this by applying the patch, and observing the value of
>/proc/sys/kernel/random/entropy_avail over time while running a Chrome
>browser (and there may be other userspace applications which are as
>aggressive in the use of /dev/urandom).  The compare it after running
>the command "echo 0 > /proc/sys/kernel/random/urandom_min_reseed_secs",
>which will restore the original pre-patch behaviour.
>
>						- Ted

-- 
Sent from my mobile phone.  Please pardon brevity and lack of formatting.

Re: [PATCH, RFC 10/12] random: cap the rate which the /dev/urandom pool gets reseeded

[Theodore Ts'o]

On Sun, Sep 22, 2013 at 03:45:11PM -0700, H. Peter Anvin wrote:
> I understand the motivation, but I question basing it in a fixed amount of time.

We already have a threshold based on the amount of the entropy in the
input pool.  I could increase that threshold, but then instead of
having the entropy hover between say, 192 and 128, it would hover
between say, 576 and 512.  What that means in practice is that there
will be a higher baseline, but we will still end up reseeding every 10
seconds or so (that being approximately how much entropy I've seen
flowing into the input pool on my laptop system --- 64 bits every 10
seconds or so).

By basing it on a time-based threshold, it means that the input pool
can build up faster such that over time, such that entropy pool ends
up hovering around 3400 bits.

What is your concern is about having it being time-based --- or more
accurately, being partially time-based, since we also keep the entorpy
count based threshold?  I'll note that the Fortuna Random Number
Generator, devised by Bruce Schneier and Niels Ferguson also uses as
part of its design a time-based reseed limit.

						- Ted

Re: [PATCH, RFC 10/12] random: cap the rate which the /dev/urandom pool gets reseeded

[H. Peter Anvin]

On 09/22/2013 04:23 PM, Theodore Ts'o wrote:
> On Sun, Sep 22, 2013 at 03:45:11PM -0700, H. Peter Anvin wrote:
>> I understand the motivation, but I question basing it in a fixed amount of time.
> 
> We already have a threshold based on the amount of the entropy in the
> input pool.  I could increase that threshold, but then instead of
> having the entropy hover between say, 192 and 128, it would hover
> between say, 576 and 512.  What that means in practice is that there
> will be a higher baseline, but we will still end up reseeding every 10
> seconds or so (that being approximately how much entropy I've seen
> flowing into the input pool on my laptop system --- 64 bits every 10
> seconds or so).
> 
> By basing it on a time-based threshold, it means that the input pool
> can build up faster such that over time, such that entropy pool ends
> up hovering around 3400 bits.
> 

So make it a threshold around 2048-3072 bits.  A.k.a. "if the input pool
is filling up fast enough, take advantage of it."

> What is your concern is about having it being time-based --- or more
> accurately, being partially time-based, since we also keep the entorpy
> count based threshold?  I'll note that the Fortuna Random Number
> Generator, devised by Bruce Schneier and Niels Ferguson also uses as
> part of its design a time-based reseed limit.

Just that it is unnecessary in a scenario when entropy is plentiful.

	-hpa

[PATCH, RFC 11/12] random: speed up the fast_mix function by a factor of four

[Theodore Ts'o]

By mixing the entropy in chunks of 32-bit words instead of byte by
byte, we can speed up the fast_mix function significantly.  Since it
is called on every single interrupt, on systems with a very heavy
interrupt load, this can make a noticeable different.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Reported-by: Jörn Engel <joern@logfs.org>
---
 drivers/char/random.c | 30 +++++++++++++++++-------------
 1 file changed, 17 insertions(+), 13 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 3439b1c..86879d1 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -583,21 +583,26 @@ 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, const void *in, int nbytes)
+static void fast_mix(struct fast_pool *f, __u32 input[4])
 {
-	const char	*bytes = in;
 	__u32		w;
-	unsigned	i = f->count;
 	unsigned	input_rotate = f->rotate;
 
-	while (nbytes--) {
-		w = rol32(*bytes++, input_rotate & 31) ^ f->pool[i & 3] ^
-			f->pool[(i + 1) & 3];
-		f->pool[i & 3] = (w >> 3) ^ twist_table[w & 7];
-		input_rotate += (i++ & 3) ? 7 : 14;
-	}
-	f->count = i;
+	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;
+	f->count++;
 }
 
 /*
@@ -836,10 +841,9 @@ void add_interrupt_randomness(int irq, int irq_flags)
 		input[3] = ip >> 32;
 	}
 
-	fast_mix(fast_pool, input, sizeof(input));
+	fast_mix(fast_pool, input);
 
-	if ((fast_pool->count & 1023) &&
-	    !time_after(now, fast_pool->last + HZ))
+	if ((fast_pool->count & 63) && !time_after(now, fast_pool->last + HZ))
 		return;
 
 	fast_pool->last = now;
-- 
1.7.12.rc0.22.gcdd159b

[PATCH, RFC 12/12] random: adjust the generator polynomials in the mixing function slightly

[Theodore Ts'o]

Our mixing functions were analyzed by Lacharme, Roeck, Strubel, and
Videau in their paper, "The Linux Pseudorandom Number Generator
Revisited" (see: http://eprint.iacr.org/2012/251.pdf).

They suggested a slight change to improve our mixing functions
slightly.  I also adjusted the comments to better explain what is
going on, and to document why the polynomials were changed.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 drivers/char/random.c | 104 ++++++++++++++++++++++++--------------------------
 1 file changed, 50 insertions(+), 54 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 86879d1..5726ff6 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -321,23 +321,62 @@ static const int trickle_thresh = (INPUT_POOL_WORDS * 28) << ENTROPY_SHIFT;
 static DEFINE_PER_CPU(int, trickle_count);
 
 /*
- * A pool of size .poolwords is stirred with a primitive polynomial
- * of degree .poolwords over GF(2).  The taps for various sizes are
- * defined below.  They are chosen to be evenly spaced (minimum RMS
- * distance from evenly spaced; the numbers in the comments are a
- * scaled squared error sum) except for the last tap, which is 1 to
- * get the twisting happening as fast as possible.
+ * Originally, we used a primitive polynomial of degree .poolwords
+ * over GF(2).  The taps for various sizes are defined below.  They
+ * were chosen to be evenly spaced except for the last tap, which is 1
+ * to get the twisting happening as fast as possible.
+ *
+ * For the purposes of better mixing, we use the CRC-32 polynomial as
+ * well to make a (modified) twisted Generalized Feedback Shift
+ * Reigster
+ *
+ * (See M. Matsumoto & Y. Kurita, 1992.  Twisted GFSR generators.  ACM
+ * Transactions on Modeling and Computer Simulation 2(3):179-194.
+ * Also see M. Matsumoto & Y. Kurita, 1994.  Twisted GFSR generators
+ * II.  ACM Transactions on Mdeling and Computer Simulation 4:254-266)
+ *
+ * Thanks to Colin Plumb for suggesting this.
+ *
+ * The mixing operation is much less sensitive than the output hash,
+ * where we use SHA-1.  All that we want of mixing operation is that
+ * it be a good non-cryptographic hash; i.e. it not produce collisions
+ * when fed "random" data of the sort we expect to see.  As long as
+ * the pool state differs for different inputs, we have preserved the
+ * input entropy and done a good job.  The fact that an intelligent
+ * attacker can construct inputs that will produce controlled
+ * alterations to the pool's state is not important because we don't
+ * consider such inputs to contribute any randomness.  The only
+ * property we need with respect to them is that the attacker can't
+ * increase his/her knowledge of the pool's state.  Since all
+ * additions are reversible (knowing the final state and the input,
+ * you can reconstruct the initial state), if an attacker has any
+ * uncertainty about the initial state, he/she can only shuffle that
+ * uncertainty about, but never cause any collisions (which would
+ * decrease the uncertainty).
+ *
+ * Our mixing functions were analyzed by Lacharme, Roeck, Strubel, and
+ * Videau in their paper, "The Linux Pseudorandom Number Generator
+ * Revisited" (see: http://eprint.iacr.org/2012/251.pdf).  In their
+ * paper, they point out that we are not using a true Twisted GFSR,
+ * since Matsumoto & Kurita used a trinomial feedback polynomial (that
+ * is, with only three taps, instead of the six that we are using).
+ * As a result, the resulting polynomial is neither primitive nor
+ * irreducible, and hence does not have a maximal period over
+ * GF(2**32).  They suggest a slight change to the generator
+ * polynomial which improves the resulting TGFSR polynomial to be
+ * irreducible, which we have made here.
  */
-
 static struct poolinfo {
 	int poolbitshift, poolwords, poolbytes, poolbits, poolfracbits;
 #define S(x) ilog2(x)+5, (x), (x)*4, (x)*32, (x) << (ENTROPY_SHIFT+5)
 	int tap1, tap2, tap3, tap4, tap5;
 } poolinfo_table[] = {
-	/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
-	{ S(128),	103,	76,	51,	25,	1 },
-	/* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */
-	{ S(32),	26,	20,	14,	7,	1 },
+	/* was: x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 */
+	/* x^128 + x^104 + x^76 + x^51 +x^25 + x + 1 */
+	{ S(128),	104,	76,	51,	25,	1 },
+	/* was: x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 */
+	/* x^32 + x^26 + x^19 + x^14 + x^7 + x + 1 */
+	{ S(32),	26,	19,	14,	7,	1 },
 #if 0
 	/* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1  -- 115 */
 	{ S(2048),	1638,	1231,	819,	411,	1 },
@@ -368,49 +407,6 @@ static struct poolinfo {
 };
 
 /*
- * For the purposes of better mixing, we use the CRC-32 polynomial as
- * well to make a twisted Generalized Feedback Shift Reigster
- *
- * (See M. Matsumoto & Y. Kurita, 1992.  Twisted GFSR generators.  ACM
- * Transactions on Modeling and Computer Simulation 2(3):179-194.
- * Also see M. Matsumoto & Y. Kurita, 1994.  Twisted GFSR generators
- * II.  ACM Transactions on Mdeling and Computer Simulation 4:254-266)
- *
- * Thanks to Colin Plumb for suggesting this.
- *
- * We have not analyzed the resultant polynomial to prove it primitive;
- * in fact it almost certainly isn't.  Nonetheless, the irreducible factors
- * of a random large-degree polynomial over GF(2) are more than large enough
- * that periodicity is not a concern.
- *
- * The input hash is much less sensitive than the output hash.  All
- * that we want of it is that it be a good non-cryptographic hash;
- * i.e. it not produce collisions when fed "random" data of the sort
- * we expect to see.  As long as the pool state differs for different
- * inputs, we have preserved the input entropy and done a good job.
- * The fact that an intelligent attacker can construct inputs that
- * will produce controlled alterations to the pool's state is not
- * important because we don't consider such inputs to contribute any
- * randomness.  The only property we need with respect to them is that
- * the attacker can't increase his/her knowledge of the pool's state.
- * Since all additions are reversible (knowing the final state and the
- * input, you can reconstruct the initial state), if an attacker has
- * any uncertainty about the initial state, he/she can only shuffle
- * that uncertainty about, but never cause any collisions (which would
- * decrease the uncertainty).
- *
- * The chosen system lets the state of the pool be (essentially) the input
- * modulo the generator polymnomial.  Now, for random primitive polynomials,
- * this is a universal class of hash functions, meaning that the chance
- * of a collision is limited by the attacker's knowledge of the generator
- * polynomail, so if it is chosen at random, an attacker can never force
- * a collision.  Here, we use a fixed polynomial, but we *can* assume that
- * ###--> it is unknown to the processes generating the input entropy. <-###
- * Because of this important property, this is a good, collision-resistant
- * hash; hash collisions will occur no more often than chance.
- */
-
-/*
  * Static global variables
  */
 static DECLARE_WAIT_QUEUE_HEAD(random_read_wait);
-- 
1.7.12.rc0.22.gcdd159b

Re: [PATCH, RFC 12/12] random: adjust the generator polynomials in the mixing function slightly

[Jörg-Volker Peetz]

Small typo:
  s/Reigster/Register/

jvp
--