[PATCH net-next 0/6] prandom fixes/improvements

[PATCH net-next 0/6] prandom fixes/improvements

[Daniel Borkmann]

Hi Dave,

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/

Daniel Borkmann (4):
  random32: fix off-by-one in seeding requirement
  random32: move rnd_state to linux/random.h
  random32: upgrade taus88 generator to taus113 from errata paper
  random32: add test cases for taus113 implementation

Hannes Frederic Sowa (2):
  random32: add periodic reseeding
  random32: add prandom_reseed_late() and call when nonblocking pool
    becomes initialized

 drivers/char/random.c       |   5 +-
 include/linux/random.h      |  14 +-
 include/uapi/linux/random.h |   7 -
 lib/Kconfig                 |   7 +
 lib/random32.c              | 307 +++++++++++++++++++++++++++++++++++++++-----
 5 files changed, 294 insertions(+), 46 deletions(-)

-- 
1.8.3.1

[PATCH net-next 1/6] random32: fix off-by-one in seeding requirement

[Daniel Borkmann]

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 <stephen@networkplumber.org>
Cc: Florian Weimer <fweimer@redhat.com>
Cc: Theodore Ts'o <tytso@mit.edu>
Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
Signed-off-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
---
 include/linux/random.h |  6 +++---
 lib/random32.c         | 14 +++++++-------
 2 files changed, 10 insertions(+), 10 deletions(-)

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);
-- 
1.8.3.1

[PATCH net-next 2/6] random32: add periodic reseeding

[Daniel Borkmann]

From: Hannes Frederic Sowa <hannes@stressinduktion.org>

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 <eric.dumazet@gmail.com>
Cc: Theodore Ts'o <tytso@mit.edu>
Signed-off-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
---
 lib/random32.c | 23 +++++++++++++++++++++++
 1 file changed, 23 insertions(+)

diff --git a/lib/random32.c b/lib/random32.c
index 01e8890..165d0a5f 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);
-- 
1.8.3.1

[PATCH net-next 3/6] random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized

[Daniel Borkmann]

From: Hannes Frederic Sowa <hannes@stressinduktion.org>

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 <eric.dumazet@gmail.com>
Cc: Theodore Ts'o <tytso@mit.edu>
Signed-off-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
---
 drivers/char/random.c  |  5 ++++-
 include/linux/random.h |  1 +
 lib/random32.c         | 23 ++++++++++++++++++++++-
 3 files changed, 27 insertions(+), 2 deletions(-)

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 165d0a5f..e048416 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;
 }
-- 
1.8.3.1

Re: [PATCH net-next 3/6] random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized

[Theodore Ts'o]

On Mon, Nov 11, 2013 at 12:20:34PM +0100, Daniel Borkmann wrote:
> From: Hannes Frederic Sowa <hannes@stressinduktion.org>
> 
> 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.

Acked-by: "Theodore Ts'o" <tytso@mit.edu>

I wasn't cc'ed on the full series (I didn't see the 0/3 or the 4/6
messages) but there are two other things that you might want to
consider.

1)  I'm pretty sure, but it would be good to get netdev confirmation,
that the call to get_random_bytes() in
net/mac80211/rc80211_minstrel.c's init_sample_table() can be replaced
by calls to prandom_u32().  

That is, I don't believe cryptographic strength randomness is needed
--- which is good, because my debugging indicates on a test system
indicates that it gets called so early that there is typically less
than two dozen bits of entropy collected in the non-blocking pool
before it calls get_random_bytes().  If we can move away from using
get_random_bytes(), those two dozen bits of entropy can be used to
make sure the urandom pool is initialized much more quickly.

2) Since the minstrel code apparently uses this information for
initializing a machine learning algorithm for backoff purposes, I
suspect it might be good if the numbers it gets are different from
machine to machine --- and right now prandom_init() does not mix in
any kind of personalization information, so calls to prandom_u32()
will be the same across machines until it gets initialized from the
/dev/random subsysem.

Currently, the way we get personlization information which uniquifies
the randomness in early boot is via add_device_randomness().  Yes,
some of the function names are a bit misleading; maybe we should try
to fix this at some point.  So perhaps we should add a hook to
add_device_randomness() so that each time it gets called, if the
random32.c state hasn't been strongly initialized by the call to
prandom_reseed_late(), we also use that information add some per-host
uniqueness into prandom32.c.  (Note: I'd prefer that we do this via
some interface other than get_random_bytes(), so we don't end up
draining entropy from the non_blocking pool, and thus delay the point
where we can strongly initialize the non_blocking pool, and thus
strongly initialize prandom32.c)

Does this make sense to folks?

Cheers,

						- Ted

Re: [PATCH net-next 3/6] random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized

[Hannes Frederic Sowa]

