[PATCH 1/5] random: fix crng_ready() test

[PATCH 1/5] random: fix crng_ready() test

[Theodore Ts'o]

The crng_init variable has three states:

0: The CRNG is not initialized at all
1: The CRNG has a small amount of entropy, hopefully good enough for
   early-boot, non-cryptographical use cases
2: The CRNG is fully initialized and we are sure it is safe for
   cryptographic use cases.

The crng_ready() function should only return true once we are in the
last state.

Reported-by: Jann Horn <jannh@google.com>
Fixes: e192be9d9a30 ("random: replace non-blocking pool...")
Cc: stable@kernel.org # 4.8+
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
Reviewed-by: Jann Horn <jannh@google.com>
---
 drivers/char/random.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index e027e7fa1472..c8ec1e70abde 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -427,7 +427,7 @@ struct crng_state primary_crng = {
  * its value (from 0->1->2).
  */
 static int crng_init = 0;
-#define crng_ready() (likely(crng_init > 0))
+#define crng_ready() (likely(crng_init > 1))
 static int crng_init_cnt = 0;
 #define CRNG_INIT_CNT_THRESH (2*CHACHA20_KEY_SIZE)
 static void _extract_crng(struct crng_state *crng,
@@ -794,7 +794,7 @@ static int crng_fast_load(const char *cp, size_t len)
 
 	if (!spin_trylock_irqsave(&primary_crng.lock, flags))
 		return 0;
-	if (crng_ready()) {
+	if (crng_init != 0) {
 		spin_unlock_irqrestore(&primary_crng.lock, flags);
 		return 0;
 	}
@@ -856,7 +856,7 @@ static void _extract_crng(struct crng_state *crng,
 {
 	unsigned long v, flags;
 
-	if (crng_init > 1 &&
+	if (crng_ready() &&
 	    time_after(jiffies, crng->init_time + CRNG_RESEED_INTERVAL))
 		crng_reseed(crng, crng == &primary_crng ? &input_pool : NULL);
 	spin_lock_irqsave(&crng->lock, flags);
@@ -1139,7 +1139,7 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	fast_mix(fast_pool);
 	add_interrupt_bench(cycles);
 
-	if (!crng_ready()) {
+	if (unlikely(crng_init == 0)) {
 		if ((fast_pool->count >= 64) &&
 		    crng_fast_load((char *) fast_pool->pool,
 				   sizeof(fast_pool->pool))) {
@@ -2212,7 +2212,7 @@ void add_hwgenerator_randomness(const char *buffer, size_t count,
 {
 	struct entropy_store *poolp = &input_pool;
 
-	if (!crng_ready()) {
+	if (unlikely(crng_init == 0)) {
 		crng_fast_load(buffer, count);
 		return;
 	}
-- 
2.16.1.72.g5be1f00a9a

[PATCH 2/5] random: use a different mixing algorithm for add_device_randomness()

[Theodore Ts'o]

add_device_randomness() use of crng_fast_load() was highly
problematic.  Some callers of add_device_randomness() can pass in a
large amount of static information.  This would immediately promote
the crng_init state from 0 to 1, without really doing much to
initialize the primary_crng's internal state with something even
vaguely unpredictable.

Since we don't have the speed constraints of add_interrupt_randomness(),
we can do a better job mixing in the what unpredictability a device
driver or architecture maintainer might see fit to give us, and do it
in a way which does not bump the crng_init_cnt variable.

Also, since add_device_randomness() doesn't bump any entropy
accounting in crng_init state 0, mix the device randomness into the
input_pool entropy pool as well.

Reported-by: Jann Horn <jannh@google.com>
Fixes: ee7998c50c26 ("random: do not ignore early device randomness")
Cc: stable@kernel.org # 4.13+
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
---
 drivers/char/random.c | 55 +++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 51 insertions(+), 4 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index c8ec1e70abde..2154a5fe4c81 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -787,6 +787,10 @@ static void crng_initialize(struct crng_state *crng)
 	crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1;
 }
 
+/*
+ * crng_fast_load() can be called by code in the interrupt service
+ * path.  So we can't afford to dilly-dally.
+ */
 static int crng_fast_load(const char *cp, size_t len)
 {
 	unsigned long flags;
@@ -813,6 +817,51 @@ static int crng_fast_load(const char *cp, size_t len)
 	return 1;
 }
 
+/*
+ * crng_slow_load() is called by add_device_randomness, which has two
+ * attributes.  (1) We can't trust the buffer passed to it is
+ * guaranteed to be unpredictable (so it might not have any entropy at
+ * all), and (2) it doesn't have the performance constraints of
+ * crng_fast_load().
+ *
+ * So we do something more comprehensive which is guaranteed to touch
+ * all of the primary_crng's state, and which uses a LFSR with a
+ * period of 255 as part of the mixing algorithm.  Finally, we do
+ * *not* advance crng_init_cnt since buffer we may get may be something
+ * like a fixed DMI table (for example), which might very well be
+ * unique to the machine, but is otherwise unvarying.
+ */
+static int crng_slow_load(const char *cp, size_t len)
+{
+	unsigned long		flags;
+	static unsigned char	lfsr = 1;
+	unsigned char		tmp;
+	unsigned		i, max = CHACHA20_KEY_SIZE;
+	const char *		src_buf = cp;
+	char *			dest_buf = (char *) &primary_crng.state[4];
+
+	if (!spin_trylock_irqsave(&primary_crng.lock, flags))
+		return 0;
+	if (crng_init != 0) {
+		spin_unlock_irqrestore(&primary_crng.lock, flags);
+		return 0;
+	}
+	if (len > max)
+		max = len;
+
+	for (i = 0; i < max ; i++) {
+		tmp = lfsr;
+		lfsr >>= 1;
+		if (tmp & 1)
+			lfsr ^= 0xE1;
+		tmp = dest_buf[i % CHACHA20_KEY_SIZE];
+		dest_buf[i % CHACHA20_KEY_SIZE] ^= src_buf[i % len] ^ lfsr;
+		lfsr += (tmp << 3) | (tmp >> 5);
+	}
+	spin_unlock_irqrestore(&primary_crng.lock, flags);
+	return 1;
+}
+
 static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
 {
 	unsigned long	flags;
@@ -981,10 +1030,8 @@ void add_device_randomness(const void *buf, unsigned int size)
 	unsigned long time = random_get_entropy() ^ jiffies;
 	unsigned long flags;
 
-	if (!crng_ready()) {
-		crng_fast_load(buf, size);
-		return;
-	}
+	if (!crng_ready())
+		crng_slow_load(buf, size);
 
 	trace_add_device_randomness(size, _RET_IP_);
 	spin_lock_irqsave(&input_pool.lock, flags);
-- 
2.16.1.72.g5be1f00a9a

[PATCH 3/5] random: set up the NUMA crng instances after the CRNG is fully initialized

[Theodore Ts'o]

Until the primary_crng is fully initialized, don't initialize the NUMA
crng nodes.  Otherwise users of /dev/urandom on NUMA systems before
the CRNG is fully initialized can get very bad quality randomness.  Of
course everyone should move to getrandom(2) where this won't be an
issue, but there's a lot of legacy code out there.

Reported-by: Jann Horn <jannh@google.com>
Fixes: 1e7f583af67b ("random: make /dev/urandom scalable for silly...")
Cc: stable@kernel.org # 4.8+
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
---
 drivers/char/random.c | 46 +++++++++++++++++++++++++++-------------------
 1 file changed, 27 insertions(+), 19 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 2154a5fe4c81..681ee0c0de24 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -787,6 +787,32 @@ static void crng_initialize(struct crng_state *crng)
 	crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1;
 }
 
+#ifdef CONFIG_NUMA
+static void numa_crng_init(void)
+{
+	int i;
+	struct crng_state *crng;
+	struct crng_state **pool;
+
+	pool = kcalloc(nr_node_ids, sizeof(*pool), GFP_KERNEL|__GFP_NOFAIL);
+	for_each_online_node(i) {
+		crng = kmalloc_node(sizeof(struct crng_state),
+				    GFP_KERNEL | __GFP_NOFAIL, i);
+		spin_lock_init(&crng->lock);
+		crng_initialize(crng);
+		pool[i] = crng;
+	}
+	mb();
+	if (cmpxchg(&crng_node_pool, NULL, pool)) {
+		for_each_node(i)
+			kfree(pool[i]);
+		kfree(pool);
+	}
+}
+#else
+static int numa_crng_init(void) {}
+#endif
+
 /*
  * crng_fast_load() can be called by code in the interrupt service
  * path.  So we can't afford to dilly-dally.
@@ -893,6 +919,7 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
 	spin_unlock_irqrestore(&primary_crng.lock, flags);
 	if (crng == &primary_crng && crng_init < 2) {
 		invalidate_batched_entropy();
+		numa_crng_init();
 		crng_init = 2;
 		process_random_ready_list();
 		wake_up_interruptible(&crng_init_wait);
@@ -1727,28 +1754,9 @@ static void init_std_data(struct entropy_store *r)
  */
 static int rand_initialize(void)
 {
-#ifdef CONFIG_NUMA
-	int i;
-	struct crng_state *crng;
-	struct crng_state **pool;
-#endif
-
 	init_std_data(&input_pool);
 	init_std_data(&blocking_pool);
 	crng_initialize(&primary_crng);
-
-#ifdef CONFIG_NUMA
-	pool = kcalloc(nr_node_ids, sizeof(*pool), GFP_KERNEL|__GFP_NOFAIL);
-	for_each_online_node(i) {
-		crng = kmalloc_node(sizeof(struct crng_state),
-				    GFP_KERNEL | __GFP_NOFAIL, i);
-		spin_lock_init(&crng->lock);
-		crng_initialize(crng);
-		pool[i] = crng;
-	}
-	mb();
-	crng_node_pool = pool;
-#endif
 	return 0;
 }
 early_initcall(rand_initialize);
-- 
2.16.1.72.g5be1f00a9a

Re: [PATCH 3/5] random: set up the NUMA crng instances after the CRNG is fully initialized

[kbuild test robot]

[-- Attachment #1: Type: text/plain, Size: 1741 bytes --]

Hi Theodore,

I love your patch! Perhaps something to improve:

[auto build test WARNING on char-misc/char-misc-testing]
[also build test WARNING on v4.16 next-20180413]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system]

url:    https://github.com/0day-ci/linux/commits/Theodore-Ts-o/random-fix-crng_ready-test/20180414-055120
config: i386-randconfig-x014-201814 (attached as .config)
compiler: gcc-7 (Debian 7.3.0-1) 7.3.0
reproduce:
        # save the attached .config to linux build tree
        make ARCH=i386 

All warnings (new ones prefixed by >>):

   drivers/char/random.c: In function 'numa_crng_init':
>> drivers/char/random.c:813:1: warning: no return statement in function returning non-void [-Wreturn-type]
    static int numa_crng_init(void) {}
    ^~~~~~

vim +813 drivers/char/random.c

   789	
   790	#ifdef CONFIG_NUMA
   791	static void numa_crng_init(void)
   792	{
   793		int i;
   794		struct crng_state *crng;
   795		struct crng_state **pool;
   796	
   797		pool = kcalloc(nr_node_ids, sizeof(*pool), GFP_KERNEL|__GFP_NOFAIL);
   798		for_each_online_node(i) {
   799			crng = kmalloc_node(sizeof(struct crng_state),
   800					    GFP_KERNEL | __GFP_NOFAIL, i);
   801			spin_lock_init(&crng->lock);
   802			crng_initialize(crng);
   803			pool[i] = crng;
   804		}
   805		mb();
   806		if (cmpxchg(&crng_node_pool, NULL, pool)) {
   807			for_each_node(i)
   808				kfree(pool[i]);
   809			kfree(pool);
   810		}
   811	}
   812	#else
 > 813	static int numa_crng_init(void) {}
   814	#endif
   815	

---
0-DAY kernel test infrastructure                Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all                   Intel Corporation

[-- Attachment #2: .config.gz --]
[-- Type: application/gzip, Size: 27319 bytes --]

[PATCH 4/5] random: crng_reseed() should lock the crng instance that it is modifying

[Theodore Ts'o]

Reported-by: Jann Horn <jannh@google.com>
Fixes: 1e7f583af67b ("random: make /dev/urandom scalable for silly...")
Cc: stable@kernel.org # 4.8+
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
Reviewed-by: Jann Horn <jannh@google.com>
---
 drivers/char/random.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 681ee0c0de24..6e7fa13b1a89 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -906,7 +906,7 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
 		_crng_backtrack_protect(&primary_crng, buf.block,
 					CHACHA20_KEY_SIZE);
 	}
-	spin_lock_irqsave(&primary_crng.lock, flags);
+	spin_lock_irqsave(&crng->lock, flags);
 	for (i = 0; i < 8; i++) {
 		unsigned long	rv;
 		if (!arch_get_random_seed_long(&rv) &&
@@ -916,7 +916,7 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
 	}
 	memzero_explicit(&buf, sizeof(buf));
 	crng->init_time = jiffies;
-	spin_unlock_irqrestore(&primary_crng.lock, flags);
+	spin_unlock_irqrestore(&crng->lock, flags);
 	if (crng == &primary_crng && crng_init < 2) {
 		invalidate_batched_entropy();
 		numa_crng_init();
-- 
2.16.1.72.g5be1f00a9a

[PATCH 5/5] random: add new ioctl RNDRESEEDCRNG

[Theodore Ts'o]

Add a new ioctl which forces the the crng to be reseeded.

Signed-off-by: Theodore Ts'o <tytso@mit.edu>
Cc: stable@kernel.org
---
 drivers/char/random.c       | 13 ++++++++++++-
 include/uapi/linux/random.h |  3 +++
 2 files changed, 15 insertions(+), 1 deletion(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 6e7fa13b1a89..c552431587a7 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -429,6 +429,7 @@ struct crng_state primary_crng = {
 static int crng_init = 0;
 #define crng_ready() (likely(crng_init > 1))
 static int crng_init_cnt = 0;
+static unsigned long crng_global_init_time = 0;
 #define CRNG_INIT_CNT_THRESH (2*CHACHA20_KEY_SIZE)
 static void _extract_crng(struct crng_state *crng,
 			  __u32 out[CHACHA20_BLOCK_WORDS]);
@@ -933,7 +934,8 @@ static void _extract_crng(struct crng_state *crng,
 	unsigned long v, flags;
 
 	if (crng_ready() &&
-	    time_after(jiffies, crng->init_time + CRNG_RESEED_INTERVAL))
+	    (time_after(crng_global_init_time, crng->init_time) ||
+	     time_after(jiffies, crng->init_time + CRNG_RESEED_INTERVAL)))
 		crng_reseed(crng, crng == &primary_crng ? &input_pool : NULL);
 	spin_lock_irqsave(&crng->lock, flags);
 	if (arch_get_random_long(&v))
@@ -1757,6 +1759,7 @@ static int rand_initialize(void)
 	init_std_data(&input_pool);
 	init_std_data(&blocking_pool);
 	crng_initialize(&primary_crng);
+	crng_global_init_time = jiffies;
 	return 0;
 }
 early_initcall(rand_initialize);
@@ -1930,6 +1933,14 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
 		input_pool.entropy_count = 0;
 		blocking_pool.entropy_count = 0;
 		return 0;
+	case RNDRESEEDCRNG:
+		if (!capable(CAP_SYS_ADMIN))
+			return -EPERM;
+		if (crng_init < 2)
+			return -ENODATA;
+		crng_reseed(&primary_crng, NULL);
+		crng_global_init_time = jiffies - 1;
+		return 0;
 	default:
 		return -EINVAL;
 	}
diff --git a/include/uapi/linux/random.h b/include/uapi/linux/random.h
index c34f4490d025..26ee91300e3e 100644
--- a/include/uapi/linux/random.h
+++ b/include/uapi/linux/random.h
@@ -35,6 +35,9 @@
 /* Clear the entropy pool and associated counters.  (Superuser only.) */
 #define RNDCLEARPOOL	_IO( 'R', 0x06 )
 
+/* Reseed CRNG.  (Superuser only.) */
+#define RNDRESEEDCRNG	_IO( 'R', 0x07 )
+
 struct rand_pool_info {
 	int	entropy_count;
 	int	buf_size;
-- 
2.16.1.72.g5be1f00a9a

Re: [PATCH 1/5] random: fix crng_ready() test

[Stephan Mueller]

Am Freitag, 13. April 2018, 03:30:42 CEST schrieb Theodore Ts'o:

Hi Theodore,

> The crng_init variable has three states:
> 
> 0: The CRNG is not initialized at all
> 1: The CRNG has a small amount of entropy, hopefully good enough for
>    early-boot, non-cryptographical use cases
> 2: The CRNG is fully initialized and we are sure it is safe for
>    cryptographic use cases.
> 
> The crng_ready() function should only return true once we are in the
> last state.
> 
Do I see that correctly that getrandom(2) will now unblock after the 
input_pool has obtained 128 bits of entropy? Similarly for 
get_random_bytes_wait.

As this seems to be the only real use case for crng_ready (apart from 
logging), what is the purpose of crng_init == 1?

Ciao
Stephan

Re: [PATCH 1/5] random: fix crng_ready() test

[Theodore Y. Ts'o]

On Fri, Apr 13, 2018 at 07:38:30AM +0200, Stephan Mueller wrote:
> > The crng_init variable has three states:
> > 
> > 0: The CRNG is not initialized at all
> > 1: The CRNG has a small amount of entropy, hopefully good enough for
> >    early-boot, non-cryptographical use cases
> > 2: The CRNG is fully initialized and we are sure it is safe for
> >    cryptographic use cases.
> > 
> > The crng_ready() function should only return true once we are in the
> > last state.
> > 
> Do I see that correctly that getrandom(2) will now unblock after the 
> input_pool has obtained 128 bits of entropy? Similarly for 
> get_random_bytes_wait.

Correct.

> As this seems to be the only real use case for crng_ready (apart from 
> logging), what is the purpose of crng_init == 1?

Immediately after boot (crng_init state 0), we funnel the harvested
entropy from add_interrupt_entropy() directly to the CRNG pool.  The
goal is to get at least some amount of entropy into the CRNG is it's
not blatently predictable.  When we have accomplished this, by mixing
in 2 * CHACHA20_KEY_SIZE bytes of input from add_input_randomness, we
enter state crng_init state 1.

In crng_init state 1, we start funnelling the harvested entropy to the
input_pool.  Once we have accumulated 128 bits of entropy in the input
pool, we then reseed the CRNG from the input_pool, and we consider the
CRNG to be fully intialized.

During crng_init state 1, the CRNG is basically in a "good enough for
government work" state.  It's going to get used by things like initial
TCP sequence numbers, and UUID's by udev, et. al, but I wouldn't want
to use it for anything that has strong cryptographic use cases.

It would be preferable if nothing in the kernel and early systemd
startup used get_random_bytes() or /dev/urandom or getrandom(2) w/
GRND_NONBLOCK.  Unfortunately, (a) there is a lot of legacy code which
still uses /dev/urandom and not getrandom(2) and (b) in some cases,
such as initialization of the Stack Canary, the kernel simply can't
wait for the CRNG to be fully initialized.  Or if the kernel needs
enough of the networking stack to mount an NFS root file system, for
example.

This was always the original design intent, but I screwed up and no
one noticed until Jann reached out to be and said, "Hey.... this
doesn't seem to make much sense".

Regards,

					- Ted

Re: [PATCH 1/5] random: fix crng_ready() test

[Stephan Mueller]

Am Freitag, 13. April 2018, 14:53:13 CEST schrieb Theodore Y. Ts'o:

Hi Theodore,
> 
> This was always the original design intent, but I screwed up and no
> one noticed until Jann reached out to be and said, "Hey.... this
> doesn't seem to make much sense".

I disagree, but I guess you would have expected that. But this is not the 
issue.

What I would like to point out that more and more folks change to 
getrandom(2). As this call will now unblock much later in the boot cycle, 
these systems see a significant departure from the current system behavior.

E.g. an sshd using getrandom(2) would be ready shortly after the boot finishes 
as of now. Now it can be a matter minutes before it responds. Thus, is such 
change in the kernel behavior something for stable?

Ciao
Stephan

Re: [PATCH 1/5] random: fix crng_ready() test

[Theodore Y. Ts'o]

On Fri, Apr 13, 2018 at 03:05:01PM +0200, Stephan Mueller wrote:
> 
> What I would like to point out that more and more folks change to 
> getrandom(2). As this call will now unblock much later in the boot cycle, 
> these systems see a significant departure from the current system behavior.
> 
> E.g. an sshd using getrandom(2) would be ready shortly after the boot finishes 
> as of now. Now it can be a matter minutes before it responds. Thus, is such 
> change in the kernel behavior something for stable?

It will have some change on the kernel behavior, but not as much as
you might think.  That's because in older kernels, we were *already*
blocking until crng_init > 2 --- if the getrandom(2) call happened
while crng_init was in state 0.

Even before this patch series, we didn't wake up a process blocked on
crng_init_wait until crng_init state 2 is reached:

static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
{
	...
	if (crng == &primary_crng && crng_init < 2) {
		invalidate_batched_entropy();
		crng_init = 2;
		process_random_ready_list();
		wake_up_interruptible(&crng_init_wait);
		pr_notice("random: crng init done\n");
	}
}

This is the reason why there are reports like this: "Boot delayed for
about 90 seconds until 'random: crng init done'"[1]

[1] https://bugs.launchpad.net/ubuntu/+source/linux/+bug/1685794


So we have the problem already.  There will be more cases of this
after this patch series is applied, true.  But what we have already is
an inconsistent state where if you call getrandom(2) while the kernel
is in crng_init state 0, you will block until crng_init state 2, but
if you are in crng_init state 1, you will assume the CRNG is fully
initialized.

Given the documentation of how getrandom(2) works what its documented
guarantees are, I think it does justify making its behavior both more
consistent with itself, and more consistent what the security
guarantees we have promised people.

I was a little worried that on VM's this could end up causing things
to block for a long time, but an experiment on a GCE VM shows that
isn't a problem:

[    0.000000] Linux version 4.16.0-rc3-ext4-00009-gf6b302ebca85 (tytso@cwcc) (gcc version 7.3.0 (Debian 7.3.0-15)) #16 SMP Thu Apr 12 16:57:17 EDT 2018
[    1.282220] random: fast init done
[    3.987092] random: crng init done
[    4.376787] EXT4-fs (sda1): re-mounted. Opts: (null)

There are some desktops where the "crng_init done" report doesn't
happen until 45-90 seconds into the boot.  I don't think I've seen
reports where it takes _minutes_ however.  Can you give me some
examples of such cases?

					- Ted

P.S.  Of course, in a VM environment, if the host supports virtio-rng,
the boot delay problem is completely not an issue.  You just have to
enable virtio-rng in the guest kernel, which I believe is already the
case for most distro kernels.

BTW, for KVM, it's fairly simple to set it the host-side support for
virtio-rng.  Just add to the kvm command-line options:

    -object rng-random,filename=/dev/urandom,id=rng0 \
	-device virtio-rng-pci,rng=rng0

Re: [PATCH 1/5] random: fix crng_ready() test

[Srivatsa S. Bhat]

On 4/13/18 10:00 AM, Theodore Y. Ts'o wrote:
> On Fri, Apr 13, 2018 at 03:05:01PM +0200, Stephan Mueller wrote:
>>
>> What I would like to point out that more and more folks change to 
>> getrandom(2). As this call will now unblock much later in the boot cycle, 
>> these systems see a significant departure from the current system behavior.
>>
>> E.g. an sshd using getrandom(2) would be ready shortly after the boot finishes 
>> as of now. Now it can be a matter minutes before it responds. Thus, is such 
>> change in the kernel behavior something for stable?

[...]

> I was a little worried that on VM's this could end up causing things
> to block for a long time, but an experiment on a GCE VM shows that
> isn't a problem:
> 
> [    0.000000] Linux version 4.16.0-rc3-ext4-00009-gf6b302ebca85 (tytso@cwcc) (gcc version 7.3.0 (Debian 7.3.0-15)) #16 SMP Thu Apr 12 16:57:17 EDT 2018
> [    1.282220] random: fast init done
> [    3.987092] random: crng init done
> [    4.376787] EXT4-fs (sda1): re-mounted. Opts: (null)
> 
> There are some desktops where the "crng_init done" report doesn't
> happen until 45-90 seconds into the boot.  I don't think I've seen
> reports where it takes _minutes_ however.  Can you give me some
> examples of such cases?

On a Photon OS VM running on VMware ESXi, this patch causes a boot speed
regression of 5 minutes :-( [ The VM doesn't have haveged or rng-tools
(rngd) installed. ]

[    1.420246] EXT4-fs (sda2): re-mounted. Opts: barrier,noacl,data=ordered
[    1.469722] tsc: Refined TSC clocksource calibration: 1900.002 MHz
[    1.470707] clocksource: tsc: mask: 0xffffffffffffffff max_cycles: 0x36c65c1a9e1, max_idle_ns: 881590695311 ns
[    1.474249] clocksource: Switched to clocksource tsc
[    1.584427] systemd-journald[216]: Received request to flush runtime journal from PID 1
[  346.620718] random: crng init done

Interestingly, the boot delay is exacerbated on VMs with large amounts
of RAM. For example, the delay is not so noticeable (< 30 seconds) on a
VM with 2GB memory, but goes up to 5 minutes on an 8GB VM.

Also, cloud-init-local.service seems to be the one blocking for entropy
here. systemd-analyze critical-chain shows:

The time after the unit is active or started is printed after the "@" character.
The time the unit takes to start is printed after the "+" character.

multi-user.target @6min 1.283s
└─vmtoolsd.service @6min 1.282s
  └─cloud-final.service @6min 366ms +914ms
    └─cloud-config.service @5min 59.174s +1.190s
      └─cloud-config.target @5min 59.172s
        └─cloud-init.service @5min 47.423s +11.744s
          └─systemd-networkd-wait-online.service @5min 45.999s +1.420s
            └─systemd-networkd.service @5min 45.975s +21ms
              └─network-pre.target @5min 45.973s
                └─cloud-init-local.service @241ms +5min 45.687s
                  └─systemd-remount-fs.service @222ms +13ms
                    └─systemd-fsck-root.service @193ms +26ms
                      └─systemd-journald.socket @188ms
                        └─-.mount @151ms
                          └─system.slice @161ms
                            └─-.slice @151ms

It would be great if this CVE can be fixed somehow without causing boot speed
to spike from ~20 seconds to 5 minutes, as that makes the system pretty much
unusable. I can workaround this by installing haveged, but ideally an in-kernel
fix would be better. If you need any other info about my setup or if you have
a patch that I can test, please let me know!

Thank you very much!

Regards,
Srivatsa
VMware Photon OS

Re: [PATCH 1/5] random: fix crng_ready() test

[Theodore Y. Ts'o]

On Wed, May 16, 2018 at 05:07:08PM -0700, Srivatsa S. Bhat wrote:
> 
> On a Photon OS VM running on VMware ESXi, this patch causes a boot speed
> regression of 5 minutes :-( [ The VM doesn't have haveged or rng-tools
> (rngd) installed. ]
> 
> [    1.420246] EXT4-fs (sda2): re-mounted. Opts: barrier,noacl,data=ordered
> [    1.469722] tsc: Refined TSC clocksource calibration: 1900.002 MHz
> [    1.470707] clocksource: tsc: mask: 0xffffffffffffffff max_cycles: 0x36c65c1a9e1, max_idle_ns: 881590695311 ns
> [    1.474249] clocksource: Switched to clocksource tsc
> [    1.584427] systemd-journald[216]: Received request to flush runtime journal from PID 1
> [  346.620718] random: crng init done
> 
> Interestingly, the boot delay is exacerbated on VMs with large amounts
> of RAM. For example, the delay is not so noticeable (< 30 seconds) on a
> VM with 2GB memory, but goes up to 5 minutes on an 8GB VM.
> 
> Also, cloud-init-local.service seems to be the one blocking for entropy
> here.

So the first thing I'd ask you to investigate is what the heck
cloud-init-local.service is doing, and why it really needs
cryptographic grade random numbers?

> It would be great if this CVE can be fixed somehow without causing boot speed
> to spuike from ~20 seconds to 5 minutes, as that makes the system pretty much
> unusable. I can workaround this by installing haveged, but ideally an in-kernel
> fix would be better. If you need any other info about my setup or if you have
> a patch that I can test, please let me know!

So the question is why is strong random numbers needed by
cloud-init-local, and how much do you trust either haveged and/or
RDRAND (which is what you will be depending upon if you install
rng-tools).  If you believe that Intel and/or the NSA hasn't
backdoored RDRAND[1], or you believe that because Intel processor's
internal cache architecture isn't publically documented, and it's
Soooooooo complicated that no one can figure it out (which is what you
will be depending upon if you if you choose haveged), be my guest.  I
personally consider the latter to be "security via obscu7rity", but
others have different opinions.

[1] As an aside, read the best paper from the 37th IEEE Symposium on
Security and Privacy and weep:

https://www.computerworld.com/article/3079417/security/researchers-built-devious-undetectable-hardware-level-backdoor-in-computer-chips.html

If it turns out that the security if your VM is critically dependent
on what cloud-init-local.service is doing, and you don't like making
those assumptions, then you may need to ask VMWare ESXi to make
virtio-rng available to guest OS's, and then make Photon OS depend on
a secure RNG available to the host OS.

Best regards,

						- Ted

Re: [PATCH 1/5] random: fix crng_ready() test

[Christophe LEROY]

Le 13/04/2018 à 19:00, Theodore Y. Ts'o a écrit :
> On Fri, Apr 13, 2018 at 03:05:01PM +0200, Stephan Mueller wrote:
>>
>> What I would like to point out that more and more folks change to
>> getrandom(2). As this call will now unblock much later in the boot cycle,
>> these systems see a significant departure from the current system behavior.
>>
>> E.g. an sshd using getrandom(2) would be ready shortly after the boot finishes
>> as of now. Now it can be a matter minutes before it responds. Thus, is such
>> change in the kernel behavior something for stable?
> 
> It will have some change on the kernel behavior, but not as much as
> you might think.  That's because in older kernels, we were *already*
> blocking until crng_init > 2 --- if the getrandom(2) call happened
> while crng_init was in state 0.
> 
> Even before this patch series, we didn't wake up a process blocked on
> crng_init_wait until crng_init state 2 is reached:
> 
> static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
> {
> 	...
> 	if (crng == &primary_crng && crng_init < 2) {
> 		invalidate_batched_entropy();
> 		crng_init = 2;
> 		process_random_ready_list();
> 		wake_up_interruptible(&crng_init_wait);
> 		pr_notice("random: crng init done\n");
> 	}
> }
> 
> This is the reason why there are reports like this: "Boot delayed for
> about 90 seconds until 'random: crng init done'"[1]
> 
> [1] https://bugs.launchpad.net/ubuntu/+source/linux/+bug/1685794
> 
> 
> So we have the problem already.  There will be more cases of this
> after this patch series is applied, true.  But what we have already is
> an inconsistent state where if you call getrandom(2) while the kernel
> is in crng_init state 0, you will block until crng_init state 2, but
> if you are in crng_init state 1, you will assume the CRNG is fully
> initialized.
> 
> Given the documentation of how getrandom(2) works what its documented
> guarantees are, I think it does justify making its behavior both more
> consistent with itself, and more consistent what the security
> guarantees we have promised people.
> 
> I was a little worried that on VM's this could end up causing things
> to block for a long time, but an experiment on a GCE VM shows that
> isn't a problem:
> 
> [    0.000000] Linux version 4.16.0-rc3-ext4-00009-gf6b302ebca85 (tytso@cwcc) (gcc version 7.3.0 (Debian 7.3.0-15)) #16 SMP Thu Apr 12 16:57:17 EDT 2018
> [    1.282220] random: fast init done
> [    3.987092] random: crng init done
> [    4.376787] EXT4-fs (sda1): re-mounted. Opts: (null)
> 
> There are some desktops where the "crng_init done" report doesn't
> happen until 45-90 seconds into the boot.  I don't think I've seen
> reports where it takes _minutes_ however.  Can you give me some
> examples of such cases?


On a powerpc embedded board which has an mpc8xx processor running at 
133Mhz, I now get the startup done in more than 7 minutes instead of 30 
seconds. This is due to the webserver blocking on read on /dev/random 
until we get 'random: crng init done':

[    0.000000] Linux version 4.17.0-rc4-00415-gd2f75d40072d 
(root@localhost) (gcc version 5.4.0 (GCC)) #203 PREEMPT Wed May 16 
16:32:02 CEST 2018
[    0.295453] random: get_random_u32 called from 
bucket_table_alloc+0x84/0x1bc with crng_init=0
[    1.030472] device: 'random': device_add
[    1.031279] device: 'urandom': device_add
[    1.420069] device: 'hw_random': device_add
[    2.156853] random: fast init done
[  462.007776] random: crng init done

This has become really critical, is there anything that can be done ?

Christophe

> 
> 					- Ted
> 
> P.S.  Of course, in a VM environment, if the host supports virtio-rng,
> the boot delay problem is completely not an issue.  You just have to
> enable virtio-rng in the guest kernel, which I believe is already the
> case for most distro kernels.
> 
> BTW, for KVM, it's fairly simple to set it the host-side support for
> virtio-rng.  Just add to the kvm command-line options:
> 
>      -object rng-random,filename=/dev/urandom,id=rng0 \
> 	-device virtio-rng-pci,rng=rng0
> 

Re: [PATCH 1/5] random: fix crng_ready() test

[Theodore Y. Ts'o]

On Thu, May 17, 2018 at 08:01:04AM +0200, Christophe LEROY wrote:
> 
> On a powerpc embedded board which has an mpc8xx processor running at 133Mhz,
> I now get the startup done in more than 7 minutes instead of 30 seconds.
> This is due to the webserver blocking on read on /dev/random until we get
> 'random: crng init done':
> 
> [    0.000000] Linux version 4.17.0-rc4-00415-gd2f75d40072d (root@localhost)
> (gcc version 5.4.0 (GCC)) #203 PREEMPT Wed May 16 16:32:02 CEST 2018
> [    0.295453] random: get_random_u32 called from
> bucket_table_alloc+0x84/0x1bc with crng_init=0
> [    1.030472] device: 'random': device_add
> [    1.031279] device: 'urandom': device_add
> [    1.420069] device: 'hw_random': device_add
> [    2.156853] random: fast init done
> [  462.007776] random: crng init done
> 
> This has become really critical, is there anything that can be done ?

Figure out why the webserver needs to read /dev/random and is it for a
security critical purpose?

A kernel patch which makes the kernel do a "lalalalala I'm secure"
when it really isn't secure is a simple "solution", but would it
really make you happy?


						- Ted

Re: [PATCH 1/5] random: fix crng_ready() test

[Geert Uytterhoeven]

Hi Ted,

On Fri, Apr 13, 2018 at 3:30 AM, Theodore Ts'o <tytso@mit.edu> wrote:
> The crng_init variable has three states:
>
> 0: The CRNG is not initialized at all
> 1: The CRNG has a small amount of entropy, hopefully good enough for
>    early-boot, non-cryptographical use cases
> 2: The CRNG is fully initialized and we are sure it is safe for
>    cryptographic use cases.
>
> The crng_ready() function should only return true once we are in the
> last state.
>
> Reported-by: Jann Horn <jannh@google.com>
> Fixes: e192be9d9a30 ("random: replace non-blocking pool...")
> Cc: stable@kernel.org # 4.8+
> Signed-off-by: Theodore Ts'o <tytso@mit.edu>
> Reviewed-by: Jann Horn <jannh@google.com>

Since commit 43838a23a05fbd13 ("random: fix crng_ready() test"),
all (few) remaining users of %p are printing too early, leading to "(ptrval)"
strings instead of actual hashed pointer values.

Sample timings on two platforms (arm / arm64) booting with lots of
debug ingo:

[   28.521158] random: crng init done
[   17.792705] random: crng init done

Gr{oetje,eeting}s,

                        Geert

-- 
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds