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

[Eric Biggers <ebiggers@kernel.org>]

On Thu, Apr 21, 2022 at 10:20:35PM +0200, Jason A. Donenfeld wrote:
> 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?
> 

I think we'll need to go there eventually, along with fixing
add_timer_randomness() and add_interrupt_randomness() to credit entropy more
accurately.  I do not think there is an easy fix, though; this is mostly an open
research area.  Looking into research papers and what has been done for other
jitter entropy implementations would be useful.

- Eric