random: fix crash on multiple early calls to add_bootloader_randomness()

PATCH Superseded Dominik Brodowski 2 participants 23 messages Dec 23, 2021 – Dec 31, 2021

Subsystems (4)

Stable branch Crypto API EFI Random number driver

lore

Share & tools

lore

Dominik Brodowski

author

2021-12-23 19:05 UTC #0 lore raw

PATCH v6 1/1 random: fix crash on multiple early calls to add_bootloader_randomness()

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 <[email protected]>

Fixes 18b915ac6b0a ("efi/random: Treat EFI_RNG_PROTOCOL output as bootloader randomness")

Cc [email protected]

Signed-off-by Dominik Brodowski <[email protected]>

---

 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.

drivers/char/random.c +6 -2

index 13c968b950c5..3c44f5ff6cc4 100644
@@ -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);

Jason A. Donenfeld

maintainer

2021-12-28 14:06 UTC #1 lore raw

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

Jason A. Donenfeld

maintainer

2021-12-28 15:39 UTC #2 lore raw

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

From: Dominik Brodowski <[email protected]>

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 <[email protected]>

Fixes 18b915ac6b0a ("efi/random: Treat EFI_RNG_PROTOCOL output as bootloader randomness")

Cc [email protected]

Signed-off-by Dominik Brodowski <[email protected]>

[Jason: added crng_need_done state and related logic.]

Signed-off-by Jason A. Donenfeld <[email protected]>

---
 drivers/char/random.c | 56 +++++++++++++++++++++++++++----------------
 1 file changed, 36 insertions(+), 20 deletions(-)

drivers/char/random.c +36 ~~-20~~

index 82db125aaed7..b003e266a499 100644
@@ -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);

Signature · 1 line

2.34.1

Jason A. Donenfeld

maintainer

2021-12-28 15:39 UTC #3 lore raw

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

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 <[email protected]>

Signed-off-by Jason A. Donenfeld <[email protected]>

---
 drivers/char/random.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

drivers/char/random.c +1 -1

index b003e266a499..95aac486177e 100644
@@ -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;

Signature · 1 line

2.34.1

Jason A. Donenfeld

maintainer

2021-12-28 15:39 UTC #4 lore raw

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

In reply to 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 <[email protected]>

Signed-off-by Jason A. Donenfeld <[email protected]>

---
 drivers/char/random.c | 19 ++++++++++++-------
 1 file changed, 12 insertions(+), 7 deletions(-)

drivers/char/random.c +12 -7

index 95aac486177e..020443e34603 100644
@@ -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.

Signature · 1 line

2.34.1

Jason A. Donenfeld

maintainer

2021-12-28 15:39 UTC #5 lore raw

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

In reply to 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 <[email protected]>

Signed-off-by Jason A. Donenfeld <[email protected]>

---
 drivers/char/random.c | 1 +
 1 file changed, 1 insertion(+)

drivers/char/random.c +1 -0

index 020443e34603..3499f6762ac1 100644
@@ -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)

Signature · 1 line

2.34.1

Dominik Brodowski

author

2021-12-29 21:13 UTC #6 lore raw

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

In reply to Jason A. Donenfeld

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 <[email protected]>

Fixes 18b915ac6b0a ("efi/random: Treat EFI_RNG_PROTOCOL output as bootloader randomness")

Cc [email protected]

Signed-off-by Dominik Brodowski <[email protected]>

[Jason: added crng_need_done state and related logic.]

Signed-off-by Jason A. Donenfeld <[email protected]>

---
 drivers/char/random.c | 56 +++++++++++++++++++++++++++----------------
 1 file changed, 36 insertions(+), 20 deletions(-)

drivers/char/random.c +36 ~~-20~~

index 82db125aaed7..144e8841bff4 100644
@@ -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);

Signature · 1 line

2.34.1

Dominik Brodowski

author

2021-12-29 21:13 UTC #7 lore raw

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

From: "Jason A. Donenfeld" <[email protected]>

Reviewed-by Dominik Brodowski <[email protected]>

Signed-off-by Jason A. Donenfeld <[email protected]>

---
 drivers/char/random.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

drivers/char/random.c +1 -1

index 144e8841bff4..916cf791ed0e 100644
@@ -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;

Signature · 1 line

2.34.1

Jason A. Donenfeld

maintainer Applied

2021-12-30 14:32 UTC #8 lore raw

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

Applied. Thanks for the review.

Dominik Brodowski

author

2021-12-29 21:13 UTC #9 lore raw

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

In reply to Dominik Brodowski

From: "Jason A. Donenfeld" <[email protected]>

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 <[email protected]>

[[email protected]: rewrite commit message]

Signed-off-by Dominik Brodowski <[email protected]>

---
 drivers/char/random.c | 19 ++++++++++++-------
 1 file changed, 12 insertions(+), 7 deletions(-)

