LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
* [PATCH] Fix xoring of arch_get_random_long into crng->state array
@ 2019-04-02 22:00 Neil Horman
  2019-05-29 13:42 ` Neil Horman
  2019-05-30  3:12 ` Theodore Ts'o
  0 siblings, 2 replies; 8+ messages in thread
From: Neil Horman @ 2019-04-02 22:00 UTC (permalink / raw)
  To: linux-kernel
  Cc: Neil Horman, Steve Grubb, Theodore Ts'o, Arnd Bergmann,
	Greg Kroah-Hartman

When _crng_extract is called, any arch that has a registered
arch_get_random_long method, attempts to mix an unsigned long value into
the crng->state buffer, it only mixes in 32 of the 64 bits available,
because the state buffer is an array of u32 values, even though 2 u32
are expected to be filled (owing to the fact that it expects indexes 14
and 15 to be filled).

Bring the expected behavior into alignment by casting index 14 to an
unsignled long pointer, and xoring that in instead.

Tested successfully by myself

Signed-off-by: Neil Horman <nhorman@tuxdriver.com>
Reported-by: Steve Grubb <sgrubb@redhat.com>
CC: "Theodore Ts'o" <tytso@mit.edu>
CC: Arnd Bergmann <arnd@arndb.de>
CC: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
---
 drivers/char/random.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 38c6d1af6d1c..8178618458ac 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -975,14 +975,16 @@ static void _extract_crng(struct crng_state *crng,
 			  __u8 out[CHACHA_BLOCK_SIZE])
 {
 	unsigned long v, flags;
-
+	unsigned long *archrnd;
 	if (crng_ready() &&
 	    (time_after(crng_global_init_time, crng->init_time) ||
 	     time_after(jiffies, crng->init_time + CRNG_RESEED_INTERVAL)))
 		crng_reseed(crng, crng == &primary_crng ? &input_pool : NULL);
 	spin_lock_irqsave(&crng->lock, flags);
-	if (arch_get_random_long(&v))
-		crng->state[14] ^= v;
+	if (arch_get_random_long(&v)) {
+		archrnd = (unsigned long *)&crng->state[14];
+		*archrnd ^= v;
+	}
 	chacha20_block(&crng->state[0], out);
 	if (crng->state[12] == 0)
 		crng->state[13]++;
-- 
2.20.1


^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] Fix xoring of arch_get_random_long into crng->state array
  2019-04-02 22:00 [PATCH] Fix xoring of arch_get_random_long into crng->state array Neil Horman
