[PATCH RFC] random: introduce get_random_bytes_busy_wait_initialized

[PATCH RFC] random: introduce get_random_bytes_busy_wait_initialized

[Hannes Frederic Sowa]

On Tue, Sep 24, 2013 at 06:19:57AM -0700, Eric Dumazet wrote:
> From: Eric Dumazet <edumazet@google.com>
> 
> A host might need net_secret[] and never open a single socket. 
> 
> Problem added in commit aebda156a570782
> ("net: defer net_secret[] initialization")
> 
> Based on prior patch from Hannes Frederic Sowa.
> 
> Reported-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
> Signed-off-by: Eric Dumazet <edumazet@google.com>

Perhaps we can even do a bit better? This patch is a RFC and I could split the
random and network parts if needed.

[PATCH RFC] random: introduce get_random_bytes_busy_wait_initialized

We want to use good entropy for initializing the secret keys used for
hashing in the core network stack. So busy wait before extracting random
data until the nonblocking_pool is initialized.

Further entropy is also gathered by interrupts, so we are guaranteed to
make progress here.

Cc: Eric Dumazet <eric.dumazet@gmail.com>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
---
 drivers/char/random.c  | 18 ++++++++++++++++++
 include/linux/random.h |  1 +
 net/core/secure_seq.c  |  3 ++-
 net/ipv4/af_inet.c     |  2 +-
 4 files changed, 22 insertions(+), 2 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 7737b5b..50e8030 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1058,6 +1058,24 @@ void get_random_bytes(void *buf, int nbytes)
 EXPORT_SYMBOL(get_random_bytes);
 
 /*
+ * Busy loop until the nonblocking_pool is intialized and return
+ * random data in buf of size nbytes.
+ *
+ * This is used by the network stack to defer the extraction of
+ * entropy from the nonblocking_pool until the pool is initialized.
+ *
+ * We need to busy loop here, because we could be called from an
+ * atomic section.
+ */
+void get_random_bytes_busy_wait_initialized(void *buf, int nbytes)
+{
+	while (!nonblocking_pool.initialized)
+		cpu_relax();
+	get_random_bytes(buf, nbytes);
+}
+EXPORT_SYMBOL(get_random_bytes_busy_wait_initialized);
+
+/*
  * This function will use the architecture-specific hardware random
  * number generator if it is available.  The arch-specific hw RNG will
  * almost certainly be faster than what we can do in software, but it
diff --git a/include/linux/random.h b/include/linux/random.h
index 3b9377d..0b7e7dd 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -15,6 +15,7 @@ extern void add_input_randomness(unsigned int type, unsigned int code,
 extern void add_interrupt_randomness(int irq, int irq_flags);
 
 extern void get_random_bytes(void *buf, int nbytes);
+void get_random_bytes_busy_wait_initialized(void *buf, int nbbytes);
 extern void get_random_bytes_arch(void *buf, int nbytes);
 void generate_random_uuid(unsigned char uuid_out[16]);
 
diff --git a/net/core/secure_seq.c b/net/core/secure_seq.c
index 3f1ec15..ac55cb7 100644
--- a/net/core/secure_seq.c
+++ b/net/core/secure_seq.c
@@ -24,7 +24,8 @@ static void net_secret_init(void)
 
 	for (i = NET_SECRET_SIZE; i > 0;) {
 		do {
-			get_random_bytes(&tmp, sizeof(tmp));
+			get_random_bytes_busy_wait_initialized(&tmp,
+							       sizeof(tmp));
 		} while (!tmp);
 		cmpxchg(&net_secret[--i], 0, tmp);
 	}
diff --git a/net/ipv4/af_inet.c b/net/ipv4/af_inet.c
index cfeb85c..3edd277 100644
--- a/net/ipv4/af_inet.c
+++ b/net/ipv4/af_inet.c
@@ -260,7 +260,7 @@ void build_ehash_secret(void)
 	u32 rnd;
 
 	do {
-		get_random_bytes(&rnd, sizeof(rnd));
+		get_random_bytes_busy_wait_initialized(&rnd, sizeof(rnd));
 	} while (rnd == 0);
 
 	if (cmpxchg(&inet_ehash_secret, 0, rnd) == 0)
-- 
1.8.3.1

Re: [PATCH RFC] random: introduce get_random_bytes_busy_wait_initialized

[Eric Dumazet]

On Wed, 2013-09-25 at 11:00 +0200, Hannes Frederic Sowa wrote:

>  /*
> + * Busy loop until the nonblocking_pool is intialized and return
> + * random data in buf of size nbytes.
> + *
> + * This is used by the network stack to defer the extraction of
> + * entropy from the nonblocking_pool until the pool is initialized.
> + *
> + * We need to busy loop here, because we could be called from an
> + * atomic section.
> + */
> +void get_random_bytes_busy_wait_initialized(void *buf, int nbytes)
> +{
> +	while (!nonblocking_pool.initialized)
> +		cpu_relax();
> +	get_random_bytes(buf, nbytes);
> +}

