Message-ID: <20200918215705.GA126697@gmail.com>
Date:   Fri, 18 Sep 2020 14:57:05 -0700
From:   Eric Biggers <ebiggers@...nel.org>
To:     "Theodore Y. Ts'o" <tytso@....edu>
Cc:     linux-kernel@...r.kernel.org, linux-crypto@...r.kernel.org
Subject: Re: [PATCH] random: initialize ChaCha20 constants with correct
 endianness

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

Powered by blists - more mailing lists