@ 2019-05-29 13:42 ` Neil Horman
  2019-05-29 13:51   ` David Laight
  2019-05-30  3:12 ` Theodore Ts'o
  1 sibling, 1 reply; 8+ messages in thread
From: Neil Horman @ 2019-05-29 13:42 UTC (permalink / raw)
  To: linux-kernel
  Cc: Steve Grubb, Theodore Ts'o, Arnd Bergmann, Greg Kroah-Hartman

On Tue, Apr 02, 2019 at 06:00:25PM -0400, Neil Horman wrote:
> When _crng_extract is called, any arch that has a registered
> arch_get_random_long method, attempts to mix an unsigned long value into
> the crng->state buffer, it only mixes in 32 of the 64 bits available,
> because the state buffer is an array of u32 values, even though 2 u32
> are expected to be filled (owing to the fact that it expects indexes 14
> and 15 to be filled).
> 
> Bring the expected behavior into alignment by casting index 14 to an
> unsignled long pointer, and xoring that in instead.
> 
> Tested successfully by myself
> 
> Signed-off-by: Neil Horman <nhorman@tuxdriver.com>
> Reported-by: Steve Grubb <sgrubb@redhat.com>
> CC: "Theodore Ts'o" <tytso@mit.edu>
> CC: Arnd Bergmann <arnd@arndb.de>
> CC: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
> ---
>  drivers/char/random.c | 8 +++++---
>  1 file changed, 5 insertions(+), 3 deletions(-)
> 
> diff --git a/drivers/char/random.c b/drivers/char/random.c
> index 38c6d1af6d1c..8178618458ac 100644
> --- a/drivers/char/random.c
> +++ b/drivers/char/random.c
> @@ -975,14 +975,16 @@ static void _extract_crng(struct crng_state *crng,
>  			  __u8 out[CHACHA_BLOCK_SIZE])
>  {
>  	unsigned long v, flags;
> -
> +	unsigned long *archrnd;
>  	if (crng_ready() &&
>  	    (time_after(crng_global_init_time, crng->init_time) ||
>  	     time_after(jiffies, crng->init_time + CRNG_RESEED_INTERVAL)))
>  		crng_reseed(crng, crng == &primary_crng ? &input_pool : NULL);
>  	spin_lock_irqsave(&crng->lock, flags);
> -	if (arch_get_random_long(&v))
> -		crng->state[14] ^= v;
> +	if (arch_get_random_long(&v)) {
> +		archrnd = (unsigned long *)&crng->state[14];
> +		*archrnd ^= v;
> +	}
>  	chacha20_block(&crng->state[0], out);
>  	if (crng->state[12] == 0)
>  		crng->state[13]++;
> -- 
> 2.20.1
> 
> 

Ping, Arnd, Ted, Greg, any comment here?
Neil


^ permalink raw reply	[flat|nested] 8+ messages in thread

* RE: [PATCH] Fix xoring of arch_get_random_long into crng->state array
  2019-05-29 13:42 ` Neil Horman
@ 2019-05-29 13:51   ` David Laight
  2019-05-29 15:51     ` Neil Horman
  0 siblings, 1 reply; 8+ messages in thread
From: David Laight @ 2019-05-29 13:51 UTC (permalink / raw)
  To: 'Neil Horman', linux-kernel
  Cc: Steve Grubb, Theodore Ts'o, Arnd Bergmann, Greg Kroah-Hartman

From: Neil Horman
> Sent: 29 May 2019 14:42
> On Tue, Apr 02, 2019 at 06:00:25PM -0400, Neil Horman wrote:
> > When _crng_extract is called, any arch that has a registered
> > arch_get_random_long method, attempts to mix an unsigned long value into
> > the crng->state buffer, it only mixes in 32 of the 64 bits available,
> > because the state buffer is an array of u32 values, even though 2 u32
> > are expected to be filled (owing to the fact that it expects indexes 14
> > and 15 to be filled).
> >
> > Bring the expected behavior into alignment by casting index 14 to an
> > unsignled long pointer, and xoring that in instead.
...
> > diff --git a/drivers/char/random.c b/drivers/char/random.c
> > index 38c6d1af6d1c..8178618458ac 100644
> > --- a/drivers/char/random.c
> > +++ b/drivers/char/random.c
> > @@ -975,14 +975,16 @@ static void _extract_crng(struct crng_state *crng,
> >  			  __u8 out[CHACHA_BLOCK_SIZE])
> >  {
> >  	unsigned long v, flags;
> > -
> > +	unsigned long *archrnd;
> >  	if (crng_ready() &&
> >  	    (time_after(crng_global_init_time, crng->init_time) ||
> >  	     time_after(jiffies, crng->init_time + CRNG_RESEED_INTERVAL)))
> >  		crng_reseed(crng, crng == &primary_crng ? &input_pool : NULL);
> >  	spin_lock_irqsave(&crng->lock, flags);
> > -	if (arch_get_random_long(&v))
> > -		crng->state[14] ^= v;
> > +	if (arch_get_random_long(&v)) {
> > +		archrnd = (unsigned long *)&crng->state[14];
> > +		*archrnd ^= v;
> > +	}

Isn't that likely to generate a misaligned memory access?

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)