No idea if this can work if called from IRQ context.

How is nonblocking_poll initialized if host has a single cpu ?

Re: [PATCH RFC] random: introduce get_random_bytes_busy_wait_initialized

[Hannes Frederic Sowa]

On Wed, Sep 25, 2013 at 05:06:50AM -0700, Eric Dumazet wrote:
> On Wed, 2013-09-25 at 11:00 +0200, Hannes Frederic Sowa wrote:
> 
> >  /*
> > + * Busy loop until the nonblocking_pool is intialized and return
> > + * random data in buf of size nbytes.
> > + *
> > + * This is used by the network stack to defer the extraction of
> > + * entropy from the nonblocking_pool until the pool is initialized.
> > + *
> > + * We need to busy loop here, because we could be called from an
> > + * atomic section.
> > + */
> > +void get_random_bytes_busy_wait_initialized(void *buf, int nbytes)
> > +{
> > +	while (!nonblocking_pool.initialized)
> > +		cpu_relax();
> > +	get_random_bytes(buf, nbytes);
> > +}
> 
> No idea if this can work if called from IRQ context.
> 
> How is nonblocking_poll initialized if host has a single cpu ?

We increase the entropy_count and can initialize the random pool from
handle_irq_event.

We can document that it should not get called from irq context and
maybe add a WARN_ON(irqs_disabled())?

Re: [PATCH RFC] random: introduce get_random_bytes_busy_wait_initialized

