From: Willy Tarreau <w@1wt•eu>
To: Marc Plumb <lkml.mplumb@gmail•com>
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:03:16 +0200 [thread overview]
Message-ID: <20200807070316.GA6357@1wt.eu> (raw)
In-Reply-To: <50b046ee-d449-8e6c-1267-f4060b527c06@gmail.com>
On Thu, Aug 06, 2020 at 10:18:55AM -0700, Marc Plumb wrote:
> Willy,
>
>
> On 2020-08-05 11:30 p.m., Willy Tarreau wrote:
> > On Wed, Aug 05, 2020 at 03:21:11PM -0700, Marc Plumb wrote:
> > > 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.
> > This is interesting because I think some of us considered it exactly the
> > other way around, i.e. we're not copying exact bits but just taking a
> > pseudo-random part of such bits at one point in time, to serve as an
> > increment among other ones. And given that these bits were collected
> > over time from not very secret sources, they appeared to be of lower
> > risk than the output.
>
> No. The output of a CPRNG can't be used to determine the internal state. The
> input can. The input entropy is the one thing that cannot be produced by a
> deterministic computer, so they are the crown jewels of this. It's much much
> safer to use the output.
OK, noted.
> > I didn't know about SFC32, it looks like a variation of the large family
> > of xorshift generators, which is thus probably quite suitable as well
> > for this task. Having used xoroshiro128** myself in another project, I
> > found it overkill for this task compared to MSWS but I definitely agree
> > that any of them is more suited to the task than the current one.
> >
> It's actually a chaotic generator (not a linear one like an xorshift
> generator), which gives it weaker period guarantees which makes it more
> difficult to reverse. With a counter added to help the period length.
>
> I'll trust Amit that SFC32 isn't strong enough and look at other options --
> I just thought of it as better, and faster than the existing one with the
> same state size. Maybe a larger state is needed.
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);
}
It passes PractRand without any warning after 1 TB of data:
rng=RNG_stdin, seed=unknown
length= 512 megabytes (2^29 bytes), time= 2.0 seconds
no anomalies in 229 test result(s)
rng=RNG_stdin, seed=unknown
length= 1 gigabyte (2^30 bytes), time= 4.3 seconds
no anomalies in 248 test result(s)
rng=RNG_stdin, seed=unknown
length= 2 gigabytes (2^31 bytes), time= 8.3 seconds
no anomalies in 266 test result(s)
rng=RNG_stdin, seed=unknown
length= 4 gigabytes (2^32 bytes), time= 15.8 seconds
no anomalies in 282 test result(s)
rng=RNG_stdin, seed=unknown
length= 8 gigabytes (2^33 bytes), time= 31.3 seconds
no anomalies in 299 test result(s)
rng=RNG_stdin, seed=unknown
length= 16 gigabytes (2^34 bytes), time= 61.9 seconds
no anomalies in 315 test result(s)
rng=RNG_stdin, seed=unknown
length= 32 gigabytes (2^35 bytes), time= 119 seconds
no anomalies in 328 test result(s)
rng=RNG_stdin, seed=unknown
length= 64 gigabytes (2^36 bytes), time= 242 seconds
no anomalies in 344 test result(s)
rng=RNG_stdin, seed=unknown
length= 128 gigabytes (2^37 bytes), time= 483 seconds
no anomalies in 359 test result(s)
rng=RNG_stdin, seed=unknown
length= 256 gigabytes (2^38 bytes), time= 940 seconds
no anomalies in 372 test result(s)
rng=RNG_stdin, seed=unknown
length= 512 gigabytes (2^39 bytes), time= 1906 seconds
no anomalies in 387 test result(s)
rng=RNG_stdin, seed=unknown
length= 1 terabyte (2^40 bytes), time= 3826 seconds
no anomalies in 401 test result(s)
The two modifications compared to the original msws are:
- mix bits on output so that we don't reveal the internal
state upon each call ;
- combination of the output with an independent noise
variable whose purpose was to be updated upon IRQ
and/or CPU usage and/or invocations. But on this point,
while implementing it I figured that updating it on each
invocation did already provide the frequent updates we
were missing in Tausworthe that required the interrupt
updates. I'd definitely update in update_process_times()
so that it's not reduced to a pure counter, but the
results, speed and simplicity look encouraging.
I'll try to work on finishing the patch proposal this week-end.
Regards,
Willy
next prev parent reply other threads:[~2020-08-07 7:04 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 [this message]
2020-08-07 16:52 ` Marc Plumb
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
-- strict thread matches above, loose matches on Subject: below --
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=20200807070316.GA6357@1wt.eu \
--to=w@1wt$(echo .)eu \
--cc=Jason@zx2c4$(echo .)com \
--cc=aksecurity@gmail$(echo .)com \
--cc=edumazet@google$(echo .)com \
--cc=keescook@chromium$(echo .)org \
--cc=lkml.mplumb@gmail$(echo .)com \
--cc=luto@kernel$(echo .)org \
--cc=netdev@vger$(echo .)kernel.org \
--cc=peterz@infradead$(echo .)org \
--cc=stable@vger$(echo .)kernel.org \
--cc=tglx@linutronix$(echo .)de \
--cc=torvalds@linux-foundation$(echo .)org \
--cc=tytso@mit$(echo .)edu \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
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