^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] Fix xoring of arch_get_random_long into crng->state array
  2019-05-29 13:51   ` David Laight
@ 2019-05-29 15:51     ` Neil Horman
  2019-05-29 15:57       ` David Laight
  0 siblings, 1 reply; 8+ messages in thread
From: Neil Horman @ 2019-05-29 15:51 UTC (permalink / raw)
  To: David Laight
  Cc: linux-kernel, Steve Grubb, Theodore Ts'o, Arnd Bergmann,
	Greg Kroah-Hartman

On Wed, May 29, 2019 at 01:51:24PM +0000, David Laight wrote:
> From: Neil Horman
> > Sent: 29 May 2019 14:42
> > On Tue, Apr 02, 2019 at 06:00:25PM -0400, Neil Horman wrote:
> > > When _crng_extract is called, any arch that has a registered
> > > arch_get_random_long method, attempts to mix an unsigned long value into
> > > the crng->state buffer, it only mixes in 32 of the 64 bits available,
> > > because the state buffer is an array of u32 values, even though 2 u32
> > > are expected to be filled (owing to the fact that it expects indexes 14
> > > and 15 to be filled).
> > >
> > > Bring the expected behavior into alignment by casting index 14 to an
> > > unsignled long pointer, and xoring that in instead.
> ...
> > > diff --git a/drivers/char/random.c b/drivers/char/random.c
> > > index 38c6d1af6d1c..8178618458ac 100644
> > > --- a/drivers/char/random.c
> > > +++ b/drivers/char/random.c
> > > @@ -975,14 +975,16 @@ static void _extract_crng(struct crng_state *crng,
> > >  			  __u8 out[CHACHA_BLOCK_SIZE])
> > >  {
> > >  	unsigned long v, flags;
> > > -
> > > +	unsigned long *archrnd;
> > >  	if (crng_ready() &&
> > >  	    (time_after(crng_global_init_time, crng->init_time) ||
> > >  	     time_after(jiffies, crng->init_time + CRNG_RESEED_INTERVAL)))
> > >  		crng_reseed(crng, crng == &primary_crng ? &input_pool : NULL);
> > >  	spin_lock_irqsave(&crng->lock, flags);
> > > -	if (arch_get_random_long(&v))
> > > -		crng->state[14] ^= v;
> > > +	if (arch_get_random_long(&v)) {
> > > +		archrnd = (unsigned long *)&crng->state[14];
> > > +		*archrnd ^= v;
> > > +	}
> 
> Isn't that likely to generate a misaligned memory access?
> 
I'm not quite sure how it would, crng->state is an array of _u32's, and so every
even element should be on a 64 bit boundary.

Neil

> 	David
> 
> -
> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> Registration No: 1397386 (Wales)
> 
> 

^ permalink raw reply	[flat|nested] 8+ messages in thread

* RE: [PATCH] Fix xoring of arch_get_random_long into crng->state array
  2019-05-29 15:51     ` Neil Horman
@ 2019-05-29 15:57       ` David Laight
  2019-05-29 16:27         ` Neil Horman
  0 siblings, 1 reply; 8+ messages in thread
From: David Laight @ 2019-05-29 15:57 UTC (permalink / raw)
  To: 'Neil Horman'
  Cc: linux-kernel, Steve Grubb, Theodore Ts'o, Arnd Bergmann,
	Greg Kroah-Hartman