[Theodore Ts'o]

On Wed, Sep 25, 2013 at 11:00:34AM +0200, Hannes Frederic Sowa wrote:
> [PATCH RFC] random: introduce get_random_bytes_busy_wait_initialized
> 
> We want to use good entropy for initializing the secret keys used for
> hashing in the core network stack. So busy wait before extracting random
> data until the nonblocking_pool is initialized.
> 
> Further entropy is also gathered by interrupts, so we are guaranteed to
> make progress here.

One thing that makes me a bit worried is that on certain
architectures, it may take quite a while before we get enough entropy
such that the non-blocking pool gets initialized.

Speaking more generally, there are many different reasons why
different parts of the kernel needs randomness.  I've found a number
of places (mostly in various file systems so far because I know that
subsystem better) because we are trying to use a random number
generator with a higher level of guarantees than what was really
required.

What's not completely clear to me is what's the potential danger if
build_ehash_secret() is initialized with a value that might be known
to an adversary.  I'll note that inet_ehash_secret() is a 32-bit uint.
A 32-bit number isn't all that hard for an adversary to brute force.
If the answer is there's now oracle that can be used so an adversary
can tell whether or not they have correctly figured out the ehash
secret, then it's not that clear that it's worth blocking until the
urandom pool has 128 bits of entropy, when ehash_secret is only a
32-bit value.

Speaking even more generally, any time you have subsystems grabbing
random entropy very shortly after boot, especially if it's less than
64 bits, it's really good idea of the secret gets periodically
rekeyed.  I understand why that may be hard in this case, since it
would require rehashing all of the currently open sockets, and maybe
in this case the security requirements are such that it's not really
necessary.  But it's something we should definitely keep in mind for
situations where we are generating random session keys for CIFS,
ipsec, etc.

Regards,

						- Ted

Re: [PATCH RFC] random: introduce get_random_bytes_busy_wait_initialized

[Hannes Frederic Sowa]

Hi!

Thanks for looking into this!

On Wed, Oct 02, 2013 at 11:10:18AM -0400, Theodore Ts'o wrote:
> On Wed, Sep 25, 2013 at 11:00:34AM +0200, Hannes Frederic Sowa wrote:
> > [PATCH RFC] random: introduce get_random_bytes_busy_wait_initialized
> > 
> > We want to use good entropy for initializing the secret keys used for
> > hashing in the core network stack. So busy wait before extracting random
> > data until the nonblocking_pool is initialized.
> > 
> > Further entropy is also gathered by interrupts, so we are guaranteed to
> > make progress here.
> 
> One thing that makes me a bit worried is that on certain
> architectures, it may take quite a while before we get enough entropy
> such that the non-blocking pool gets initialized.

Yes, I understand. My main concern is that we would feed instruction
addresses of limited randomness into the entropy pool while busy looping
until the pool is initialized on uni-processor machines. It would only be
helpful on multiprocessor machines I guess.

So, I am currently a bit skeptic if this change does improve things and
have to think about this again.

> Speaking more generally, there are many different reasons why
> different parts of the kernel needs randomness.  I've found a number
> of places (mostly in various file systems so far because I know that
> subsystem better) because we are trying to use a random number
> generator with a higher level of guarantees than what was really
> required.
> 
> What's not completely clear to me is what's the potential danger if
> build_ehash_secret() is initialized with a value that might be known
> to an adversary.  I'll note that inet_ehash_secret() is a 32-bit uint.
> A 32-bit number isn't all that hard for an adversary to brute force.
> If the answer is there's now oracle that can be used so an adversary
> can tell whether or not they have correctly figured out the ehash
> secret, then it's not that clear that it's worth blocking until the
> urandom pool has 128 bits of entropy, when ehash_secret is only a
> 32-bit value.

It may be possible to find multicollisions if the hash is known which could
lead to a DoS against the hash table if the lookups become linear (and someone
finds a fast way to do this for jash in this case, also depending if one
hashes variable or static size data). So this is minor issue currently.

But this is not my main concern:

We currently initialize the syncookie secrets pretty early on boot-up:
http://lxr.free-electrons.com/source/net/ipv4/syncookies.c#L31

Because of this problem I came up with another solution. My plan is to
introduce a macro 'net_get_random_once' which could be used to initialize
secret keys used for hashing as late as possible:
http://patchwork.ozlabs.org/patch/278308/

David Miller suggested that I should use static_keys to reduce overhead in the
fast-path and I am currently testing this change. I'll send it for review
maybe tomorrow. Otherwise I have to come up with another solution, maybe only
specific for syncookies in the beginning.

> Speaking even more generally, any time you have subsystems grabbing
> random entropy very shortly after boot, especially if it's less than
> 64 bits, it's really good idea of the secret gets periodically
> rekeyed.  I understand why that may be hard in this case, since it
> would require rehashing all of the currently open sockets, and maybe
> in this case the security requirements are such that it's not really
> necessary.  But it's something we should definitely keep in mind for
> situations where we are generating random session keys for CIFS,
> ipsec, etc.

I agree. I will look if this is easily possible for secure_seq and
syncookies but depending on the data structure and its size it is a much
harder thing to do. I wanted to try the low-hanging fruits first. ;)

Thanks,

  Hannes

Re: [PATCH RFC] random: introduce get_random_bytes_busy_wait_initialized

[Theodore Ts'o]

On Wed, Oct 02, 2013 at 07:18:40PM +0200, Hannes Frederic Sowa wrote:
> 
> I agree. I will look if this is easily possible for secure_seq and
> syncookies but depending on the data structure and its size it is a much
> harder thing to do. I wanted to try the low-hanging fruits first. ;)

To use syncookies as an example, you shouldn't need to store all of
the old syncookies.  Instead, if every 10 minutes or so, you rekey,
and you keep both the old and the new secrets around, you could just
simply check an incoming TCP packet using first the new key, and then
the old key.  During the transition window it would take a wee bit
more CPU time, but most of the time, it wouldn't cost anything extra
in CPU time, and the only extra cost is the space for the old key.

>From a security perspective it would be much better if we tried to
make all of the places where we draw randomness and somehow try to
rekey on a periodic basis.  That way, even if the initial value isn't
super-secure, that situation will heal itself fairly rapidly.  And it
also means that even if an adversary can brute-force break a 32-bit
secret, they would have to do so within 5 or 10 minutes in order for
it to be useful, and even if they could, it would only be useful for a
short window of time.

I know it won't always be possible, but to the extent that we can do
this, it would be a big improvement from a security perspective.

Cheers,

							- Ted