linux-kernel - Re: [RFC PATCH v1 00/52] Audit kernel random number use

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: <20200329174122.GD4675@SDF.ORG>
Date:   Sun, 29 Mar 2020 17:41:22 +0000
From:   George Spelvin <lkml@....ORG>
To:     David Laight <David.Laight@...LAB.COM>
Cc:     Dan Williams <dan.j.williams@...el.com>,
        Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
        Qian Cai <cai@....pw>, Kees Cook <keescook@...omium.org>,
        Michal Hocko <mhocko@...e.com>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Linux MM <linux-mm@...ck.org>, lkml@....org
Subject: Re: [RFC PATCH v1 00/52] Audit kernel random number use

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.