Message-ID: <66f06ea1-3221-5661-e0de-6eef45ac3664@gmail.com>
Date:   Wed, 5 Aug 2020 08:44:04 -0700
From:   Marc Plumb <lkml.mplumb@...il.com>
To:     Willy Tarreau <w@....eu>
Cc:     tytso@....edu, netdev@...r.kernel.org, aksecurity@...il.com,
        torvalds@...ux-foundation.org, edumazet@...gle.com,
        Jason@...c4.com, luto@...nel.org, keescook@...omium.org,
        tglx@...utronix.de, peterz@...radead.org, stable@...r.kernel.org
Subject: Re: Flaw in "random32: update the net random state on interrupt and
 activity"

Hi Willy,

On 2020-08-04 7:49 p.m., Willy Tarreau wrote:
> Hi Marc,
>
> On Tue, Aug 04, 2020 at 05:52:36PM -0700, Marc Plumb wrote:
>> Seeding two PRNGs with the same entropy causes two problems. The minor one
>> is that you're double counting entropy. The major one is that anyone who can
>> determine the state of one PRNG can determine the state of the other.
>>
>> The net_rand_state PRNG is effectively a 113 bit LFSR, so anyone who can see
>> any 113 bits of output can determine the complete internal state.
>>
>> The output of the net_rand_state PRNG is used to determine how data is sent
>> to the network, so the output is effectively broadcast to anyone watching
>> network traffic. Therefore anyone watching the network traffic can determine
>> the seed data being fed to the net_rand_state PRNG.
> The problem this patch is trying to work around is that the reporter
> (Amit) was able to determine the entire net_rand_state after observing
> a certain number of packets due to this trivial LFSR and the fact that
> its internal state between two reseedings only depends on the number
> of calls to read it.

I thought net_rand_state was assumed to be insecure and that anyone 
could determine the internal state. Isn't this Working as Designed? It's 
a PRNG not a CPRNG. If some aspects of security depends on the sate 
remaining secret then this is fundamentally the wrong tool.

> (please note that regarding this point I'll
> propose a patch to replace that PRNG to stop directly exposing the
> internal state to the network).

I'm glad to hear that. A good option would be SFC32.

> If you look closer at the patch, you'll see that in one interrupt
> the patch only uses any 32 out of the 128 bits of fast_pool to
> update only 32 bits of the net_rand_state. As such, the sequence
> observed on the network also depends on the remaining bits of
> net_rand_state, while the 96 other bits of the fast_pool are not
> exposed there.

The fast pool contains 128 bits of state, not 128 bits of entropy. The 
purpose of the large pool size is to make sure that the entropy is not 
lost due to collisions. The non-linear mixing function (a simplified 
version of a single round of the ChaCha mixing function so the entropy 
diffusion is low) means that the 32 bits leaked are not independent from 
the other 96 bits, and in fact you can reconstruct the entire pool from 
a single reading of 32 bits (as long as there aren't more than 32 bits 
of entropy added during this time -- which isn't the case, see below). 
Please think harder about this part. I think you are misunderstanding 
how this code works.

>> Since this is the same
>> seed data being fed to get_random_bytes, it allows an attacker to determine
>> the state and there output of /dev/random. I sincerely hope that this was
>> not the intended goal. :)
> Not only was this obviously not the goal, but I'd be particularly
> interested in seeing this reality demonstrated, considering that
> the whole 128 bits of fast_pool together count as a single bit of
> entropy, and that as such, even if you were able to figure the
> value of the 32 bits leaked to net_rand_state, you'd still have to
> guess the 96 other bits for each single entropy bit :-/

The code assumes that there is at least 1/64 bit of entropy per sample, 
and at most 2 bits of entropy per sample (which is why it dumps 128 bits 
every 64 samples). If you're extracting 32 bits every sample, which 
means it's leaking 2048 bits in 64 samples (to net_random, how fast it 
leaks to the outside world is a different issue). So the question is if 
an attacker can reconstruct 128 bits of entropy from 2048 bits of 
internal state -- this does not seem obviously impossible, since there 
are no cryptographically vetted operations in this.

The other thing that this misses is that reseeding in dribs and drabs 
makes it much easier to recover the new state. This is is explained well 
in the documentation about catastrophic reseeding in the Fortuna CPRNG. 
This entire approach is flawed. Throwing in single bits of entropy at a 
time doesn't really help since an attacker can brute force a single bit 
at a time. (There is a challenge in deriving the initial fast_pool 
states which this makes more difficult, but there is no real 
crytptographic guarantee about how difficult it is.)

Thanks,

Marc

Powered by blists - more mailing lists