From: Marc Plumb <lkml.mplumb@gmail.com>
To: Willy Tarreau <w@1wt.eu>
Cc: tytso@mit.edu, netdev@vger.kernel.org, aksecurity@gmail.com,
torvalds@linux-foundation.org, edumazet@google.com,
Jason@zx2c4.com, luto@kernel.org, keescook@chromium.org,
tglx@linutronix.de, peterz@infradead.org, stable@vger.kernel.org
Subject: Re: Flaw in "random32: update the net random state on interrupt and activity"
Date: Fri, 7 Aug 2020 09:52:14 -0700 [thread overview]
Message-ID: <a1833e06-1ce5-9a2b-f518-92e7c6b47d4f@gmail.com> (raw)
In-Reply-To: <20200807070316.GA6357@1wt.eu>
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
next prev parent reply other threads:[~2020-08-07 16:52 UTC|newest]
Thread overview: 64+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <9f74230f-ba4d-2e19-5751-79dc2ab59877@gmail.com>
2020-08-05 0:57 ` Flaw in "random32: update the net random state on interrupt and activity" Marc Plumb
2020-08-05 1:02 ` Linus Torvalds
2020-08-05 2:49 ` Willy Tarreau
2020-08-05 15:34 ` tytso
2020-08-05 16:06 ` Marc Plumb
2020-08-05 19:38 ` Willy Tarreau
2020-08-05 22:21 ` Marc Plumb
2020-08-06 6:30 ` Willy Tarreau
2020-08-06 17:18 ` Marc Plumb
2020-08-07 7:03 ` Willy Tarreau
2020-08-07 16:52 ` Marc Plumb [this message]
2020-08-07 17:43 ` Willy Tarreau
[not found] ` <C74EC3BC-F892-416F-A95C-4ACFC96EEECE@amacapital.net>
2020-08-07 18:04 ` Willy Tarreau
2020-08-07 18:10 ` Linus Torvalds
2020-08-07 19:08 ` Andy Lutomirski
2020-08-07 19:21 ` Linus Torvalds
2020-08-07 19:33 ` Andy Lutomirski
2020-08-07 19:56 ` Linus Torvalds
2020-08-07 20:16 ` Andy Lutomirski
2020-08-07 20:24 ` Linus Torvalds
2020-08-07 19:59 ` Marc Plumb
2020-08-07 22:19 ` Willy Tarreau
2020-08-07 22:45 ` Marc Plumb
2020-08-07 23:11 ` Willy Tarreau
2020-08-05 22:05 ` tytso
2020-08-05 23:03 ` Andy Lutomirski
2020-08-06 17:00 ` Marc Plumb
2020-08-05 16:24 ` Jason A. Donenfeld
2020-08-05 16:53 ` Willy Tarreau
2020-08-05 15:44 ` Marc Plumb
2020-08-05 16:39 ` Linus Torvalds
2020-08-05 23:49 ` Stephen Hemminger
2020-08-08 15:26 George Spelvin
2020-08-08 17:07 ` Andy Lutomirski
2020-08-08 18:08 ` Willy Tarreau
2020-08-08 18:13 ` Linus Torvalds
2020-08-08 19:03 ` George Spelvin
2020-08-08 19:49 ` Andy Lutomirski
2020-08-08 21:29 ` George Spelvin
2020-08-08 17:44 ` Willy Tarreau
2020-08-08 18:19 ` Linus Torvalds
2020-08-08 18:53 ` Willy Tarreau
2020-08-08 20:47 ` George Spelvin
2020-08-08 20:52 ` Linus Torvalds
2020-08-08 22:27 ` George Spelvin
2020-08-09 2:07 ` Linus Torvalds
2020-08-11 16:01 ` Eric Dumazet
2020-08-08 19:18 ` Florian Westphal
2020-08-08 20:59 ` George Spelvin
2020-08-08 21:18 ` Willy Tarreau
2020-08-08 20:08 ` George Spelvin
2020-08-08 20:47 ` Linus Torvalds
2020-08-12 6:03 Sedat Dilek
2020-08-12 6:35 ` Sedat Dilek
2020-08-12 7:13 ` Sedat Dilek
2020-08-12 15:16 ` Eric Dumazet
2020-08-12 16:20 ` Sedat Dilek
2020-08-12 16:24 ` Eric Dumazet
2020-08-12 16:38 ` Sedat Dilek
2020-08-19 9:51 ` Sedat Dilek
2021-01-08 13:08 ` Sedat Dilek
2021-01-08 13:51 ` Sedat Dilek
2021-01-08 15:41 ` Eric Dumazet
2021-01-08 21:32 ` Sedat Dilek
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=a1833e06-1ce5-9a2b-f518-92e7c6b47d4f@gmail.com \
--to=lkml.mplumb@gmail.com \
--cc=Jason@zx2c4.com \
--cc=aksecurity@gmail.com \
--cc=edumazet@google.com \
--cc=keescook@chromium.org \
--cc=luto@kernel.org \
--cc=netdev@vger.kernel.org \
--cc=peterz@infradead.org \
--cc=stable@vger.kernel.org \
--cc=tglx@linutronix.de \
--cc=torvalds@linux-foundation.org \
--cc=tytso@mit.edu \
--cc=w@1wt.eu \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).