diff mbox series

[v2,3/4] random: use linear min-entropy accumulation crediting

Message ID 20220204135325.8327-4-Jason@zx2c4.com (mailing list archive)
State Not Applicable
Delegated to: Herbert Xu
Headers show
Series random: use computational hash for entropy extraction, and related fixes | expand

Commit Message

Jason A. Donenfeld Feb. 4, 2022, 1:53 p.m. UTC 
30e37ec516ae ("random: account for entropy loss due to overwrites")
assumed that adding new entropy to the LFSR pool probabilistically
cancelled out old entropy there, so entropy was credited asymptotically,
approximating Shannon entropy of independent sources (rather than a
stronger min-entropy notion) using 1/8th fractional bits and replacing
a constant 2-2/√

Comments

Eric Biggers Feb. 5, 2022, 7 a.m. UTC | #1 
On Fri, Feb 04, 2022 at 02:53:24PM +0100, Jason A. Donenfeld wrote:
> What if we're wrong and the above is nonsense? It's not, but let's
> assume we don't want the actual _behavior_ of the code to change much.
> Currently that behavior is not extracting from the input pool until it
> has 128 bits of entropy in it. With the old algorithm, we'd hit that
> magic 128 number after roughly 256 calls to credit_entropy_bits(1). So,
> we can retain more or less the old behavior by waiting to extract from
> the input pool until it hits 256 bits of entropy using the new code. For
> people concerned about this change, it means that there's not that much
> practical behavioral change. And for folks actually trying to model
> the behavior rigorously, it means that we have an even higher margin
> against attacks.

I tested this, and it actually was 205 calls prior to patch 1 in this series,
and 267 calls after patch 1.  That's in contrast to 256 calls after this patch.
Not a big difference, but this is going to result in ~25% more single-bit calls
being needed compared to the old version.  It's unclear whether you're arguing
that's basically the same, or whether you thought it was a smaller difference.

> +enum {
>  	POOL_BITS = BLAKE2S_HASH_SIZE * 8,
> -	POOL_BITSHIFT = ilog2(POOL_BITS),
> -	POOL_MIN_BITS = POOL_BITS / 2,
> -
> -	/* To allow fractional bits to be tracked, the entropy_count field is
> -	 * denominated in units of 1/8th bits. */
> -	POOL_ENTROPY_SHIFT = 3,
> -#define POOL_ENTROPY_BITS() (input_pool.entropy_count >> POOL_ENTROPY_SHIFT)
> -	POOL_FRACBITS = POOL_BITS << POOL_ENTROPY_SHIFT,
> -	POOL_MIN_FRACBITS = POOL_MIN_BITS << POOL_ENTROPY_SHIFT
> +	POOL_MIN_BITS = POOL_BITS /* No point in settling for less. */
>  };

Doesn't the default value of random_write_wakeup_bits need to be increased to
this value?  Otherwise, the pool can get stuck with entropy_count greater than
or equal to random_write_wakeup_bits (192) but less than POOL_MIN_BITS (256).

In fact, the only correct value of random_write_wakeup_bits will be 256, i.e.
the entire pool.  Perhaps it should no longer be configurable via /proc/sys?
Note that there's also an off-by one bug that will need to be fixed:
add_hwgenerator_randomness() checks entropy_count <= random_write_wakeup_bits
rather than entropy_count < random_write_wakeup_bits as random_poll() does.

Also: given all these considerations, perhaps the increase in POOL_MIN_BITS is
best done in a separate patch?

> +	do {
> +		entropy_count = orig = READ_ONCE(input_pool.entropy_count);
> +		entropy_count = min(POOL_BITS, entropy_count + nbits);
> +	} while (cmpxchg(&input_pool.entropy_count, orig, entropy_count) != orig);

This can be simplified slightly:

	do {
		orig = READ_ONCE(input_pool.entropy_count);
		entropy_count = min(POOL_BITS, orig + nbits);
	} while (cmpxchg(&input_pool.entropy_count, orig, entropy_count) != orig);

