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