On Mon, Nov 11, 2013 at 08:43:57AM -0500, Theodore Ts'o wrote:
> On Mon, Nov 11, 2013 at 12:20:34PM +0100, Daniel Borkmann wrote:
> > From: Hannes Frederic Sowa <hannes@stressinduktion.org>
> > 
> > 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.
> 
> Acked-by: "Theodore Ts'o" <tytso@mit.edu>
> 
> I wasn't cc'ed on the full series (I didn't see the 0/3 or the 4/6
> messages) but there are two other things that you might want to
> consider.
> 
> 1)  I'm pretty sure, but it would be good to get netdev confirmation,
> that the call to get_random_bytes() in
> net/mac80211/rc80211_minstrel.c's init_sample_table() can be replaced
> by calls to prandom_u32().

Would make sense. I added wireless-devel to confirm.

[...]
[    0.673260] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
[    0.674024] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
[    0.675012] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
[    0.676032] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
[    0.677020] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
[    0.678011] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
[    0.679011] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
[...]

In total 80 calls to get_random_bytes.

Normally this initialization is called at module load time, so with most
distributions it runs much later. I had it built-in.

> That is, I don't believe cryptographic strength randomness is needed
> --- which is good, because my debugging indicates on a test system
> indicates that it gets called so early that there is typically less
> than two dozen bits of entropy collected in the non-blocking pool
> before it calls get_random_bytes().  If we can move away from using
> get_random_bytes(), those two dozen bits of entropy can be used to
> make sure the urandom pool is initialized much more quickly.
> 
> 2) Since the minstrel code apparently uses this information for
> initializing a machine learning algorithm for backoff purposes, I
> suspect it might be good if the numbers it gets are different from
> machine to machine --- and right now prandom_init() does not mix in
> any kind of personalization information, so calls to prandom_u32()
> will be the same across machines until it gets initialized from the
> /dev/random subsysem.

Yes, I agree.

We are much too early to enumerate hardware, so it would be hard to
integrate something like mac addresses etc.

On x86 it would be easy to seed the cpu type and model from a cpuid call,
but I fear we could not easily extend it to all architectures. And it
does not differ that much between systems.

> Currently, the way we get personlization information which uniquifies
> the randomness in early boot is via add_device_randomness().  Yes,
> some of the function names are a bit misleading; maybe we should try
> to fix this at some point.  So perhaps we should add a hook to
> add_device_randomness() so that each time it gets called, if the
> random32.c state hasn't been strongly initialized by the call to
> prandom_reseed_late(), we also use that information add some per-host
> uniqueness into prandom32.c.  (Note: I'd prefer that we do this via
> some interface other than get_random_bytes(), so we don't end up
> draining entropy from the non_blocking pool, and thus delay the point
> where we can strongly initialize the non_blocking pool, and thus
> strongly initialize prandom32.c)
> 
> Does this make sense to folks?

Totally! That was also the reason why I left the late_initcall intact
in this patch.

Btw. do you see problems regarding get_random_int on architectures without
hardware offloading?

We are initializing random_int_secret really late (after all the init
calls) and I wonder if we should also use a two stage initialization
there, so we have a more unpredictable MD5 hash at early boot.

Greetings,

  Hannes

Re: [PATCH net-next 3/6] random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized

[Karl Beldan]

On Tue, Nov 12, 2013 at 01:03:07AM +0100, Hannes Frederic Sowa wrote:
> On Mon, Nov 11, 2013 at 08:43:57AM -0500, Theodore Ts'o wrote:
> > On Mon, Nov 11, 2013 at 12:20:34PM +0100, Daniel Borkmann wrote:
> > > From: Hannes Frederic Sowa <hannes-tFNcAqjVMyqKXQKiL6tip0B+6BGkLq7r@public.gmane.org>
> > > 
> > > 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.
> > 
> > Acked-by: "Theodore Ts'o" <tytso-3s7WtUTddSA@public.gmane.org>
> > 
> > I wasn't cc'ed on the full series (I didn't see the 0/3 or the 4/6
> > messages) but there are two other things that you might want to
> > consider.
> > 
> > 1)  I'm pretty sure, but it would be good to get netdev confirmation,
> > that the call to get_random_bytes() in
> > net/mac80211/rc80211_minstrel.c's init_sample_table() can be replaced
> > by calls to prandom_u32().
> 
> Would make sense. I added wireless-devel to confirm.
> 
> [...]
> [    0.673260] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> [    0.674024] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> [    0.675012] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> [    0.676032] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> [    0.677020] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> [    0.678011] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> [    0.679011] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> [...]
> 
> In total 80 calls to get_random_bytes.
> 

It is already 8 times what rc80211_minstrel_ht_init uses.
If you could apply on top of:
http://marc.info/?l=linux-wireless&m=138392850030987&w=2
although Johannes has not yet agreed/applied this.

 
Karl
--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH net-next 3/6] random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized

