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

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