[PATCH 00/11] random: code cleanups

[PATCH 00/11] random: code cleanups

[Greg Price]

Hi Ted, hi all,

I recently read through the random number generator's code.
This series has fixes for some minor things I spotted.

Four of the patches touch comments only.  Four simplify code without
changing its behavior (total diffstat: 35 insertions, 73 deletions),
and one is a trivial signedness fix.  Two patches change the locking
and lockless concurrency control in account(), including one bugfix.
The bug is related to the one Jiri found and fixed in May.

Cheers,
Greg


Greg Price (11):
  random: fix typos / spelling errors in comments
  random: fix comment on proc_do_uuid
  random: fix description of get_random_bytes
  random: simplify loop in random_read
  random: declare trickle_count unsigned
  random: fix comment on "account"
  random: simplify accounting code slightly
  random: simplify accounting logic
  random: forget lock in lockless accounting
  random: pull 'min' check in accounting to inside lockless update
  random: simplify accounting code

 drivers/char/random.c | 164 ++++++++++++++++++++------------------------------
 1 file changed, 66 insertions(+), 98 deletions(-)

-- 
1.8.3.2

[PATCH 01/11] random: fix typos / spelling errors in comments

[Greg Price]

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

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 7a744d3..ef3e15b 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -348,12 +348,12 @@ 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
+ * well to make a twisted Generalized Feedback Shift Register
  *
  * (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)
+ * II.  ACM Transactions on Modeling and Computer Simulation 4:254-266)
  *
  * Thanks to Colin Plumb for suggesting this.
  *
