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

Willy,

On 2020-08-05 12:38 p.m., Willy Tarreau wrote:

It's not *that* major an issue (in my personal opinion) but the current
net_rand_state is easy enough to guess so that an observer may reduce
the difficulty to build certain attacks (using known source ports for
example). The goal of this change (and the one in update_process_times())
is to disturb the net_rand_state a little bit so that external observations
turn from "this must be that" to "this may be this or maybe that", which
is sufficient to limit the ability to reliably guess a state and reduce
the cost of an attack.

There is nothing wrong with perturbing net_rand_state, the sin is doing 
it with the raw entropy that is also the seed for your CPRNG. Use the 
output of a CPRNG to perturb the pool all you want, but don't do things 
that bit by bit reveal the entropy that is being fed into the CPRNG.

Another approach involving the replacement of the algorithm was considered
but we were working with -stable in mind, trying to limit the backporting
difficulty (and it revealed a circular dependency nightmare that had been
sleeping there for years), and making the changes easier to check (which
is precisely what you're doing).

Really? You can replace the LFSR and only change lib/random32.c. That 
might fix the problem without the need to use the raw fast_pool data for 
seed material. As Linus said, speed is a concern but SFC32 is faster 
than existing Tausworthe generator, and it's a drop-in replacement with 
the same state size if that makes your life easier. If you're willing to 
expand the state there are even better options (like SFC64 or some of 
chaotic generators like Jenkins' Frog).

We're not trying to invent any stream cipher or whatever, just making
use of a few bits that are never exposed alone as-is to internal nor
external states, to slightly disturb another state that otherwise only
changes once a minute so that there's no more a 100% chance of guessing
a 16-bit port after seeing a few packets. I mean, I'm pretty sure that
even stealing three or four bits only from there would be quite enough
to defeat the attack given that Amit only recovers a few bits per packet.

If Amit's attack can recover that much per packet (in practice not just 
in theory) and there is even one packet per interrupt, then it's a major 
problem. There are at most 2 bits of entropy added per call to 
add_interrupt_randomness, so it you're leaking "a few bits per packet" 
then that's everything. Over 64 interrupts you've lost the 128 bits of 
entropy that the fast_pool has spilled into the input_pool.

Marc