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

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

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

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

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

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

[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@mit.edu>
Signed-off-by: Hannes Frederic Sowa <hannes@stressinduktion.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

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?

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

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@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?

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.

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@mit.edu> 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

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

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