Skip to contentSkip to conversation

random: improve entropy pool initialization at boot time

PATCH In review Theodore Ts'o 2 participants 8 messages Nov 3, 2013

Subsystems (4)
lore
Share & tools
lore

Theodore Ts'o

author maintainer
#0 lore raw

cover random: improve entropy pool initialization at boot time

These patches improve how /dev/random initializes its entropy pool during the kernel boot sequence. With these changes, using an x86 test kernel run under KVM, the urandom pool gets initialized before the init scripts start running, and of the kernel users of get_random_bytes(), a debugging printk found only two users of get_random_bytes() before the nonblocking pool could be fully initialized:

rc80211_minstrel_ht_init+0x2b/0x6a called get_random_bytes with 22 bits of entropy available
neigh_hash_alloc+0x82/0x94 called get_random_bytes with 31 bits of entropy available

Both of these calls were in a subsys_initcall(); and the first one I'm fairly certain could be replaced by the use of prandom_u32().

Note: I've cc'ed these patches to linux-crypto so hopefully more people will review these patches.

- Ted

Theodore Ts'o (4):
random: use device attach events for entropy
random: make add_timer_randomness() fill the nonblocking pool first
random: printk notifications for urandom pool initialization
random: don't zap entropy count in rand_initialize()

 drivers/base/core.c    |  3 +++
 drivers/char/random.c  | 42 +++++++++++++++++++++++++++++++-----------
 include/linux/random.h |  2 ++
 3 files changed, 36 insertions(+), 11 deletions(-)
Signature · 1 line
1.7.12.rc0.22.gcdd159b
author maintainer
#1 lore raw

PATCH 1/4 random: use device attach events for entropy

Some investigation from FreeBSD shows that there is entropy available from measuring the device attach times:

http://lists.randombit.net/pipermail/cryptography/2013-October/005689.html

This will hopefully help us more quickly initialize the entropy pools while the system is booting (which is one of the times when we really badly need more entropy, especially in the case of the first boot after an consumer electronics device is taken out of the box).

Measurements indicate this makes a huge improvement in the security of /dev/urandom during the boot sequence, so I'm cc'ing this to the stable kernel series. Especially for embedded systems, which use flash and which don't necessarily have the network enabled when they first generate ssh or x.509 keys (sigh), this can be a big deal.

---
 drivers/base/core.c    | 3 +++
 drivers/char/random.c  | 7 +++++++
 include/linux/random.h | 2 ++
 3 files changed, 12 insertions(+)
drivers/base/core.c +3 -0
index 8856d74..5e98fc3 100644
@@ -26,6 +26,7 @@
 #include <linux/async.h>
 #include <linux/pm_runtime.h>
 #include <linux/netdevice.h>
+#include <linux/random.h>
 
 #include "base.h"
 #include "power/power.h"
@@ -1156,6 +1157,8 @@ int device_add(struct device *dev)
 				class_intf->add_dev(dev, class_intf);
 		mutex_unlock(&dev->class->p->mutex);
 	}
+	add_device_attach_randomness(dev);
+
 done:
 	put_device(dev);
 	return error;
drivers/char/random.c +7 -0
index f126bd2..51153fe 100644
@@ -829,6 +829,13 @@ void add_input_randomness(unsigned int type, unsigned int code,
 }
 EXPORT_SYMBOL_GPL(add_input_randomness);
 
+void add_device_attach_randomness(struct device *dev)
+{
+	static struct timer_rand_state attach_state = { 0, };
+
+	add_timer_randomness(&attach_state, dev->devt);
+}
+
 static DEFINE_PER_CPU(struct fast_pool, irq_randomness);
 
 void add_interrupt_randomness(int irq, int irq_flags)
include/linux/random.h +2 -0
index 6312dd9..5ef9470 100644
@@ -12,6 +12,8 @@
 extern void add_device_randomness(const void *, unsigned int);
 extern void add_input_randomness(unsigned int type, unsigned int code,
 				 unsigned int value);
+struct device;
+extern void add_device_attach_randomness(struct device *dev);
 extern void add_interrupt_randomness(int irq, int irq_flags);
 
 extern void get_random_bytes(void *buf, int nbytes);
Signature · 1 line
1.7.12.rc0.22.gcdd159b
#2 lore raw

Re: [PATCH 1/4] random: use device attach events for entropy

Quoted 50 lines · Theodore Ts'o

Some investigation from FreeBSD shows that there is entropy available from measuring the device attach times:

http://lists.randombit.net/pipermail/cryptography/2013-October/005689.html

