[PATCH v2] random: avoid mis-detecting a slow counter as a cycle counter

[PATCH v2] random: avoid mis-detecting a slow counter as a cycle counter

[Eric Biggers]

From: Eric Biggers <ebiggers@google.com>

The method that try_to_generate_entropy() uses to detect a cycle counter
is to check whether two calls to random_get_entropy() return different
values.  This is uncomfortably prone to false positives if
random_get_entropy() is a slow counter, as the two calls could return
different values if the counter happens to be on the cusp of a change.
Making things worse, the task can be preempted between the calls.

This is problematic because try_to_generate_entropy() doesn't do any
real entropy estimation later; it always credits 1 bit per loop
iteration.  To avoid crediting garbage, it relies entirely on the
preceding check for whether a cycle counter is present.

Therefore, increase the number of counter comparisons from 1 to 3, to
greatly reduce the rate of false positive cycle counter detections.

Fixes: 50ee7529ec45 ("random: try to actively add entropy rather than passively wait for it")
Signed-off-by: Eric Biggers <ebiggers@google.com>
---

v2: compare with previous value rather than first one.

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

diff --git a/drivers/char/random.c b/drivers/char/random.c
index bf89c6f27a192..18d2d1f959683 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1382,12 +1382,22 @@ static void try_to_generate_entropy(void)
 		unsigned long entropy;
 		struct timer_list timer;
 	} stack;
+	int i;
 
+	/*
+	 * We must not proceed if we don't actually have a cycle counter.  To
+	 * detect a cycle counter, check whether random_get_entropy() returns a
+	 * new value each time.  Check this multiple times to avoid false
+	 * positives where a slow counter could be just on the cusp of a change.
+	 */
 	stack.entropy = random_get_entropy();
