lkml.org 
[lkml]   [2022]   [Apr]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH] random: avoid mis-detecting a slow counter as a cycle counter
Hi Eric,

On Thu, Apr 21, 2022 at 9:30 PM Eric Biggers <ebiggers@kernel.org> wrote:
> 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.

Thanks for the patch. It seems like this at least is not worse than
before. But before I commit this and we forget about the problem for a
while, I was also wondering if we can do much, much better than before,
and actually make this "work" with slow counters. Right now, the core
algorithm is:

while (!crng_ready()) {
if (no timer) mod_timer(jiffies + 1);
mix(sample);
schedule(); // <---- calls the timer, which does credit_entry_bits(1)
sample = rdtsc;
}

So we credit 1 bit every time that timer fires. What if the timer
instead did this:

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;
}
}

Currently, samples_per_bit is 1. What if we make it >1 on systems with
slow cycle counters? The question then is: how do we relate some
information about cycle counter samples to the samples_per_bit estimate?
The jitter stuff in crypto/ does something. Andy (CC'd) mentioned to me
last week that he did something some time ago computing FFTs on the fly
or something like that. And maybe there are other ideas still. I wonder
if we can find something appropriate for the kernel here.

Any thoughts on that direction?

Jason

\
 
 \ /
  Last update: 2022-04-21 22:22    [W:0.193 / U:0.024 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site