[PATCH v6] random: fix crash on multiple early calls to add_bootloader_randomness()

[PATCH v6] random: fix crash on multiple early calls to add_bootloader_randomness()

[Dominik Brodowski]

Currently, if CONFIG_RANDOM_TRUST_BOOTLOADER is enabled, multiple calls
to add_bootloader_randomness() are broken and can cause a NULL pointer
dereference, as noted by Ivan T. Ivanov. This is not only a hypothetical
problem, as qemu on arm64 may provide bootloader entropy via EFI and via
devicetree.

On the first call to add_hwgenerator_randomness(), crng_fast_load() is
executed, and if the seed is long enough, crng_init will be set to 1.
On subsequent calls to add_bootloader_randomness() and then to
add_hwgenerator_randomness(), crng_fast_load() will be skipped. Instead,
wait_event_interruptible() and then credit_entropy_bits() will be called.
If the entropy count for that second seed is large enough, that proceeds
to crng_reseed().

However, both wait_event_interruptible() and crng_reseed() depends
(at least in numa_crng_init()) on workqueues. Therefore, test whether
system_wq is already initialized, which is a sufficient indicator that
workqueue_init_early() has progressed far enough.

Reported-by: Ivan T. Ivanov <iivanov@suse.de>
Fixes: 18b915ac6b0a ("efi/random: Treat EFI_RNG_PROTOCOL output as bootloader randomness")
Cc: stable@vger.kernel.org
Signed-off-by: Dominik Brodowski <linux@dominikbrodowski.net>

---

 drivers/char/random.c |    8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

---

This is now a truly minimalist approach which tests for system_wq != NULL,
as suggested by Jason.

Another issue remains, though, but should be addressed separately: If one
trusts the randnomness provided by the bootloader, and if the primary_crng
is then seeded with 512 bits of entropy, warnings will still be emited that
unseeded randomness is used with crng_init=1.


diff --git a/drivers/char/random.c b/drivers/char/random.c
index 13c968b950c5..3c44f5ff6cc4 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -993,7 +993,10 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
 	memzero_explicit(&buf, sizeof(buf));
 	WRITE_ONCE(crng->init_time, jiffies);
 	spin_unlock_irqrestore(&crng->lock, flags);