[Johannes Berg]

On Tue, 2013-11-12 at 01:37 +0100, Karl Beldan wrote:

> > > 1)  I'm pretty sure, but it would be good to get netdev confirmation,
> > > that the call to get_random_bytes() in
> > > net/mac80211/rc80211_minstrel.c's init_sample_table() can be replaced
> > > by calls to prandom_u32().
> > 
> > Would make sense. I added wireless-devel to confirm.
> > 
> > [...]
> > [    0.673260] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > [    0.674024] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > [    0.675012] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > [    0.676032] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > [    0.677020] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > [    0.678011] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > [    0.679011] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > [...]
> > 
> > In total 80 calls to get_random_bytes.
> > 
> 
> It is already 8 times what rc80211_minstrel_ht_init uses.
> If you could apply on top of:
> http://marc.info/?l=linux-wireless&m=138392850030987&w=2
> although Johannes has not yet agreed/applied this.

I'll take the patch, I just wanted a more useful commit log :)

I guess if really needed I'll write that myself :(

Anyway, I can't comment on prandom_u32(), but it doesn't really have to
be all that random here, it's just sample tables for what order to try
things in. Technically that could even be static with some per-device
pertubation, I guess?

johannes

--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH net-next 3/6] random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized

[Karl Beldan]

On Tue, Nov 12, 2013 at 09:36:15AM +0100, Johannes Berg wrote:
> On Tue, 2013-11-12 at 01:37 +0100, Karl Beldan wrote:
> 
> > > > 1)  I'm pretty sure, but it would be good to get netdev confirmation,
> > > > that the call to get_random_bytes() in
> > > > net/mac80211/rc80211_minstrel.c's init_sample_table() can be replaced
> > > > by calls to prandom_u32().
> > > 
> > > Would make sense. I added wireless-devel to confirm.
> > > 
> > > [...]
> > > [    0.673260] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > > [    0.674024] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > > [    0.675012] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > > [    0.676032] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > > [    0.677020] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > > [    0.678011] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > > [    0.679011] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > > [...]
> > > 
> > > In total 80 calls to get_random_bytes.
> > > 
> > 
> > It is already 8 times what rc80211_minstrel_ht_init uses.
> > If you could apply on top of:
> > http://marc.info/?l=linux-wireless&m=138392850030987&w=2
> > although Johannes has not yet agreed/applied this.
> 
> I'll take the patch, I just wanted a more useful commit log :)
> 
The commit log still feels very right to me, but I don't want you to go
grumpy ;) and will reword the log - Hannes, have you staged replacing
get_random_bytes with prandom_u32 already or can I do it in a reworded
v2 for minstrel ?

> I guess if really needed I'll write that myself :(
> 
> Anyway, I can't comment on prandom_u32(), but it doesn't really have to
> be all that random here, it's just sample tables for what order to try
> things in. Technically that could even be static with some per-device
> pertubation, I guess?
> 
The LFSR is way enough for minstrel, as for moving from prandom to
handcrafted sample table, this will be another discussion I guess.
 
Karl
--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH net-next 3/6] random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized

[Hannes Frederic Sowa]

On Tue, Nov 12, 2013 at 12:13:10PM +0100, Karl Beldan wrote:
> On Tue, Nov 12, 2013 at 09:36:15AM +0100, Johannes Berg wrote:
> > On Tue, 2013-11-12 at 01:37 +0100, Karl Beldan wrote:
> > 
> > > > > 1)  I'm pretty sure, but it would be good to get netdev confirmation,
> > > > > that the call to get_random_bytes() in
> > > > > net/mac80211/rc80211_minstrel.c's init_sample_table() can be replaced
> > > > > by calls to prandom_u32().
> > > > 
> > > > Would make sense. I added wireless-devel to confirm.
> > > > 
> > > > [...]
> > > > [    0.673260] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > > > [    0.674024] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > > > [    0.675012] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > > > [    0.676032] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > > > [    0.677020] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > > > [    0.678011] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > > > [    0.679011] random: rc80211_minstrel_ht_init+0x47/0xaa get_random_bytes called with 3 bits of entropy available
> > > > [...]
> > > > 
> > > > In total 80 calls to get_random_bytes.
> > > > 
> > > 
> > > It is already 8 times what rc80211_minstrel_ht_init uses.
> > > If you could apply on top of:
> > > http://marc.info/?l=linux-wireless&m=138392850030987&w=2
> > > although Johannes has not yet agreed/applied this.
> > 
> > I'll take the patch, I just wanted a more useful commit log :)
> > 
> The commit log still feels very right to me, but I don't want you to go
> grumpy ;) and will reword the log - Hannes, have you staged replacing
> get_random_bytes with prandom_u32 already or can I do it in a reworded
> v2 for minstrel ?

