From: George Spelvin <lkml@SDF.ORG>
To: David Laight <David.Laight@ACULAB.COM>
Cc: Dan Williams <dan.j.williams@intel.com>,
Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
Qian Cai <cai@lca.pw>, Kees Cook <keescook@chromium.org>,
Michal Hocko <mhocko@suse.com>,
Andrew Morton <akpm@linux-foundation.org>,
Linux MM <linux-mm@kvack.org>,
lkml@sdf.org
Subject: Re: [RFC PATCH v1 00/52] Audit kernel random number use
Date: Sun, 29 Mar 2020 17:41:22 +0000 [thread overview]
Message-ID: <20200329174122.GD4675@SDF.ORG> (raw)
In-Reply-To: <98bd30f23b374ccbb61dd46125dc9669@AcuMS.aculab.com>
On Sun, Mar 29, 2020 at 12:21:46PM +0000, David Laight wrote:
>From: George Spelvin
>> Sent: 28 March 2020 18:28
>...
>> 20..23: Changes to the prandom_u32() generator itself. Including
>> switching to a stronger & faster PRNG.
>
> Does this remove the code that used 'xor' to combine the output
> of (about) 5 LFSR?
> Or is that somewhere else?
> I didn't spot it in the patches - so it might already have gone.
Yes, Patch #21 ("lib/random32.c: Change to SFC32 PRNG") changes
out the generator. I kept the same 128-bit (per CPU) state size.
The previous degree-113 LFSR was okay, but not great.
(It was factored into degree-31, -29, -28 and -25 components,
so there were four subgenerators.)
(If people are willing to spend the additional state size on 64-bit
machines, there are lots of good 64-bit generators with 256 bits of state.
Just remember that we have one state per possible CPU, so that's
a jump from 2KB to 4KB with the default NR_CPUS = 64.)
> Using xor was particularly stupid.
> The whole generator was then linear and trivially reversable.
> Just using addition would have made it much stronger.
I considered changing it to addition (actually, add pairs and XOR the
sums), but that would break its self-test. And once I'd done that,
there are much better possibilities.
Actually, addition doesn't make it *much* stronger. To start
with, addition and xor are the same thing at the lsbit, so
observing 113 lsbits gives you a linear decoding problem.
next prev parent reply other threads:[~2020-03-29 17:46 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-10-03 9:51 [RFC PATCH v1 46/50] mm/shuffle.c: use get_random_max() George Spelvin
2020-03-28 18:23 ` Dan Williams
2020-03-28 18:23 ` Dan Williams
2020-03-28 18:28 ` [RFC PATCH v1 00/52] Audit kernel random number use George Spelvin
2020-03-29 12:21 ` David Laight
2020-03-29 17:41 ` George Spelvin [this message]
2020-03-29 21:42 ` Theodore Y. Ts'o
2020-03-30 2:45 ` Another batched entropy idea George Spelvin
2020-03-30 5:54 ` [PATCH] random: reduce temporary buffers George Spelvin
2020-03-30 9:27 ` [RFC PATCH v1 00/52] Audit kernel random number use David Laight
2020-04-01 5:17 ` lib/random32.c security George Spelvin
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=20200329174122.GD4675@SDF.ORG \
--to=lkml@sdf.org \
--cc=David.Laight@ACULAB.COM \
--cc=akpm@linux-foundation.org \
--cc=cai@lca.pw \
--cc=dan.j.williams@intel.com \
--cc=keescook@chromium.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=mhocko@suse.com \
/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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.