Skip to contentSkip to conversation

random: code cleanups

PATCH Superseded Greg Price 3 participants 22 messages Nov 7, 2013 – Nov 13, 2013 Random number driver

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Greg Price

author
#0 lore raw

cover random: code cleanups

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(-)
Signature · 1 line
1.8.3.2
author
#1 lore raw

PATCH 1/11 random: fix typos / spelling errors in comments

Cc "Theodore Ts'o" <[email protected]>
---
 drivers/char/random.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)
drivers/char/random.c +4 -4
index 7a744d3..ef3e15b 100644
@@ -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++) {
Signature · 1 line
1.8.3.2
author
#2 lore raw

PATCH 2/11 random: fix comment on proc_do_uuid

In reply to 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" <[email protected]>
---
 drivers/char/random.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)
drivers/char/random.c +4 -4
index ef3e15b..a89ba74 100644
@@ -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)
Signature · 1 line
1.8.3.2
author
#3 lore raw

PATCH 3/11 random: fix description of get_random_bytes

In reply to 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" <[email protected]>
---
 drivers/char/random.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)
drivers/char/random.c +3 -2
index a89ba74..d1466c9 100644
@@ -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)
 {
Signature · 1 line
1.8.3.2
author
#4 lore raw

PATCH 4/11 random: simplify loop in random_read

In reply to 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" <[email protected]>
---
 drivers/char/random.c | 68 +++++++++++++++++----------------------------------
 1 file changed, 22 insertions(+), 46 deletions(-)
drivers/char/random.c +22 -46
index d1466c9..85f5fce 100644
@@ -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
Signature · 1 line
1.8.3.2
author
#5 lore raw

PATCH 5/11 random: declare trickle_count unsigned

In reply to 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" <[email protected]>
---
 drivers/char/random.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
drivers/char/random.c +1 -1
index 85f5fce..04a117a 100644
@@ -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
Signature · 1 line
1.8.3.2
author
#6 lore raw

PATCH 6/11 random: fix comment on "account"

In reply to 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" <[email protected]>
---
 drivers/char/random.c | 31 +++++++++++++++++++++----------
 1 file changed, 21 insertions(+), 10 deletions(-)
drivers/char/random.c +21 -10
index 04a117a..8ec4a9a 100644
@@ -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)
 {
Signature · 1 line
1.8.3.2
author
#7 lore raw

PATCH 7/11 random: simplify accounting code slightly

In reply to 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" <[email protected]>
Cc Jiri Kosina <[email protected]>
---
 drivers/char/random.c | 10 ++++------
 1 file changed, 4 insertions(+), 6 deletions(-)
drivers/char/random.c +4 -6
index 8ec4a9a..8824e8d 100644
@@ -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;
Signature · 1 line
1.8.3.2
author
#8 lore raw

PATCH 8/11 random: simplify accounting logic

In reply to 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" <[email protected]>
Cc Jiri Kosina <[email protected]>
---
 drivers/char/random.c | 7 +------
 1 file changed, 1 insertion(+), 6 deletions(-)
drivers/char/random.c +1 -6
index 8824e8d..9e4645e 100644
@@ -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;
 
Signature · 1 line
1.8.3.2
author
#9 lore raw

PATCH 9/11 random: forget lock in lockless accounting

In reply to 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 <[email protected]>
Cc "Theodore Ts'o" <[email protected]>
---
 drivers/char/random.c | 5 -----
 1 file changed, 5 deletions(-)
drivers/char/random.c +0 -5
index 9e4645e..1bf6bf8 100644
@@ -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);
Signature · 1 line
1.8.3.2
author
#10 lore raw

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

In reply to 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 <[email protected]>
Cc "Theodore Ts'o" <[email protected]>
---
 drivers/char/random.c | 9 ++++-----
 1 file changed, 4 insertions(+), 5 deletions(-)
drivers/char/random.c +4 -5
index 1bf6bf8..87d3728 100644
@@ -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);
Signature · 1 line
1.8.3.2
author
#11 lore raw

PATCH 11/11 random: simplify accounting code

In reply to 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" <[email protected]>
Cc Jiri Kosina <[email protected]>
---
 drivers/char/random.c | 23 ++++++++---------------
 1 file changed, 8 insertions(+), 15 deletions(-)
drivers/char/random.c +8 -15
index 87d3728..3f343ff 100644
@@ -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);
 	}
Signature · 1 line
1.8.3.2
maintainer
#12 lore raw
In reply to Greg Price
Quoted 9 lines · Greg Price

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

author
#13 lore raw
Quoted 9 lines · Theodore Ts'o

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

maintainer
#14 lore raw
Quoted 8 lines · Greg Price

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

#15 lore raw
Quoted 18 lines · Theodore Ts'o
Quoted 8 lines · Greg Price

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.

Quoted 10 lines

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

author
#16 lore raw
Quoted 4 lines · H. Peter Anvin

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

#17 lore raw
Quoted 8 lines · Greg Price

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

author
#18 lore raw
Quoted 11 lines · H. Peter Anvin
Quoted 6 lines · Greg Price

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.

maintainer
#19 lore raw
In reply to H. Peter Anvin
Quoted 7 lines · Greg Price
Quoted 4 lines

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.

Quoted 4 lines

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

author
#20 lore raw
Quoted 9 lines · Theodore Ts'o
Quoted 2 lines · Greg Price

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: [...]

Quoted 4 lines

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!

Quoted 3 lines

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

author
#21 lore raw
In reply to Theodore Ts'o
Quoted 8 lines · Theodore Ts'o

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.

Quoted 4 lines

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