I haven't done that so far. So, go ahead, I would love to see
that. Btw. there is prandom_bytes, which should be a suitable drop-in.

Btw. if the initialization is run later (as in, after the boot process),
the prandom-PRNG will be better seeded.

Thank you,

  Hannes

Re: [PATCH net-next 3/6] random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized

[Theodore Ts'o]

On Tue, Nov 12, 2013 at 01:03:07AM +0100, Hannes Frederic Sowa wrote:
>
> We are much too early to enumerate hardware, so it would be hard to
> integrate something like mac addresses etc.

Stupid question --- is there a reason why the minstrel code is
initialized so early when it is compiled into the kernel?  Can we
change it so it gets initialized later, after the devices are
initialized and we get the mac addresses?  

> Btw. do you see problems regarding get_random_int on architectures without
> hardware offloading?
> 
> We are initializing random_int_secret really late (after all the init
> calls) and I wonder if we should also use a two stage initialization
> there, so we have a more unpredictable MD5 hash at early boot.

Most of the users of get_random_int(), at least to date, have been for
things like ASLR.  A quick audit shows only one device driver user
that might be impacted: drivers/net/wireless/cw1200/wsm.c.

It's not a bad idea to do a two stage init just in case
get_random_int() gets used by other code --- although that brings up
something that I know is really needed, but which I haven't had time
to try to address yet: we really need to document all of the various
interfaces that various kernel routines can use to get random numbers,
and document what their performance and security characteristics are.
We have probably have a lot of code where the authors didn't realize
that some other interface would be a better match for their needs, or
the code is old enough that predates some of the newer interfaces.

    	    	       	    	     - Ted

Re: [PATCH net-next 3/6] random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized

[Johannes Berg]

On Tue, 2013-11-12 at 06:53 -0500, Theodore Ts'o wrote:
> On Tue, Nov 12, 2013 at 01:03:07AM +0100, Hannes Frederic Sowa wrote:
> >
> > We are much too early to enumerate hardware, so it would be hard to
> > integrate something like mac addresses etc.
> 
> Stupid question --- is there a reason why the minstrel code is
> initialized so early when it is compiled into the kernel?  Can we
> change it so it gets initialized later, after the devices are
> initialized and we get the mac addresses?  

It's a bit of a chicken & egg problem - the minstrel rate control is
needed for the wireless device to get registered - if anything were to
fail there then we wouldn't want to register.

johannes

Re: [PATCH net-next 3/6] random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized

[Hannes Frederic Sowa]

On Tue, Nov 12, 2013 at 06:53:50AM -0500, Theodore Ts'o wrote:
> > Btw. do you see problems regarding get_random_int on architectures without
> > hardware offloading?
> > 
> > We are initializing random_int_secret really late (after all the init
> > calls) and I wonder if we should also use a two stage initialization
> > there, so we have a more unpredictable MD5 hash at early boot.
> 
> Most of the users of get_random_int(), at least to date, have been for
> things like ASLR.  A quick audit shows only one device driver user
> that might be impacted: drivers/net/wireless/cw1200/wsm.c.
> 
> It's not a bad idea to do a two stage init just in case
> get_random_int() gets used by other code --- although that brings up
> something that I know is really needed, but which I haven't had time
> to try to address yet: we really need to document all of the various
> interfaces that various kernel routines can use to get random numbers,
> and document what their performance and security characteristics are.
> We have probably have a lot of code where the authors didn't realize
> that some other interface would be a better match for their needs, or
> the code is old enough that predates some of the newer interfaces.

It is needed by fork to set up the stack canary. And this actually gets
called before the secret is initialized.

Btw. the kaslr seeding techniques become quite interesting. It looks like
they want to hash struct boot_params, maybe the ACPI memory part and also the
DMI table.

I guess we should start to implement an interface for early-boot entropy which
the architectures must override to not use jiffies ^ get_cycles() all the
time.

The documentation idea also does sound as a very good one. ;)

Greetings,

  Hannes

--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[PATCH] random: seed random_int_secret at least poorly at core_initcall time

[Hannes Frederic Sowa]