From: Neil Horman [mailto:nhorman@tuxdriver.com]
> Sent: 29 May 2019 16:52
> On Wed, May 29, 2019 at 01:51:24PM +0000, David Laight wrote:
> > From: Neil Horman
> > > Sent: 29 May 2019 14:42
> > > On Tue, Apr 02, 2019 at 06:00:25PM -0400, Neil Horman wrote:
> > > > When _crng_extract is called, any arch that has a registered
> > > > arch_get_random_long method, attempts to mix an unsigned long value into
> > > > the crng->state buffer, it only mixes in 32 of the 64 bits available,
> > > > because the state buffer is an array of u32 values, even though 2 u32
> > > > are expected to be filled (owing to the fact that it expects indexes 14
> > > > and 15 to be filled).
> > > >
> > > > Bring the expected behavior into alignment by casting index 14 to an
> > > > unsignled long pointer, and xoring that in instead.
> > ...
> > > > diff --git a/drivers/char/random.c b/drivers/char/random.c
> > > > index 38c6d1af6d1c..8178618458ac 100644
> > > > --- a/drivers/char/random.c
> > > > +++ b/drivers/char/random.c
> > > > @@ -975,14 +975,16 @@ static void _extract_crng(struct crng_state *crng,
> > > >  			  __u8 out[CHACHA_BLOCK_SIZE])
> > > >  {
> > > >  	unsigned long v, flags;
> > > > -
> > > > +	unsigned long *archrnd;
> > > >  	if (crng_ready() &&
> > > >  	    (time_after(crng_global_init_time, crng->init_time) ||
> > > >  	     time_after(jiffies, crng->init_time + CRNG_RESEED_INTERVAL)))
> > > >  		crng_reseed(crng, crng == &primary_crng ? &input_pool : NULL);
> > > >  	spin_lock_irqsave(&crng->lock, flags);
> > > > -	if (arch_get_random_long(&v))
> > > > -		crng->state[14] ^= v;
> > > > +	if (arch_get_random_long(&v)) {
> > > > +		archrnd = (unsigned long *)&crng->state[14];
> > > > +		*archrnd ^= v;
> > > > +	}
> >
> > Isn't that likely to generate a misaligned memory access?
> >
> I'm not quite sure how it would, crng->state is an array of _u32's, and so every
> even element should be on a 64 bit boundary.

Only if the first item is aligned....
Add a u32 before it and you'll probably flip the alignment.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)


^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] Fix xoring of arch_get_random_long into crng->state array
  2019-05-29 15:57       ` David Laight
@ 2019-05-29 16:27         ` Neil Horman
  0 siblings, 0 replies; 8+ messages in thread
From: Neil Horman @ 2019-05-29 16:27 UTC (permalink / raw)
  To: David Laight
  Cc: linux-kernel, Steve Grubb, Theodore Ts'o, Arnd Bergmann,
	Greg Kroah-Hartman

