[PATCH] random: initialize ChaCha20 constants with correct endianness

[PATCH] random: initialize ChaCha20 constants with correct endianness

[Eric Biggers]

From: Eric Biggers <ebiggers@google.com>

On big endian CPUs, the ChaCha20-based CRNG is using the wrong
endianness for the ChaCha20 constants.

This doesn't matter cryptographically, but technically it means it's not
ChaCha20 anymore.  Fix it to always use the standard constants.

Cc: linux-crypto@vger.kernel.org
Signed-off-by: Eric Biggers <ebiggers@google.com>
---
 drivers/char/random.c   | 4 ++--
 include/crypto/chacha.h | 9 +++++++--
 2 files changed, 9 insertions(+), 4 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 26f0a23a6f021..09b1551d4092f 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -809,7 +809,7 @@ static bool __init crng_init_try_arch_early(struct crng_state *crng)
 
 static void __maybe_unused crng_initialize_secondary(struct crng_state *crng)
 {
-	memcpy(&crng->state[0], "expand 32-byte k", 16);
+	chacha_init_consts(crng->state);
 	_get_random_bytes(&crng->state[4], sizeof(__u32) * 12);
 	crng_init_try_arch(crng);
 	crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1;
@@ -817,7 +817,7 @@ static void __maybe_unused crng_initialize_secondary(struct crng_state *crng)
 
 static void __init crng_initialize_primary(struct crng_state *crng)
 {
-	memcpy(&crng->state[0], "expand 32-byte k", 16);
+	chacha_init_consts(crng->state);
 	_extract_entropy(&input_pool, &crng->state[4], sizeof(__u32) * 12, 0);
 	if (crng_init_try_arch_early(crng) && trust_cpu) {
 		invalidate_batched_entropy();
diff --git a/include/crypto/chacha.h b/include/crypto/chacha.h
index 3a1c72fdb7cf5..dabaee6987186 100644
--- a/include/crypto/chacha.h
+++ b/include/crypto/chacha.h
@@ -47,13 +47,18 @@ static inline void hchacha_block(const u32 *state, u32 *out, int nrounds)
 		hchacha_block_generic(state, out, nrounds);
 }
 
-void chacha_init_arch(u32 *state, const u32 *key, const u8 *iv);
-static inline void chacha_init_generic(u32 *state, const u32 *key, const u8 *iv)
+static inline void chacha_init_consts(u32 *state)
 {
 	state[0]  = 0x61707865; /* "expa" */
 	state[1]  = 0x3320646e; /* "nd 3" */
 	state[2]  = 0x79622d32; /* "2-by" */
 	state[3]  = 0x6b206574; /* "te k" */
+}
+
+void chacha_init_arch(u32 *state, const u32 *key, const u8 *iv);
+static inline void chacha_init_generic(u32 *state, const u32 *key, const u8 *iv)
+{
+	chacha_init_consts(state);
 	state[4]  = key[0];
 	state[5]  = key[1];
 	state[6]  = key[2];
-- 
2.28.0

Re: [PATCH] random: initialize ChaCha20 constants with correct endianness

[Herbert Xu]

Eric Biggers <ebiggers@kernel.org> wrote:
> From: Eric Biggers <ebiggers@google.com>
> 
> On big endian CPUs, the ChaCha20-based CRNG is using the wrong
> endianness for the ChaCha20 constants.
> 
> This doesn't matter cryptographically, but technically it means it's not
> ChaCha20 anymore.  Fix it to always use the standard constants.
> 
> Cc: linux-crypto@vger.kernel.org
> Signed-off-by: Eric Biggers <ebiggers@google.com>
> ---
> drivers/char/random.c   | 4 ++--
> include/crypto/chacha.h | 9 +++++++--
> 2 files changed, 9 insertions(+), 4 deletions(-)

Acked-by: Herbert Xu <herbert@gondor.apana.org.au>
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] random: initialize ChaCha20 constants with correct endianness

[Theodore Y. Ts'o]

On Tue, Sep 15, 2020 at 09:50:13PM -0700, Eric Biggers wrote:
> From: Eric Biggers <ebiggers@google.com>
> 
> On big endian CPUs, the ChaCha20-based CRNG is using the wrong
> endianness for the ChaCha20 constants.
> 
> This doesn't matter cryptographically, but technically it means it's not
> ChaCha20 anymore.  Fix it to always use the standard constants.

I'll note that we're not technically ChaCha20 in terms of how we
handle the IV.  ChaCha20 is defined as having a 96 bit IV and a 32-bit
counter.  The counter is "usually initialized to be zero or one" (per
RFC 7539) and the counter is defined to be Little Endian.

We're currently not bothering to deal with Endian conversions with the
counter, and we're using a 64-bit counter, instead of a 32-bit
counter.  We also twiddle 32-bits of the state (crng->state[14]) by
XOR'ing it with RDRAND if available at each round, which is also a
spec violation.

WE also initialize the counter to be a random value, using the
input_pool or the primary crng state (if we are initializing the
secondary state), but given that the specification says _usually_ zero
or one, that's not an out-and-out spec violation.

As far as the other deviations / "spec violations" from ChaCha-20 are
concerned...  I'm "sorry not sorry".  :-)

I have no objections to changing things so that the first 4 words of
the crng state are more ChaCha-20-like, on the theory that most of the
cryptoanlysis work (both positive and negative) have been done with
the little-endian version of "expand 32-byte k".  I don't think it
really makes a difference, either positively or negatively.  But
technically we'd *still* not be using ChaCha20.  We could say that
we're using the ChaCha20 block function, regardless.

Cheers,

						- Ted

Re: [PATCH] random: initialize ChaCha20 constants with correct endianness

[Eric Biggers]

On Fri, Sep 18, 2020 at 04:42:07PM -0400, Theodore Y. Ts'o wrote:
>
> We're currently not bothering to deal with Endian conversions with the counter

Endianness conversion for the counter isn't needed because the implementation
only treats it as words, not as bytes.

(Exception: the counter does get filled with random bytes.  But that doesn't
matter, since they're random bytes.)

> we're using a 64-bit counter, instead of a 32-bit counter.

The original ChaCha paper (https://cr.yp.to/chacha/chacha-20080128.pdf) uses a
64-bit counter.  RFC 7539 decided to reduce it to 32-bit and expand the nonce to
96-bit.  So there are two variants, and we're using the original variant.

Alternatively, we're using RFC 7539 where we happen to increment the nonce each
time the counter wraps to 0.  That's an equivalent interpretation.

> We also twiddle 32-bits of the state (crng->state[14]) by XOR'ing it with
> RDRAND if available at each round, which is also a spec violation.

It's not after each ChaCha round, but rather after generating each block of
output.  ChaCha expands each key into 2^64 randomly accessible streams, each
containing 2^64 randomly accessible 64-byte blocks.  (Alternatively, RFC 7539
interprets those same 2^128 blocks as 2^96 streams, each with 2^32 blocks.)

So basically the output of the CRNG is:

	ChaCha20(key=k, counter=n, nonce=random(), len=64)
	ChaCha20(key=k, counter=n+1, nonce=random(), len=64)
	ChaCha20(key=k, counter=n+2, nonce=random(), len=64)

instead of:

	ChaCha20(key=k, counter=n, nonce=random(), len=<very large>)

It's still ChaCha20.  It's just that instead of doing one big invocation of
ChaCha20 where we take lots of consecutive blocks from a single stream, we do a
lot of smaller invocations where we take output from randomly selected streams.

> WE also initialize the counter to be a random value, using the
> input_pool or the primary crng state (if we are initializing the
> secondary state), but given that the specification says _usually_ zero
> or one, that's not an out-and-out spec violation.

The original ChaCha paper doesn't say that the counter has to be initialized to
0.  It just says each key generates 2^64 randomly accessible streams, each
containing 2^64 randomly accessible 64-byte blocks.  Naturally, most users want
to start the counter at 0, but that's not a *requirement*.

> I have no objections to changing things so that the first 4 words of
> the crng state are more ChaCha-20-like, on the theory that most of the
> cryptoanlysis work (both positive and negative) have been done with
> the little-endian version of "expand 32-byte k".  I don't think it
> really makes a difference, either positively or negatively.  But
> technically we'd *still* not be using ChaCha20.  We could say that
> we're using the ChaCha20 block function, regardless.

The endianness of the constants is the only thing that makes it so that the CRNG
isn't necessarily actually using ChaCha20 as defined by the original paper.
Everything else is just different ways of describing the series of calls that
are made to the ChaCha20 block function.

- Eric

Re: [PATCH] random: initialize ChaCha20 constants with correct endianness

[Eric Biggers]

On Fri, Sep 18, 2020 at 02:57:05PM -0700, Eric Biggers wrote:
> On Fri, Sep 18, 2020 at 04:42:07PM -0400, Theodore Y. Ts'o wrote:

Ted, any further feedback on this?  Are you planning to apply this patch?

- Eric

Re: [PATCH] random: initialize ChaCha20 constants with correct endianness

[Eric Biggers]

On Tue, Oct 06, 2020 at 08:51:45PM -0700, Eric Biggers wrote:
> On Fri, Sep 18, 2020 at 02:57:05PM -0700, Eric Biggers wrote:
> > On Fri, Sep 18, 2020 at 04:42:07PM -0400, Theodore Y. Ts'o wrote:
> 
> Ted, any further feedback on this?  Are you planning to apply this patch?
> 
> - Eric

Ping.

Re: [PATCH] random: initialize ChaCha20 constants with correct endianness

[Eric Biggers]

On Mon, Oct 26, 2020 at 09:33:54AM -0700, Eric Biggers wrote:
> On Tue, Oct 06, 2020 at 08:51:45PM -0700, Eric Biggers wrote:
> > On Fri, Sep 18, 2020 at 02:57:05PM -0700, Eric Biggers wrote:
> > > On Fri, Sep 18, 2020 at 04:42:07PM -0400, Theodore Y. Ts'o wrote:
> > 
> > Ted, any further feedback on this?  Are you planning to apply this patch?
> > 
> > - Eric
> 
> Ping.

Ping.

Re: [PATCH] random: initialize ChaCha20 constants with correct endianness

[Eric Biggers]

On Fri, Nov 20, 2020 at 10:52:54AM -0800, Eric Biggers wrote:
> On Mon, Oct 26, 2020 at 09:33:54AM -0700, Eric Biggers wrote:
> > On Tue, Oct 06, 2020 at 08:51:45PM -0700, Eric Biggers wrote:
> > > On Fri, Sep 18, 2020 at 02:57:05PM -0700, Eric Biggers wrote:
> > > > On Fri, Sep 18, 2020 at 04:42:07PM -0400, Theodore Y. Ts'o wrote:
> > > 
> > > Ted, any further feedback on this?  Are you planning to apply this patch?
> > > 
> > > - Eric
> > 
> > Ping.
> 
> Ping.

Ping.