- Eric
Jason A. Donenfeld Feb. 5, 2022, 12:54 p.m. UTC | #2 
Hi Eric,

On Sat, Feb 5, 2022 at 8:00 AM Eric Biggers <ebiggers@kernel.org> wrote:
> I tested this, and it actually was 205 calls prior to patch 1 in this series,
> and 267 calls after patch 1.  That's in contrast to 256 calls after this patch.
> Not a big difference, but this is going to result in ~25% more single-bit calls
> being needed compared to the old version.  It's unclear whether you're arguing
> that's basically the same, or whether you thought it was a smaller difference.

My argument is that we're not _decreasing_ the security in any
substantive way with this change.

> Doesn't the default value of random_write_wakeup_bits need to be increased to
> this value?  Otherwise, the pool can get stuck with entropy_count greater than
> or equal to random_write_wakeup_bits (192) but less than POOL_MIN_BITS (256).

Good catch, thanks.

> In fact, the only correct value of random_write_wakeup_bits will be 256, i.e.
> the entire pool.  Perhaps it should no longer be configurable via /proc/sys?

I think so, yea. I'll change up in an add-on commit.

> Note that there's also an off-by one bug that will need to be fixed:
> add_hwgenerator_randomness() checks entropy_count <= random_write_wakeup_bits
> rather than entropy_count < random_write_wakeup_bits as random_poll() does.

Thanks.

> > +     do {
> > +             entropy_count = orig = READ_ONCE(input_pool.entropy_count);
> > +             entropy_count = min(POOL_BITS, entropy_count + nbits);
> > +     } while (cmpxchg(&input_pool.entropy_count, orig, entropy_count) != orig);
>
> This can be simplified slightly:
>
>         do {
>                 orig = READ_ONCE(input_pool.entropy_count);
>                 entropy_count = min(POOL_BITS, orig + nbits);
>         } while (cmpxchg(&input_pool.entropy_count, orig, entropy_count) != orig);

That looks nicer indeed. Will do.

Thanks for your comments.

Jason
diff mbox series

Patch

diff --git a/drivers/char/random.c b/drivers/char/random.c
index d1a3b203ef87..b4798a3f7bf6 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -286,17 +286,9 @@ 
 
 /* #define ADD_INTERRUPT_BENCH */
 
