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

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

[David Laight]

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

[PATCH next 1/7] random32: Improve security of prandom_u32_state()

[David Laight]

While security isn't that important in can easily be made a lot better.

The four LFSR are linear are reversable.
Combining the outputs with xor is still linear.
This means that the initial state of the prng can be trivially determined
from 113 output bits that have a known distance from that state.
(Each state bit is just the xor of some combination of the output bits.)

Replace the final xor with add making it non-linear and nothing like
as easy to invert.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 lib/random32.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/random32.c b/lib/random32.c
index dad90219c351..34f08f6540e6 100644
--- a/lib/random32.c
+++ b/lib/random32.c
@@ -58,7 +58,7 @@ u32 prandom_u32_state(struct rnd_state *state)
 	state->s3 = TAUSWORTHE(state->s3, 13U, 21U, 4294967280U,  7U);
 	state->s4 = TAUSWORTHE(state->s4,  3U, 12U, 4294967168U, 13U);
 
-	return (state->s1 ^ state->s2 ^ state->s3 ^ state->s4);
+	return (state->s1 + state->s2 + state->s3 + state->s4);
 }
 EXPORT_SYMBOL(prandom_u32_state);
 
-- 
2.39.5

[PATCH next 2/7] random32: Remove some unnecessary #includes

[David Laight]

These haven't been needed since the self tests were separated out.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 lib/random32.c | 4 ----
 1 file changed, 4 deletions(-)

diff --git a/lib/random32.c b/lib/random32.c
index 34f08f6540e6..53cb289a5db4 100644
--- a/lib/random32.c
+++ b/lib/random32.c
@@ -35,11 +35,7 @@
 #include <linux/types.h>
 #include <linux/percpu.h>
 #include <linux/export.h>
-#include <linux/jiffies.h>
 #include <linux/prandom.h>
-#include <linux/sched.h>
-#include <linux/bitops.h>
-#include <linux/slab.h>
 #include <linux/unaligned.h>
 #include <kunit/visibility.h>
 
-- 
2.39.5

[PATCH next 3/7] random32: Fix tests for xor -> add change to prandom_u32_state()

[David Laight]

The test vectors check the result of prandom_u32_state() against known
values. The change to prandom_u32_state() to add the four values to
make determining the state not completely trivial breaks this.

Rather than change the test data fix the tests by adding a local
function that combines the four values using xor.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 lib/tests/random32_kunit.c | 14 ++++++++++++--
 1 file changed, 12 insertions(+), 2 deletions(-)

diff --git a/lib/tests/random32_kunit.c b/lib/tests/random32_kunit.c
index 0b4af2b09c01..ccf439686fda 100644
--- a/lib/tests/random32_kunit.c
+++ b/lib/tests/random32_kunit.c
@@ -136,6 +136,16 @@ static void prandom_state_test_seed(struct rnd_state *state, u32 seed)
 	state->s4 = __seed(LCG(state->s3), 128U);
 }
 
+/*
+ * prandom_u32_state() adds the values to stop the generator being linear.
+ * To avoid changing the test recover the expected value.
+ */
+static u32 prandom_u32_state_xor(struct rnd_state *state)
+{
+	prandom_u32_state(state);
+	return state->s1 ^ state->s2 ^ state->s3 ^ state->s4;
+}
+
 static void test_prandom_seed_boundary(struct kunit *test)
 {
 	int i;
@@ -144,7 +154,7 @@ static void test_prandom_seed_boundary(struct kunit *test)
 	for (i = 0; i < ARRAY_SIZE(test1); i++) {
 		prandom_state_test_seed(&state, test1[i].seed);
 		prandom_warmup(&state);
-		KUNIT_EXPECT_EQ(test, test1[i].result, prandom_u32_state(&state));
+		KUNIT_EXPECT_EQ(test, test1[i].result, prandom_u32_state_xor(&state));
 	}
 }
 
@@ -160,7 +170,7 @@ static void test_prandom_taus113(struct kunit *test)
 		for (j = 0; j < test2[i].iteration - 1; j++)
 			prandom_u32_state(&state);
 
-		KUNIT_EXPECT_EQ(test, test2[i].result, prandom_u32_state(&state));
+		KUNIT_EXPECT_EQ(test, test2[i].result, prandom_u32_state_xor(&state));
 	}
 }
 
-- 
2.39.5

[PATCH next 4/7] random32: Change prandom_seed_state() to be a real function

[David Laight]

There is no reason for it to be inlined.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 include/linux/prandom.h | 10 +---------
 lib/random32.c          | 11 +++++++++++
 2 files changed, 12 insertions(+), 9 deletions(-)

diff --git a/include/linux/prandom.h b/include/linux/prandom.h
index ff7dcc3fa105..d4627e62098c 100644
--- a/include/linux/prandom.h
+++ b/include/linux/prandom.h
@@ -37,14 +37,6 @@ static inline u32 __seed(u32 x, u32 m)
  * @state: pointer to state structure to receive the seed.
  * @seed: arbitrary 64-bit value to use as a seed.
  */