+	for (i = 0; i < 3; i++) {
+		unsigned long entropy = random_get_entropy();
 
-	/* Slow counter - or none. Don't even bother */
-	if (stack.entropy == random_get_entropy())
-		return;
+		if (stack.entropy == entropy)
+			return;
+		stack.entropy = entropy;
+	}
 
 	timer_setup_on_stack(&stack.timer, entropy_timer, 0);
 	while (!crng_ready() && !signal_pending(current)) {

base-commit: 939ee380b17589d026e132a1be91199409c3c934
-- 
2.35.2

Re: [PATCH v2] random: avoid mis-detecting a slow counter as a cycle counter

[Jason A. Donenfeld]

Hi Eric,

Thanks. This looks better.

On Thu, Apr 21, 2022 at 04:31:52PM -0700, Eric Biggers wrote:
> Therefore, increase the number of counter comparisons from 1 to 3, to
> greatly reduce the rate of false positive cycle counter detections.
> +	for (i = 0; i < 3; i++) {
> +		unsigned long entropy = random_get_entropy();
 
Wondering: why do you do 3 comparisons rather than 2? What does 3 get
you that 2 doesn't already? I thought the only real requirement was that
in the event where (a)!=(b), (b) is read as meaningfully close as
possible to when the counter changes.

Jason

Re: [PATCH v2] random: avoid mis-detecting a slow counter as a cycle counter

[Eric Biggers]

On Fri, Apr 22, 2022 at 01:40:25AM +0200, Jason A. Donenfeld wrote:
> Hi Eric,
> 
> Thanks. This looks better.
> 
> On Thu, Apr 21, 2022 at 04:31:52PM -0700, Eric Biggers wrote:
> > Therefore, increase the number of counter comparisons from 1 to 3, to
> > greatly reduce the rate of false positive cycle counter detections.
> > +	for (i = 0; i < 3; i++) {
> > +		unsigned long entropy = random_get_entropy();
>  
> Wondering: why do you do 3 comparisons rather than 2? What does 3 get
> you that 2 doesn't already? I thought the only real requirement was that
> in the event where (a)!=(b), (b) is read as meaningfully close as
> possible to when the counter changes.
> 

On CONFIG_PREEMPT kernels this code usually runs with preemption enabled, so I
don't think it's guaranteed that any particular number of comparisons will be
sufficient, since the task could get preempted for a long time between each call
to random_get_entropy().  However, the chance of a false positive should
decrease exponentially, and should be pretty small in the first place, so 3
comparisons seems like a good number.

We could also disable IRQs while checking, if you'd prefer to go that route.  We
would still need 2 comparisons.

- Eric

Re: [PATCH v2] random: avoid mis-detecting a slow counter as a cycle counter

[Jason A. Donenfeld]

Hi Eric,

On Thu, Apr 21, 2022 at 05:34:58PM -0700, Eric Biggers wrote:
> On Fri, Apr 22, 2022 at 01:40:25AM +0200, Jason A. Donenfeld wrote:
> > Hi Eric,
> > 
> > Thanks. This looks better.
> > 
> > On Thu, Apr 21, 2022 at 04:31:52PM -0700, Eric Biggers wrote:
> > > Therefore, increase the number of counter comparisons from 1 to 3, to
> > > greatly reduce the rate of false positive cycle counter detections.
> > > +	for (i = 0; i < 3; i++) {
> > > +		unsigned long entropy = random_get_entropy();
> >  
> > Wondering: why do you do 3 comparisons rather than 2? What does 3 get
> > you that 2 doesn't already? I thought the only real requirement was that
> > in the event where (a)!=(b), (b) is read as meaningfully close as
> > possible to when the counter changes.
> > 
> 
> On CONFIG_PREEMPT kernels this code usually runs with preemption enabled, so I
> don't think it's guaranteed that any particular number of comparisons will be
> sufficient, since the task could get preempted for a long time between each call
> to random_get_entropy().  However, the chance of a false positive should
> decrease exponentially, and should be pretty small in the first place, so 3
> comparisons seems like a good number.

Ahh, I see. So you check three times instead of disabling
preemption/irqs, which would be awfully heavy weight. Seems like a
reasonable compromise.

By the way, I was thinking about the assumptions we're making with this
comparison ("two adjacent counters shouldn't be the same") in the
context of this idea from my first reply to you:

    static void entropy_timer(struct timer_list *t)
    {
        struct timer_state *s = container_of(...t...);
        if (++s->samples == s->samples_per_bit) {
            credit_entropy_bits(1);
            s->samples = 0;
        }
    }

A naive approach that strikes me as strictly _no worse_ than what we
currently have would be to say that right now we require every counter
to be different in order to credit everytime. If every other counter is
different, then we should credit every other time. If every third
counter is different, we should credit every third time. And so forth.
While that simple logic isn't some sort of fancy realtime FFT thing, it
also doesn't appear on its surface to be relying on assumptions that
we're not already making. I think? It has flaws -- it doesn't account
for the possibility that while the counter changes, it's way too uniform
in how it changes -- but neither does the current technique. So while
it's not the end goal of actually looking at this through some
statistical lens, it feels like an improvement on what we have now with
little complication.

If that seems convincing, what do you make of the below snippet?

Jason

------------8<--------------------------------------------------------------

diff --git a/drivers/char/random.c b/drivers/char/random.c
index bf89c6f27a19..cabba031cbaf 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1354,6 +1354,12 @@ void add_interrupt_randomness(int irq)
 }
 EXPORT_SYMBOL_GPL(add_interrupt_randomness);
 
+struct entropy_timer_state {
+	unsigned long entropy;
+	struct timer_list timer;
+	unsigned int samples, samples_per_bit;
+};
+
 /*
  * Each time the timer fires, we expect that we got an unpredictable
  * jump in the cycle counter. Even if the timer is running on another
@@ -1367,9 +1373,14 @@ EXPORT_SYMBOL_GPL(add_interrupt_randomness);
  *
  * So the re-arming always happens in the entropy loop itself.
  */
-static void entropy_timer(struct timer_list *t)
+static void entropy_timer(struct timer_list *timer)
 {
-	credit_entropy_bits(1);
+	struct entropy_timer_state *state = container_of(timer, struct entropy_timer_state, timer);
+
+	if (++state->samples == state->samples_per_bit) {
+		credit_entropy_bits(1);
+		state->samples = 0;
+	}
 }
 
 /*
@@ -1378,16 +1389,26 @@ static void entropy_timer(struct timer_list *t)
  */
 static void try_to_generate_entropy(void)
 {
-	struct {
-		unsigned long entropy;
-		struct timer_list timer;
-	} stack;
+	enum { NUM_TRIALS = 2048, MAX_BITS_PER_SAMPLE = 256 };
+	struct entropy_timer_state stack;
+	unsigned int i, num_different = 1;
 
-	stack.entropy = random_get_entropy();
-
-	/* Slow counter - or none. Don't even bother */
-	if (stack.entropy == random_get_entropy())
+	unsigned long *trials = kmalloc_array(NUM_TRIALS, sizeof(*trials), GFP_KERNEL);
+	if (!trials)
 		return;
+	for (i = 0; i < NUM_TRIALS; ++i)
+		trials[i] = random_get_entropy();
+	for (i = 0; i < NUM_TRIALS - 1; ++i) {
+		if (trials[i] != trials[i + 1])
+			++num_different;
+	}
+	mix_pool_bytes(trials, NUM_TRIALS * sizeof(*trials));
+	kfree(trials);
+	stack.samples_per_bit = DIV_ROUND_UP(NUM_TRIALS, num_different);
+	if (stack.samples > MAX_BITS_PER_SAMPLE)
+		return;
+	stack.samples = 0;
+	stack.entropy = random_get_entropy();
 
 	timer_setup_on_stack(&stack.timer, entropy_timer, 0);
 	while (!crng_ready() && !signal_pending(current)) {

Re: [PATCH v2] random: avoid mis-detecting a slow counter as a cycle counter

[Jason A. Donenfeld]

On Fri, Apr 22, 2022 at 11:42:04AM +0200, Jason A. Donenfeld wrote:
> Hi Eric,
> 
> On Thu, Apr 21, 2022 at 05:34:58PM -0700, Eric Biggers wrote:
> > On Fri, Apr 22, 2022 at 01:40:25AM +0200, Jason A. Donenfeld wrote:
> > > Hi Eric,
> > > 
> > > Thanks. This looks better.
> > > 
> > > On Thu, Apr 21, 2022 at 04:31:52PM -0700, Eric Biggers wrote:
> > > > Therefore, increase the number of counter comparisons from 1 to 3, to
> > > > greatly reduce the rate of false positive cycle counter detections.
> > > > +	for (i = 0; i < 3; i++) {
> > > > +		unsigned long entropy = random_get_entropy();
> > >  
> > > Wondering: why do you do 3 comparisons rather than 2? What does 3 get
> > > you that 2 doesn't already? I thought the only real requirement was that
> > > in the event where (a)!=(b), (b) is read as meaningfully close as
> > > possible to when the counter changes.
> > > 
> > 
> > On CONFIG_PREEMPT kernels this code usually runs with preemption enabled, so I
> > don't think it's guaranteed that any particular number of comparisons will be
> > sufficient, since the task could get preempted for a long time between each call
> > to random_get_entropy().  However, the chance of a false positive should
> > decrease exponentially, and should be pretty small in the first place, so 3
> > comparisons seems like a good number.
> 
> Ahh, I see. So you check three times instead of disabling
> preemption/irqs, which would be awfully heavy weight. Seems like a
> reasonable compromise.
> 
> By the way, I was thinking about the assumptions we're making with this
> comparison ("two adjacent counters shouldn't be the same") in the
> context of this idea from my first reply to you:

Rather than buggy inline email code, I made a real patch out of it for
your consideration:
https://lore.kernel.org/linux-crypto/20220422132027.1267060-1-Jason@zx2c4.com/

Jason