On Tue, Nov 12, 2013 at 02:16:27PM +0100, Hannes Frederic Sowa wrote:
> On Tue, Nov 12, 2013 at 06:53:50AM -0500, Theodore Ts'o wrote:
> > > Btw. do you see problems regarding get_random_int on architectures without
> > > hardware offloading?
> > > 
> > > We are initializing random_int_secret really late (after all the init
> > > calls) and I wonder if we should also use a two stage initialization
> > > there, so we have a more unpredictable MD5 hash at early boot.
> > 
> > Most of the users of get_random_int(), at least to date, have been for
> > things like ASLR.  A quick audit shows only one device driver user
> > that might be impacted: drivers/net/wireless/cw1200/wsm.c.
> > 
> > It's not a bad idea to do a two stage init just in case
> > get_random_int() gets used by other code --- although that brings up
> > something that I know is really needed, but which I haven't had time
> > to try to address yet: we really need to document all of the various
> > interfaces that various kernel routines can use to get random numbers,
> > and document what their performance and security characteristics are.
> > We have probably have a lot of code where the authors didn't realize
> > that some other interface would be a better match for their needs, or
> > the code is old enough that predates some of the newer interfaces.
> 
> It is needed by fork to set up the stack canary. And this actually gets
> called before the secret is initialized.

Maybe we could use this for the time being and use the seeding method
of kaslr as soon as it hits the tree?

I didn't bother including arch_get_random_int as we don't use the seed at all
if that function is available on the particular architecture.

[PATCH] random: seed random_int_secret at least poorly at core_initcall time

We don't seed random_int secret until after all the initcalls happend. But
it does get used before that. So try at least to seed it before initial
usage until it gets reseeded again after the initcalls.

Cc: "Theodore Ts'o" <tytso-3s7WtUTddSA@public.gmane.org>
Signed-off-by: Hannes Frederic Sowa <hannes-tFNcAqjVMyqKXQKiL6tip0B+6BGkLq7r@public.gmane.org>
---
 drivers/char/random.c | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 4fe5609..9f2623c 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1468,6 +1468,16 @@ int random_int_secret_init(void)
 	return 0;
 }
 
