prandom fixes/improvements

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

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.

---
 include/linux/random.h |  6 +++---
 lib/random32.c         | 14 +++++++-------
 2 files changed, 10 insertions(+), 10 deletions(-)

index 6312dd9..bf9085e 100644
@@ -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

index 52280d5..01e8890 100644
@@ -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

From: Hannes Frederic Sowa <[email protected]>

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.

---
 lib/random32.c | 23 +++++++++++++++++++++++
 1 file changed, 23 insertions(+)

index 01e8890..165d0a5f 100644
@@ -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

From: Hannes Frederic Sowa <[email protected]>

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.

---
 drivers/char/random.c  |  5 ++++-
 include/linux/random.h |  1 +
 lib/random32.c         | 23 ++++++++++++++++++++++-
 3 files changed, 27 insertions(+), 2 deletions(-)

index 7a744d3..4fe5609 100644
@@ -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,

index bf9085e..5117ae3 100644
@@ -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);

index 165d0a5f..e048416 100644
@@ -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

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

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.

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.

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

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 [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

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 [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

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 ?

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 [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

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

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?

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

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

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 [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

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.

---
 drivers/char/random.c | 10 ++++++++++
 1 file changed, 10 insertions(+)

index 4fe5609..9f2623c 100644
@@ -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 [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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 [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

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

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.

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

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 [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

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

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

-Kees

Kees Cook
Chrome OS Security

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 [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

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.

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 [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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 [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

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

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 [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html

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.

---
 include/linux/random.h      | 4 ++++
 include/uapi/linux/random.h | 7 -------
 2 files changed, 4 insertions(+), 7 deletions(-)

index 5117ae3..8ef0b70 100644
@@ -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);
 

index 7471b5b..fff3528 100644
@@ -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

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.

---
 include/linux/random.h | 11 +++----
 lib/random32.c         | 80 +++++++++++++++++++++++++++++---------------------
 2 files changed, 52 insertions(+), 39 deletions(-)

index 8ef0b70..4002b3d 100644
@@ -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

1.8.3.1

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.

---
 lib/Kconfig    |   7 +++
 lib/random32.c | 195 +++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 196 insertions(+), 6 deletions(-)

index b3c8be0..75485e1 100644
@@ -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
 #

1.8.3.1

From: Daniel Borkmann <[email protected]>
Date: Mon, 11 Nov 2013 12:20:31 +0100

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

Thanks!

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

Thank you,

Hannes

From: Hannes Frederic Sowa <[email protected]>
Date: Mon, 11 Nov 2013 20:44:32 +0100

Yes Daniel mentioned that, I queued it up already.

Thanks.