[PATCH next 0/7] random32: Improve security and simplify keying

[David Laight <david.laight.linux@gmail.com>]

The change a96ef5848cb0 to use prandom_u32_state() for kernel stack
randomisation noted that 'if the prng state can be accessed, we have
bigger problems'.

However the prandom_u32_state() function is linear. So, if you know
enough output values (eg 4 adjacent 64 bit values or 19 adjacent 6 bit
ones), you can trivially determine the original/current state so know
exactly what the following outputs will be.
Basically you can determine the constants and then calculate each bit:
	state(n) = parity(constant(n) & output)
It is the same 'schoolboy' reduction usually used to solve 2 equations.

For the kernel stack randomisation this means that if one syscall leaks
the stack alignment you can determine the alignment that will be used
for the following syscall (or loop until it has the alignment you want).

While not making is cryptographically secure, just replacing the xor used
to combile the LFSR outputs with additions makes it enourmously more
difficult to invert.

The LFSR cycle through all their possible outputs except zero, so they
must not be initialised to zero. Additionally they are less than 32 bits
and the lower few (max 6) bits are not used when generating the next value.
The easy way to achieve this is to just set one of the higher bits.
This reduces the number of initial states to 'only' 2**109.

David Laight (7):
  random32: Use add not xor to combine the LFSR outputs
  random32: Remove some unnecessary #includes
  random32: Fix tests for xor -> add change to prandom_u32_state()
  random32: Change prandom_seed_state() to be a real function
  random32: Use add (not xor) in tools prandom_u32_state()
  random32: prandom_seed_state() use all 64 bits of the seed
  random32: Simplify prandom_seed_full_state()

 include/linux/prandom.h       | 10 +---------
 lib/random32.c                | 30 +++++++++++++++++++-----------
 lib/tests/random32_kunit.c    | 14 ++++++++++++--
 tools/include/linux/prandom.h |  2 +-
 4 files changed, 33 insertions(+), 23 deletions(-)

-- 
2.39.5