This will hopefully help us more quickly initialize the entropy pools while the system is booting (which is one of the times when we really badly need more entropy, especially in the case of the first boot after an consumer electronics device is taken out of the box).

Measurements indicate this makes a huge improvement in the security of /dev/urandom during the boot sequence, so I'm cc'ing this to the stable kernel series. Especially for embedded systems, which use flash and which don't necessarily have the network enabled when they first generate ssh or x.509 keys (sigh), this can be a big deal.

---
 drivers/base/core.c    | 3 +++
 drivers/char/random.c  | 7 +++++++
 include/linux/random.h | 2 ++
 3 files changed, 12 insertions(+)
drivers/base/core.c +3 -0
index 8856d74..5e98fc3 100644
@@ -26,6 +26,7 @@
 #include <linux/async.h>
 #include <linux/pm_runtime.h>
 #include <linux/netdevice.h>
+#include <linux/random.h>
 
 #include "base.h"
 #include "power/power.h"
@@ -1156,6 +1157,8 @@ int device_add(struct device *dev)
 				class_intf->add_dev(dev, class_intf);
 		mutex_unlock(&dev->class->p->mutex);
 	}
+	add_device_attach_randomness(dev);
+
 done:
 	put_device(dev);
 	return error;
drivers/char/random.c +0 -0
index f126bd2..51153fe 100644

drivers/char/random.c void add_input_randomness(unsigned int type, unsigned int code, · line 836

Quoted 8 lines
drivers/char/random.c +5 -0
@@ -829,6 +829,13 @@ void add_input_randomness(unsigned int type, unsigned int code,
 }
 EXPORT_SYMBOL_GPL(add_input_randomness);
 
+void add_device_attach_randomness(struct device *dev)
+{
+	static struct timer_rand_state attach_state = { 0, };
+
+	add_timer_randomness(&attach_state, dev->devt);

Is it an issue that dev->devt will almost always be 0,0 for this function call? Why not use the name instead here, that's more "unique" and every device has one, not just a tiny %.

thanks,

greg k-h

author maintainer
#3 lore raw

Re: [PATCH 1/4] random: use device attach events for entropy

Quoted 3 lines · Greg KH

Is it an issue that dev->devt will almost always be 0,0 for this function call? Why not use the name instead here, that's more "unique" and every device has one, not just a tiny %.

Hmm, good point. Thanks for raising it. I'll make this change and respin the patches.

- Ted

author maintainer
#4 lore raw

Re: [PATCH 1/4] random: use device attach events for entropy

In reply to Theodore Ts'o
Quoted 10 lines · Theodore Ts'o

Some investigation from FreeBSD shows that there is entropy available from measuring the device attach times:

http://lists.randombit.net/pipermail/cryptography/2013-October/005689.html

This will hopefully help us more quickly initialize the entropy pools while the system is booting (which is one of the times when we really badly need more entropy, especially in the case of the first boot after an consumer electronics device is taken out of the box).

Quoted 8 lines

Measurements indicate this makes a huge improvement in the security of /dev/urandom during the boot sequence, so I'm cc'ing this to the stable kernel series. Especially for embedded systems, which use flash and which don't necessarily have the network enabled when they first generate ssh or x.509 keys (sigh), this can be a big deal.

Self-NAK. After doing some more measurements, I'm not convinced the entropy estimator is working well given how we are collecting the device attach times. Instead, we need to measure the delta between the start and the end of the device probe, which in turn will only work if we have a valid cycle counter. (random_get_entropy() is not going to cut it.)

So with some changes, this approach will improve things on x86, but on architectures like ARM, which generally don't have a cycle counter, the jiffies counter is not going to have enough resolution to do something useful --- and it was on platforms such as ARM and MIPS
where I was hoping this would be most useful. Grumble.

Why can't ARM and MIPS have decent cycle counters? <Shakes fist>

- Ted

author maintainer
#5 lore raw

PATCH 2/4 random: make add_timer_randomness() fill the nonblocking pool first

In reply to Theodore Ts'o

Change add_timer_randomness() so that it directs incoming entropy to the nonblocking pool first if it hasn't been fully initialized yet. This matches the strategy we use in add_interrupt_randomness(), which allows us to push the randomness where we need it the most during when the system is first booting up, so that get_random_bytes() and /dev/urandom become safe to use as soon as possible.

---
 drivers/char/random.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)
drivers/char/random.c +4 -3
index 51153fe..b578c03 100644
@@ -761,6 +761,7 @@ static struct timer_rand_state input_timer_state;
  */
 static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
 {
+	struct entropy_store	*r;
 	struct {
 		long jiffies;
 		unsigned cycles;
@@ -773,7 +774,8 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
 	sample.jiffies = jiffies;
 	sample.cycles = random_get_entropy();
 	sample.num = num;
-	mix_pool_bytes(&input_pool, &sample, sizeof(sample), NULL);
+	r = nonblocking_pool.initialized ? &input_pool : &nonblocking_pool;
+	mix_pool_bytes(r, &sample, sizeof(sample), NULL);
 
 	/*
 	 * Calculate number of bits of randomness we probably added.
@@ -807,8 +809,7 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
 		 * Round down by 1 bit on general principles,
 		 * and limit entropy entimate to 12 bits.
 		 */
-		credit_entropy_bits(&input_pool,
-				    min_t(int, fls(delta>>1), 11));
+		credit_entropy_bits(r, min_t(int, fls(delta>>1), 11));
 	}
 	preempt_enable();
 }
Signature · 1 line
1.7.12.rc0.22.gcdd159b
author maintainer
#6 lore raw

PATCH 3/4 random: printk notifications for urandom pool initialization

In reply to Theodore Ts'o

Print a notification to the console when the nonblocking pool is initialized. Also printk a warning when a process tries reading from /dev/urandom before it is fully initialized.

---
 drivers/char/random.c | 12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)
