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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <a1833e06-1ce5-9a2b-f518-92e7c6b47d4f@gmail.com>
Date:   Fri, 7 Aug 2020 09:52:14 -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"

On 2020-08-07 12:03 a.m., Willy Tarreau wrote:

> Just to give a heads up on this, here's what I'm having pending regarding
> MSWS:
>
>    struct rnd_state {
>          uint64_t x, w;
>          uint64_t seed;
>          uint64_t noise;
>    };
>
>    uint32_t msws32(struct rnd_state *state)
>    {
>          uint64_t x;
>
>          x  = state->w += state->seed;
>          x += state->x * state->x;
>          x  = state->x = (x >> 32) | (x << 32);
>          x -= state->noise++;
>          return x ^ (x >> 32);
>    }

A few comments:

This is still another non-cryptographic PRNG. An LFSR can pass PractRand 
(if you do a tweak to get around the specific linear complexity test for 
LFSRs).

On a 64-bit machine it should be fast: 4 adds, 1 multiply, 1 rotate, 1 
shift, 1 xor

This will be much slower on 32-bit machines, if that's still a concern

As long as the noise is the output of a CPRNG, this doesn't hurt the 
security of dev/dandom.

The noise is more like effective 32-bits since you're xoring the low and 
high half of the noise together (ignoring the minor details of carry 
bits). Which means that it's 2^32 effort to brute force this (which Amit 
called "no biggie for modern machines"). If the noise is the raw sample 
data with only a few bits of entropy, then it's even easier to brute force.

Given the uses of this, I think we really should look into a CPRNG for 
this and then completely reseed it periodically. The problem is finding 
one that's fast enough. Is there a hard instruction budget for this, or 
it is just "fast enough to not hurt the network benchmarks" (i.e. if 
Dave Miller screams)?

Marc