+static int __init random_int_secret_init_early(void)
+{
+	int i;
+
+	for (i = 0; i < ARRAY_SIZE(random_int_secret); i++)
+		random_int_secret[i] = jiffies ^ random_get_entropy();
+	return 0;
+}
+core_initcall(random_int_secret_init_early);
+
 /*
  * Get a random word for internal kernel use only. Similar to urandom but
  * with the goal of minimal entropy pool depletion. As a result, the random
-- 
1.8.3.1

--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] random: seed random_int_secret at least poorly at core_initcall time

[Theodore Ts'o]

On Tue, Nov 12, 2013 at 02:46:03PM +0100, Hannes Frederic Sowa wrote:
> > It is needed by fork to set up the stack canary. And this actually gets
> > called before the secret is initialized.
> 
> Maybe we could use this for the time being and use the seeding method
> of kaslr as soon as it hits the tree?

Hmm, from what I can tell even early_initcall() is going to be early
enough.  The stack canary is set up by boot_init_stack_canary(), which
is run very, very early in start_kerne() --- way before
early_initcalls, or even before interrupts are enabled.  So adding
random_int_secret_init_early() as a core_initcall is still too late.

I wonder if we need to do something in common with what Kees has been
considering for the kaslr code, since it's a similar issue --- we need
random number way earlier than we can really afford to initialize
/dev/random.

						- Ted

P.S.  Unless I'm missing something (and I hope I am), it would appear
that the stack canary is going to easily predictable by an attacker on
non-x86 platforms that don't have RDRAND.  Has someone tested whether
or not the stack canary isn't constant across ARM or pre-Sandy Bridge
x86 systems?

--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] random: seed random_int_secret at least poorly at core_initcall time

[Hannes Frederic Sowa]

On Wed, Nov 13, 2013 at 09:54:48PM -0500, Theodore Ts'o wrote:
> On Tue, Nov 12, 2013 at 02:46:03PM +0100, Hannes Frederic Sowa wrote:
> > > It is needed by fork to set up the stack canary. And this actually gets
> > > called before the secret is initialized.
> > 
> > Maybe we could use this for the time being and use the seeding method
> > of kaslr as soon as it hits the tree?
> 
> Hmm, from what I can tell even early_initcall() is going to be early
> enough.  The stack canary is set up by boot_init_stack_canary(), which
> is run very, very early in start_kerne() --- way before
> early_initcalls, or even before interrupts are enabled.  So adding
> random_int_secret_init_early() as a core_initcall is still too late.

Actually I tried to protect the tsk->stack_canary = get_random_int()
in fork.c. It sets up the per-task canary.

> I wonder if we need to do something in common with what Kees has been
> considering for the kaslr code, since it's a similar issue --- we need
> random number way earlier than we can really afford to initialize
> /dev/random.

Definiteley. I would also propose hashing the boot arguments, often
enough there is a filesystem UUID in there, or even hash the multiboot
information we are given from grub. Maybe compile-time entropy, at least
a bit.

> P.S.  Unless I'm missing something (and I hope I am), it would appear
> that the stack canary is going to easily predictable by an attacker on
> non-x86 platforms that don't have RDRAND.  Has someone tested whether
> or not the stack canary isn't constant across ARM or pre-Sandy Bridge
> x86 systems?

In case of protection for interrupt stacks and early cmwq threads,
it looks pretty bad from a first look at the source (at least for the
first initialized CPU).

I'll try to do some tests tomorrow.

Greetings,

  Hannes

Re: [PATCH] random: seed random_int_secret at least poorly at core_initcall time

[Hannes Frederic Sowa]

On Thu, Nov 14, 2013 at 05:18:30AM +0100, Hannes Frederic Sowa wrote:
> On Wed, Nov 13, 2013 at 09:54:48PM -0500, Theodore Ts'o wrote:
> > On Tue, Nov 12, 2013 at 02:46:03PM +0100, Hannes Frederic Sowa wrote:
> > > > It is needed by fork to set up the stack canary. And this actually gets
> > > > called before the secret is initialized.
> > > 
> > > Maybe we could use this for the time being and use the seeding method
> > > of kaslr as soon as it hits the tree?
> > 
> > Hmm, from what I can tell even early_initcall() is going to be early
> > enough.  The stack canary is set up by boot_init_stack_canary(), which
> > is run very, very early in start_kerne() --- way before
> > early_initcalls, or even before interrupts are enabled.  So adding
> > random_int_secret_init_early() as a core_initcall is still too late.
> 
> Actually I tried to protect the tsk->stack_canary = get_random_int()
> in fork.c. It sets up the per-task canary.
> 
> > I wonder if we need to do something in common with what Kees has been
> > considering for the kaslr code, since it's a similar issue --- we need
> > random number way earlier than we can really afford to initialize
> > /dev/random.
> 
> Definiteley. I would also propose hashing the boot arguments, often
> enough there is a filesystem UUID in there, or even hash the multiboot
> information we are given from grub. Maybe compile-time entropy, at least
> a bit.
> 
> > P.S.  Unless I'm missing something (and I hope I am), it would appear
> > that the stack canary is going to easily predictable by an attacker on
> > non-x86 platforms that don't have RDRAND.  Has someone tested whether
> > or not the stack canary isn't constant across ARM or pre-Sandy Bridge
> > x86 systems?
> 
> In case of protection for interrupt stacks and early cmwq threads,
> it looks pretty bad from a first look at the source (at least for the
> first initialized CPU).

First output on first cpu of get_random_bytes is always identical on amd64
without rdrand. :/

--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] random: seed random_int_secret at least poorly at core_initcall time

[Kees Cook]

On Wed, Nov 13, 2013 at 8:18 PM, Hannes Frederic Sowa
<hannes@stressinduktion.org> wrote:
> On Wed, Nov 13, 2013 at 09:54:48PM -0500, Theodore Ts'o wrote:
>> On Tue, Nov 12, 2013 at 02:46:03PM +0100, Hannes Frederic Sowa wrote:
>> > > It is needed by fork to set up the stack canary. And this actually gets
>> > > called before the secret is initialized.
>> >
>> > Maybe we could use this for the time being and use the seeding method
>> > of kaslr as soon as it hits the tree?
>>
>> Hmm, from what I can tell even early_initcall() is going to be early
>> enough.  The stack canary is set up by boot_init_stack_canary(), which
>> is run very, very early in start_kerne() --- way before
>> early_initcalls, or even before interrupts are enabled.  So adding
>> random_int_secret_init_early() as a core_initcall is still too late.
>
> Actually I tried to protect the tsk->stack_canary = get_random_int()
> in fork.c. It sets up the per-task canary.

I haven't looked closely yet at how the stack canary gets plumbed, but
what do things outside of process context end up using?

>> I wonder if we need to do something in common with what Kees has been
>> considering for the kaslr code, since it's a similar issue --- we need
>> random number way earlier than we can really afford to initialize
>> /dev/random.
>
> Definiteley. I would also propose hashing the boot arguments, often
> enough there is a filesystem UUID in there, or even hash the multiboot
> information we are given from grub. Maybe compile-time entropy, at least
> a bit.

Yeah, other suggestions were things ACPI tables, memory layouts, etc.
Basically anything that might be different from system to system. Even
just perturbing by the build strings (which has compiler version,
build date, build host, etc etc) gets us a tiny amount of entropy
(which is still better than 0).

>> P.S.  Unless I'm missing something (and I hope I am), it would appear
>> that the stack canary is going to easily predictable by an attacker on
>> non-x86 platforms that don't have RDRAND.  Has someone tested whether
>> or not the stack canary isn't constant across ARM or pre-Sandy Bridge
>> x86 systems?
>
> In case of protection for interrupt stacks and early cmwq threads,
> it looks pretty bad from a first look at the source (at least for the
> first initialized CPU).
>
> I'll try to do some tests tomorrow.
>
> Greetings,
>
>   Hannes
>

-Kees

-- 
Kees Cook
Chrome OS Security

Re: [PATCH] random: seed random_int_secret at least poorly at core_initcall time

[Hannes Frederic Sowa]

On Fri, Nov 15, 2013 at 10:42:28AM -0800, Kees Cook wrote:
> On Wed, Nov 13, 2013 at 8:18 PM, Hannes Frederic Sowa
> <hannes-tFNcAqjVMyqKXQKiL6tip0B+6BGkLq7r@public.gmane.org> wrote:
> > On Wed, Nov 13, 2013 at 09:54:48PM -0500, Theodore Ts'o wrote:
> >> On Tue, Nov 12, 2013 at 02:46:03PM +0100, Hannes Frederic Sowa wrote:
> >> > > It is needed by fork to set up the stack canary. And this actually gets
> >> > > called before the secret is initialized.
> >> >
> >> > Maybe we could use this for the time being and use the seeding method
> >> > of kaslr as soon as it hits the tree?
> >>
> >> Hmm, from what I can tell even early_initcall() is going to be early
> >> enough.  The stack canary is set up by boot_init_stack_canary(), which
> >> is run very, very early in start_kerne() --- way before
> >> early_initcalls, or even before interrupts are enabled.  So adding
> >> random_int_secret_init_early() as a core_initcall is still too late.
> >
> > Actually I tried to protect the tsk->stack_canary = get_random_int()
> > in fork.c. It sets up the per-task canary.
> 
> I haven't looked closely yet at how the stack canary gets plumbed, but
> what do things outside of process context end up using?

Early on boot __stack_chk_guard gets initialized. The address of this symbol
is looked up by gcc to assemble the stack guard checks.

Only on ARM with !CONFIG_SMP the __stack_chk_guard is switched as soon
as a new process context is entered. This is not possible if the kernel
is compiled for CONFIG_SMP and the kernel will fallback to the one global
__stack_chk_guard canary.

--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] random: seed random_int_secret at least poorly at core_initcall time

[Kees Cook]

On Wed, Nov 13, 2013 at 6:54 PM, Theodore Ts'o <tytso-3s7WtUTddSA@public.gmane.org> wrote:
> On Tue, Nov 12, 2013 at 02:46:03PM +0100, Hannes Frederic Sowa wrote:
>> > It is needed by fork to set up the stack canary. And this actually gets
>> > called before the secret is initialized.
>>
>> Maybe we could use this for the time being and use the seeding method
>> of kaslr as soon as it hits the tree?
>
> Hmm, from what I can tell even early_initcall() is going to be early
> enough.  The stack canary is set up by boot_init_stack_canary(), which
> is run very, very early in start_kerne() --- way before
> early_initcalls, or even before interrupts are enabled.  So adding
> random_int_secret_init_early() as a core_initcall is still too late.
>
> I wonder if we need to do something in common with what Kees has been
> considering for the kaslr code, since it's a similar issue --- we need
> random number way earlier than we can really afford to initialize
> /dev/random.

Right now I've only been looking at x86. As things currently stand,
we'll make use of RDRAND and RDTSC if they're available, and if
neither are then go to the i8254 timer. Ingo wanted even more
unpredictability, in the face of total failure from these more dynamic
sources, so x86 also "seeds" itself with the build string and the
boot_params. These last two are hardly high entropy, but they should
at least make 2 different systems not have _identical_ entropy at the
start. It's far from cryptographically secure, but it's something, I
hope.

> P.S.  Unless I'm missing something (and I hope I am), it would appear
> that the stack canary is going to easily predictable by an attacker on
> non-x86 platforms that don't have RDRAND.  Has someone tested whether
> or not the stack canary isn't constant across ARM or pre-Sandy Bridge
> x86 systems?

When the static stack canary was mentioned during the ARM summit, I
dug around a little bit and saw that at very early boot, yes, it was
always the same, but after boot finished, it was different from boot
to boot. I didn't get far enough to figure out what was changing it
later on.

-Kees

-- 
Kees Cook
Chrome OS Security
--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] random: seed random_int_secret at least poorly at core_initcall time

[Dave Jones]

On Fri, Nov 15, 2013 at 10:33:04AM -0800, Kees Cook wrote:
 
 > Ingo wanted even more
 > unpredictability, in the face of total failure from these more dynamic
 > sources, so x86 also "seeds" itself with the build string and the
 > boot_params. These last two are hardly high entropy, but they should
 > at least make 2 different systems not have _identical_ entropy at the
 > start. It's far from cryptographically secure, but it's something, I
 > hope.

Those are both likely to be the same on some configurations.
On x86, we could maybe hash the dmi tables ? Vendor stupidity aside,
things like serial numbers in those tables _should_ be different.
 
	Dave

--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] random: seed random_int_secret at least poorly at core_initcall time

[Kees Cook]

On Fri, Nov 15, 2013 at 10:45 AM, Dave Jones <davej@redhat.com> wrote:
> On Fri, Nov 15, 2013 at 10:33:04AM -0800, Kees Cook wrote:
>
>  > Ingo wanted even more
>  > unpredictability, in the face of total failure from these more dynamic
>  > sources, so x86 also "seeds" itself with the build string and the
>  > boot_params. These last two are hardly high entropy, but they should
>  > at least make 2 different systems not have _identical_ entropy at the
>  > start. It's far from cryptographically secure, but it's something, I
>  > hope.
>
> Those are both likely to be the same on some configurations.
> On x86, we could maybe hash the dmi tables ? Vendor stupidity aside,
> things like serial numbers in those tables _should_ be different.

Yeah, DMI tables were suggested as well. (Hopefully people will start
using -uuid with KVM!) How hard would that be to hook up to the
pre-random-init code?

-Kees

-- 
Kees Cook
Chrome OS Security

Re: [PATCH] random: seed random_int_secret at least poorly at core_initcall time

[Theodore Ts'o]

On Fri, Nov 15, 2013 at 10:33:04AM -0800, Kees Cook wrote:
> 
> When the static stack canary was mentioned during the ARM summit, I
> dug around a little bit and saw that at very early boot, yes, it was
> always the same, but after boot finished, it was different from boot
> to boot. I didn't get far enough to figure out what was changing it
> later on.

I've been in Seoul this past week, so I haven't had a chance look more
closely at this, but what's not clear to me what the impact will be of
having a static statck canary during early boot.  Does that mean the
stack canary for the certain kernel threads and the pid 1 are always
constant, since their stacks are getting set up before we're actually
able to initialize the stack canary with something random?

     		       	     	    	 - Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[PATCH net-next 4/6] random32: move rnd_state to linux/random.h

[Daniel Borkmann]

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 <jeykholt@cisco.com>
Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
Signed-off-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
---
 include/linux/random.h      | 4 ++++
 include/uapi/linux/random.h | 7 -------
 2 files changed, 4 insertions(+), 7 deletions(-)

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 */
-- 
1.8.3.1