On Wed, May 29, 2019 at 03:57:07PM +0000, David Laight wrote:
> From: Neil Horman [mailto:nhorman@tuxdriver.com]
> > Sent: 29 May 2019 16:52
> > On Wed, May 29, 2019 at 01:51:24PM +0000, David Laight wrote:
> > > From: Neil Horman
> > > > Sent: 29 May 2019 14:42
> > > > On Tue, Apr 02, 2019 at 06:00:25PM -0400, Neil Horman wrote:
> > > > > When _crng_extract is called, any arch that has a registered
> > > > > arch_get_random_long method, attempts to mix an unsigned long value into
> > > > > the crng->state buffer, it only mixes in 32 of the 64 bits available,
> > > > > because the state buffer is an array of u32 values, even though 2 u32
> > > > > are expected to be filled (owing to the fact that it expects indexes 14
> > > > > and 15 to be filled).
> > > > >
> > > > > Bring the expected behavior into alignment by casting index 14 to an
> > > > > unsignled long pointer, and xoring that in instead.
> > > ...
> > > > > diff --git a/drivers/char/random.c b/drivers/char/random.c
> > > > > index 38c6d1af6d1c..8178618458ac 100644
> > > > > --- a/drivers/char/random.c
> > > > > +++ b/drivers/char/random.c
> > > > > @@ -975,14 +975,16 @@ static void _extract_crng(struct crng_state *crng,
> > > > >  			  __u8 out[CHACHA_BLOCK_SIZE])
> > > > >  {
> > > > >  	unsigned long v, flags;
> > > > > -
> > > > > +	unsigned long *archrnd;
> > > > >  	if (crng_ready() &&
> > > > >  	    (time_after(crng_global_init_time, crng->init_time) ||
> > > > >  	     time_after(jiffies, crng->init_time + CRNG_RESEED_INTERVAL)))
> > > > >  		crng_reseed(crng, crng == &primary_crng ? &input_pool : NULL);
> > > > >  	spin_lock_irqsave(&crng->lock, flags);
> > > > > -	if (arch_get_random_long(&v))
> > > > > -		crng->state[14] ^= v;
> > > > > +	if (arch_get_random_long(&v)) {
> > > > > +		archrnd = (unsigned long *)&crng->state[14];
> > > > > +		*archrnd ^= v;
> > > > > +	}
> > >
> > > Isn't that likely to generate a misaligned memory access?
> > >
> > I'm not quite sure how it would, crng->state is an array of _u32's, and so every
> > even element should be on a 64 bit boundary.
> 
> Only if the first item is aligned....
> Add a u32 before it and you'll probably flip the alignment.
> 
Sure (assuming no padding by the compiler of leading elements), but thats not
the case here, state is the first element in the array.  I suppose we could add
an __attribute__((aligned,8)) to the element if you think it would help

Neil

> 	David
> 
> -
> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> Registration No: 1397386 (Wales)
> 
> 

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] Fix xoring of arch_get_random_long into crng->state array
  2019-04-02 22:00 [PATCH] Fix xoring of arch_get_random_long into crng->state array Neil Horman
  2019-05-29 13:42 ` Neil Horman
@ 2019-05-30  3:12 ` Theodore Ts'o
  2019-05-30 11:14   ` Neil Horman
  1 sibling, 1 reply; 8+ messages in thread
From: Theodore Ts'o @ 2019-05-30  3:12 UTC (permalink / raw)
  To: Neil Horman; +Cc: linux-kernel, Steve Grubb, Arnd Bergmann, Greg Kroah-Hartman

On Tue, Apr 02, 2019 at 06:00:25PM -0400, Neil Horman wrote:
> When _crng_extract is called, any arch that has a registered
> arch_get_random_long method, attempts to mix an unsigned long value into
> the crng->state buffer, it only mixes in 32 of the 64 bits available,
> because the state buffer is an array of u32 values, even though 2 u32
> are expected to be filled (owing to the fact that it expects indexes 14
> and 15 to be filled).

Index 15 does get initialized; in fact, it's changed each time
crng_reseed() is called.

The way things currently work is that we use state[12] and state[13]
as 64-bit counter (it gets incremented each time we call
_extract_crng), and state[14] and state[15] are nonce values.  After
crng->state has been in use for five minutes, we reseed the crng by
grabbing randomness from the input pool, and using that to initialize
state[4..15].  (State[0..3] are always set to the ChaCha20 constant of
"expand 32-byte k".)

If the CPU provides and RDRAND-like instruction (which can be the case
for x86, PPC, and S390), we xor it into state[14].  Whether we xor any
extra entropy into state[15] to be honest, really doesn't matter much.
I think I was trying to keep things simple, and it wasn't worth it to
call RDRAND twice on a 32-bit x86.  (And there isn't an
arch_get_random_long_long.  :-)

Why do we do this at all?  Well, the goal was to feed in some
contributing randomness from RDRAND when we turn the CRNG crank.  (The
reason why we don't just XOR in the RDRAND into the output ohf the
CRNG is mainly to assuage critics that hypothetical RDRAND backdoor
has access to the CPU registers.  So we perturb the inputs to the
CRNG, on the theory that if malicious firmware can reverse
CHACHA20... we've got bigger problems.  :-)  We get up to 20 bytes out
of a single turn of the CRNG crank, so whether we mix in 4 bytes or 8
bytes from RDRAND, we're never going to be depending on RDRAND
completely in any case.

The bottom line is that I'm not at all convinced it worth the effort
to mix in 8 bytes versus 4 bytes from RDRAND.  This is really a CRNG,
and the RDRAND inputs really don't change that.

    	       	      	     	   	  - Ted

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] Fix xoring of arch_get_random_long into crng->state array
  2019-05-30  3:12 ` Theodore Ts'o