-	if (crng == &primary_crng && crng_init < 2) {
+	/* Only finalize initialization if workqueues are ready; otherwise
+	 * numa_crng_init() and other things may go wrong.
+	 */
+	if (crng == &primary_crng && crng_init < 2 && system_wq) {
 		invalidate_batched_entropy();
 		numa_crng_init();
 		crng_init = 2;
@@ -2299,7 +2302,8 @@ void add_hwgenerator_randomness(const char *buffer, size_t count,
 	 * We'll be woken up again once below random_write_wakeup_thresh,
 	 * or when the calling thread is about to terminate.
 	 */
-	wait_event_interruptible(random_write_wait, kthread_should_stop() ||
+	wait_event_interruptible(random_write_wait,
+			!system_wq || kthread_should_stop() ||
 			ENTROPY_BITS(&input_pool) <= random_write_wakeup_bits);
 	mix_pool_bytes(poolp, buffer, count);
 	credit_entropy_bits(poolp, entropy);

Re: [PATCH v6] random: fix crash on multiple early calls to add_bootloader_randomness()

[Jason A. Donenfeld]

Hi Dominik,

Thanks. I like where this is going. It seems like we can tackle this
problem and the other one separately like this as you've done. It'd be
helpful though if you could send the patches for all the problems in
one patchset so that I'm not left wondering, "hey what about this
other thing; did you forget it?" Since these issues are kind of
intermingled, it'd be nice to see how the puzzle pieces fit together.

One question about this patch:
- If crng_reseed is called early, before system_wq is non-NULL, that
block will be skipped. When will it be called again?
- There's no call to it in crng_initialize_primary/rand_initialize
when not trusting the CPU and such, and that block there isn't quite
the same as crng_reseed either.

Also, something I noticed when looking at this, which I'm not sure has
come up yet in the various problems identified:
- If crng_reseed is called early, but not too early, and that block is
called, we'll set crng_init=2 and do various things and print, "crng
init done\n".
- Later, when rand_initialize is called, if we're trusting the CPU and
such, we'll re-initialize it and print, "crng done (trusting CPU's
manufacturer)\n".
That seems like a problem, though I assume we haven't hit that yet
because the race window is pretty small, so we've mostly been crashing
on a NULL system_wq instead, or having crng_reseed called _after_
crng_initialize_primary/rand_initialize anyway.

Thanks a lot for working on this. If you get tired of this back and
forth, by the way, and want me to start proposing patches for you to
look at instead, we can trade off. I'm also happy to keep looking at
what you send; it's just that as we're already on v6 here, I'm hoping
you won't get too frustrated.

Jason

[PATCH v7 1/4] random: fix crash on multiple early calls to add_bootloader_randomness()

[Jason A. Donenfeld]

From: Dominik Brodowski <linux@dominikbrodowski.net>

Currently, if CONFIG_RANDOM_TRUST_BOOTLOADER is enabled, multiple calls
to add_bootloader_randomness() are broken and can cause a NULL pointer
dereference, as noted by Ivan T. Ivanov. This is not only a hypothetical
problem, as qemu on arm64 may provide bootloader entropy via EFI and via
devicetree.

On the first call to add_hwgenerator_randomness(), crng_fast_load() is
executed, and if the seed is long enough, crng_init will be set to 1.
On subsequent calls to add_bootloader_randomness() and then to
add_hwgenerator_randomness(), crng_fast_load() will be skipped. Instead,
wait_event_interruptible() and then credit_entropy_bits() will be called.
If the entropy count for that second seed is large enough, that proceeds
to crng_reseed().

However, both wait_event_interruptible() and crng_reseed() depends
(at least in numa_crng_init()) on workqueues. Therefore, test whether
system_wq is already initialized, which is a sufficient indicator that
workqueue_init_early() has progressed far enough.

If we wind up hitting the !system_wq case, we later want to do what
would have been done there when wqs are up, so set a flag, and do that
work later from the rand_initialize() call.

Reported-by: Ivan T. Ivanov <iivanov@suse.de>
Fixes: 18b915ac6b0a ("efi/random: Treat EFI_RNG_PROTOCOL output as bootloader randomness")
Cc: stable@vger.kernel.org
Signed-off-by: Dominik Brodowski <linux@dominikbrodowski.net>
[Jason: added crng_need_done state and related logic.]
Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
---
 drivers/char/random.c | 56 +++++++++++++++++++++++++++----------------
 1 file changed, 36 insertions(+), 20 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 82db125aaed7..b003e266a499 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -468,6 +468,7 @@ static struct crng_state primary_crng = {
  * its value (from 0->1->2).
  */
 static int crng_init = 0;
+static bool crng_need_done = false;
 #define crng_ready() (likely(crng_init > 1))
 static int crng_init_cnt = 0;
 static unsigned long crng_global_init_time = 0;
@@ -835,6 +836,36 @@ static void __init crng_initialize_primary(struct crng_state *crng)
 	crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1;
 }
 
+static void crng_init_done(struct crng_state *crng)
+{
+	if (crng != &primary_crng || crng_init >= 2)
+		return;
+	if (!system_wq) {
+		/* We can't call numa_crng_init until we have workqueues,
+		 * so mark this for processing later. */
+		crng_need_done = true;
+		return;
+	}
+
+	invalidate_batched_entropy();
+	numa_crng_init();
+	crng_init = 2;
+	process_random_ready_list();
+	wake_up_interruptible(&crng_init_wait);
+	kill_fasync(&fasync, SIGIO, POLL_IN);
+	pr_notice("crng init done\n");
+	if (unseeded_warning.missed) {
+		pr_notice("%d get_random_xx warning(s) missed due to ratelimiting\n",
+			  unseeded_warning.missed);
+		unseeded_warning.missed = 0;
+	}
+	if (urandom_warning.missed) {
+		pr_notice("%d urandom warning(s) missed due to ratelimiting\n",
+			  urandom_warning.missed);
+		urandom_warning.missed = 0;
+	}
+}
+
 #ifdef CONFIG_NUMA
 static void do_numa_crng_init(struct work_struct *work)
 {
@@ -989,25 +1020,7 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
 	memzero_explicit(&buf, sizeof(buf));
 	WRITE_ONCE(crng->init_time, jiffies);
 	spin_unlock_irqrestore(&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);
-		kill_fasync(&fasync, SIGIO, POLL_IN);
-		pr_notice("crng init done\n");
-		if (unseeded_warning.missed) {
-			pr_notice("%d get_random_xx warning(s) missed due to ratelimiting\n",
-				  unseeded_warning.missed);
-			unseeded_warning.missed = 0;
-		}
-		if (urandom_warning.missed) {
-			pr_notice("%d urandom warning(s) missed due to ratelimiting\n",
-				  urandom_warning.missed);
-			urandom_warning.missed = 0;
-		}
-	}
+	crng_init_done(crng);
 }
 
 static void _extract_crng(struct crng_state *crng,
@@ -1780,6 +1793,8 @@ static void __init init_std_data(struct entropy_store *r)
 int __init rand_initialize(void)
 {
 	init_std_data(&input_pool);
+	if (crng_need_done)
+		crng_init_done(&primary_crng);
 	crng_initialize_primary(&primary_crng);
 	crng_global_init_time = jiffies;
 	if (ratelimit_disable) {
@@ -2288,7 +2303,8 @@ void add_hwgenerator_randomness(const char *buffer, size_t count,
 	 * We'll be woken up again once below random_write_wakeup_thresh,
 	 * or when the calling thread is about to terminate.
 	 */
-	wait_event_interruptible(random_write_wait, kthread_should_stop() ||
+	wait_event_interruptible(random_write_wait,
+			!system_wq || kthread_should_stop() ||
 			ENTROPY_BITS(&input_pool) <= random_write_wakeup_bits);
 	mix_pool_bytes(poolp, buffer, count);
 	credit_entropy_bits(poolp, entropy);
-- 
2.34.1

[PATCH v7 2/4] random: do not re-init if crng_reseed completes before primary init

[Jason A. Donenfeld]

If the bootloader supplies sufficient material and crng_reseed() is called
very early on, but not too early that wqs aren't available yet, then we
might transition to crng_init==2 before rand_initialize()'s call to
crng_initialize_primary() made. Then, when crng_initialize_primary() is
called, if we're trusting the CPU's RDRAND instructions, we'll
needlessly reinitialize the RNG and emit a message about it. This is
mostly harmless, as numa_crng_init() will allocate and then free what it
just allocated, and excessive calls to invalidate_batched_entropy()
aren't so harmful. But it is funky and the extra message is confusing,
so avoid the re-initialization all together by checking for crng_init <
2 in crng_initialize_primary(), just as we already do in crng_reseed().

Cc: Dominik Brodowski <linux@dominikbrodowski.net>
Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
---
 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 b003e266a499..95aac486177e 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -827,7 +827,7 @@ static void __init crng_initialize_primary(struct crng_state *crng)
 {
 	chacha_init_consts(crng->state);
 	_extract_entropy(&input_pool, &crng->state[4], sizeof(__u32) * 12, 0);
-	if (crng_init_try_arch_early(crng) && trust_cpu) {
+	if (crng_init_try_arch_early(crng) && trust_cpu && crng_init < 2) {
 		invalidate_batched_entropy();
 		numa_crng_init();
 		crng_init = 2;
-- 
2.34.1

[PATCH v7 3/4] random: do not throw away excess input to crng_fast_load

[Jason A. Donenfeld]

When crng_fast_load() is called by add_hwgenerator_randomness(), we
currently will advance to crng_init==1 if we've acquired 64 bytes, and
then throw away the rest of the buffer. This is a problem if irq
randomness creates one call to crng_fast_load(), and then
add_hwgenerator_randomness() gets called via EFI with 64 bytes. In that
case, we'll advance to crng_init==1, but won't continue onward feeding
in bytes to progress to crng_init==2. This commit fixes the issue by
feeding leftover bytes into the next phase in
add_hwgenerator_randomness().

Cc: Dominik Brodowski <linux@dominikbrodowski.net>
Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
---
 drivers/char/random.c | 19 ++++++++++++-------
 1 file changed, 12 insertions(+), 7 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 95aac486177e..020443e34603 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -919,12 +919,14 @@ static struct crng_state *select_crng(void)
 
 /*
  * crng_fast_load() can be called by code in the interrupt service
- * path.  So we can't afford to dilly-dally.
+ * path.  So we can't afford to dilly-dally. Returns the number of
+ * bytes processed from cp.
  */
-static int crng_fast_load(const char *cp, size_t len)
+static size_t crng_fast_load(const char *cp, size_t len)
 {
 	unsigned long flags;
 	char *p;
+	size_t ret = 0;
 
 	if (!spin_trylock_irqsave(&primary_crng.lock, flags))
 		return 0;
@@ -935,7 +937,7 @@ static int crng_fast_load(const char *cp, size_t len)
 	p = (unsigned char *) &primary_crng.state[4];
 	while (len > 0 && crng_init_cnt < CRNG_INIT_CNT_THRESH) {
 		p[crng_init_cnt % CHACHA_KEY_SIZE] ^= *cp;
-		cp++; crng_init_cnt++; len--;
+		cp++; crng_init_cnt++; len--; ret++;
 	}
 	spin_unlock_irqrestore(&primary_crng.lock, flags);
 	if (crng_init_cnt >= CRNG_INIT_CNT_THRESH) {
@@ -943,7 +945,7 @@ static int crng_fast_load(const char *cp, size_t len)
 		crng_init = 1;
 		pr_notice("fast init done\n");
 	}
-	return 1;
+	return ret;
 }
 
 /*
@@ -1294,7 +1296,7 @@ void add_interrupt_randomness(int irq)
 	if (unlikely(crng_init == 0)) {
 		if ((fast_pool->count >= 64) &&
 		    crng_fast_load((char *) fast_pool->pool,
-				   sizeof(fast_pool->pool))) {
+				   sizeof(fast_pool->pool)) > 0) {
 			fast_pool->count = 0;
 			fast_pool->last = now;
 		}
@@ -2295,8 +2297,11 @@ void add_hwgenerator_randomness(const char *buffer, size_t count,
 	struct entropy_store *poolp = &input_pool;
 
 	if (unlikely(crng_init == 0)) {
-		crng_fast_load(buffer, count);
-		return;
+		size_t ret = crng_fast_load(buffer, count);
+		count -= ret;
+		buffer += ret;
+		if (!count || crng_init == 0)
+			return;
 	}
 
 	/* Suspend writing if we're above the trickle threshold.
-- 
2.34.1

[PATCH v7 4/4] random: mix bootloader randomness into pool

[Jason A. Donenfeld]

If we're trusting bootloader randomness, crng_fast_load() is called by
add_hwgenerator_randomness(), which sets us to crng_init==1. However, if
it's not called after that initial 64-byte push, it won't additionally
mix any bytes into the entropy pool. So it's conceivable that
crng_init==1 when later crng_initialize_primary() is called, but the
entropy pool is empty. When that happens, the crng state key will then
be overwritten with extracted output from the empty input pool. That's
bad.

In contrast, if we're not trusting bootloader randomness, we call
crng_slow_load() *and* we call mix_pool_bytes(), so that later
crng_initialize_primary() isn't drawing on nothing.

In order to prevent crng_initialize_primary() from extracting an empty
pool, have the trusted bootloader case mirror that of the untrusted
bootloader case, mixing the input into the pool.

Cc: Dominik Brodowski <linux@dominikbrodowski.net>
Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
---
 drivers/char/random.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 020443e34603..3499f6762ac1 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -2298,6 +2298,7 @@ void add_hwgenerator_randomness(const char *buffer, size_t count,
 
 	if (unlikely(crng_init == 0)) {
 		size_t ret = crng_fast_load(buffer, count);
+		mix_pool_bytes(poolp, buffer, ret);
 		count -= ret;
 		buffer += ret;
 		if (!count || crng_init == 0)
-- 
2.34.1

[PATCH v8 1/7] random: fix crash on multiple early calls to add_bootloader_randomness()

[Dominik Brodowski]

Currently, if CONFIG_RANDOM_TRUST_BOOTLOADER is enabled, multiple calls
to add_bootloader_randomness() are broken and can cause a NULL pointer
dereference, as noted by Ivan T. Ivanov. This is not only a hypothetical
problem, as qemu on arm64 may provide bootloader entropy via EFI and via
devicetree.

On the first call to add_hwgenerator_randomness(), crng_fast_load() is
executed, and if the seed is long enough, crng_init will be set to 1.
On subsequent calls to add_bootloader_randomness() and then to
add_hwgenerator_randomness(), crng_fast_load() will be skipped. Instead,
wait_event_interruptible() and then credit_entropy_bits() will be called.
If the entropy count for that second seed is large enough, that proceeds
to crng_reseed().

However, both wait_event_interruptible() and crng_reseed() depends
(at least in numa_crng_init()) on workqueues. Therefore, test whether
system_wq is already initialized, which is a sufficient indicator that
workqueue_init_early() has progressed far enough.

If we wind up hitting the !system_wq case, we later want to do what
would have been done there when wqs are up, so set a flag, and do that
work later from the rand_initialize() call.

Reported-by: Ivan T. Ivanov <iivanov@suse.de>
Fixes: 18b915ac6b0a ("efi/random: Treat EFI_RNG_PROTOCOL output as bootloader randomness")
Cc: stable@vger.kernel.org
Signed-off-by: Dominik Brodowski <linux@dominikbrodowski.net>
[Jason: added crng_need_done state and related logic.]
Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
---
 drivers/char/random.c | 56 +++++++++++++++++++++++++++----------------
 1 file changed, 36 insertions(+), 20 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 82db125aaed7..144e8841bff4 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -468,6 +468,7 @@ static struct crng_state primary_crng = {
  * its value (from 0->1->2).
  */
 static int crng_init = 0;
+static bool crng_need_final_init = false;
 #define crng_ready() (likely(crng_init > 1))
 static int crng_init_cnt = 0;
 static unsigned long crng_global_init_time = 0;
@@ -835,6 +836,36 @@ static void __init crng_initialize_primary(struct crng_state *crng)
 	crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1;
 }
 
+static void crng_finalize_init(struct crng_state *crng)
+{
+	if (crng != &primary_crng || crng_init >= 2)
+		return;
+	if (!system_wq) {
+		/* We can't call numa_crng_init until we have workqueues,
+		 * so mark this for processing later. */
+		crng_need_final_init = true;
+		return;
+	}
+
+	invalidate_batched_entropy();
+	numa_crng_init();
+	crng_init = 2;
+	process_random_ready_list();
+	wake_up_interruptible(&crng_init_wait);
+	kill_fasync(&fasync, SIGIO, POLL_IN);
+	pr_notice("crng init done\n");
+	if (unseeded_warning.missed) {
+		pr_notice("%d get_random_xx warning(s) missed due to ratelimiting\n",
+			  unseeded_warning.missed);
+		unseeded_warning.missed = 0;
+	}
+	if (urandom_warning.missed) {
+		pr_notice("%d urandom warning(s) missed due to ratelimiting\n",
+			  urandom_warning.missed);
+		urandom_warning.missed = 0;
+	}
+}
+
 #ifdef CONFIG_NUMA
 static void do_numa_crng_init(struct work_struct *work)
 {
@@ -989,25 +1020,7 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
 	memzero_explicit(&buf, sizeof(buf));
 	WRITE_ONCE(crng->init_time, jiffies);
 	spin_unlock_irqrestore(&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);
-		kill_fasync(&fasync, SIGIO, POLL_IN);
-		pr_notice("crng init done\n");
-		if (unseeded_warning.missed) {
-			pr_notice("%d get_random_xx warning(s) missed due to ratelimiting\n",
-				  unseeded_warning.missed);
-			unseeded_warning.missed = 0;
-		}
-		if (urandom_warning.missed) {
-			pr_notice("%d urandom warning(s) missed due to ratelimiting\n",
-				  urandom_warning.missed);
-			urandom_warning.missed = 0;
-		}
-	}
+	crng_finalize_init(crng);
 }
 
 static void _extract_crng(struct crng_state *crng,
@@ -1780,6 +1793,8 @@ static void __init init_std_data(struct entropy_store *r)
 int __init rand_initialize(void)
 {
 	init_std_data(&input_pool);
+	if (crng_need_final_init)
+		crng_finalize_init(&primary_crng);
 	crng_initialize_primary(&primary_crng);
 	crng_global_init_time = jiffies;
 	if (ratelimit_disable) {
@@ -2288,7 +2303,8 @@ void add_hwgenerator_randomness(const char *buffer, size_t count,
 	 * We'll be woken up again once below random_write_wakeup_thresh,
 	 * or when the calling thread is about to terminate.
 	 */
-	wait_event_interruptible(random_write_wait, kthread_should_stop() ||
+	wait_event_interruptible(random_write_wait,
+			!system_wq || kthread_should_stop() ||
 			ENTROPY_BITS(&input_pool) <= random_write_wakeup_bits);
 	mix_pool_bytes(poolp, buffer, count);
 	credit_entropy_bits(poolp, entropy);
-- 
2.34.1

[PATCH v8 2/7] random: do not re-init if crng_reseed completes before primary init

[Dominik Brodowski]

From: "Jason A. Donenfeld" <Jason@zx2c4.com>

If the bootloader supplies sufficient material and crng_reseed() is called
very early on, but not too early that wqs aren't available yet, then we
might transition to crng_init==2 before rand_initialize()'s call to
crng_initialize_primary() made. Then, when crng_initialize_primary() is
called, if we're trusting the CPU's RDRAND instructions, we'll
needlessly reinitialize the RNG and emit a message about it. This is
mostly harmless, as numa_crng_init() will allocate and then free what it
just allocated, and excessive calls to invalidate_batched_entropy()
aren't so harmful. But it is funky and the extra message is confusing,
so avoid the re-initialization all together by checking for crng_init <
2 in crng_initialize_primary(), just as we already do in crng_reseed().

Reviewed-by: Dominik Brodowski <linux@dominikbrodowski.net>
Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
---
 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 144e8841bff4..916cf791ed0e 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -827,7 +827,7 @@ static void __init crng_initialize_primary(struct crng_state *crng)
 {
 	chacha_init_consts(crng->state);
 	_extract_entropy(&input_pool, &crng->state[4], sizeof(__u32) * 12, 0);
-	if (crng_init_try_arch_early(crng) && trust_cpu) {
+	if (crng_init_try_arch_early(crng) && trust_cpu && crng_init < 2) {
 		invalidate_batched_entropy();
 		numa_crng_init();
 		crng_init = 2;
-- 
2.34.1

Re: [PATCH v8 2/7] random: do not re-init if crng_reseed completes before primary init

[Jason A. Donenfeld]

Applied. Thanks for the review.

[PATCH v8 3/7] random: do not throw away excess input to crng_fast_load

[Dominik Brodowski]

From: "Jason A. Donenfeld" <Jason@zx2c4.com>

When crng_fast_load() is called by add_hwgenerator_randomness(), we
currently will advance to crng_init==1 once we've acquired 64 bytes, and
then throw away the rest of the buffer. Usually, that is not a problem:
When add_hwgenerator_randomness() gets called via EFI or DT during
setup_arch(), there won't be any IRQ randomness. Therefore, the 64 bytes
passed by EFI exactly matches what is needed to advance to crng_init==1.
Usually, DT seems to pass 64 bytes as well -- with one notable exception
being kexec, which hands over 128 bytes of entropy to the kexec'd kernel.
In that case, we'll advance to crng_init==1 once 64 of those bytes are
consumed by crng_fast_load(), but won't continue onward feeding in bytes
to progress to crng_init==2. This commit fixes the issue by feeding
any leftover bytes into the next phase in add_hwgenerator_randomness().

Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
[linux@dominikbrodowski.net: rewrite commit message]
Signed-off-by: Dominik Brodowski <linux@dominikbrodowski.net>
---
 drivers/char/random.c | 19 ++++++++++++-------
 1 file changed, 12 insertions(+), 7 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 916cf791ed0e..21166188b7e1 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -919,12 +919,14 @@ static struct crng_state *select_crng(void)
 
 /*
  * crng_fast_load() can be called by code in the interrupt service
- * path.  So we can't afford to dilly-dally.
+ * path.  So we can't afford to dilly-dally. Returns the number of
+ * bytes processed from cp.
  */
-static int crng_fast_load(const char *cp, size_t len)
+static size_t crng_fast_load(const char *cp, size_t len)
 {
 	unsigned long flags;
 	char *p;
+	size_t ret = 0;
 
 	if (!spin_trylock_irqsave(&primary_crng.lock, flags))
 		return 0;
@@ -935,7 +937,7 @@ static int crng_fast_load(const char *cp, size_t len)
 	p = (unsigned char *) &primary_crng.state[4];
 	while (len > 0 && crng_init_cnt < CRNG_INIT_CNT_THRESH) {
 		p[crng_init_cnt % CHACHA_KEY_SIZE] ^= *cp;
-		cp++; crng_init_cnt++; len--;
+		cp++; crng_init_cnt++; len--; ret++;
 	}
 	spin_unlock_irqrestore(&primary_crng.lock, flags);
 	if (crng_init_cnt >= CRNG_INIT_CNT_THRESH) {
@@ -943,7 +945,7 @@ static int crng_fast_load(const char *cp, size_t len)
 		crng_init = 1;
 		pr_notice("fast init done\n");
 	}
-	return 1;
+	return ret;
 }
 
 /*
@@ -1294,7 +1296,7 @@ void add_interrupt_randomness(int irq)
 	if (unlikely(crng_init == 0)) {
 		if ((fast_pool->count >= 64) &&
 		    crng_fast_load((char *) fast_pool->pool,
-				   sizeof(fast_pool->pool))) {
+				   sizeof(fast_pool->pool)) > 0) {
 			fast_pool->count = 0;
 			fast_pool->last = now;
 		}
@@ -2295,8 +2297,11 @@ void add_hwgenerator_randomness(const char *buffer, size_t count,
 	struct entropy_store *poolp = &input_pool;
 
 	if (unlikely(crng_init == 0)) {
-		crng_fast_load(buffer, count);
-		return;
+		size_t ret = crng_fast_load(buffer, count);
+		count -= ret;
+		buffer += ret;
+		if (!count || crng_init == 0)
+			return;
 	}
 
 	/* Suspend writing if we're above the trickle threshold.
-- 
2.34.1

Re: [PATCH v8 3/7] random: do not throw away excess input to crng_fast_load

[Jason A. Donenfeld]

Interesting additional analysis about kexec. Patch applied.

[PATCH v8 4/7] random: mix bootloader randomness into pool

[Dominik Brodowski]

From: "Jason A. Donenfeld" <Jason@zx2c4.com>

If we're trusting bootloader randomness, crng_fast_load() is called by
add_hwgenerator_randomness(), which sets us to crng_init==1. However,
usually it is only called once for an initial 64-byte push, so bootloader
entropy will not mix any bytes into the input pool. So it's conceivable
that crng_init==1 when crng_initialize_primary() is called later, but
then the input pool is empty. When that happens, the crng state key will
be overwritten with extracted output from the empty input pool. That's
bad.

In contrast, if we're not trusting bootloader randomness, we call
crng_slow_load() *and* we call mix_pool_bytes(), so that later
crng_initialize_primary() isn't drawing on nothing.

In order to prevent crng_initialize_primary() from extracting an empty
pool, have the trusted bootloader case mirror that of the untrusted
bootloader case, mixing the input into the pool.

Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
[linux@dominikbrodowski.net: rewrite commit message]
Signed-off-by: Dominik Brodowski <linux@dominikbrodowski.net>
---
 drivers/char/random.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 21166188b7e1..9d4e1907e4b1 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -2298,6 +2298,7 @@ void add_hwgenerator_randomness(const char *buffer, size_t count,
 
 	if (unlikely(crng_init == 0)) {
 		size_t ret = crng_fast_load(buffer, count);
+		mix_pool_bytes(poolp, buffer, ret);
 		count -= ret;
 		buffer += ret;
 		if (!count || crng_init == 0)
-- 
2.34.1

Re: [PATCH v8 4/7] random: mix bootloader randomness into pool

[Jason A. Donenfeld]

Thanks for the commit message rework. Applied.

[PATCH v8 5/7] random: harmonize "crng init done" messages

[Dominik Brodowski]

We print out "crng init done" for !TRUST_CPU, so we should also print
out the same for TRUST_CPU.

Signed-off-by: Dominik Brodowski <linux@dominikbrodowski.net>
---
 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 9d4e1907e4b1..9b5eb6cf82ce 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -831,7 +831,7 @@ static void __init crng_initialize_primary(struct crng_state *crng)
 		invalidate_batched_entropy();
 		numa_crng_init();
 		crng_init = 2;
-		pr_notice("crng done (trusting CPU's manufacturer)\n");
+		pr_notice("crng init done (trusting CPU's manufacturer)\n");
 	}
 	crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1;
 }
-- 
2.34.1

Re: [PATCH v8 5/7] random: harmonize "crng init done" messages

[Jason A. Donenfeld]

Applied, thanks.

[PATCH v8 6/7] random: early initialization of ChaCha constants

[Dominik Brodowski]

Previously, the ChaCha constants for the primary pool were only
initialized once rand_initialize() calls crng_initialize_primary().
However, some randomness is actually extracted from the primary pool
beforehand, e.g. by kmem_cache_create(). Therefore, statically
initialize the ChaCha constants for the primary pool.

In exchange, we can remove the dynamic initialization in
crng_initialize_primary(), as it is only called - as the name suggests -
for the primary pool. Therefore, no parameter to this function is needed.

Signed-off-by: Dominik Brodowski <linux@dominikbrodowski.net>
---
 drivers/char/random.c   | 10 +++++++---
 include/crypto/chacha.h | 15 +++++++++++----
 2 files changed, 18 insertions(+), 7 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 9b5eb6cf82ce..a5bf662578cb 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -457,6 +457,10 @@ struct crng_state {
 
 static struct crng_state primary_crng = {
 	.lock = __SPIN_LOCK_UNLOCKED(primary_crng.lock),
+	.state[0] = CHACHA_CONSTANT_EXPA, /* "expa" */
+	.state[1] = CHACHA_CONSTANT_ND_3, /* "nd 3" */
+	.state[2] = CHACHA_CONSTANT_2_BY, /* "2-by" */
+	.state[3] = CHACHA_CONSTANT_TE_K, /* "te k" */
 };
 
 /*
@@ -823,9 +827,9 @@ static void __maybe_unused crng_initialize_secondary(struct crng_state *crng)
 	crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1;
 }
 
-static void __init crng_initialize_primary(struct crng_state *crng)
+static void __init crng_initialize_primary(void)
 {
-	chacha_init_consts(crng->state);
+	struct crng_state *crng = &primary_crng;
 	_extract_entropy(&input_pool, &crng->state[4], sizeof(__u32) * 12, 0);
 	if (crng_init_try_arch_early(crng) && trust_cpu && crng_init < 2) {
 		invalidate_batched_entropy();
@@ -1797,7 +1801,7 @@ int __init rand_initialize(void)
 	init_std_data(&input_pool);
 	if (crng_need_final_init)
 		crng_finalize_init(&primary_crng);
-	crng_initialize_primary(&primary_crng);
+	crng_initialize_primary();
 	crng_global_init_time = jiffies;
 	if (ratelimit_disable) {
 		urandom_warning.interval = 0;
diff --git a/include/crypto/chacha.h b/include/crypto/chacha.h
index dabaee698718..147e56fc755e 100644
--- a/include/crypto/chacha.h
+++ b/include/crypto/chacha.h
@@ -47,12 +47,19 @@ static inline void hchacha_block(const u32 *state, u32 *out, int nrounds)
 		hchacha_block_generic(state, out, nrounds);
 }
 
+enum chacha_constants { /* expand 32-byte k */
+	CHACHA_CONSTANT_EXPA = 0x61707865U,
+	CHACHA_CONSTANT_ND_3 = 0x3320646eU,
+	CHACHA_CONSTANT_2_BY = 0x79622d32U,
+	CHACHA_CONSTANT_TE_K = 0x6b206574U
+};
+
 static inline void chacha_init_consts(u32 *state)
 {
-	state[0]  = 0x61707865; /* "expa" */
-	state[1]  = 0x3320646e; /* "nd 3" */
-	state[2]  = 0x79622d32; /* "2-by" */
-	state[3]  = 0x6b206574; /* "te k" */
+	state[0]  = CHACHA_CONSTANT_EXPA; /* "expa" */
+	state[1]  = CHACHA_CONSTANT_ND_3; /* "nd 3" */
+	state[2]  = CHACHA_CONSTANT_2_BY; /* "2-by" */
+	state[3]  = CHACHA_CONSTANT_TE_K; /* "te k" */
 }
 
 void chacha_init_arch(u32 *state, const u32 *key, const u8 *iv);
-- 
2.34.1

Re: [PATCH v8 6/7] random: early initialization of ChaCha constants

[Jason A. Donenfeld]

Thanks for the patch. Comments are inline below.

On Wed, Dec 29, 2021 at 10:13 PM Dominik Brodowski
<linux@dominikbrodowski.net> wrote:
>  drivers/char/random.c   | 10 +++++++---
>  include/crypto/chacha.h | 15 +++++++++++----

For the next submission of this (which you can do standalone and call
a v2), please Cc linux-crypto and Herbert as part of the commit body.
I still intend to take this through the random tree, since that's the
purpose of it, but because it touches the lib/crypto code, they should
be in the loop.

>  static struct crng_state primary_crng = {
>         .lock = __SPIN_LOCK_UNLOCKED(primary_crng.lock),
> +       .state[0] = CHACHA_CONSTANT_EXPA, /* "expa" */
> +       .state[1] = CHACHA_CONSTANT_ND_3, /* "nd 3" */
> +       .state[2] = CHACHA_CONSTANT_2_BY, /* "2-by" */
> +       .state[3] = CHACHA_CONSTANT_TE_K, /* "te k" */
>  };

I don't think you need the comments here, since the constant is
already descriptive.

>
>  /*
> @@ -823,9 +827,9 @@ static void __maybe_unused crng_initialize_secondary(struct crng_state *crng)
>         crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1;
>  }
>
> -static void __init crng_initialize_primary(struct crng_state *crng)
> +static void __init crng_initialize_primary(void)
>  {
> +       struct crng_state *crng = &primary_crng;
> -       crng_initialize_primary(&primary_crng);
> +       crng_initialize_primary();

There are a bunch of places where we're passing around globals when we
could collapse them down. It probably makes sense to do that in a
separate cleanup series (please feel free!), rather than here, since
the init-time constants issue doesn't really change anything with
regards to this function signature.

>  static inline void chacha_init_consts(u32 *state)
>  {
> -       state[0]  = 0x61707865; /* "expa" */
> -       state[1]  = 0x3320646e; /* "nd 3" */
> -       state[2]  = 0x79622d32; /* "2-by" */
> -       state[3]  = 0x6b206574; /* "te k" */
> +       state[0]  = CHACHA_CONSTANT_EXPA; /* "expa" */
> +       state[1]  = CHACHA_CONSTANT_ND_3; /* "nd 3" */
> +       state[2]  = CHACHA_CONSTANT_2_BY; /* "2-by" */
> +       state[3]  = CHACHA_CONSTANT_TE_K; /* "te k" */
>  }

I don't think you need the comments here, since the constant is
already descriptive.

[PATCH v8 7/7] random: move crng_initialize_secondary to CONFIG_NUMA section

[Dominik Brodowski]

By moving crng_initialize_secondary() a few lines lower to the
CONFIG_NUMA ifdef section, we can remove the __maybe_unused parameter.

Suggested-by: Jason A. Donenfeld <Jason@zx2c4.com>
Signed-off-by: Dominik Brodowski <linux@dominikbrodowski.net>
---
 drivers/char/random.c | 16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index a5bf662578cb..64949c43f588 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -819,14 +819,6 @@ static bool __init crng_init_try_arch_early(struct crng_state *crng)
 	return arch_init;
 }
 
-static void __maybe_unused crng_initialize_secondary(struct crng_state *crng)
-{
-	chacha_init_consts(crng->state);
-	_get_random_bytes(&crng->state[4], sizeof(__u32) * 12);
-	crng_init_try_arch(crng);
-	crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1;
-}
-
 static void __init crng_initialize_primary(void)
 {
 	struct crng_state *crng = &primary_crng;
@@ -871,6 +863,14 @@ static void crng_finalize_init(struct crng_state *crng)
 }
 
 #ifdef CONFIG_NUMA
+static void crng_initialize_secondary(struct crng_state *crng)
+{
+	chacha_init_consts(crng->state);
+	_get_random_bytes(&crng->state[4], sizeof(__u32) * 12);
+	crng_init_try_arch(crng);
+	crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1;
+}
+
 static void do_numa_crng_init(struct work_struct *work)
 {
 	int i;
-- 
2.34.1

[PATCH v8.1 7/7] random: move NUMA-related code to CONFIG_NUMA section

[Dominik Brodowski]

By moving crng_initialize_secondary() and crng_init_try_arch() a few
lines lower to the CONFIG_NUMA ifdef section, we can remove the
__maybe_unused attribute from the first function, and reduce the
footprint for !CONFIG_NUMA.

Suggested-by: Jason A. Donenfeld <Jason@zx2c4.com>
Signed-off-by: Dominik Brodowski <linux@dominikbrodowski.net>
---
 drivers/char/random.c |   52 +++++++++++++++++++++++++-------------------------
 1 file changed, 26 insertions(+), 26 deletions(-)

v8->v8.1:
crng_init_try_arch() isn't used elsewhere, therefore it needed to be
moved to CONFIG_NUMA as well.

diff --git a/drivers/char/random.c b/drivers/char/random.c
index a5bf662578cb..181b61104948 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -783,24 +783,6 @@ static int __init parse_trust_cpu(char *arg)
 }
 early_param("random.trust_cpu", parse_trust_cpu);
 
-static bool crng_init_try_arch(struct crng_state *crng)
-{
-	int		i;
-	bool		arch_init = true;
-	unsigned long	rv;
-
-	for (i = 4; i < 16; i++) {
-		if (!arch_get_random_seed_long(&rv) &&
-		    !arch_get_random_long(&rv)) {
-			rv = random_get_entropy();
-			arch_init = false;
-		}
-		crng->state[i] ^= rv;
-	}
-
-	return arch_init;
-}
-
 static bool __init crng_init_try_arch_early(struct crng_state *crng)
 {
 	int		i;
@@ -819,14 +801,6 @@ static bool __init crng_init_try_arch_early(struct crng_state *crng)
 	return arch_init;
 }
 
-static void __maybe_unused crng_initialize_secondary(struct crng_state *crng)
-{
-	chacha_init_consts(crng->state);
-	_get_random_bytes(&crng->state[4], sizeof(__u32) * 12);
-	crng_init_try_arch(crng);
-	crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1;
-}
-
 static void __init crng_initialize_primary(void)
 {
 	struct crng_state *crng = &primary_crng;
@@ -871,6 +845,32 @@ static void crng_finalize_init(struct crng_state *crng)
 }
 
 #ifdef CONFIG_NUMA
+static bool crng_init_try_arch(struct crng_state *crng)
+{
+	int		i;
+	bool		arch_init = true;
+	unsigned long	rv;
+
+	for (i = 4; i < 16; i++) {
+		if (!arch_get_random_seed_long(&rv) &&
+		    !arch_get_random_long(&rv)) {
+			rv = random_get_entropy();
+			arch_init = false;
+		}
+		crng->state[i] ^= rv;
+	}
+
+	return arch_init;
+}
+
+static void crng_initialize_secondary(struct crng_state *crng)
+{
+	chacha_init_consts(crng->state);
+	_get_random_bytes(&crng->state[4], sizeof(__u32) * 12);
+	crng_init_try_arch(crng);
+	crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1;
+}
+
 static void do_numa_crng_init(struct work_struct *work)
 {
 	int i;

Re: [PATCH v8.1 7/7] random: move NUMA-related code to CONFIG_NUMA section

[Jason A. Donenfeld]

Rather than the fallout of this v8->v8.1 resulting in functions
needing to move around, I think it might actually be cleaner to do an
IS_ENABLED thing. I'll send a patch to this thread and you can tell me
what you think of that instead.

Jason

[PATCH] random: use IS_ENABLED(CONFIG_NUMA) instead of ifdefs

[Jason A. Donenfeld]

Rather than an awkward combination of ifdefs and __maybe_unused, we can
ensure more source gets parsed, regardless of the configuration, by
using IS_ENABLED for the CONFIG_NUMA conditional code. This makes things
cleaner and easier to follow.

I've confirmed that on !CONFIG_NUMA, we don't wind up with excess code
by accident; the generated object file is the same.

Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
---
 drivers/char/random.c | 30 +++++++++++-------------------
 1 file changed, 11 insertions(+), 19 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 9b5eb6cf82ce..54086e9da05b 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -759,7 +759,6 @@ static int credit_entropy_bits_safe(struct entropy_store *r, int nbits)
 
 static DECLARE_WAIT_QUEUE_HEAD(crng_init_wait);
 
-#ifdef CONFIG_NUMA
 /*
  * Hack to deal with crazy userspace progams when they are all trying
  * to access /dev/urandom in parallel.  The programs are almost
@@ -767,7 +766,6 @@ static DECLARE_WAIT_QUEUE_HEAD(crng_init_wait);
  * their brain damage.
  */
 static struct crng_state **crng_node_pool __read_mostly;
-#endif
 
 static void invalidate_batched_entropy(void);
 static void numa_crng_init(void);
@@ -815,7 +813,7 @@ static bool __init crng_init_try_arch_early(struct crng_state *crng)
 	return arch_init;
 }
 
-static void __maybe_unused crng_initialize_secondary(struct crng_state *crng)
+static void crng_initialize_secondary(struct crng_state *crng)
 {
 	chacha_init_consts(crng->state);
 	_get_random_bytes(&crng->state[4], sizeof(__u32) * 12);
@@ -866,7 +864,6 @@ static void crng_finalize_init(struct crng_state *crng)
 	}
 }
 
-#ifdef CONFIG_NUMA
 static void do_numa_crng_init(struct work_struct *work)
 {
 	int i;
@@ -893,29 +890,24 @@ static DECLARE_WORK(numa_crng_init_work, do_numa_crng_init);
 
 static void numa_crng_init(void)
 {
-	schedule_work(&numa_crng_init_work);
+	if (IS_ENABLED(CONFIG_NUMA))
+		schedule_work(&numa_crng_init_work);
 }
 
 static struct crng_state *select_crng(void)
 {
-	struct crng_state **pool;
-	int nid = numa_node_id();
-
-	/* pairs with cmpxchg_release() in do_numa_crng_init() */
-	pool = READ_ONCE(crng_node_pool);
-	if (pool && pool[nid])
-		return pool[nid];
+	if (IS_ENABLED(CONFIG_NUMA)) {
+		struct crng_state **pool;
+		int nid = numa_node_id();
 
-	return &primary_crng;
-}
-#else
-static void numa_crng_init(void) {}
+		/* pairs with cmpxchg_release() in do_numa_crng_init() */
+		pool = READ_ONCE(crng_node_pool);
+		if (pool && pool[nid])
+			return pool[nid];
+	}
 
-static struct crng_state *select_crng(void)
-{
 	return &primary_crng;
 }
-#endif
 
 /*
  * crng_fast_load() can be called by code in the interrupt service
-- 
2.34.1

Re: [PATCH] random: use IS_ENABLED(CONFIG_NUMA) instead of ifdefs

[Dominik Brodowski]

Am Thu, Dec 30, 2021 at 04:14:10PM +0100 schrieb Jason A. Donenfeld:
> Rather than an awkward combination of ifdefs and __maybe_unused, we can
> ensure more source gets parsed, regardless of the configuration, by
> using IS_ENABLED for the CONFIG_NUMA conditional code. This makes things
> cleaner and easier to follow.
> 
> I've confirmed that on !CONFIG_NUMA, we don't wind up with excess code
> by accident; the generated object file is the same.
> 
> Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>

Reviewed-by: Dominik Brodowski <linux@dominikbrodowski.net>

Thanks,
	Dominik

Re: [PATCH v8 1/7] random: fix crash on multiple early calls to add_bootloader_randomness()

[Jason A. Donenfeld]

Applied, thanks.