[PATCH net-next 5/6] random32: upgrade taus88 generator to taus113 from errata paper

[Daniel Borkmann]

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 <fweimer@redhat.com>
Cc: Theodore Ts'o <tytso@mit.edu>
Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
Signed-off-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
---
 include/linux/random.h | 11 +++----
 lib/random32.c         | 80 +++++++++++++++++++++++++++++---------------------
 2 files changed, 52 insertions(+), 39 deletions(-)

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 e048416..7b8ed69 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)<<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 +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);
-- 
1.8.3.1

[PATCH net-next 6/6] random32: add test cases for taus113 implementation

[Daniel Borkmann]

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 <fweimer@redhat.com>
Cc: Theodore Ts'o <tytso@mit.edu>
Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
Signed-off-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
---
 lib/Kconfig    |   7 +++
 lib/random32.c | 195 +++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 196 insertions(+), 6 deletions(-)

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 7b8ed69..bc2016a 100644
--- a/lib/random32.c
+++ b/lib/random32.c
@@ -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);
 
@@ -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
-- 
1.8.3.1

Re: [PATCH net-next 0/6] prandom fixes/improvements

[David Miller]

From: Daniel Borkmann <dborkman@redhat.com>
Date: Mon, 11 Nov 2013 12:20:31 +0100

> 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.