drivers/char/random.c +12 -7

index 916cf791ed0e..21166188b7e1 100644
@@ -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.

Signature · 1 line

2.34.1

Jason A. Donenfeld

maintainer

2021-12-30 14:33 UTC #10 lore raw

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

Interesting additional analysis about kexec. Patch applied.

Dominik Brodowski

author

2021-12-29 21:13 UTC #11 lore raw

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

In reply to Dominik Brodowski

From: "Jason A. Donenfeld" <[email protected]>

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 <[email protected]>

[[email protected]: rewrite commit message]

Signed-off-by Dominik Brodowski <[email protected]>

---
 drivers/char/random.c | 1 +
 1 file changed, 1 insertion(+)

drivers/char/random.c +1 -0

index 21166188b7e1..9d4e1907e4b1 100644
@@ -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)

Signature · 1 line

2.34.1

Jason A. Donenfeld

maintainer

2021-12-30 14:34 UTC #12 lore raw

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

Thanks for the commit message rework. Applied.

Dominik Brodowski

author

2021-12-29 21:13 UTC #13 lore raw

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

In reply to 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 <[email protected]>

---
 drivers/char/random.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

drivers/char/random.c +1 -1

index 9d4e1907e4b1..9b5eb6cf82ce 100644
@@ -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;
 }

Signature · 1 line

2.34.1

Jason A. Donenfeld

maintainer Applied

2021-12-30 14:34 UTC #14 lore raw

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

Applied, thanks.

Dominik Brodowski

author

2021-12-29 21:13 UTC #15 lore raw

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

In reply to 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 <[email protected]>

---
 drivers/char/random.c   | 10 +++++++---
 include/crypto/chacha.h | 15 +++++++++++----
 2 files changed, 18 insertions(+), 7 deletions(-)

drivers/char/random.c +7 -3

index 9b5eb6cf82ce..a5bf662578cb 100644
@@ -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;

include/crypto/chacha.h +11 -4

index dabaee698718..147e56fc755e 100644
@@ -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);

Signature · 1 line

2.34.1

Jason A. Donenfeld

maintainer

2021-12-30 14:40 UTC #16 lore raw

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

Thanks for the patch. Comments are inline below.

Quoted 2 lines · Dominik Brodowski

 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.

drivers/char/random.c struct crng_state { · line 464

Quoted 7 lines

static struct crng_state primary_crng = {
.lock = __SPIN_LOCK_UNLOCKED(primary_crng.lock),
drivers/char/random.c +4 -0
+       .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.

drivers/char/random.c static void __maybe_unused crng_initialize_secondary(struct crng_state *crng) · line 833

Quoted 12 lines

drivers/char/random.c +3 -2

@@ -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.

include/crypto/chacha.h static inline void hchacha_block(const u32 *state, u32 *out, int nrounds) · line 63

Quoted 11 lines

include/crypto/chacha.h +4 -4

 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.

Dominik Brodowski

author

2021-12-29 21:13 UTC #17 lore raw

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

In reply to Dominik Brodowski

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

Signed-off-by Dominik Brodowski <[email protected]>

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

drivers/char/random.c +8 -8

index a5bf662578cb..64949c43f588 100644
@@ -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;

Signature · 1 line

2.34.1

Dominik Brodowski

author

2021-12-30 08:59 UTC #18 lore raw

PATCH 7/7 random: move NUMA-related code to CONFIG_NUMA section

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.

Signed-off-by Dominik Brodowski <[email protected]>

---
 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.

drivers/char/random.c +26 ~~-26~~

index a5bf662578cb..181b61104948 100644
@@ -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;

Jason A. Donenfeld

maintainer

2021-12-30 15:12 UTC #19 lore raw

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

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

Jason A. Donenfeld

maintainer

2021-12-30 15:14 UTC #20 lore raw

PATCH 1/1 random: use IS_ENABLED(CONFIG_NUMA) instead of ifdefs

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 <[email protected]>

---
 drivers/char/random.c | 30 +++++++++++-------------------
 1 file changed, 11 insertions(+), 19 deletions(-)

drivers/char/random.c +11 ~~-19~~

index 9b5eb6cf82ce..54086e9da05b 100644
@@ -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

Signature · 1 line

2.34.1

Dominik Brodowski

author Reviewed-by on v1 1/1

2021-12-31 08:35 UTC #21 lore raw

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

Am Thu, Dec 30, 2021 at 04:14:10PM +0100 schrieb Jason A. Donenfeld:

Quoted 9 lines

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 <[email protected]>

Reviewed-by Dominik Brodowski <[email protected]>

Thanks,
Dominik

Jason A. Donenfeld

maintainer Applied

2021-12-30 14:31 UTC #22 lore raw

In reply to Dominik Brodowski

Applied, thanks.