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 --- include/linux/random.h | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'include/linux/random.h') diff --git a/include/linux/random.h b/include/linux/random.h index 6312dd9ba449..bf9085e89fb5 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 -- cgit 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 --- drivers/char/random.c | 5 ++++- include/linux/random.h | 1 + lib/random32.c | 23 ++++++++++++++++++++++- 3 files changed, 27 insertions(+), 2 deletions(-) (limited to 'include/linux/random.h') diff --git a/drivers/char/random.c b/drivers/char/random.c index 7a744d391756..4fe5609eeb72 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 bf9085e89fb5..5117ae348fe8 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 12215df701e8..9f2f2fb03dfe 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 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 --- include/linux/random.h | 4 ++++ include/uapi/linux/random.h | 7 ------- 2 files changed, 4 insertions(+), 7 deletions(-) (limited to 'include/linux/random.h') diff --git a/include/linux/random.h b/include/linux/random.h index 5117ae348fe8..8ef0b70bd1f9 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 7471b5b3b8ba..fff3528a078f 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 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 --- include/linux/random.h | 11 +++---- lib/random32.c | 80 +++++++++++++++++++++++++++++--------------------- 2 files changed, 52 insertions(+), 39 deletions(-) (limited to 'include/linux/random.h') diff --git a/include/linux/random.h b/include/linux/random.h index 8ef0b70bd1f9..4002b3df4c85 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 9f2f2fb03dfe..27adb753180f 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