Ok, series applied, I'll give Linus the merge conflict resolution
instructions.

Thanks!

Re: [PATCH net-next 0/6] prandom fixes/improvements

[Hannes Frederic Sowa]

On Mon, Nov 11, 2013 at 02:33:41PM -0500, David Miller wrote:
> From: Daniel Borkmann <dborkman@redhat.com>
> Date: Mon, 11 Nov 2013 12:20:31 +0100
> 
> > 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.
> 
> Ok, series applied, I'll give Linus the merge conflict resolution
> instructions.

We would also suggest to push Patch #1 to -stable.

Thank you,

  Hannes

Re: [PATCH net-next 0/6] prandom fixes/improvements

[David Miller]

From: Hannes Frederic Sowa <hannes@stressinduktion.org>
Date: Mon, 11 Nov 2013 20:44:32 +0100

> On Mon, Nov 11, 2013 at 02:33:41PM -0500, David Miller wrote:
>> From: Daniel Borkmann <dborkman@redhat.com>
>> Date: Mon, 11 Nov 2013 12:20:31 +0100
>> 
>> > 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.
>> 
>> Ok, series applied, I'll give Linus the merge conflict resolution
>> instructions.
> 
> We would also suggest to push Patch #1 to -stable.

Yes Daniel mentioned that, I queued it up already.

Thanks.