drivers/char/random.c +11 -1
index b578c03..f553600 100644
@@ -655,6 +655,9 @@ retry:
 	r->entropy_total += nbits;
 	if (!r->initialized && nbits > 0) {
 		if (r->entropy_total > 128) {
+			if (r == &nonblocking_pool)
+				pr_notice("random: %s pool is initialized\n",
+					  r->name);
 			r->initialized = 1;
 			r->entropy_total = 0;
 		}
@@ -1334,7 +1337,14 @@ random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
 static ssize_t
 urandom_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
 {
-	int ret = extract_entropy_user(&nonblocking_pool, buf, nbytes);
+	int ret;
+
+	if (unlikely(nonblocking_pool.initialized == 0))
+		printk_once(KERN_NOTICE "random: %s urandom read "
+			    "with %d bits of entropy available\n",
+			    current->comm, nonblocking_pool.entropy_total);
+
+	ret = extract_entropy_user(&nonblocking_pool, buf, nbytes);
 
 	trace_urandom_read(8 * nbytes, ENTROPY_BITS(&nonblocking_pool),
 			   ENTROPY_BITS(&input_pool));
Signature · 1 line
1.7.12.rc0.22.gcdd159b
author maintainer
#7 lore raw

PATCH 4/4 random: don't zap entropy count in rand_initialize()

In reply to Theodore Ts'o

The rand_initialize() function was being run fairly late in the kernel boot sequence. This was unfortunate, since it zero'ed the entropy counters, thus throwing away credit that was accumulated earlier in the boot sequence, and it also meant that initcall functions run before rand_initialize were using a minimally initialized pool.

To fix this, fix init_std_data() to no longer zap the entropy counter; it wasn't necessary, and move rand_initialize() to be an early initcall.

---
 drivers/char/random.c | 16 +++++++++-------
 1 file changed, 9 insertions(+), 7 deletions(-)
drivers/char/random.c +9 -7
index f553600..4a0e458 100644
@@ -1235,14 +1235,11 @@ static void init_std_data(struct entropy_store *r)
 	ktime_t now = ktime_get_real();
 	unsigned long rv;
 
-	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))
-			break;
+			rv = random_get_entropy();
 		mix_pool_bytes(r, &rv, sizeof(rv), NULL);
 	}
 	mix_pool_bytes(r, utsname(), sizeof(*(utsname())), NULL);
@@ -1265,7 +1262,7 @@ static int rand_initialize(void)
 	init_std_data(&nonblocking_pool);
 	return 0;
 }
-module_init(rand_initialize);
+early_initcall(rand_initialize);
 
 #ifdef CONFIG_BLOCK
 void rand_initialize_disk(struct gendisk *disk)
@@ -1440,10 +1437,15 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
 		return 0;
 	case RNDZAPENTCNT:
 	case RNDCLEARPOOL:
-		/* Clear the entropy pool counters. */
+		/*
+		 * Clear the entropy pool counters. We no longer clear
+		 * the entropy pool, as that's silly.
+		 */
 		if (!capable(CAP_SYS_ADMIN))
 			return -EPERM;
-		rand_initialize();
+		input_pool.entropy_count = 0;
+		nonblocking_pool.entropy_count = 0;
+		blocking_pool.entropy_count = 0;
 		return 0;
 	default:
 		return -EINVAL;
Signature · 1 line
1.7.12.rc0.22.gcdd159b