Merge branch 'prandom'

prandom fixes/improvements

====================
It would be great if you could still consider this series that fixes and
improves prandom for 3.13. We have sent it to netdev as prandom() originally
came from net/core/utils.c and networking is its main user. For a detailled
description, please see individual patches.

For patch 3 in this series, there will be a minor merge conflict with the
random tree that is for 3.13. See below how to resolve it.

====
Hannes says: on merge with the random tree I would suggest to resolve the
conflict in drivers/char/random.c like this:

if (r->entropy_total > 128) {
	r->initialized = 1;
	r->entropy_total = 0;
	if (r == &nonblocking_pool) {
		prandom_reseed_late();
		pr_notice("random: %s pool is initialized\n",
			  r->name);
	}
}

So it won't generate a warning if DEBUG_RANDOM_BOOT gets activated.
====

Patch 1 should probably also go to -stable.

Set tested on 32 and 64 bit machines.

Thanks a lot!

Ref. original discussion: http://patchwork.ozlabs.org/patch/289951/
====================

Signed-off-by: David S. Miller <davem@davemloft.net>

5 files changed, 294 insertions, 46 deletions

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 6312dd9ba449..4002b3df4c85 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -29,8 +29,13 @@ 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 *);
+struct rnd_state {
+        __u32 s1, s2, s3, s4;
+};
+
+u32 prandom_u32_state(struct rnd_state *state);
 void prandom_bytes_state(struct rnd_state *state, void *buf, int nbytes);
 
 /*
@@ -50,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, 1);
-        state->s2 = __seed(i, 7);
-        state->s3 = __seed(i, 15);
+        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/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 */
diff --git a/lib/Kconfig b/lib/Kconfig
index b3c8be0da17f..75485e163ca3 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 52280d5526be..82da4f4c3489 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.
 
 */
 
@@ -38,6 +38,11 @@
 #include <linux/export.h>
 #include <linux/jiffies.h>
 #include <linux/random.h>
+#include <linux/sched.h>
+
+#ifdef CONFIG_RANDOM32_SELFTEST
+static void __init prandom_state_selftest(void);
+#endif
 
 static DEFINE_PER_CPU(struct rnd_state, net_rand_state);
 
@@ -52,11 +57,12 @@ 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, 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 +132,38 @@ 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);
+}
+
+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!