Re: Flaw in "random32: update the net random state on interrupt and activity"

[Willy Tarreau <w@1wt.eu>]

On Fri, Aug 07, 2020 at 03:45:48PM -0700, Marc Plumb wrote:
> Willy,
> 
> 
> On 2020-08-07 3:19 p.m., Willy Tarreau wrote:
> > On Fri, Aug 07, 2020 at 12:59:48PM -0700, Marc Plumb wrote:
> > > 
> > > If I can figure the state out once,
> > Yes but how do you take that as granted ? This state doesn't appear
> > without its noise counterpart,
> 
> Amit has shown attacks that can deduce the full internal state from 4-5
> packets with a weak PRNG. If the noise is added less often than that, an
> attacker can figure out the entire state at which point the partial
> reseeding doesn't help. If the noise is added more often than that, and it's
> raw timing events, then it's only adding a few bits of entropy so its easy
> to guess (and it weakens dev/random). If the noise is added more often, and
> it's from the output of a CPRNG, then we have all the performance/latency
> problems from the CPRNG itself, so we might as well use it directly.

His attacks is based on the fact that internal state bits leak as-is.
So it is possible to collect them and perform the inverse operation to
reconstruct the input.

Here the output is made by mixing two input bits with two noise bits
and produce one single output bit. So for each output bit you see,
you don't have just one possible input bit, but 16 possibilities.
That's 128 bits of internal changing states that once combined result
in 32 bits. For each 32-bit output you still have 2^96 possible
internal (x,noise) states producing it. And that's without counting
on the 64-bit seed that you still don't know but can be deduced from
two guessed 128 bit states (assuming that can be brute-forced at all,
of course).

For sure there are plenty of number theories allowing you to
significantly reduce the space you need to work on to brute-force
this but it will definitely remain above 2^32 attempts for each
iteration, which is the floor you have without the noise part,
while the whole internal state will be reseeded every minute
anyway.

I mean, I'm not trying to sell this thing, I'm just trying to defend
that we use a reasonable tool for a reasonable protection level. And
yes, probably that 15 years from now, someone will say "hey look, I
can brute-force this thing in less than a minute on my 1024-core 39th
gen core i7 machine with 2^60 operations per second, why don't we use
our CPU's native 10 picosecond AES1024 instruction instead ?" and we'll
say "well, it's an old story and it's probably about time to change it
again".

I don't see anything wrong with evolving this way, matching concrete
needs more than pure theory.

Regards,
Willy