-static inline void prandom_seed_state(struct rnd_state *state, u64 seed)
-{
-	u32 i = ((seed >> 32) ^ (seed << 10) ^ seed) & 0xffffffffUL;
-
-	state->s1 = __seed(i,   2U);
-	state->s2 = __seed(i,   8U);
-	state->s3 = __seed(i,  16U);
-	state->s4 = __seed(i, 128U);
-}
+void prandom_seed_state(struct rnd_state *state, u64 seed);
 
 #endif
diff --git a/lib/random32.c b/lib/random32.c
index 53cb289a5db4..83776345adda 100644
--- a/lib/random32.c
+++ b/lib/random32.c
@@ -130,3 +130,14 @@ void prandom_seed_full_state(struct rnd_state __percpu *pcpu_state)
 	}
 }
 EXPORT_SYMBOL(prandom_seed_full_state);
+
+void prandom_seed_state(struct rnd_state *state, u64 seed)
+{
+	u32 i = ((seed >> 32) ^ (seed << 10) ^ seed) & 0xffffffffUL;
+
+	state->s1 = __seed(i,   2U);
+	state->s2 = __seed(i,   8U);
+	state->s3 = __seed(i,  16U);
+	state->s4 = __seed(i, 128U);
+}
+EXPORT_SYMBOL(prandom_seed_state);
-- 
2.39.5

[PATCH next 5/7] random32: Use add (not xor) in tools prandom_u32_state()

[David Laight]

Matches the main kernel change.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 tools/include/linux/prandom.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/tools/include/linux/prandom.h b/tools/include/linux/prandom.h
index b745041ccd6a..56d1422e54a8 100644
--- a/tools/include/linux/prandom.h
+++ b/tools/include/linux/prandom.h
@@ -46,6 +46,6 @@ static inline u32 prandom_u32_state(struct rnd_state *state)
 	state->s3 = TAUSWORTHE(state->s3, 13U, 21U, 4294967280U,  7U);
 	state->s4 = TAUSWORTHE(state->s4,  3U, 12U, 4294967168U, 13U);
 
-	return (state->s1 ^ state->s2 ^ state->s3 ^ state->s4);
+	return (state->s1 + state->s2 + state->s3 + state->s4);
 }
 #endif // __TOOLS_LINUX_PRANDOM_H
-- 
2.39.5

[PATCH next 6/7] random32: prandom_seed_state() use all 64 bits of the seed

[David Laight]

Use the high 32bits to initialise s3 and s4 rather than reducing
the value to 32 bits.
Simplify the avoidance of values near zero by just setting a bit.
Keep the '<< 10' so that bits 0 and 32-35 get used.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 lib/random32.c | 11 ++++++-----
 1 file changed, 6 insertions(+), 5 deletions(-)

diff --git a/lib/random32.c b/lib/random32.c
index 83776345adda..1d6468045267 100644
--- a/lib/random32.c
+++ b/lib/random32.c
@@ -133,11 +133,12 @@ EXPORT_SYMBOL(prandom_seed_full_state);
 
 void prandom_seed_state(struct rnd_state *state, u64 seed)
 {
-	u32 i = ((seed >> 32) ^ (seed << 10) ^ seed) & 0xffffffffUL;
+	seed ^= seed << 10;
 
-	state->s1 = __seed(i,   2U);
-	state->s2 = __seed(i,   8U);
-	state->s3 = __seed(i,  16U);
-	state->s4 = __seed(i, 128U);
+	/* The values must not be near zero. */
+	state->s1 = seed | 0x100;
+	state->s2 = seed | 0x200;
+	state->s3 = (seed >> 32) | 0x100;
+	state->s4 = (seed >> 32) | 0x200;
 }
 EXPORT_SYMBOL(prandom_seed_state);
-- 
2.39.5

[PATCH next 7/7] random32: Simplify prandom_seed_full_state()

[David Laight]

Instead of offsetting values that would be treated as zero, just set
a bit that ensures they wont be treated as zero.

Reduces the number of initial states from just under 2**113 to 2**109.
This really shouldn't matter.

Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
 lib/random32.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/lib/random32.c b/lib/random32.c
index 1d6468045267..2c5c3519a0f8 100644
--- a/lib/random32.c
+++ b/lib/random32.c
@@ -118,13 +118,13 @@ void prandom_seed_full_state(struct rnd_state __percpu *pcpu_state)
 
 	for_each_possible_cpu(i) {
 		struct rnd_state *state = per_cpu_ptr(pcpu_state, i);
-		u32 seeds[4];
 
-		get_random_bytes(&seeds, sizeof(seeds));
-		state->s1 = __seed(seeds[0],   2U);
-		state->s2 = __seed(seeds[1],   8U);
-		state->s3 = __seed(seeds[2],  16U);
-		state->s4 = __seed(seeds[3], 128U);
+		get_random_bytes(state, sizeof(state));
+		/* The values must not be near zero. */
+		state->s1 |= 0x100;
+		state->s2 |= 0x100;
+		state->s3 |= 0x100;
+		state->s4 |= 0x100;
 
 		prandom_warmup(state);
 	}
-- 
2.39.5