-enum poolinfo {
+enum {
 	POOL_BITS = BLAKE2S_HASH_SIZE * 8,
-	POOL_BITSHIFT = ilog2(POOL_BITS),
-	POOL_MIN_BITS = POOL_BITS / 2,
-
-	/* To allow fractional bits to be tracked, the entropy_count field is
-	 * denominated in units of 1/8th bits. */
-	POOL_ENTROPY_SHIFT = 3,
-#define POOL_ENTROPY_BITS() (input_pool.entropy_count >> POOL_ENTROPY_SHIFT)
-	POOL_FRACBITS = POOL_BITS << POOL_ENTROPY_SHIFT,
-	POOL_MIN_FRACBITS = POOL_MIN_BITS << POOL_ENTROPY_SHIFT
+	POOL_MIN_BITS = POOL_BITS /* No point in settling for less. */
 };
 
 /*
@@ -469,66 +461,18 @@  static void process_random_ready_list(void)
 static void credit_entropy_bits(int nbits)
 {
 	int entropy_count, orig;
-	int nfrac = nbits << POOL_ENTROPY_SHIFT;
-
-	/* Ensure that the multiplication can avoid being 64 bits wide. */
-	BUILD_BUG_ON(2 * (POOL_ENTROPY_SHIFT + POOL_BITSHIFT) > 31);
 
 	if (!nbits)
 		return;
 
-retry:
-	entropy_count = orig = READ_ONCE(input_pool.entropy_count);
-	if (nfrac < 0) {
-		/* Debit */
-		entropy_count += nfrac;
-	} else {
-		/*
-		 * Credit: we have to account for the possibility of
-		 * overwriting already present entropy.	 Even in the
-		 * ideal case of pure Shannon entropy, new contributions
-		 * approach the full value asymptotically:
-		 *
-		 * entropy <- entropy + (pool_size - entropy) *
-		 *	(1 - exp(-add_entropy/pool_size))
-		 *
-		 * For add_entropy <= pool_size/2 then
-		 * (1 - exp(-add_entropy/pool_size)) >=
-		 *    (add_entropy/pool_size)*0.7869...
-		 * so we can approximate the exponential with
-		 * 3/4*add_entropy/pool_size and still be on the
-		 * safe side by adding at most pool_size/2 at a time.
-		 *
-		 * The use of pool_size-2 in the while statement is to
-		 * prevent rounding artifacts from making the loop
-		 * arbitrarily long; this limits the loop to log2(pool_size)*2
-		 * turns no matter how large nbits is.
-		 */
-		int pnfrac = nfrac;
-		const int s = POOL_BITSHIFT + POOL_ENTROPY_SHIFT + 2;
-		/* The +2 corresponds to the /4 in the denominator */
-
-		do {
-			unsigned int anfrac = min(pnfrac, POOL_FRACBITS / 2);
-			unsigned int add =
-				((POOL_FRACBITS - entropy_count) * anfrac * 3) >> s;
-
-			entropy_count += add;
-			pnfrac -= anfrac;
-		} while (unlikely(entropy_count < POOL_FRACBITS - 2 && pnfrac));
-	}
-
-	if (WARN_ON(entropy_count < 0)) {
-		pr_warn("negative entropy/overflow: count %d\n", entropy_count);
-		entropy_count = 0;
-	} else if (entropy_count > POOL_FRACBITS)
-		entropy_count = POOL_FRACBITS;
-	if (cmpxchg(&input_pool.entropy_count, orig, entropy_count) != orig)
-		goto retry;
+	do {
+		entropy_count = orig = READ_ONCE(input_pool.entropy_count);
+		entropy_count = min(POOL_BITS, entropy_count + nbits);
+	} while (cmpxchg(&input_pool.entropy_count, orig, entropy_count) != orig);
 
-	trace_credit_entropy_bits(nbits, entropy_count >> POOL_ENTROPY_SHIFT, _RET_IP_);
+	trace_credit_entropy_bits(nbits, entropy_count, _RET_IP_);
 
-	if (crng_init < 2 && entropy_count >= POOL_MIN_FRACBITS)
+	if (crng_init < 2 && entropy_count >= POOL_MIN_BITS)
 		crng_reseed(&primary_crng, true);
 }
 
@@ -791,7 +735,7 @@  static void crng_reseed(struct crng_state *crng, bool use_input_pool)
 		int entropy_count;
 		do {
 			entropy_count = READ_ONCE(input_pool.entropy_count);
-			if (entropy_count < POOL_MIN_FRACBITS)
+			if (entropy_count < POOL_MIN_BITS)
 				return;
 		} while (cmpxchg(&input_pool.entropy_count, entropy_count, 0) != entropy_count);
 		extract_entropy(buf.key, sizeof(buf.key));
@@ -1014,7 +958,7 @@  void add_input_randomness(unsigned int type, unsigned int code,
 	last_value = value;
 	add_timer_randomness(&input_timer_state,
 			     (type << 4) ^ code ^ (code >> 4) ^ value);
-	trace_add_input_randomness(POOL_ENTROPY_BITS());
+	trace_add_input_randomness(input_pool.entropy_count);
 }
 EXPORT_SYMBOL_GPL(add_input_randomness);
 
@@ -1112,7 +1056,7 @@  void add_disk_randomness(struct gendisk *disk)
 		return;
 	/* first major is 1, so we get >= 0x200 here */
 	add_timer_randomness(disk->random, 0x100 + disk_devt(disk));
-	trace_add_disk_randomness(disk_devt(disk), POOL_ENTROPY_BITS());
+	trace_add_disk_randomness(disk_devt(disk), input_pool.entropy_count);
 }
 EXPORT_SYMBOL_GPL(add_disk_randomness);
 #endif
