* [PATCH 0/2] prandom: add crypto warnings and switch to new PRNG
@ 2025-02-14 8:18 Markus Theil
2025-02-14 8:18 ` [PATCH 1/2] prandom: add usage comments for cryptography Markus Theil
2025-02-14 8:18 ` [PATCH 2/2] prandom/random32: switch to Xoshiro256++ Markus Theil
0 siblings, 2 replies; 6+ messages in thread
From: Markus Theil @ 2025-02-14 8:18 UTC (permalink / raw)
To: linux-crypto; +Cc: davem, netdev, akpm, Jason, Markus Theil
This series builds on top of the series:
"prandom: remove next_pseudo_random32."
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 (2):
prandom: add usage comments for cryptography
prandom/random32: switch to Xoshiro256++
include/linux/prandom.h | 30 +---
lib/random32.c | 351 ++++++++++++++++++++--------------------
2 files changed, 180 insertions(+), 201 deletions(-)
--
2.47.2
^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH 1/2] prandom: add usage comments for cryptography
2025-02-14 8:18 [PATCH 0/2] prandom: add crypto warnings and switch to new PRNG Markus Theil
@ 2025-02-14 8:18 ` Markus Theil
2025-02-14 8:18 ` [PATCH 2/2] prandom/random32: switch to Xoshiro256++ Markus Theil
1 sibling, 0 replies; 6+ messages in thread
From: Markus Theil @ 2025-02-14 8:18 UTC (permalink / raw)
To: linux-crypto; +Cc: davem, netdev, akpm, Jason, Markus Theil
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.
Signed-off-by: Markus Theil <theil.markus@gmail.com>
---
include/linux/prandom.h | 2 ++
lib/random32.c | 6 ++++++
2 files changed, 8 insertions(+)
diff --git a/include/linux/prandom.h b/include/linux/prandom.h
index ff7dcc3fa105..63d1fe4b30c8 100644
--- a/include/linux/prandom.h
+++ b/include/linux/prandom.h
@@ -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);
diff --git a/lib/random32.c b/lib/random32.c
index 24e7acd9343f..c808745a4b53 100644
--- a/lib/random32.c
+++ b/lib/random32.c
@@ -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)
{
--
2.47.2
^ permalink raw reply related [flat|nested] 6+ messages in thread
* [PATCH 2/2] prandom/random32: switch to Xoshiro256++
2025-02-14 8:18 [PATCH 0/2] prandom: add crypto warnings and switch to new PRNG Markus Theil
2025-02-14 8:18 ` [PATCH 1/2] prandom: add usage comments for cryptography Markus Theil
@ 2025-02-14 8:18 ` Markus Theil
2025-02-17 11:18 ` Simon Horman
1 sibling, 1 reply; 6+ messages in thread
From: Markus Theil @ 2025-02-14 8:18 UTC (permalink / raw)
To: linux-crypto; +Cc: davem, netdev, akpm, Jason, Markus Theil
The 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.
Signed-off-by: Markus Theil <theil.markus@gmail.com>
---
include/linux/prandom.h | 28 +---
lib/random32.c | 347 +++++++++++++++++++---------------------
2 files changed, 173 insertions(+), 202 deletions(-)
diff --git a/include/linux/prandom.h b/include/linux/prandom.h
index 63d1fe4b30c8..0a5c12bee5e1 100644
--- a/include/linux/prandom.h
+++ b/include/linux/prandom.h
@@ -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! */
u32 prandom_u32_state(struct rnd_state *state);
/* WARNING: this API MUST NOT be used for cryptographic purposes! */
+u64 prandom_u64_state(struct rnd_state *state);
void prandom_bytes_state(struct rnd_state *state, void *buf, size_t nbytes);
+
+void prandom_seed_state(struct rnd_state *state, u64 seed);
void prandom_seed_full_state(struct rnd_state __percpu *pcpu_state);
#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
diff --git a/lib/random32.c b/lib/random32.c
index c808745a4b53..50cbff0b995e 100644
--- a/lib/random32.c
+++ b/lib/random32.c
@@ -2,36 +2,18 @@
/*
* 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)
+ * xoshiro256++ is a high-quality non-cryptographic
+ * pseudorandom number generator (PRNG).
*
- * lfsr113 version:
+ * For a more detailed description, see:
+ * https://vigna.di.unimi.it/ftp/papers/ScrambledLinear.pdf
*
- * x_n = (s1_n ^ s2_n ^ s3_n ^ s4_n)
+ * Usage Advice: As the cryptographic random subsystem is really fast these days,
+ * you should come up with a good reason, to introduce PRNG usage into new code.
+ * Consider its usage, when a predictable/repeatable sequence is needed for
+ * testing purposes. Prefer to use get_random_32(), when possible.
*
- * s1_{n+1} = (((s1_n & 4294967294) << 18) ^ (((s1_n << 6) ^ s1_n) >> 13))
- * s2_{n+1} = (((s2_n & 4294967288) << 2) ^ (((s2_n << 2) ^ s2_n) >> 27))
- * s3_{n+1} = (((s3_n & 4294967280) << 7) ^ (((s3_n << 13) ^ s3_n) >> 21))
- * s4_{n+1} = (((s4_n & 4294967168) << 13) ^ (((s4_n << 3) ^ s4_n) >> 12))
- *
- * The period of this generator is about 2^113 (see erratum paper).
- *
- * From: P. L'Ecuyer, "Maximally Equidistributed Combined Tausworthe
- * Generators", Mathematics of Computation, 65, 213 (1996), 203--213:
- * http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
- * ftp://ftp.iro.umontreal.ca/pub/simulation/lecuyer/papers/tausme.ps
- *
- * There is an erratum in the paper "Tables of Maximally Equidistributed
- * Combined LFSR Generators", Mathematics of Computation, 68, 225 (1999),
- * 261--269: http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
- *
- * ... the k_j most significant bits of z_j must be non-zero,
- * for each j. (Note: this restriction also applies to the
- * computer code given in [4], but was mistakenly not mentioned
- * in that paper.)
- *
- * This affects the seeding procedure by imposing the requirement
- * s1 > 1, s2 > 7, s3 > 15, s4 > 127.
+ * Based on: https://prng.di.unimi.it/xoshiro256plusplus.c
*/
#include <linux/types.h>
@@ -44,6 +26,33 @@
#include <linux/slab.h>
#include <linux/unaligned.h>
+/**
+ * prandom_u64_state - seeded pseudo-random number generator.
+ * @state: pointer to state structure holding seeded state.
+ *
+ * This is used for pseudo-randomness with no outside seeding.
+ * For more random results, use get_random_u64().
+ *
+ * WARNING: this API MUST NOT be used for cryptographic purposes!
+ */
+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;
+
+ state->s[2] ^= state->s[0];
+ state->s[3] ^= state->s[1];
+ state->s[1] ^= state->s[2];
+ state->s[0] ^= state->s[3];
+
+ state->s[2] ^= t;
+
+ state->s[3] = rol64(state->s[3], 45);
+
+ return result;
+}
+EXPORT_SYMBOL(prandom_u64_state);
+
/**
* prandom_u32_state - seeded pseudo-random number generator.
* @state: pointer to state structure holding seeded state.
@@ -55,13 +64,7 @@
*/
u32 prandom_u32_state(struct rnd_state *state)
{
-#define TAUSWORTHE(s, a, b, c, d) ((s & c) << d) ^ (((s << a) ^ s) >> b)
- state->s1 = TAUSWORTHE(state->s1, 6U, 13U, 4294967294U, 18U);
- state->s2 = TAUSWORTHE(state->s2, 2U, 27U, 4294967288U, 2U);
- 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 (u32) prandom_u64_state(state);
}
EXPORT_SYMBOL(prandom_u32_state);
@@ -81,14 +84,14 @@ void prandom_bytes_state(struct rnd_state *state, void *buf, size_t bytes)
{
u8 *ptr = buf;
- while (bytes >= sizeof(u32)) {
- put_unaligned(prandom_u32_state(state), (u32 *) ptr);
- ptr += sizeof(u32);
- bytes -= sizeof(u32);
+ while (bytes >= sizeof(u64)) {
+ put_unaligned(prandom_u64_state(state), (u64 *) ptr);
+ ptr += sizeof(u64);
+ bytes -= sizeof(u64);
}
if (bytes > 0) {
- u32 rem = prandom_u32_state(state);
+ u64 rem = prandom_u64_state(state);
do {
*ptr++ = (u8) rem;
bytes--;
@@ -98,20 +101,27 @@ void prandom_bytes_state(struct rnd_state *state, void *buf, size_t bytes)
}
EXPORT_SYMBOL(prandom_bytes_state);
-static void prandom_warmup(struct rnd_state *state)
+/**
+ * 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.
+ *
+ * splitmix64 init as suggested for xoshiro256++
+ * See: https://prng.di.unimi.it/splitmix64.c
+ */
+void prandom_seed_state(struct rnd_state *state, u64 seed)
{
- /* Calling RNG ten times to satisfy recurrence condition */
- prandom_u32_state(state);
- prandom_u32_state(state);
- prandom_u32_state(state);
- prandom_u32_state(state);
- prandom_u32_state(state);
- prandom_u32_state(state);
- prandom_u32_state(state);
- prandom_u32_state(state);
- prandom_u32_state(state);
- prandom_u32_state(state);
+ int i;
+
+ for (i = 0; i < ARRAY_SIZE(state->s); ++i) {
+ seed += 0x9e3779b97f4a7c15;
+ u64 z = seed;
+ z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
+ z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
+ state->s[i] = z ^ (z >> 31);
+ }
}
+EXPORT_SYMBOL(prandom_seed_state);
void prandom_seed_full_state(struct rnd_state __percpu *pcpu_state)
{
@@ -119,15 +129,7 @@ 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);
-
- prandom_warmup(state);
+ get_random_bytes(&state->s, sizeof(state->s));
}
}
EXPORT_SYMBOL(prandom_seed_full_state);
@@ -137,10 +139,10 @@ static struct prandom_test1 {
u32 seed;
u32 result;
} test1[] = {
- { 1U, 3484351685U },
- { 2U, 2623130059U },
- { 3U, 3125133893U },
- { 4U, 984847254U },
+ { 1U, 1862517403U },
+ { 2U, 3049585706U },
+ { 3U, 3105450281U },
+ { 4U, 2527704881U },
};
static struct prandom_test2 {
@@ -148,118 +150,109 @@ static struct prandom_test2 {
u32 iteration;
u32 result;
} test2[] = {
- /* Test cases against taus113 from GSL library. */
- { 931557656U, 959U, 2975593782U },
- { 1339693295U, 876U, 3887776532U },
- { 1545556285U, 961U, 1615538833U },
- { 601730776U, 723U, 1776162651U },
- { 1027516047U, 687U, 511983079U },
- { 416526298U, 700U, 916156552U },
- { 1395522032U, 652U, 2222063676U },
- { 366221443U, 617U, 2992857763U },
- { 1539836965U, 714U, 3783265725U },
- { 556206671U, 994U, 799626459U },
- { 684907218U, 799U, 367789491U },
- { 2121230701U, 931U, 2115467001U },
- { 1668516451U, 644U, 3620590685U },
- { 768046066U, 883U, 2034077390U },
- { 1989159136U, 833U, 1195767305U },
- { 536585145U, 996U, 3577259204U },
- { 1008129373U, 642U, 1478080776U },
- { 1740775604U, 939U, 1264980372U },
- { 1967883163U, 508U, 10734624U },
- { 1923019697U, 730U, 3821419629U },
- { 442079932U, 560U, 3440032343U },
- { 1961302714U, 845U, 841962572U },
- { 2030205964U, 962U, 1325144227U },
- { 1160407529U, 507U, 240940858U },
- { 635482502U, 779U, 4200489746U },
- { 1252788931U, 699U, 867195434U },
- { 1961817131U, 719U, 668237657U },
- { 1071468216U, 983U, 917876630U },
- { 1281848367U, 932U, 1003100039U },
- { 582537119U, 780U, 1127273778U },
- { 1973672777U, 853U, 1071368872U },
- { 1896756996U, 762U, 1127851055U },
- { 847917054U, 500U, 1717499075U },
- { 1240520510U, 951U, 2849576657U },
- { 1685071682U, 567U, 1961810396U },
- { 1516232129U, 557U, 3173877U },
- { 1208118903U, 612U, 1613145022U },
- { 1817269927U, 693U, 4279122573U },
- { 1510091701U, 717U, 638191229U },
- { 365916850U, 807U, 600424314U },
- { 399324359U, 702U, 1803598116U },
- { 1318480274U, 779U, 2074237022U },
- { 697758115U, 840U, 1483639402U },
- { 1696507773U, 840U, 577415447U },
- { 2081979121U, 981U, 3041486449U },
- { 955646687U, 742U, 3846494357U },
- { 1250683506U, 749U, 836419859U },
- { 595003102U, 534U, 366794109U },
- { 47485338U, 558U, 3521120834U },
- { 619433479U, 610U, 3991783875U },
- { 704096520U, 518U, 4139493852U },
- { 1712224984U, 606U, 2393312003U },
- { 1318233152U, 922U, 3880361134U },
- { 855572992U, 761U, 1472974787U },
- { 64721421U, 703U, 683860550U },
- { 678931758U, 840U, 380616043U },
- { 692711973U, 778U, 1382361947U },
- { 677703619U, 530U, 2826914161U },
- { 92393223U, 586U, 1522128471U },
- { 1222592920U, 743U, 3466726667U },
- { 358288986U, 695U, 1091956998U },
- { 1935056945U, 958U, 514864477U },
- { 735675993U, 990U, 1294239989U },
- { 1560089402U, 897U, 2238551287U },
- { 70616361U, 829U, 22483098U },
- { 368234700U, 731U, 2913875084U },
- { 20221190U, 879U, 1564152970U },
- { 539444654U, 682U, 1835141259U },
- { 1314987297U, 840U, 1801114136U },
- { 2019295544U, 645U, 3286438930U },
- { 469023838U, 716U, 1637918202U },
- { 1843754496U, 653U, 2562092152U },
- { 400672036U, 809U, 4264212785U },
- { 404722249U, 965U, 2704116999U },
- { 600702209U, 758U, 584979986U },
- { 519953954U, 667U, 2574436237U },
- { 1658071126U, 694U, 2214569490U },
- { 420480037U, 749U, 3430010866U },
- { 690103647U, 969U, 3700758083U },
- { 1029424799U, 937U, 3787746841U },
- { 2012608669U, 506U, 3362628973U },
- { 1535432887U, 998U, 42610943U },
- { 1330635533U, 857U, 3040806504U },
- { 1223800550U, 539U, 3954229517U },
- { 1322411537U, 680U, 3223250324U },
- { 1877847898U, 945U, 2915147143U },
- { 1646356099U, 874U, 965988280U },
- { 805687536U, 744U, 4032277920U },
- { 1948093210U, 633U, 1346597684U },
- { 392609744U, 783U, 1636083295U },
- { 690241304U, 770U, 1201031298U },
- { 1360302965U, 696U, 1665394461U },
- { 1220090946U, 780U, 1316922812U },
- { 447092251U, 500U, 3438743375U },
- { 1613868791U, 592U, 828546883U },
- { 523430951U, 548U, 2552392304U },
- { 726692899U, 810U, 1656872867U },
- { 1364340021U, 836U, 3710513486U },
- { 1986257729U, 931U, 935013962U },
- { 407983964U, 921U, 728767059U },
+ /* Test cases against Xoshiro256++, generated with reference impl. */
+ { 931557656U, 959U, 2221272722U },
+ { 1339693295U, 876U, 12322103U },
+ { 1545556285U, 961U, 2793306339U },
+ { 601730776U, 723U, 186699327U },
+ { 1027516047U, 687U, 3385354088U },
+ { 416526298U, 700U, 3047662436U },
+ { 1395522032U, 652U, 370169503U },
+ { 366221443U, 617U, 2468792816U },
+ { 1539836965U, 714U, 4178175423U },
+ { 556206671U, 994U, 1935910425U },
+ { 684907218U, 799U, 2892366361U },
+ { 2121230701U, 931U, 2395880533U },
+ { 1668516451U, 644U, 659315062U },
+ { 768046066U, 883U, 729262650U },
+ { 1989159136U, 833U, 44268867U },
+ { 536585145U, 996U, 3734292685U },
+ { 1008129373U, 642U, 3779097844U },
+ { 1740775604U, 939U, 958440770U },
+ { 1967883163U, 508U, 2766790334U },
+ { 1923019697U, 730U, 4188718967U },
+ { 442079932U, 560U, 2658351430U },
+ { 1961302714U, 845U, 418725413U },
+ { 2030205964U, 962U, 3541720353U },
+ { 1160407529U, 507U, 155686916U },
+ { 635482502U, 779U, 2954399934U },
+ { 1252788931U, 699U, 3195364074U },
+ { 1961817131U, 719U, 3860285454U },
+ { 1071468216U, 983U, 2558711391U },
+ { 1281848367U, 932U, 2429019683U },
+ { 582537119U, 780U, 2251637575U },
+ { 1973672777U, 853U, 2686341687U },
+ { 1896756996U, 762U, 3853948474U },
+ { 847917054U, 500U, 1352384361U },
+ { 1240520510U, 951U, 424294678U },
+ { 1685071682U, 567U, 1127358663U },
+ { 1516232129U, 557U, 2438163725U },
+ { 1208118903U, 612U, 494560814U },
+ { 1817269927U, 693U, 2296243096U },
+ { 1510091701U, 717U, 2522390997U },
+ { 365916850U, 807U, 1704622356U },
+ { 399324359U, 702U, 1692076319U },
+ { 1318480274U, 779U, 3132074148U },
+ { 697758115U, 840U, 2298934293U },
+ { 1696507773U, 840U, 460426950U },
+ { 2081979121U, 981U, 2030259222U },
+ { 955646687U, 742U, 849374769U },
+ { 1250683506U, 749U, 3793648395U },
+ { 595003102U, 534U, 312261219U },
+ { 47485338U, 558U, 1498074521U },
+ { 619433479U, 610U, 3298978919U },
+ { 704096520U, 518U, 1859635041U },
+ { 1712224984U, 606U, 2636341373U },
+ { 1318233152U, 922U, 4294083073U },
+ { 855572992U, 761U, 1398432208U },
+ { 64721421U, 703U, 2917659579U },
+ { 678931758U, 840U, 2610263429U },
+ { 692711973U, 778U, 2364471195U },
+ { 677703619U, 530U, 4293322414U },
+ { 92393223U, 586U, 2200038234U },
+ { 1222592920U, 743U, 3902404436U },
+ { 358288986U, 695U, 4187968216U },
+ { 1935056945U, 958U, 2216763617U },
+ { 735675993U, 990U, 3851267177U },
+ { 1560089402U, 897U, 3110095036U },
+ { 70616361U, 829U, 2727884311U },
+ { 368234700U, 731U, 1394533121U },
+ { 20221190U, 879U, 2426527948U },
+ { 539444654U, 682U, 3323050847U },
+ { 1314987297U, 840U, 1532766257U },
+ { 2019295544U, 645U, 2824742190U },
+ { 469023838U, 716U, 2626662944U },
+ { 1843754496U, 653U, 3912965452U },
+ { 400672036U, 809U, 794673667U },
+ { 404722249U, 965U, 2590267245U },
+ { 600702209U, 758U, 3742697327U },
+ { 519953954U, 667U, 909153960U },
+ { 1658071126U, 694U, 1016441204U },
+ { 420480037U, 749U, 4007274669U },
+ { 690103647U, 969U, 2262636339U },
+ { 1029424799U, 937U, 1940659603U },
+ { 2012608669U, 506U, 239338087U },
+ { 1535432887U, 998U, 1889887018U },
+ { 1330635533U, 857U, 4029849650U },
+ { 1223800550U, 539U, 678829248U },
+ { 1322411537U, 680U, 2745139632U },
+ { 1877847898U, 945U, 153715577U },
+ { 1646356099U, 874U, 525516737U },
+ { 805687536U, 744U, 1564399105U },
+ { 1948093210U, 633U, 507042967U },
+ { 392609744U, 783U, 33573161U },
+ { 690241304U, 770U, 1551691277U },
+ { 1360302965U, 696U, 391079011U },
+ { 1220090946U, 780U, 2587343386U },
+ { 447092251U, 500U, 3335665101U },
+ { 1613868791U, 592U, 131974931U },
+ { 523430951U, 548U, 3871675719U },
+ { 726692899U, 810U, 2919536533U },
+ { 1364340021U, 836U, 1695810824U },
+ { 1986257729U, 931U, 550308813U },
+ { 407983964U, 921U, 360202562U }
};
-static void prandom_state_selftest_seed(struct rnd_state *state, u32 seed)
-{
-#define LCG(x) ((x) * 69069U) /* super-duper LCG */
- state->s1 = __seed(LCG(seed), 2U);
- state->s2 = __seed(LCG(state->s1), 8U);
- state->s3 = __seed(LCG(state->s2), 16U);
- state->s4 = __seed(LCG(state->s3), 128U);
-}
-
static int __init prandom_state_selftest(void)
{
int i, j, errors = 0, runs = 0;
@@ -268,8 +261,7 @@ static int __init prandom_state_selftest(void)
for (i = 0; i < ARRAY_SIZE(test1); i++) {
struct rnd_state state;
- prandom_state_selftest_seed(&state, test1[i].seed);
- prandom_warmup(&state);
+ prandom_seed_state(&state, test1[i].seed);
if (test1[i].result != prandom_u32_state(&state))
error = true;
@@ -283,8 +275,7 @@ static int __init prandom_state_selftest(void)
for (i = 0; i < ARRAY_SIZE(test2); i++) {
struct rnd_state state;
- prandom_state_selftest_seed(&state, test2[i].seed);
- prandom_warmup(&state);
+ prandom_seed_state(&state, test2[i].seed);
for (j = 0; j < test2[i].iteration - 1; j++)
prandom_u32_state(&state);
--
2.47.2
^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH 2/2] prandom/random32: switch to Xoshiro256++
2025-02-14 8:18 ` [PATCH 2/2] prandom/random32: switch to Xoshiro256++ Markus Theil
@ 2025-02-17 11:18 ` Simon Horman
2025-03-22 18:24 ` Markus Theil
0 siblings, 1 reply; 6+ messages in thread
From: Simon Horman @ 2025-02-17 11:18 UTC (permalink / raw)
To: Markus Theil; +Cc: linux-crypto, davem, netdev, akpm, Jason
On Fri, Feb 14, 2025 at 09:18:40AM +0100, Markus Theil wrote:
> The 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.
>
> Signed-off-by: Markus Theil <theil.markus@gmail.com>
...
> diff --git a/lib/random32.c b/lib/random32.c
...
> +/**
> + * 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.
> + *
> + * splitmix64 init as suggested for xoshiro256++
> + * See: https://prng.di.unimi.it/splitmix64.c
> + */
> +void prandom_seed_state(struct rnd_state *state, u64 seed)
> {
> - /* Calling RNG ten times to satisfy recurrence condition */
> - prandom_u32_state(state);
> - prandom_u32_state(state);
> - prandom_u32_state(state);
> - prandom_u32_state(state);
> - prandom_u32_state(state);
> - prandom_u32_state(state);
> - prandom_u32_state(state);
> - prandom_u32_state(state);
> - prandom_u32_state(state);
> - prandom_u32_state(state);
> + int i;
> +
> + for (i = 0; i < ARRAY_SIZE(state->s); ++i) {
> + seed += 0x9e3779b97f4a7c15;
> + u64 z = seed;
> + z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
> + z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
> + state->s[i] = z ^ (z >> 31);
nit: The indentation seems off here.
> + }
> }
> +EXPORT_SYMBOL(prandom_seed_state);
...
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH 2/2] prandom/random32: switch to Xoshiro256++
2025-02-17 11:18 ` Simon Horman
@ 2025-03-22 18:24 ` Markus Theil
2025-03-24 17:32 ` Simon Horman
0 siblings, 1 reply; 6+ messages in thread
From: Markus Theil @ 2025-03-22 18:24 UTC (permalink / raw)
To: Simon Horman; +Cc: linux-crypto, davem, netdev, akpm, Jason
[-- Attachment #1.1.1: Type: text/plain, Size: 2124 bytes --]
On 2/17/25 12:18, Simon Horman wrote:
> On Fri, Feb 14, 2025 at 09:18:40AM +0100, Markus Theil wrote:
>> The 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.
>>
>> Signed-off-by: Markus Theil <theil.markus@gmail.com>
> ...
>
>> diff --git a/lib/random32.c b/lib/random32.c
> ...
>
>> +/**
>> + * 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.
>> + *
>> + * splitmix64 init as suggested for xoshiro256++
>> + * See: https://prng.di.unimi.it/splitmix64.c
>> + */
>> +void prandom_seed_state(struct rnd_state *state, u64 seed)
>> {
>> - /* Calling RNG ten times to satisfy recurrence condition */
>> - prandom_u32_state(state);
>> - prandom_u32_state(state);
>> - prandom_u32_state(state);
>> - prandom_u32_state(state);
>> - prandom_u32_state(state);
>> - prandom_u32_state(state);
>> - prandom_u32_state(state);
>> - prandom_u32_state(state);
>> - prandom_u32_state(state);
>> - prandom_u32_state(state);
>> + int i;
>> +
>> + for (i = 0; i < ARRAY_SIZE(state->s); ++i) {
>> + seed += 0x9e3779b97f4a7c15;
>> + u64 z = seed;
>> + z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
>> + z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
>> + state->s[i] = z ^ (z >> 31);
> nit: The indentation seems off here.
Shall I resend for this line?
>> + }
>> }
>> +EXPORT_SYMBOL(prandom_seed_state);
> ...
[-- Attachment #1.1.2: OpenPGP public key --]
[-- Type: application/pgp-keys, Size: 3211 bytes --]
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 840 bytes --]
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH 2/2] prandom/random32: switch to Xoshiro256++
2025-03-22 18:24 ` Markus Theil
@ 2025-03-24 17:32 ` Simon Horman
0 siblings, 0 replies; 6+ messages in thread
From: Simon Horman @ 2025-03-24 17:32 UTC (permalink / raw)
To: Markus Theil; +Cc: linux-crypto, davem, netdev, akpm, Jason
On Sat, Mar 22, 2025 at 07:24:57PM +0100, Markus Theil wrote:
> On 2/17/25 12:18, Simon Horman wrote:
> > On Fri, Feb 14, 2025 at 09:18:40AM +0100, Markus Theil wrote:
> > > The 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.
> > >
> > > Signed-off-by: Markus Theil <theil.markus@gmail.com>
> > ...
> >
> > > diff --git a/lib/random32.c b/lib/random32.c
> > ...
> >
> > > +/**
> > > + * 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.
> > > + *
> > > + * splitmix64 init as suggested for xoshiro256++
> > > + * See: https://prng.di.unimi.it/splitmix64.c
> > > + */
> > > +void prandom_seed_state(struct rnd_state *state, u64 seed)
> > > {
> > > - /* Calling RNG ten times to satisfy recurrence condition */
> > > - prandom_u32_state(state);
> > > - prandom_u32_state(state);
> > > - prandom_u32_state(state);
> > > - prandom_u32_state(state);
> > > - prandom_u32_state(state);
> > > - prandom_u32_state(state);
> > > - prandom_u32_state(state);
> > > - prandom_u32_state(state);
> > > - prandom_u32_state(state);
> > > - prandom_u32_state(state);
> > > + int i;
> > > +
> > > + for (i = 0; i < ARRAY_SIZE(state->s); ++i) {
> > > + seed += 0x9e3779b97f4a7c15;
> > > + u64 z = seed;
> > > + z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
> > > + z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
> > > + state->s[i] = z ^ (z >> 31);
> > nit: The indentation seems off here.
> Shall I resend for this line?
The maintainer may think otherwise.
But in my opinion that would be a good idea.
> > > + }
> > > }
> > > +EXPORT_SYMBOL(prandom_seed_state);
> > ...
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2025-03-24 17:32 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2025-02-14 8:18 [PATCH 0/2] prandom: add crypto warnings and switch to new PRNG Markus Theil
2025-02-14 8:18 ` [PATCH 1/2] prandom: add usage comments for cryptography Markus Theil
2025-02-14 8:18 ` [PATCH 2/2] prandom/random32: switch to Xoshiro256++ Markus Theil
2025-02-17 11:18 ` Simon Horman
2025-03-22 18:24 ` Markus Theil
2025-03-24 17:32 ` Simon Horman
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).