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

[George Spelvin]

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.