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

["Jason A. Donenfeld" <Jason@zx2c4.com>]

Hey Eric,

On Thu, Apr 21, 2022 at 01:49:54PM -0700, Eric Biggers wrote:
> 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.

Alright, so my feeble attempt at nerd sniping you into working on this
inside of a mailing list thread didn't catch, alas. :)) But yea, I guess
this is something we'll have to look at. For add_timer_randomness(), I
actually wonder whether we could just get rid of all the estimation
stuff and credit either 1 or 0 bits per event, like all other sources.
Food for thought.

Anyway, onto your actual patch. I was just looking at this and something
didn't look right:

> +       for (i = 0; i < 3; i++) {
> +               if (stack.entropy == random_get_entropy())
> +                       return;
> +       }

So stack.entropy is set once when the function starts. Then we see if it
becomes equal to a new counter three times in a row. But if it's not
equal on the first try, it's probably not equal on the second and third,
right?

I suspect what you actually meant to do here is check adjacent counters,
the rationale being that on a system with a slow counter, you might be
[un]lucky and read the counter _just_ before it changes, and then the
new one differs, even though there's usually quite a large period of
time in between the two. For example:

| real time | cycle counter |
| --------- | ------------- |
| 3         | 5             |
| 4         | 5             |
| 5         | 5             |
| 6         | 5             |
| 7         | 5             | <--- a
| 8         | 6             | <--- b
| 9         | 6             | <--- c
| 10        | 6             | <--- d

If we read the counter at (a) and compare it to (b), we might be fooled
into thinking that it's a fast counter, when in reality it is not. The
solution is to also compare counter (b) to counter (c), on the theory
that if the counter is _actually_ slow, and (a)!=(b), then certainly
(b)==(c). And for this we probably only need two comparisons, not three.
What your code does is compare (a)==(b), (a)==(c), (a)==(d), but I don't
think that gives us much.

So maybe a different way of writing this is just:

    if (random_get_entropy() == (stack.entropy = random_get_entropy()) ||
        stack.entropy == (stack.entropy = random_get_entropy()))
            return;

Or at least something to that extent.

Jason