@@ -382,7 +382,7 @@ static struct poolinfo {
  * 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
+ * polynomial, 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
@@ -943,7 +943,7 @@ static void extract_buf(struct entropy_store *r, __u8 *out)
 	hash.w[2] ^= rol32(hash.w[2], 16);
 
 	/*
-	 * If we have a architectural hardware random number
+	 * If we have an architectural hardware random number
 	 * generator, mix that in, too.
 	 */
 	for (i = 0; i < LONGS(EXTRACT_SIZE); i++) {
-- 
1.8.3.2

[PATCH 02/11] random: fix comment on proc_do_uuid

[Greg Price]

There's only one function here now, as uuid_strategy is long gone.
Also make the bit about "If accesses via ..." clearer.

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

diff --git a/drivers/char/random.c b/drivers/char/random.c
index ef3e15b..a89ba74 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1370,13 +1370,13 @@ static int max_write_thresh = INPUT_POOL_WORDS * 32;
 static char sysctl_bootid[16];
 
 /*
- * These functions is used to return both the bootid UUID, and random
+ * This function is used to return both the bootid UUID, and random
  * UUID.  The difference is in whether table->data is NULL; if it is,
  * then a new UUID is generated and returned to the user.
  *
- * If the user accesses this via the proc interface, it will be returned
- * as an ASCII string in the standard UUID format.  If accesses via the
- * sysctl system call, it is returned as 16 bytes of binary data.
+ * If the user accesses this via the proc interface, the UUID will be
+ * returned as an ASCII string in the standard UUID format; if via the
+ * sysctl system call, as 16 bytes of binary data.
  */
 static int proc_do_uuid(struct ctl_table *table, int write,
 			void __user *buffer, size_t *lenp, loff_t *ppos)
-- 
1.8.3.2

[PATCH 03/11] random: fix description of get_random_bytes

[Greg Price]

After this remark was written, commit d2e7c96af added a use of
arch_get_random_long() inside the get_random_bytes codepath.
The main point stands, but it needs to be reworded.

Cc: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Greg Price <price@mit.edu>
---
 drivers/char/random.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index a89ba74..d1466c9 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1048,8 +1048,9 @@ static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf,
 /*
  * This function is the exported kernel interface.  It returns some
  * number of good random numbers, suitable for key generation, seeding
- * TCP sequence numbers, etc.  It does not use the hw random number
- * generator, if available; use get_random_bytes_arch() for that.
+ * TCP sequence numbers, etc.  It does not rely on the hardware random
+ * number generator.  For random bytes direct from the hardware RNG
+ * (when available), use get_random_bytes_arch().
  */
 void get_random_bytes(void *buf, int nbytes)
 {
-- 
1.8.3.2

[PATCH 04/11] random: simplify loop in random_read

[Greg Price]

The loop condition never changes until just before a break, so we
might as well write it as a constant.  Also since v2.6.33-rc7~40^2~2
("random: drop weird m_time/a_time manipulation") we don't do
anything after the loop finishes, so the 'break's might as well
return directly.  Some other simplifications.

The behavior should be identical except that I've changed a debug
message.

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

diff --git a/drivers/char/random.c b/drivers/char/random.c
index d1466c9..85f5fce 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1155,58 +1155,34 @@ void rand_initialize_disk(struct gendisk *disk)
 static ssize_t
 random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
 {
-	ssize_t n, retval = 0, count = 0;
+	ssize_t n;
 
 	if (nbytes == 0)
 		return 0;
 
-	while (nbytes > 0) {
-		n = nbytes;
-		if (n > SEC_XFER_SIZE)
-			n = SEC_XFER_SIZE;
-
-		DEBUG_ENT("reading %zu bits\n", n*8);
-
-		n = extract_entropy_user(&blocking_pool, buf, n);
-
-		if (n < 0) {
-			retval = n;
-			break;
-		}
-
-		DEBUG_ENT("read got %zd bits (%zd still needed)\n",
+	nbytes = min_t(size_t, nbytes, SEC_XFER_SIZE);
+	while (1) {
+		DEBUG_ENT("reading %zu bits\n", nbytes*8);
+		n = extract_entropy_user(&blocking_pool, buf, nbytes);
+		if (n < 0)
+			return n;
+		DEBUG_ENT("read got %zd bits (%zd short)\n",
 			  n*8, (nbytes-n)*8);
-
-		if (n == 0) {
-			if (file->f_flags & O_NONBLOCK) {
-				retval = -EAGAIN;
-				break;
-			}
-
-			DEBUG_ENT("sleeping?\n");
-
-			wait_event_interruptible(random_read_wait,
-				input_pool.entropy_count >=
-						 random_read_wakeup_thresh);
-
-			DEBUG_ENT("awake\n");
-
-			if (signal_pending(current)) {
-				retval = -ERESTARTSYS;
-				break;
-			}
-
-			continue;
-		}
-
-		count += n;
-		buf += n;
-		nbytes -= n;
-		break;		/* This break makes the device work */
-				/* like a named pipe */
+		if (n > 0)
+			return n;
+		/* Pool is (near) empty.  Maybe wait and retry. */
+
+		if (file->f_flags & O_NONBLOCK)
+			return -EAGAIN;
+
+		DEBUG_ENT("sleeping?\n");
+		wait_event_interruptible(random_read_wait,
+			input_pool.entropy_count >=
+					 random_read_wakeup_thresh);
+		DEBUG_ENT("awake\n");
+		if (signal_pending(current))
+			return -ERESTARTSYS;
 	}
-
-	return (count ? count : retval);
 }
 
 static ssize_t
-- 
1.8.3.2

[PATCH 05/11] random: declare trickle_count unsigned

[Greg Price]

We cheerfully overflow these variables (at least where "int"
is 32 bits wide), so pedantically they should be unsigned.

Cc: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Greg Price <price@mit.edu>
---
 drivers/char/random.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 85f5fce..04a117a 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -296,7 +296,7 @@ static int random_write_wakeup_thresh = 128;
 
 static int trickle_thresh __read_mostly = INPUT_POOL_WORDS * 28;
 
-static DEFINE_PER_CPU(int, trickle_count);
+static DEFINE_PER_CPU(unsigned int, trickle_count);
 
 /*
  * A pool of size .poolwords is stirred with a primitive polynomial
-- 
1.8.3.2

[PATCH 06/11] random: fix comment on "account"

[Greg Price]

This comment didn't quite keep up as extract_entropy() was split into
four functions.  Put each bit by the function it describes.

Cc: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Greg Price <price@mit.edu>
---
 drivers/char/random.c | 31 +++++++++++++++++++++----------
 1 file changed, 21 insertions(+), 10 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 04a117a..8ec4a9a 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -834,17 +834,9 @@ static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
 }
 
 /*
- * These functions extracts randomness from the "entropy pool", and
- * returns it in a buffer.
- *
- * The min parameter specifies the minimum amount we can pull before
- * failing to avoid races that defeat catastrophic reseeding while the
- * reserved parameter indicates how much entropy we must leave in the
- * pool after each pull to avoid starving other readers.
- *
- * Note: extract_entropy() assumes that .poolwords is a multiple of 16 words.
+ * This function decides how many bytes to actually take from the
+ * given pool, and also debits the entropy count accordingly.
  */
-
 static size_t account(struct entropy_store *r, size_t nbytes, int min,
 		      int reserved)
 {
@@ -896,6 +888,12 @@ retry:
 	return nbytes;
 }
 
+/*
+ * This function does the actual extraction for extract_entropy and
+ * extract_entropy_user.
+ *
+ * Note: we assume that .poolwords is a multiple of 16 words.
+ */
 static void extract_buf(struct entropy_store *r, __u8 *out)
 {
 	int i;
@@ -957,6 +955,15 @@ static void extract_buf(struct entropy_store *r, __u8 *out)
 	memset(&hash, 0, sizeof(hash));
 }
 
+/*
+ * This function extracts randomness from the "entropy pool", and
+ * returns it in a buffer.
+ *
+ * The min parameter specifies the minimum amount we can pull before
+ * failing to avoid races that defeat catastrophic reseeding while the
+ * reserved parameter indicates how much entropy we must leave in the
+ * pool after each pull to avoid starving other readers.
+ */
 static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 				 size_t nbytes, int min, int reserved)
 {
@@ -1007,6 +1014,10 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 	return ret;
 }
 
+/*
+ * This function extracts randomness from the "entropy pool", and
+ * returns it in a userspace buffer.
+ */
 static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf,
 				    size_t nbytes)
 {
-- 
1.8.3.2

[PATCH 07/11] random: simplify accounting code slightly

[Greg Price]

This commit makes the very boring simplifications so that the next
commit, which is a little trickier, is isolated and easy to review.
No change in behavior here at all.

Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Jiri Kosina <jkosina@suse.cz>
Signed-off-by: Greg Price <price@mit.edu>
---
 drivers/char/random.c | 10 ++++------
 1 file changed, 4 insertions(+), 6 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 8ec4a9a..8824e8d 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -858,18 +858,16 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min,
 retry:
 		entropy_count = orig = ACCESS_ONCE(r->entropy_count);
 		/* If limited, never pull more than available */
-		if (r->limit && nbytes + reserved >= entropy_count / 8)
-			nbytes = entropy_count/8 - reserved;
+		if (r->limit)
+			nbytes = min_t(size_t, 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 (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
+			goto retry;
 
 		if (entropy_count < random_write_wakeup_thresh)
 			wakeup_write = 1;
-- 
1.8.3.2

[PATCH 08/11] random: simplify accounting logic

[Greg Price]

This logic is exactly equivalent to the old logic, but it should
be easier to see what it's doing.

The equivalence depends on one fact from outside this function:
when 'r->limit' is false, 'reserved' is zero.  (Well, two facts;
the other is that 'reserved' is never negative.)

Which is a good thing, too, because the "entropy_count = reserved"
line would have had a bug otherwise -- 'reserved' counts bytes and
'entropy_count' counts bits.  Fortunately that line could only be
reached if 'r->limit' was false, and zero bytes is zero bits.

Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Jiri Kosina <jkosina@suse.cz>
Signed-off-by: Greg Price <price@mit.edu>
---
 drivers/char/random.c | 7 +------
 1 file changed, 1 insertion(+), 6 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 8824e8d..9e4645e 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -860,12 +860,7 @@ retry:
 		/* If limited, never pull more than available */
 		if (r->limit)
 			nbytes = min_t(size_t, nbytes, entropy_count/8 - reserved);
-
-		if (entropy_count / 8 >= nbytes + reserved) {
-			entropy_count -= nbytes*8;
-		} else {
-			entropy_count = reserved;
-		}
+		entropy_count = max_t(int, entropy_count - nbytes*8, 0);
 		if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
 			goto retry;
 
-- 
1.8.3.2

[PATCH 09/11] random: forget lock in lockless accounting

[Greg Price]

The only mutable data accessed here is ->entropy_count, but since
902c098a3 ("random: use lockless techniques in the interrupt path")
that member isn't protected by the lock anyway.  Since 10b3a32d2
("random: fix accounting race condition") we use cmpxchg to protect
our accesses to ->entropy_count here.  Drop the use of the lock.

Cc: Jiri Kosina <jkosina@suse.cz>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Greg Price <price@mit.edu>
---
 drivers/char/random.c | 5 -----
 1 file changed, 5 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 9e4645e..1bf6bf8 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -843,9 +843,6 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min,
 	unsigned long flags;
 	int wakeup_write = 0;
 
-	/* Hold lock while accounting */
-	spin_lock_irqsave(&r->lock, flags);
-
 	BUG_ON(r->entropy_count > r->poolinfo->POOLBITS);
 	DEBUG_ENT("trying to extract %zu bits from %s\n",
 		  nbytes * 8, r->name);
@@ -871,8 +868,6 @@ retry:
 	DEBUG_ENT("debiting %zu entropy credits from %s%s\n",
 		  nbytes * 8, r->name, r->limit ? "" : " (unlimited)");
 
-	spin_unlock_irqrestore(&r->lock, flags);
-
 	if (wakeup_write) {
 		wake_up_interruptible(&random_write_wait);
 		kill_fasync(&fasync, SIGIO, POLL_OUT);
-- 
1.8.3.2

[PATCH 10/11] random: pull 'min' check in accounting to inside lockless update

[Greg Price]

Since 902c098a3 ("random: use lockless techniques in the interrupt
path") we have protected entropy_count only with cmpxchg, not the
lock.  In 10b3a32d2 ("random: fix accounting race condition") we
put a cmpxchg-retry loop around most of the logic in account(),
but the enforcement of the 'min' parameter stayed outside.

Under concurrent accesses to /dev/urandom this can suffer a race
that defeats our "catastrophic reseed" measures so that our
reseeding isn't effective.  If accesses to /dev/urandom and
/dev/random are interleaved in the wrong pattern, we could go
indefinitely long without a successful catastrophic reseed of
/dev/urandom, even while consuming an indefinite amount of entropy
in ineffective smaller reseeds.

NB that with or without this bug, if /dev/random is simply
accessed constantly, we can go indefinitely long without any
reseed of /dev/urandom.  So the effect of the bug is not that big.

The race comes when two tasks are in account() on input_pool
and access ->entropy_count in the following order:

             task A                           task B
   if (r->entropy_count / 8
               < min + reserved)
                                   ACCESS_ONCE(r->entropy_count)
                                   cmpxchg
   ACCESS_ONCE(r->entropy_count)
   cmpxchg

where B causes r->entropy_count / 8 to fall below A's
min + reserved but above reserved.  Task A will cheerfully
take r->entropy_count / 8 - reserved bytes from the pool,
even though this is less than min.

Move the "min" check inside the ACCESS_ONCE/cmpxchg loop to
prevent the race.

Cc: Jiri Kosina <jkosina@suse.cz>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Greg Price <price@mit.edu>
---
 drivers/char/random.c | 9 ++++-----
 1 file changed, 4 insertions(+), 5 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 1bf6bf8..87d3728 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -842,18 +842,17 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min,
 {
 	unsigned long flags;
 	int wakeup_write = 0;
+	int entropy_count, orig;
 
 	BUG_ON(r->entropy_count > r->poolinfo->POOLBITS);
 	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) {
+retry:
+	entropy_count = orig = ACCESS_ONCE(r->entropy_count);
+	if (entropy_count / 8 < min + reserved) {
 		nbytes = 0;
 	} else {
-		int entropy_count, orig;
-retry:
-		entropy_count = orig = ACCESS_ONCE(r->entropy_count);
 		/* If limited, never pull more than available */
 		if (r->limit)
 			nbytes = min_t(size_t, nbytes, entropy_count/8 - reserved);
-- 
1.8.3.2

[PATCH 11/11] random: simplify accounting code

[Greg Price]

With this we handle "reserved" in just one place.  As a bonus the
code becomes less nested, and the "wakeup_write" flag variable
becomes unnecessary.  The variable "flags" was already unused.

This code behaves identically to the previous version except in
two pathological cases that don't occur.  If the argument "nbytes"
is already less than "min", then we didn't previously enforce
"min".  If r->limit is false while "reserved" is nonzero, then we
previously applied "reserved" in checking whether we had enough
bits, even though we don't apply it to actually limit how many we
take.  The callers of account() never exercise either of these cases.

Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Jiri Kosina <jkosina@suse.cz>
Signed-off-by: Greg Price <price@mit.edu>
---
 drivers/char/random.c | 23 ++++++++---------------
 1 file changed, 8 insertions(+), 15 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 87d3728..3f343ff 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -840,8 +840,6 @@ static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
 static size_t account(struct entropy_store *r, size_t nbytes, int min,
 		      int reserved)
 {
-	unsigned long flags;
-	int wakeup_write = 0;
 	int entropy_count, orig;
 
 	BUG_ON(r->entropy_count > r->poolinfo->POOLBITS);
@@ -850,24 +848,19 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min,
 
 retry:
 	entropy_count = orig = ACCESS_ONCE(r->entropy_count);
-	if (entropy_count / 8 < min + reserved) {
+	/* If limited, never pull more than available */
+	if (r->limit)
+		nbytes = min_t(size_t, nbytes, entropy_count/8 - reserved);
+	if (nbytes < min)
 		nbytes = 0;
-	} else {
-		/* If limited, never pull more than available */
-		if (r->limit)
-			nbytes = min_t(size_t, nbytes, entropy_count/8 - reserved);
-		entropy_count = max_t(int, entropy_count - nbytes*8, 0);
-		if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
-			goto retry;
-
-		if (entropy_count < random_write_wakeup_thresh)
-			wakeup_write = 1;
-	}
+	entropy_count = max_t(int, entropy_count - nbytes*8, 0);
+	if (nbytes && cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
+		goto retry;
 
 	DEBUG_ENT("debiting %zu entropy credits from %s%s\n",
 		  nbytes * 8, r->name, r->limit ? "" : " (unlimited)");
 
-	if (wakeup_write) {
+	if (nbytes && entropy_count < random_write_wakeup_thresh) {
 		wake_up_interruptible(&random_write_wait);
 		kill_fasync(&fasync, SIGIO, POLL_OUT);
 	}
-- 
1.8.3.2

Re: [PATCH 00/11] random: code cleanups

[Theodore Ts'o]

On Thu, Nov 07, 2013 at 06:57:25PM -0500, Greg Price wrote:
> 
> I recently read through the random number generator's code.
> This series has fixes for some minor things I spotted.
> 
> Four of the patches touch comments only.  Four simplify code without
> changing its behavior (total diffstat: 35 insertions, 73 deletions),
> and one is a trivial signedness fix.  Two patches change the locking
> and lockless concurrency control in account(), including one bugfix.
> The bug is related to the one Jiri found and fixed in May.

Hi Greg,

My apologies for not being able to get to this patch series before the
patch window opened --- this week has been crazy.  None of the changes
seem to be especially critical, and a number of the patches don't
apply cleanly to the random.git tree (some of the spelling fixes have
already been fixed, for example), which has patches queued up for the
upcoming merge window.  So I'm going to defer applying these patches
for 2.13, and I'd ask you if you'd be willing to rebase these patches
against the random.git tree, so they can be pulled in after the merge
window closes.

Thanks,

					- Ted

Re: [PATCH 00/11] random: code cleanups

[Greg Price]

On Mon, Nov 11, 2013 at 11:24:44PM -0500, Theodore Ts'o wrote:
> My apologies for not being able to get to this patch series before the
> patch window opened --- this week has been crazy.  None of the changes
> seem to be especially critical, and a number of the patches don't
> apply cleanly to the random.git tree (some of the spelling fixes have
> already been fixed, for example), which has patches queued up for the
> upcoming merge window.  So I'm going to defer applying these patches
> for 2.13, and I'd ask you if you'd be willing to rebase these patches
> against the random.git tree, so they can be pulled in after the merge
> window closes.

Ah, I hadn't spotted the random.git tree!  Looks like 'dev' at
v3.11-20-g392a546 is the tip -- is that right?  Rebasing now, and I'll
follow up with the result.

I agree that none of the changes are especially critical.  There is
one bugfix, and the rest are code cleanups.

Beyond these easy cleanups, I have a couple of patches queued up (just
written yesterday, not quite finished) to make /dev/urandom block at
boot until it has enough entropy, as the "Mining your P's and Q's"
paper recommended and people have occasionally discussed since then.
Those patches were definitely for after 3.13 anyway, and I'll send
them when they're ready.  I see some notifications and warnings in
this direction in the random.git tree, which is great.

Cheers,
Greg

Re: [PATCH 00/11] random: code cleanups

[Theodore Ts'o]

On Tue, Nov 12, 2013 at 05:40:09PM -0500, Greg Price wrote:
> 
> Beyond these easy cleanups, I have a couple of patches queued up (just
> written yesterday, not quite finished) to make /dev/urandom block at
> boot until it has enough entropy, as the "Mining your P's and Q's"
> paper recommended and people have occasionally discussed since then.
> Those patches were definitely for after 3.13 anyway, and I'll send
> them when they're ready.  I see some notifications and warnings in
> this direction in the random.git tree, which is great.

One of the things I've been thinking about with respect to making
/dev/urandom block is being able to configure (via a module parameter
which could be specified on the boot command line) which allows us to
set a limit for how long /dev/urandom will block after which we log a
high priority message that there was an attempt to read from
/dev/urandom which couldn't be satisified, and then allowing the
/dev/urandom read to succed.

The basic idea is that we don't want to break systems, but we do want
to gently coerce people to do the right thing.  Otherwise, I'm worried
that distros, or embedded/mobile/consume electronics engineers would
just patch out the check.  If we make the default be something like
"block for 5 minutes", and then log a message, we won't completely
break a user who is trying to login to a VM, but it will be obvious,
both from the delay and from the kern.crit log message, that there is
a potential problem here that a system administrator needs to worry
about.

						- Ted

Re: [PATCH 00/11] random: code cleanups

[H. Peter Anvin]

On 11/12/2013 07:32 PM, Theodore Ts'o wrote:
> On Tue, Nov 12, 2013 at 05:40:09PM -0500, Greg Price wrote:
>>
>> Beyond these easy cleanups, I have a couple of patches queued up (just
>> written yesterday, not quite finished) to make /dev/urandom block at
>> boot until it has enough entropy, as the "Mining your P's and Q's"
>> paper recommended and people have occasionally discussed since then.
>> Those patches were definitely for after 3.13 anyway, and I'll send
>> them when they're ready.  I see some notifications and warnings in
>> this direction in the random.git tree, which is great.
> 
> One of the things I've been thinking about with respect to making
> /dev/urandom block is being able to configure (via a module parameter
> which could be specified on the boot command line) which allows us to
> set a limit for how long /dev/urandom will block after which we log a
> high priority message that there was an attempt to read from
> /dev/urandom which couldn't be satisified, and then allowing the
> /dev/urandom read to succed.
> 
> The basic idea is that we don't want to break systems, but we do want
> to gently coerce people to do the right thing.  Otherwise, I'm worried
> that distros, or embedded/mobile/consume electronics engineers would
> just patch out the check.  If we make the default be something like
> "block for 5 minutes", and then log a message, we won't completely
> break a user who is trying to login to a VM, but it will be obvious,
> both from the delay and from the kern.crit log message, that there is
> a potential problem here that a system administrator needs to worry
> about.
> 

One thing, too, if we are talking about anything other than
boot-time-only blocking: going from a nonblocking to a blocking
condition means being able to accept a short read, and right now *many*
users of /dev/urandom are not ready to accept a short read.

	-hpa

Re: [PATCH 00/11] random: code cleanups

[Greg Price]

On Tue, Nov 12, 2013 at 10:32:05PM -0500, Theodore Ts'o wrote:
> One of the things I've been thinking about with respect to making
> /dev/urandom block is being able to configure (via a module parameter
> which could be specified on the boot command line) which allows us to
> set a limit for how long /dev/urandom will block after which we log a
> high priority message that there was an attempt to read from
> /dev/urandom which couldn't be satisified, and then allowing the
> /dev/urandom read to succed.
> 
> The basic idea is that we don't want to break systems, but we do want
> to gently coerce people to do the right thing.  Otherwise, I'm worried
> that distros, or embedded/mobile/consume electronics engineers would
> just patch out the check.

That's a good idea.  I've worried about the same thing, but hadn't
thought of that solution.

Greg

Re: [PATCH 00/11] random: code cleanups

[Greg Price]

On Tue, Nov 12, 2013 at 08:02:09PM -0800, H. Peter Anvin wrote:
> One thing, too, if we are talking about anything other than
> boot-time-only blocking: going from a nonblocking to a blocking
> condition means being able to accept a short read, and right now *many*
> users of /dev/urandom are not ready to accept a short read.

I'm thinking only of boot-time blocking.  The idea is that once
/dev/urandom is seeded with, say, 128 bits of min-entropy in the
absolute, information-theoretic sense, it can produce an infinite
supply (or something like 2^128 bits, which amounts to the same thing)
of bits that can't be distinguished from random, short of breaking or
brute-forcing the crypto.  So once it's seeded, it's good forever.

We don't even strictly need to keep adding more entropy once it's
seeded, but it's good because (a) hey, it's cheap, (b) entropy
estimation is hard, and maybe in some situations we're too optimistic
and think we're well seeded before we really are, (c) some
cryptographers like to imagine having a PRNG recover from an attacker
learning its internal state by using fresh entropy.  Other
cryptographers think (c) is a little silly because an attacker that
can do that can probably keep doing it, or take over the machine
entirely, but it's not inconceivable, and there's (a) and (b).  So we
keep adding entropy when we have it, but if we don't have new entropy
for a long time there's no need to start blocking again.

Cheers,
Greg

Re: [PATCH 00/11] random: code cleanups

[H. Peter Anvin]

On 11/12/2013 08:37 PM, Greg Price wrote:
> 
> I'm thinking only of boot-time blocking.  The idea is that once
> /dev/urandom is seeded with, say, 128 bits of min-entropy in the
> absolute, information-theoretic sense, it can produce an infinite
> supply (or something like 2^128 bits, which amounts to the same thing)
> of bits that can't be distinguished from random, short of breaking or
> brute-forcing the crypto.  So once it's seeded, it's good forever.
> 

And, pray tell, how will you know that you have done that?

Even the best entropy estimation algorithms are nothing but estimations,
and min-entropy is the hardest form of entropy to estimate.

	-hpa

Re: [PATCH 00/11] random: code cleanups

[Greg Price]

On Tue, Nov 12, 2013 at 08:51:18PM -0800, H. Peter Anvin wrote:
> On 11/12/2013 08:37 PM, Greg Price wrote:
> > I'm thinking only of boot-time blocking.  The idea is that once
> > /dev/urandom is seeded with, say, 128 bits of min-entropy in the
> > absolute, information-theoretic sense, it can produce an infinite
> > supply (or something like 2^128 bits, which amounts to the same thing)
> > of bits that can't be distinguished from random, short of breaking or
> > brute-forcing the crypto.  So once it's seeded, it's good forever.
> 
> And, pray tell, how will you know that you have done that?
> 
> Even the best entropy estimation algorithms are nothing but estimations,

Indeed.  We do our best, but we can't be sure we have as much entropy
as we think.

The status quo here is that /dev/urandom will cheerfully answer
requests even when, by our own estimates, we only have a small amount
of entropy and anything we return will be guessable.  What Ted and I
are discussing in this thread is to have it wait until, as best we can
estimate, it has enough entropy to give an unpredictable answer.  The
status quo has the same effect as an arbitrarily too-optimistic
estimate.

The key point when it comes to the question of going *back* to
blocking is that even if the estimates are bad and in reality the
answer is guessable, it won't get any *more* guessable in the future.
If we think we have 128 bits of input min-entropy but we only have
(say) 32, meaning some states we could be in are as likely as 2^(-32),
then once an attacker sees a handful of bytes of output (*) they can
check a guess at our input and predict all our other output with as
few as 2^32 guesses, depending on the distribution.  If the attacker
sees a gigabyte or a petabyte of output, they have exactly the same
ability.  So there's no good reason to stop.

On the other hand, because our estimates may be wrong it certainly
make sense to keep feeding new entropy into the pool.  Maybe a later
seeding will have enough real entropy to make us unpredictable from
then on.  We could also use bigger and bigger reseeds, as a hedge
against our estimates being systematically too low in some
environment.

Does that make sense?  Do you have other ideas for guarding against
the case where our estimates are low?

Greg


(*) Math note: the attacker morally needs only 32 bits.  They actually
need a little more than that, because some of the (at least) 2^32
possible states probably correspond to the same first 32 bits of
output.  By standard probability bounds, for any given set of 2^32
possible input states, if the generator is good then probably no more
than ln(2^32) = 22 or so of them correspond to the same first 32 bits.
About 37 bits of output is enough to probably make all the outputs
different, and with even 64 bits = 8 bytes of output it becomes
overwhelmingly likely that all the outputs are different.  If there
are more than 2^32 possible states because the min-entropy is 32 but
some inputs are less likely, then the attacker needs even less output
to be able to confirm the most likely guesses.

Re: [PATCH 00/11] random: code cleanups

[Theodore Ts'o]

On Tue, Nov 12, 2013 at 11:23:03PM -0500, Greg Price wrote:
> > The basic idea is that we don't want to break systems, but we do want
> > to gently coerce people to do the right thing.  Otherwise, I'm worried
> > that distros, or embedded/mobile/consume electronics engineers would
> > just patch out the check.
> 
> That's a good idea.  I've worried about the same thing, but hadn't
> thought of that solution.

I think the key is that we set a default of requiring 128 bits, or 5
minutes, with boot-line options to change the defaults.  BTW, with the
changes that are scheduled for 3.13, this shouldn't be a problem on
most desktops.  From my T430s laptop:

...
[    4.446047] random: nonblocking pool is initialized
[    4.542119] usb 3-1.6: New USB device found, idVendor=04f2, idProduct=b2da
[    4.542124] usb 3-1.6: New USB device strings: Mfr=1, Product=2, SerialNumber=0
[    4.542128] usb 3-1.6: Product: Integrated Camera
[    4.542131] usb 3-1.6: Manufacturer: Chicony Electronics Co., Ltd.
[    4.575753] SELinux: initialized (dev tmpfs, type tmpfs), uses transition SIDs
[    4.653338] udevd[462]: starting version 175
...
[    6.253131] EXT4-fs (sdc3): re-mounted. Opts: (null)

So even without adding device attach times (which is on the todo list)
the /dev/urandom pool is getting an estimated 128 bits of entropy
almost two seconds *before* the root file system is remouted
read/write.

(And this is also before fixing the rc80211 minstrel code to stop
wasting about two dozen bits of entropy at startup --- it's using
get_random_bytes even though it doesn't actually need
cryptographically secure random numbers.)

This is why I've been working improving the random driver's efficiency
in getting the urandom pool as soon as possible, as higher priority
than adding blocking-on-boot for /dev/urandom.

> And, pray tell, how will you know that you have done that?
> 
> Even the best entropy estimation algorithms are nothing but estimations,
> and min-entropy is the hardest form of entropy to estimate.

Of course it's only an estimate.  Some researchers have looked into
this and their results show that at least for x86 desktop/servers, we
appear to be conservative enough in our entropy estimation.  But
ultimately, yes, that is an issue which I am concerned about.  But I
believe that's a separable problem that we can work on separately from
other /dev/random issues --- and I'm hoping we can get some students
to study this problem on a variety of different hardware platforms and
entropy sources.

					- Ted

Re: [PATCH 00/11] random: code cleanups

[Greg Price]

On Wed, Nov 13, 2013 at 01:08:07AM -0500, Theodore Ts'o wrote:
> On Tue, Nov 12, 2013 at 11:23:03PM -0500, Greg Price wrote:
> > That's a good idea.  I've worried about the same thing, but hadn't
> > thought of that solution.
> 
> I think the key is that we set a default of requiring 128 bits, or 5
> minutes, with boot-line options to change the defaults.  BTW, with the
> changes that are scheduled for 3.13, this shouldn't be a problem on
> most desktops.  From my T430s laptop: [...]
> 
> So even without adding device attach times (which is on the todo list)
> the /dev/urandom pool is getting an estimated 128 bits of entropy
> almost two seconds *before* the root file system is remouted
> read/write.

Great!


> This is why I've been working improving the random driver's efficiency
> in getting the urandom pool as soon as possible, as higher priority
> than adding blocking-on-boot for /dev/urandom.

Makes sense.  Blocking on boot is only sustainable anyway if it rarely
lasts past early boot.

Greg