@ 2019-05-30 11:14   ` Neil Horman
  0 siblings, 0 replies; 8+ messages in thread
From: Neil Horman @ 2019-05-30 11:14 UTC (permalink / raw)
  To: Theodore Ts'o, linux-kernel, Steve Grubb, Arnd Bergmann,
	Greg Kroah-Hartman

On Wed, May 29, 2019 at 11:12:01PM -0400, Theodore Ts'o wrote:
> On Tue, Apr 02, 2019 at 06:00:25PM -0400, Neil Horman wrote:
> > When _crng_extract is called, any arch that has a registered
> > arch_get_random_long method, attempts to mix an unsigned long value into
> > the crng->state buffer, it only mixes in 32 of the 64 bits available,
> > because the state buffer is an array of u32 values, even though 2 u32
> > are expected to be filled (owing to the fact that it expects indexes 14
> > and 15 to be filled).
> 
> Index 15 does get initialized; in fact, it's changed each time
> crng_reseed() is called.
> 
> The way things currently work is that we use state[12] and state[13]
> as 64-bit counter (it gets incremented each time we call
> _extract_crng), and state[14] and state[15] are nonce values.  After
> crng->state has been in use for five minutes, we reseed the crng by
> grabbing randomness from the input pool, and using that to initialize
> state[4..15].  (State[0..3] are always set to the ChaCha20 constant of
> "expand 32-byte k".)
> 
> If the CPU provides and RDRAND-like instruction (which can be the case
> for x86, PPC, and S390), we xor it into state[14].  Whether we xor any
> extra entropy into state[15] to be honest, really doesn't matter much.
> I think I was trying to keep things simple, and it wasn't worth it to
> call RDRAND twice on a 32-bit x86.  (And there isn't an
> arch_get_random_long_long.  :-)
> 
> Why do we do this at all?  Well, the goal was to feed in some
> contributing randomness from RDRAND when we turn the CRNG crank.  (The
> reason why we don't just XOR in the RDRAND into the output ohf the
> CRNG is mainly to assuage critics that hypothetical RDRAND backdoor
> has access to the CPU registers.  So we perturb the inputs to the
> CRNG, on the theory that if malicious firmware can reverse
> CHACHA20... we've got bigger problems.  :-)  We get up to 20 bytes out
> of a single turn of the CRNG crank, so whether we mix in 4 bytes or 8
> bytes from RDRAND, we're never going to be depending on RDRAND
> completely in any case.
> 
> The bottom line is that I'm not at all convinced it worth the effort
> to mix in 8 bytes versus 4 bytes from RDRAND.  This is really a CRNG,
> and the RDRAND inputs really don't change that.
> 
Ok, so what I'm getting is that the exclusion of the second 32 bit word here
from &crng->state[15], isn't an oversight, its just skipped because its not
worth taking the time for the extra write there, and this is not a bug.  I'm ok
with that.

Thanks for the explination
Neil

>     	       	      	     	   	  - Ted
> 

^ permalink raw reply	[flat|nested] 8+ messages in thread

end of thread, other threads:[~2019-05-30 11:15 UTC | newest]

Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-04-02 22:00 [PATCH] Fix xoring of arch_get_random_long into crng->state array Neil Horman
2019-05-29 13:42 ` Neil Horman
2019-05-29 13:51   ` David Laight
2019-05-29 15:51     ` Neil Horman
2019-05-29 15:57       ` David Laight
2019-05-29 16:27         ` Neil Horman
2019-05-30  3:12 ` Theodore Ts'o
2019-05-30 11:14   ` Neil Horman

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).