@@ -1137,7 +1081,7 @@  static void extract_entropy(void *buf, size_t nbytes)
 	} block;
 	size_t i;
 
-	trace_extract_entropy(nbytes, POOL_ENTROPY_BITS());
+	trace_extract_entropy(nbytes, input_pool.entropy_count);
 
 	for (i = 0; i < ARRAY_SIZE(block.rdrand); ++i) {
 		if (!arch_get_random_long(&block.rdrand[i]))
@@ -1486,9 +1430,9 @@  static ssize_t urandom_read_nowarn(struct file *file, char __user *buf,
 {
 	int ret;
 
-	nbytes = min_t(size_t, nbytes, INT_MAX >> (POOL_ENTROPY_SHIFT + 3));
+	nbytes = min_t(size_t, nbytes, INT_MAX >> 6);
 	ret = extract_crng_user(buf, nbytes);
-	trace_urandom_read(8 * nbytes, 0, POOL_ENTROPY_BITS());
+	trace_urandom_read(8 * nbytes, 0, input_pool.entropy_count);
 	return ret;
 }
 
@@ -1527,7 +1471,7 @@  static __poll_t random_poll(struct file *file, poll_table *wait)
 	mask = 0;
 	if (crng_ready())
 		mask |= EPOLLIN | EPOLLRDNORM;
-	if (POOL_ENTROPY_BITS() < random_write_wakeup_bits)
+	if (input_pool.entropy_count < random_write_wakeup_bits)
 		mask |= EPOLLOUT | EPOLLWRNORM;
 	return mask;
 }
@@ -1582,8 +1526,7 @@  static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
 	switch (cmd) {
 	case RNDGETENTCNT:
 		/* inherently racy, no point locking */
-		ent_count = POOL_ENTROPY_BITS();
-		if (put_user(ent_count, p))
+		if (put_user(input_pool.entropy_count, p))
 			return -EFAULT;
 		return 0;
 	case RNDADDTOENTCNT:
@@ -1734,23 +1677,6 @@  static int proc_do_uuid(struct ctl_table *table, int write, void *buffer,
 	return proc_dostring(&fake_table, write, buffer, lenp, ppos);
 }
 
-/*
- * Return entropy available scaled to integral bits
- */
-static int proc_do_entropy(struct ctl_table *table, int write, void *buffer,
-			   size_t *lenp, loff_t *ppos)
-{
-	struct ctl_table fake_table;
-	int entropy_count;
-
-	entropy_count = *(int *)table->data >> POOL_ENTROPY_SHIFT;
-
-	fake_table.data = &entropy_count;
-	fake_table.maxlen = sizeof(entropy_count);
-
-	return proc_dointvec(&fake_table, write, buffer, lenp, ppos);
-}
-
 static int sysctl_poolsize = POOL_BITS;
 extern struct ctl_table random_table[];
 struct ctl_table random_table[] = {
@@ -1763,10 +1689,10 @@  struct ctl_table random_table[] = {
 	},
 	{
 		.procname	= "entropy_avail",
+		.data		= &input_pool.entropy_count,
 		.maxlen		= sizeof(int),
 		.mode		= 0444,
-		.proc_handler	= proc_do_entropy,
-		.data		= &input_pool.entropy_count,
+		.proc_handler	= proc_dointvec,
 	},
 	{
 		.procname	= "write_wakeup_threshold",
@@ -1962,7 +1888,7 @@  void add_hwgenerator_randomness(const char *buffer, size_t count,
 	 */
 	wait_event_interruptible_timeout(random_write_wait,
 			!system_wq || kthread_should_stop() ||
-			POOL_ENTROPY_BITS() <= random_write_wakeup_bits,
+			input_pool.entropy_count <= random_write_wakeup_bits,
 			CRNG_RESEED_INTERVAL);
 	mix_pool_bytes(buffer, count);
 	credit_entropy_bits(entropy);