From 51c37a70aaa3f95773af560e6db3073520513912 Mon Sep 17 00:00:00 2001 From: Daniel Borkmann Date: Mon, 11 Nov 2013 12:20:32 +0100 Subject: random32: fix off-by-one in seeding requirement For properly initialising the Tausworthe generator [1], we have a strict seeding requirement, that is, s1 > 1, s2 > 7, s3 > 15. Commit 697f8d0348 ("random32: seeding improvement") introduced a __seed() function that imposes boundary checks proposed by the errata paper [2] to properly ensure above conditions. However, we're off by one, as the function is implemented as: "return (x < m) ? x + m : x;", and called with __seed(X, 1), __seed(X, 7), __seed(X, 15). Thus, an unwanted seed of 1, 7, 15 would be possible, whereas the lower boundary should actually be of at least 2, 8, 16, just as GSL does. Fix this, as otherwise an initialization with an unwanted seed could have the effect that Tausworthe's PRNG properties cannot not be ensured. Note that this PRNG is *not* used for cryptography in the kernel. [1] http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps [2] http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps Joint work with Hannes Frederic Sowa. Fixes: 697f8d0348a6 ("random32: seeding improvement") Cc: Stephen Hemminger Cc: Florian Weimer Cc: Theodore Ts'o Signed-off-by: Daniel Borkmann Signed-off-by: Hannes Frederic Sowa Signed-off-by: David S. Miller diff --git a/include/linux/random.h b/include/linux/random.h index 6312dd9..bf9085e 100644 --- a/include/linux/random.h +++ b/include/linux/random.h @@ -50,9 +50,9 @@ static inline void prandom_seed_state(struct rnd_state *state, u64 seed) { u32 i = (seed >> 32) ^ (seed << 10) ^ seed; - state->s1 = __seed(i, 1); - state->s2 = __seed(i, 7); - state->s3 = __seed(i, 15); + state->s1 = __seed(i, 2); + state->s2 = __seed(i, 8); + state->s3 = __seed(i, 16); } #ifdef CONFIG_ARCH_RANDOM diff --git a/lib/random32.c b/lib/random32.c index 52280d5..01e8890 100644 --- a/lib/random32.c +++ b/lib/random32.c @@ -141,7 +141,7 @@ void prandom_seed(u32 entropy) */ for_each_possible_cpu (i) { struct rnd_state *state = &per_cpu(net_rand_state, i); - state->s1 = __seed(state->s1 ^ entropy, 1); + state->s1 = __seed(state->s1 ^ entropy, 2); } } EXPORT_SYMBOL(prandom_seed); @@ -158,9 +158,9 @@ static int __init prandom_init(void) struct rnd_state *state = &per_cpu(net_rand_state,i); #define LCG(x) ((x) * 69069) /* super-duper LCG */ - state->s1 = __seed(LCG(i + jiffies), 1); - state->s2 = __seed(LCG(state->s1), 7); - state->s3 = __seed(LCG(state->s2), 15); + state->s1 = __seed(LCG(i + jiffies), 2); + state->s2 = __seed(LCG(state->s1), 8); + state->s3 = __seed(LCG(state->s2), 16); /* "warm it up" */ prandom_u32_state(state); @@ -187,9 +187,9 @@ static int __init prandom_reseed(void) u32 seeds[3]; get_random_bytes(&seeds, sizeof(seeds)); - state->s1 = __seed(seeds[0], 1); - state->s2 = __seed(seeds[1], 7); - state->s3 = __seed(seeds[2], 15); + state->s1 = __seed(seeds[0], 2); + state->s2 = __seed(seeds[1], 8); + state->s3 = __seed(seeds[2], 16); /* mix it in */ prandom_u32_state(state); -- cgit v0.10.2 From 6d31920246a9fc80be4f16acd27c0bbe8d7b8494 Mon Sep 17 00:00:00 2001 From: Hannes Frederic Sowa Date: Mon, 11 Nov 2013 12:20:33 +0100 Subject: random32: add periodic reseeding The current Tausworthe PRNG is never reseeded with truly random data after the first attempt in late_initcall. As this PRNG is used for some critical random data as e.g. UDP port randomization we should try better and reseed the PRNG once in a while with truly random data from get_random_bytes(). When we reseed with prandom_seed we now make also sure to throw the first output away. This suffices the reseeding procedure. The delay calculation is based on a proposal from Eric Dumazet. Joint work with Daniel Borkmann. Cc: Eric Dumazet Cc: Theodore Ts'o Signed-off-by: Hannes Frederic Sowa Signed-off-by: Daniel Borkmann Signed-off-by: David S. Miller diff --git a/lib/random32.c b/lib/random32.c index 01e8890..12215df 100644 --- a/lib/random32.c +++ b/lib/random32.c @@ -142,6 +142,7 @@ void prandom_seed(u32 entropy) for_each_possible_cpu (i) { struct rnd_state *state = &per_cpu(net_rand_state, i); state->s1 = __seed(state->s1 ^ entropy, 2); + prandom_u32_state(state); } } EXPORT_SYMBOL(prandom_seed); @@ -174,6 +175,27 @@ static int __init prandom_init(void) } core_initcall(prandom_init); +static void __prandom_timer(unsigned long dontcare); +static DEFINE_TIMER(seed_timer, __prandom_timer, 0, 0); + +static void __prandom_timer(unsigned long dontcare) +{ + u32 entropy; + + get_random_bytes(&entropy, sizeof(entropy)); + prandom_seed(entropy); + /* reseed every ~60 seconds, in [40 .. 80) interval with slack */ + seed_timer.expires = jiffies + (40 * HZ + (prandom_u32() % (40 * HZ))); + add_timer(&seed_timer); +} + +static void prandom_start_seed_timer(void) +{ + set_timer_slack(&seed_timer, HZ); + seed_timer.expires = jiffies + 40 * HZ; + add_timer(&seed_timer); +} + /* * Generate better values after random number generator * is fully initialized. @@ -194,6 +216,7 @@ static int __init prandom_reseed(void) /* mix it in */ prandom_u32_state(state); } + prandom_start_seed_timer(); return 0; } late_initcall(prandom_reseed); -- cgit v0.10.2 From 4af712e8df998475736f3e2727701bd31e3751a9 Mon Sep 17 00:00:00 2001 From: Hannes Frederic Sowa Date: Mon, 11 Nov 2013 12:20:34 +0100 Subject: random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized The Tausworthe PRNG is initialized at late_initcall time. At that time the entropy pool serving get_random_bytes is not filled sufficiently. This patch adds an additional reseeding step as soon as the nonblocking pool gets marked as initialized. On some machines it might be possible that late_initcall gets called after the pool has been initialized. In this situation we won't reseed again. (A call to prandom_seed_late blocks later invocations of early reseed attempts.) Joint work with Daniel Borkmann. Cc: Eric Dumazet Cc: Theodore Ts'o Signed-off-by: Hannes Frederic Sowa Signed-off-by: Daniel Borkmann Acked-by: "Theodore Ts'o" Signed-off-by: David S. Miller diff --git a/drivers/char/random.c b/drivers/char/random.c index 7a744d3..4fe5609 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -603,8 +603,11 @@ retry: if (!r->initialized && nbits > 0) { r->entropy_total += nbits; - if (r->entropy_total > 128) + if (r->entropy_total > 128) { r->initialized = 1; + if (r == &nonblocking_pool) + prandom_reseed_late(); + } } trace_credit_entropy_bits(r->name, nbits, entropy_count, diff --git a/include/linux/random.h b/include/linux/random.h index bf9085e..5117ae3 100644 --- a/include/linux/random.h +++ b/include/linux/random.h @@ -29,6 +29,7 @@ unsigned long randomize_range(unsigned long start, unsigned long end, unsigned l u32 prandom_u32(void); void prandom_bytes(void *buf, int nbytes); void prandom_seed(u32 seed); +void prandom_reseed_late(void); u32 prandom_u32_state(struct rnd_state *); void prandom_bytes_state(struct rnd_state *state, void *buf, int nbytes); diff --git a/lib/random32.c b/lib/random32.c index 12215df..9f2f2fb 100644 --- a/lib/random32.c +++ b/lib/random32.c @@ -200,9 +200,18 @@ static void prandom_start_seed_timer(void) * Generate better values after random number generator * is fully initialized. */ -static int __init prandom_reseed(void) +static void __prandom_reseed(bool late) { int i; + unsigned long flags; + static bool latch = false; + static DEFINE_SPINLOCK(lock); + + /* only allow initial seeding (late == false) once */ + spin_lock_irqsave(&lock, flags); + if (latch && !late) + goto out; + latch = true; for_each_possible_cpu(i) { struct rnd_state *state = &per_cpu(net_rand_state,i); @@ -216,6 +225,18 @@ static int __init prandom_reseed(void) /* mix it in */ prandom_u32_state(state); } +out: + spin_unlock_irqrestore(&lock, flags); +} + +void prandom_reseed_late(void) +{ + __prandom_reseed(true); +} + +static int __init prandom_reseed(void) +{ + __prandom_reseed(false); prandom_start_seed_timer(); return 0; } -- cgit v0.10.2 From 38e9efcdb33270b4da72143d8e7ca4dcf7f0989b Mon Sep 17 00:00:00 2001 From: Daniel Borkmann Date: Mon, 11 Nov 2013 12:20:35 +0100 Subject: random32: move rnd_state to linux/random.h struct rnd_state got mistakenly pulled into uapi header. It is not used anywhere and does also not belong there! Commit 5960164fde ("lib/random32: export pseudo-random number generator for modules"), the last commit on rnd_state before it got moved to uapi, says: This patch moves the definition of struct rnd_state and the inline __seed() function to linux/random.h. It renames the static __random32() function to prandom32() and exports it for use in modules. Hence, the structure was moved from lib/random32.c to linux/random.h so that it can be used within modules (FCoE-related code in this case), but not from user space. However, it seems to have been mistakenly moved to uapi header through the uapi script. Since no-one should make use of it from the linux headers, move the structure back to the kernel for internal use, so that it can be modified on demand. Joint work with Hannes Frederic Sowa. Cc: Joe Eykholt Signed-off-by: Daniel Borkmann Signed-off-by: Hannes Frederic Sowa Signed-off-by: David S. Miller diff --git a/include/linux/random.h b/include/linux/random.h index 5117ae3..8ef0b70 100644 --- a/include/linux/random.h +++ b/include/linux/random.h @@ -31,6 +31,10 @@ void prandom_bytes(void *buf, int nbytes); void prandom_seed(u32 seed); void prandom_reseed_late(void); +struct rnd_state { + __u32 s1, s2, s3; +}; + u32 prandom_u32_state(struct rnd_state *); void prandom_bytes_state(struct rnd_state *state, void *buf, int nbytes); diff --git a/include/uapi/linux/random.h b/include/uapi/linux/random.h index 7471b5b..fff3528 100644 --- a/include/uapi/linux/random.h +++ b/include/uapi/linux/random.h @@ -40,11 +40,4 @@ struct rand_pool_info { __u32 buf[0]; }; -struct rnd_state { - __u32 s1, s2, s3; -}; - -/* Exported functions */ - - #endif /* _UAPI_LINUX_RANDOM_H */ -- cgit v0.10.2 From a98814cef87946d2708812ad9f8b1e03b8366b6f Mon Sep 17 00:00:00 2001 From: Daniel Borkmann Date: Mon, 11 Nov 2013 12:20:36 +0100 Subject: random32: upgrade taus88 generator to taus113 from errata paper Since we use prandom*() functions quite often in networking code i.e. in UDP port selection, netfilter code, etc, upgrade the PRNG from Pierre L'Ecuyer's original paper "Maximally Equidistributed Combined Tausworthe Generators", Mathematics of Computation, 65, 213 (1996), 203--213 to the version published in his errata paper [1]. The Tausworthe generator is a maximally-equidistributed generator, that is fast and has good statistical properties [1]. The version presented there upgrades the 3 state LFSR to a 4 state LFSR with increased periodicity from about 2^88 to 2^113. The algorithm is presented in [1] by the very same author who also designed the original algorithm in [2]. Also, by increasing the state, we make it a bit harder for attackers to "guess" the PRNGs internal state. See also discussion in [3]. Now, as we use this sort of weak initialization discussed in [3] only between core_initcall() until late_initcall() time [*] for prandom32*() users, namely in prandom_init(), it is less relevant from late_initcall() onwards as we overwrite seeds through prandom_reseed() anyways with a seed source of higher entropy, that is, get_random_bytes(). In other words, a exhaustive keysearch of 96 bit would be needed. Now, with the help of this patch, this state-search increases further to 128 bit. Initialization needs to make sure that s1 > 1, s2 > 7, s3 > 15, s4 > 127. taus88 and taus113 algorithm is also part of GSL. I added a test case in the next patch to verify internal behaviour of this patch with GSL and ran tests with the dieharder 3.31.1 RNG test suite: $ dieharder -g 052 -a -m 10 -s 1 -S 4137730333 #taus88 $ dieharder -g 054 -a -m 10 -s 1 -S 4137730333 #taus113 With this seed configuration, in order to compare both, we get the following differences: algorithm taus88 taus113 rands/second [**] 1.61e+08 1.37e+08 sts_serial(4, 1st run) WEAK PASSED sts_serial(9, 2nd run) WEAK PASSED rgb_lagged_sum(31) WEAK PASSED We took out diehard_sums test as according to the authors it is considered broken and unusable [4]. Despite that and the slight decrease in performance (which is acceptable), taus113 here passes all 113 tests (only rgb_minimum_distance_5 in WEAK, the rest PASSED). In general, taus/taus113 is considered "very good" by the authors of dieharder [5]. The papers [1][2] states a single warm-up step is sufficient by running quicktaus once on each state to ensure proper initialization of ~s_{0}: Our selection of (s) according to Table 1 of [1] row 1 holds the condition L - k <= r - s, that is, (32 32 32 32) - (31 29 28 25) <= (25 27 15 22) - (18 2 7 13) with r = k - q and q = (6 2 13 3) as also stated by the paper. So according to [2] we are safe with one round of quicktaus for initialization. However we decided to include the warm-up phase of the PRNG as done in GSL in every case as a safety net. We also use the warm up phase to make the output of the RNG easier to verify by the GSL output. In prandom_init(), we also mix random_get_entropy() into it, just like drivers/char/random.c does it, jiffies ^ random_get_entropy(). random-get_entropy() is get_cycles(). xor is entropy preserving so it is fine if it is not implemented by some architectures. Note, this PRNG is *not* used for cryptography in the kernel, but rather as a fast PRNG for various randomizations i.e. in the networking code, or elsewhere for debugging purposes, for example. [*]: In order to generate some "sort of pseduo-randomness", since get_random_bytes() is not yet available for us, we use jiffies and initialize states s1 - s3 with a simple linear congruential generator (LCG), that is x <- x * 69069; and derive s2, s3, from the 32bit initialization from s1. So the above quote from [3] accounts only for the time from core to late initcall, not afterwards. [**] Single threaded run on MacBook Air w/ Intel Core i5-3317U [1] http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps [2] http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps [3] http://thread.gmane.org/gmane.comp.encryption.general/12103/ [4] http://code.google.com/p/dieharder/source/browse/trunk/libdieharder/diehard_sums.c?spec=svn490&r=490#20 [5] http://www.phy.duke.edu/~rgb/General/dieharder.php Joint work with Hannes Frederic Sowa. Cc: Florian Weimer Cc: Theodore Ts'o Signed-off-by: Daniel Borkmann Signed-off-by: Hannes Frederic Sowa Signed-off-by: David S. Miller diff --git a/include/linux/random.h b/include/linux/random.h index 8ef0b70..4002b3d 100644 --- a/include/linux/random.h +++ b/include/linux/random.h @@ -32,10 +32,10 @@ void prandom_seed(u32 seed); void prandom_reseed_late(void); struct rnd_state { - __u32 s1, s2, s3; + __u32 s1, s2, s3, s4; }; -u32 prandom_u32_state(struct rnd_state *); +u32 prandom_u32_state(struct rnd_state *state); void prandom_bytes_state(struct rnd_state *state, void *buf, int nbytes); /* @@ -55,9 +55,10 @@ static inline void prandom_seed_state(struct rnd_state *state, u64 seed) { u32 i = (seed >> 32) ^ (seed << 10) ^ seed; - state->s1 = __seed(i, 2); - state->s2 = __seed(i, 8); - state->s3 = __seed(i, 16); + state->s1 = __seed(i, 2U); + state->s2 = __seed(i, 8U); + state->s3 = __seed(i, 16U); + state->s4 = __seed(i, 128U); } #ifdef CONFIG_ARCH_RANDOM diff --git a/lib/random32.c b/lib/random32.c index 9f2f2fb..27adb75 100644 --- a/lib/random32.c +++ b/lib/random32.c @@ -2,19 +2,19 @@ This is a maximally equidistributed combined Tausworthe generator based on code from GNU Scientific Library 1.5 (30 Jun 2004) - x_n = (s1_n ^ s2_n ^ s3_n) + lfsr113 version: - s1_{n+1} = (((s1_n & 4294967294) <<12) ^ (((s1_n <<13) ^ s1_n) >>19)) - s2_{n+1} = (((s2_n & 4294967288) << 4) ^ (((s2_n << 2) ^ s2_n) >>25)) - s3_{n+1} = (((s3_n & 4294967280) <<17) ^ (((s3_n << 3) ^ s3_n) >>11)) + x_n = (s1_n ^ s2_n ^ s3_n ^ s4_n) - The period of this generator is about 2^88. + 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)) - From: P. L'Ecuyer, "Maximally Equidistributed Combined Tausworthe - Generators", Mathematics of Computation, 65, 213 (1996), 203--213. - - This is available on the net from L'Ecuyer's home page, + 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 @@ -29,7 +29,7 @@ that paper.) This affects the seeding procedure by imposing the requirement - s1 > 1, s2 > 7, s3 > 15. + s1 > 1, s2 > 7, s3 > 15, s4 > 127. */ @@ -52,11 +52,12 @@ u32 prandom_u32_state(struct rnd_state *state) { #define TAUSWORTHE(s,a,b,c,d) ((s&c)<>b) - state->s1 = TAUSWORTHE(state->s1, 13, 19, 4294967294UL, 12); - state->s2 = TAUSWORTHE(state->s2, 2, 25, 4294967288UL, 4); - state->s3 = TAUSWORTHE(state->s3, 3, 11, 4294967280UL, 17); + 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); + return (state->s1 ^ state->s2 ^ state->s3 ^ state->s4); } EXPORT_SYMBOL(prandom_u32_state); @@ -126,6 +127,21 @@ void prandom_bytes(void *buf, int bytes) } EXPORT_SYMBOL(prandom_bytes); +static void prandom_warmup(struct rnd_state *state) +{ + /* Calling RNG ten times to satify 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); +} + /** * prandom_seed - add entropy to pseudo random number generator * @seed: seed value @@ -141,8 +157,9 @@ void prandom_seed(u32 entropy) */ for_each_possible_cpu (i) { struct rnd_state *state = &per_cpu(net_rand_state, i); - state->s1 = __seed(state->s1 ^ entropy, 2); - prandom_u32_state(state); + + state->s1 = __seed(state->s1 ^ entropy, 2U); + prandom_warmup(state); } } EXPORT_SYMBOL(prandom_seed); @@ -158,18 +175,13 @@ static int __init prandom_init(void) for_each_possible_cpu(i) { struct rnd_state *state = &per_cpu(net_rand_state,i); -#define LCG(x) ((x) * 69069) /* super-duper LCG */ - state->s1 = __seed(LCG(i + jiffies), 2); - state->s2 = __seed(LCG(state->s1), 8); - state->s3 = __seed(LCG(state->s2), 16); - - /* "warm it up" */ - prandom_u32_state(state); - prandom_u32_state(state); - prandom_u32_state(state); - prandom_u32_state(state); - prandom_u32_state(state); - prandom_u32_state(state); +#define LCG(x) ((x) * 69069U) /* super-duper LCG */ + state->s1 = __seed(LCG((i + jiffies) ^ random_get_entropy()), 2U); + state->s2 = __seed(LCG(state->s1), 8U); + state->s3 = __seed(LCG(state->s2), 16U); + state->s4 = __seed(LCG(state->s3), 128U); + + prandom_warmup(state); } return 0; } @@ -215,15 +227,15 @@ static void __prandom_reseed(bool late) for_each_possible_cpu(i) { struct rnd_state *state = &per_cpu(net_rand_state,i); - u32 seeds[3]; + u32 seeds[4]; get_random_bytes(&seeds, sizeof(seeds)); - state->s1 = __seed(seeds[0], 2); - state->s2 = __seed(seeds[1], 8); - state->s3 = __seed(seeds[2], 16); + state->s1 = __seed(seeds[0], 2U); + state->s2 = __seed(seeds[1], 8U); + state->s3 = __seed(seeds[2], 16U); + state->s4 = __seed(seeds[3], 128U); - /* mix it in */ - prandom_u32_state(state); + prandom_warmup(state); } out: spin_unlock_irqrestore(&lock, flags); -- cgit v0.10.2 From a6a9c0f1bf5a9a5faa605773ea75e0b93c3ab108 Mon Sep 17 00:00:00 2001 From: Daniel Borkmann Date: Mon, 11 Nov 2013 12:20:37 +0100 Subject: random32: add test cases for taus113 implementation We generated a battery of 100 test cases from GSL taus113 implemention and compare the results from a particular seed and a particular iteration with our implementation in the kernel. We have verified on 32 and 64 bit machines that our taus113 kernel implementation gives same results as GSL taus113 implementation: [ 0.147370] prandom: seed boundary self test passed [ 0.148078] prandom: 100 self tests passed This is a Kconfig option that is disabled on default, just like the crc32 init selftests in order to not unnecessary slow down boot process. We also refactored out prandom_seed_very_weak() as it's now used in multiple places in order to reduce redundant code. GSL code we used for generating test cases: int i, j; srand(time(NULL)); for (i = 0; i < 100; ++i) { int iteration = 500 + (rand() % 500); gsl_rng_default_seed = rand() + 1; gsl_rng *r = gsl_rng_alloc(gsl_rng_taus113); printf("\t{ %lu, ", gsl_rng_default_seed); for (j = 0; j < iteration - 1; ++j) gsl_rng_get(r); printf("%u, %lu },\n", iteration, gsl_rng_get(r)); gsl_rng_free(r); } Joint work with Hannes Frederic Sowa. Cc: Florian Weimer Cc: Theodore Ts'o Signed-off-by: Daniel Borkmann Signed-off-by: Hannes Frederic Sowa Signed-off-by: David S. Miller diff --git a/lib/Kconfig b/lib/Kconfig index b3c8be0..75485e1 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -189,6 +189,13 @@ config AUDIT_GENERIC depends on AUDIT && !AUDIT_ARCH default y +config RANDOM32_SELFTEST + bool "PRNG perform self test on init" + default n + help + This option enables the 32 bit PRNG library functions to perform a + self test on initialization. + # # compression support is select'ed if needed # diff --git a/lib/random32.c b/lib/random32.c index 27adb75..82da4f4 100644 --- a/lib/random32.c +++ b/lib/random32.c @@ -38,6 +38,11 @@ #include #include #include +#include + +#ifdef CONFIG_RANDOM32_SELFTEST +static void __init prandom_state_selftest(void); +#endif static DEFINE_PER_CPU(struct rnd_state, net_rand_state); @@ -142,6 +147,23 @@ static void prandom_warmup(struct rnd_state *state) prandom_u32_state(state); } +static void prandom_seed_very_weak(struct rnd_state *state, u32 seed) +{ + /* Note: This sort of seeding is ONLY used in test cases and + * during boot at the time from core_initcall until late_initcall + * as we don't have a stronger entropy source available yet. + * After late_initcall, we reseed entire state, we have to (!), + * otherwise an attacker just needs to search 32 bit space to + * probe for our internal 128 bit state if he knows a couple + * of prandom32 outputs! + */ +#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); +} + /** * prandom_seed - add entropy to pseudo random number generator * @seed: seed value @@ -172,15 +194,14 @@ static int __init prandom_init(void) { int i; +#ifdef CONFIG_RANDOM32_SELFTEST + prandom_state_selftest(); +#endif + for_each_possible_cpu(i) { struct rnd_state *state = &per_cpu(net_rand_state,i); -#define LCG(x) ((x) * 69069U) /* super-duper LCG */ - state->s1 = __seed(LCG((i + jiffies) ^ random_get_entropy()), 2U); - state->s2 = __seed(LCG(state->s1), 8U); - state->s3 = __seed(LCG(state->s2), 16U); - state->s4 = __seed(LCG(state->s3), 128U); - + prandom_seed_very_weak(state, (i + jiffies) ^ random_get_entropy()); prandom_warmup(state); } return 0; @@ -253,3 +274,165 @@ static int __init prandom_reseed(void) return 0; } late_initcall(prandom_reseed); + +#ifdef CONFIG_RANDOM32_SELFTEST +static struct prandom_test1 { + u32 seed; + u32 result; +} test1[] = { + { 1U, 3484351685U }, + { 2U, 2623130059U }, + { 3U, 3125133893U }, + { 4U, 984847254U }, +}; + +static struct prandom_test2 { + u32 seed; + 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 }, +}; + +static void __init prandom_state_selftest(void) +{ + int i, j, errors = 0, runs = 0; + bool error = false; + + for (i = 0; i < ARRAY_SIZE(test1); i++) { + struct rnd_state state; + + prandom_seed_very_weak(&state, test1[i].seed); + prandom_warmup(&state); + + if (test1[i].result != prandom_u32_state(&state)) + error = true; + } + + if (error) + pr_warn("prandom: seed boundary self test failed\n"); + else + pr_info("prandom: seed boundary self test passed\n"); + + for (i = 0; i < ARRAY_SIZE(test2); i++) { + struct rnd_state state; + + prandom_seed_very_weak(&state, test2[i].seed); + prandom_warmup(&state); + + for (j = 0; j < test2[i].iteration - 1; j++) + prandom_u32_state(&state); + + if (test2[i].result != prandom_u32_state(&state)) + errors++; + + runs++; + cond_resched(); + } + + if (errors) + pr_warn("prandom: %d/%d self tests failed\n", errors, runs); + else + pr_info("prandom: %d self tests passed\n", runs); +} +#endif -- cgit v0.10.2