add usage hints to prandom and switch to Xoshiro
Subsystems (3)
v2 cover add usage hints to prandom and switch to Xoshiro
This series builds on top of the crng/master repository, as other prandom commits are already queued there.
v2:
- fix indentation
- add better checks against invalid state
- rebase
With the current cryptographically safe PRNG in drivers/char/random.c fast enough for most purposes, make annoyingly clear, that no one should use the prandom PRNG for cryptographic purposes without known about this.
While looking at the prandom/random32 code, I informed myself about PRNGs and saw that currently fast PRNGs with better statistical properties than LFSR113, which is currently used, are available.
Recent alternatives to consider are in my opinion:
* PCG: https://www.pcg-random.org
* Xoshiro: https://prng.di.unimi.it
While both seem to have good statistical properties, I recommend to chose Xoshiro256++ here, because it seems to be even faster than RNGs from the PCG series.
Furthermore, the authors of Xoshiro provide a small RNG named SplitMix64 for generating high quality seeds for the Xoshiro RNG. By using this in the default way, no further seed checks or state warmup are necessary. This simplifies the PRNG code IMHO.
Markus Theil (4):
prandom: add usage comments for cryptography prandom/random32: switch to Xoshiro256++ prandom/random32: add checks against invalid state test_hash.c: replace custom PRNG by prandom
include/linux/prandom.h | 30 +--- lib/random32.c | 378 +++++++++++++++++++++------------------- lib/tests/test_hash.c | 40 ++--- 3 files changed, 220 insertions(+), 228 deletions(-)
Signature · 1 line
2.49.0
PATCH v2 1/4 prandom: add usage comments for cryptography
Make it more explicit, that the PRNG must not be used for cryptographic purposes.
Future code may also check such things in checkpatch.pl, but it is probably hard to differentiate valid testing code only by looking at paths. Therefore this is left out here by intention.
--- include/linux/prandom.h | 2 ++ lib/random32.c | 6 ++++++ 2 files changed, 8 insertions(+)
include/linux/prandom.h +2 -0
@@ -17,7 +17,9 @@ struct rnd_state {__u32 s1, s2, s3, s4; }; +/* WARNING: this API MUST NOT be used for cryptographic purposes! */ u32 prandom_u32_state (struct rnd_state *state); +/* WARNING: this API MUST NOT be used for cryptographic purposes! */ void prandom_bytes_state (struct rnd_state *state,void *buf,size_t nbytes);void prandom_seed_full_state (struct rnd_state __percpu *pcpu_state);
lib/random32.c +6 -0
@@ -1,5 +1,7 @@// SPDX-License-Identifier: GPL-2.0 /* +* WARNING: this API MUST NOT be used for cryptographic purposes! +* * This is a maximally equidistributed combined Tausworthe generator * based on code from GNU Scientific Library 1.5 (30 Jun 2004) *
@@ -48,6 +50,8 @@* * This is used for pseudo-randomness with no outside seeding. * For more random results, use get_random_u32(). +* +* WARNING: this API MUST NOT be used for cryptographic purposes! */ u32 prandom_u32_state (struct rnd_state *state) {
@@ -70,6 +74,8 @@ EXPORT_SYMBOL(prandom_u32_state);* * This is used for pseudo-randomness with no outside seeding. * For more random results, use get_random_bytes(). +* +* WARNING: this API MUST NOT be used for cryptographic purposes! */ void prandom_bytes_state (struct rnd_state *state,void *buf,size_t bytes) {
Signature · 1 line
2.49.0
PATCH v2 2/4 prandom/random32: switch to Xoshiro256++
In reply to Markus TheilThe current Linux PRNG is based on LFSR113, which means:
- needs some warmup rounds to yield better statistical properties
- seeds/initial states must be of certain structure
- does not pass L’Ecuyer's BigCrush in TestU01
While of course, there is no clear "best" PRNG, replace with Xoshiro256++, which seams to be a sensible replacement, from todays point of view:
- only needs one bit set to 1 in the seed, needs no warmup, when seeded with splitmix64.
- Also has statistical evaluation, like LFSR113.
- Passes BigCrush in TestU01.
The code got smaller, because some edge cases are ruled out now. I kept the test vectors and adapted them to this RNG.
--- include/linux/prandom.h | 28 +--- lib/random32.c | 351 ++++++++++++++++++++-------------------- 2 files changed, 177 insertions(+), 202 deletions(-)
include/linux/prandom.h +4 -24
@@ -14,39 +14,19 @@#include <linux/random.h> struct rnd_state { -__u32 s1, s2, s3, s4; +__u64 s[4 ]; }; +/* WARNING: this API MUST NOT be used for cryptographic purposes! */ +u64 prandom_u64_state (struct rnd_state *state);/* WARNING: this API MUST NOT be used for cryptographic purposes! */ u32 prandom_u32_state (struct rnd_state *state);/* WARNING: this API MUST NOT be used for cryptographic purposes! */ void prandom_bytes_state (struct rnd_state *state,void *buf,size_t nbytes);void prandom_seed_full_state (struct rnd_state __percpu *pcpu_state); +void prandom_seed_state (struct rnd_state *state,u64 seed);#define prandom_init_once (pcpu_state) \ DO_ONCE(prandom_seed_full_state, (pcpu_state)) -/* -* Handle minimum values for seeds -*/ -static inline u32 __seed (u32 x,u32 m) -{ -return (x < m) ? x + m : x; -} - -/** -* prandom_seed_state - set seed for prandom_u32_state(). -* @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 ); -} -#endif
lib/random32.c +173 -178
422 lines not on this page · raw message
Signature · 1 line
2.49.0
PATCH v2 3/4 prandom/random32: add checks against invalid state
In reply to Markus TheilXoshiro256++ will not work in the very unlikely case, that it is used with an all zeroes state. Add checks against this in all necessary places.
--- lib/random32.c | 25 ++++++++++++++++++++++++- 1 file changed, 24 insertions(+), 1 deletion(-)
lib/random32.c +24 -1
@@ -26,6 +26,8 @@#include <linux/slab.h> #include <linux/unaligned.h> +#define IS_ALL_ZERO_STATE (state) (!state->s[0] && !state->s[1] && !state->s[2] && !state->s[3]) +/** * prandom_u64_state - seeded pseudo-random number generator. * @state: pointer to state structure holding seeded state.
@@ -40,6 +42,9 @@ u64 prandom_u64_state(struct rnd_state *state)const u64 result =rol64 (state->s[0 ] + state->s[3 ],23 ) + state->s[0 ];const u64 t = state->s[1 ] <<17 ; +/* defensive check, as this fn returns always zero otherwise */ +BUG_ON (IS_ALL_ZERO_STATE (state)); + state->s[2 ] ^= state->s[0 ]; state->s[3 ] ^= state->s[1 ]; state->s[1 ] ^= state->s[2 ];
@@ -108,6 +113,12 @@ EXPORT_SYMBOL(prandom_bytes_state);* * splitmix64 init as suggested for xoshiro256++ * See: https://prng.di.unimi.it/splitmix64.c +* +* Seeding with this routine cannot result in an +* all zeroes state due to the addition operation +* with the fixed constant 0x9e3779b97f4a7c15! +* Nevertheless check early for such a state +* as a defensive mechanism. */ void prandom_seed_state (struct rnd_state *state,u64 seed) {
@@ -120,6 +131,9 @@ void prandom_seed_state(struct rnd_state *state, u64 seed) z = (z ^ (z >>27 )) *0x94d049bb133111eb ; state->s[i] = z ^ (z >>31 ); } + +/* shall never happen */ +BUG_ON (IS_ALL_ZERO_STATE (state)); }EXPORT_SYMBOL (prandom_seed_state);
@@ -133,7 +147,16 @@ 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); -get_random_bytes (&state->s,sizeof (state->s)); +memset (state,0 ,sizeof (struct rnd_state )); +/* +* Internal state MUST not be all zeroes. Check and repeat if necessary. +* +* Highly unlikely, that we ever need more than one round. Just defensive +* coding, as this could happen in theory. +*/ +while (IS_ALL_ZERO_STATE (state)) { +get_random_bytes (&state->s,sizeof (state->s)); + } } }EXPORT_SYMBOL (prandom_seed_full_state);
Signature · 1 line
2.49.0
PATCH v2 4/4 test_hash.c: replace custom PRNG by prandom
In reply to Markus TheilUse default PRNG, as there is no real need for a custom solution here.
We know the sequence provided by our seed and do not need to do bit magic in order to obtain a non-zero byte. Just iterate a small number of times, if needed.
--- lib/tests/test_hash.c | 40 +++++++++++++--------------------------- 1 file changed, 13 insertions(+), 27 deletions(-)
lib/tests/test_hash.c +13 -27
@@ -17,39 +17,21 @@#include <linux/compiler.h> #include <linux/types.h> #include <linux/module.h> +#include <linux/prandom.h> #include <linux/hash.h> #include <linux/stringhash.h> #include <kunit/test.h> -/* 32-bit XORSHIFT generator. Seed must not be zero. */ -static u32 __attribute_const__ -xorshift (u32 seed) -{ - seed ^= seed <<13 ; - seed ^= seed >>17 ; - seed ^= seed <<5 ; -return seed; -} - -/* Given a non-zero x, returns a non-zero byte. */ -static u8 __attribute_const__ -mod255 (u32 x) -{ - x = (x &0xffff ) + (x >>16 );/* 1 <= x <= 0x1fffe */ - x = (x &0xff ) + (x >>8 );/* 1 <= x <= 0x2fd */ - x = (x &0xff ) + (x >>8 );/* 1 <= x <= 0x100 */ - x = (x &0xff ) + (x >>8 );/* 1 <= x <= 0xff */ -return x; -} -/* Fill the buffer with non-zero bytes. */ -static void fill_buf (char *buf,size_t len,u32 seed) +static void fill_buf (char *buf,size_t len,struct rnd_state *prng) {size_t i;for (i =0 ; i < len; i++) { - seed =xorshift (seed); - buf[i] =mod255 (seed); +/* we know our seeds, no need to worry about endless runtime */ +do { + buf[i] = (u8 )prandom_u32_state (prng); + }while (!buf[i]); } }
@@ -143,11 +125,13 @@ test_int_hash(struct kunit *test, unsigned long long h64, u32 hash_or[2][33])static void test_string_or (struct kunit *test) { -char buf[SIZE +1 ]; +struct rnd_state prng;u32 string_or =0 ; +char buf[SIZE +1 ];int i, j; -fill_buf (buf,SIZE ,1 ); +prandom_seed_state (&prng,0x1 ); +fill_buf (buf,SIZE , &prng);/* Test every possible non-empty substring in the buffer. */ for (j =SIZE ; j >0 ; --j) {
@@ -171,9 +155,11 @@ static void test_hash_or(struct kunit *test)char buf[SIZE +1 ];u32 hash_or[2 ][33 ] = { {0 , } };unsigned long long h64 =0 ; +struct rnd_state prng;int i, j; -fill_buf (buf,SIZE ,1 ); +prandom_seed_state (&prng,0x1 ); +fill_buf (buf,SIZE , &prng);/* Test every possible non-empty substring in the buffer. */ for (j =SIZE ; j >0 ; --j) {
Signature · 1 line
2.49.0