[PATCH] random Remove setting of chacha state to constant values.

[PATCH] random Remove setting of chacha state to constant values.

[Sandy Harris]

Setting parts of the state to known constants is needed in
some Chacha applications to ensure that blocks can be processed
in parallel and that when needed (e.g. when encrypting disk
blocks) the algorithm can jump to an arbitrary part of the
output stream. In an RNG these are not required, and setting
the constants wastes cycles.

If (as we hope) the enemy does not know the state, then
this is more secure since it makes the chacha outputs
depend on more unknown bits.

If they can peek at the state or infer parts of it from
outputs, knowable values cannot possibly be worse than
known ones. This at least prevents them from using
pre-computed tables based on the known constants.

Signed-off-by: Sandy Harris <sandyinchina@gmail.com>
---
 drivers/char/random.c | 2 --
 1 file changed, 2 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 655e327d425e..6df9e656a157 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -249,9 +249,7 @@ static void crng_fast_key_erasure(u8 key[CHACHA_KEY_SIZE],

     BUG_ON(random_data_len > 32);

-    chacha_init_consts(chacha_state);
     memcpy(&chacha_state[4], key, CHACHA_KEY_SIZE);
-    memset(&chacha_state[12], 0, sizeof(u32) * 4);
     chacha20_block(chacha_state, first_block);

     memcpy(key, first_block, CHACHA_KEY_SIZE);
-- 
2.25.1

Re: [PATCH] random Remove setting of chacha state to constant values.

[Jason A. Donenfeld]

Hi Sandy,

On Thu, Jun 16, 2022 at 01:18:23PM +0800, Sandy Harris wrote:
> Setting parts of the state to known constants is needed in
> some Chacha applications to ensure that blocks can be processed
> in parallel and that when needed (e.g. when encrypting disk
> blocks) the algorithm can jump to an arbitrary part of the
> output stream. In an RNG these are not required, and setting
> the constants wastes cycles.
> 
> If (as we hope) the enemy does not know the state, then
> this is more secure since it makes the chacha outputs
> depend on more unknown bits.
> 
> If they can peek at the state or infer parts of it from
> outputs, knowable values cannot possibly be worse than
> known ones. This at least prevents them from using
> pre-computed tables based on the known constants.
> 
> Signed-off-by: Sandy Harris <sandyinchina@gmail.com>
> ---
>  drivers/char/random.c | 2 --
>  1 file changed, 2 deletions(-)
> 
> diff --git a/drivers/char/random.c b/drivers/char/random.c
> index 655e327d425e..6df9e656a157 100644
> --- a/drivers/char/random.c
> +++ b/drivers/char/random.c
> @@ -249,9 +249,7 @@ static void crng_fast_key_erasure(u8 key[CHACHA_KEY_SIZE],
> 
>      BUG_ON(random_data_len > 32);
> 
> -    chacha_init_consts(chacha_state);
>      memcpy(&chacha_state[4], key, CHACHA_KEY_SIZE);
> -    memset(&chacha_state[12], 0, sizeof(u32) * 4);
>      chacha20_block(chacha_state, first_block);
> 
>      memcpy(key, first_block, CHACHA_KEY_SIZE);

Hard NACK here, sorry. You proposed removing the constants used with
BLAKE2s, also, and Eric and I told you the same then:

https://lore.kernel.org/all/YfLtrrB+140KkiN0@sol.localdomain/
https://lore.kernel.org/all/CAHmME9pyj-ejZn8KpVKqhELYB=-5bVYTeNhLk4SZOnBM1zeidA@mail.gmail.com/

Same sort of justification here. ChaCha is a permutation that requires
those constants.

Jason

Re: [PATCH] random Remove setting of chacha state to constant values.

[Sandy Harris]

Jason A. Donenfeld <Jason@zx2c4.com> wrote:

> ChaCha is a permutation that requires those constants.

No. The actual permutation does not use the constants.
They are used in setting up the state & directly affect
only the first round. The other 19 rounds do not use
the constants; they operate on the more-or-less random
state left by the previous round.

The actual permutation works fine with any input.
The only question is how to set the initial state.

I think it is nearsighted, but there is a reasonable
argument for using chacha_init_consts(). That is
exactly what ChaCha does, and arguably we
should not deviate from it.

There is no such argument for
memset(&chacha_state[12], 0, sizeof(u32) * 4);
ChaCha has a counter and a nonce in those
bits, so setting them to zero is a deviation.
Dropping the memset() and using whatever
the existing state has there may not be ideal,
but it is certainly better than the zeroes.

Re: [PATCH] random Remove setting of chacha state to constant values.

[Jason A. Donenfeld]

On Sat, Jun 18, 2022 at 07:17:00AM +0800, Sandy Harris wrote:
> Jason A. Donenfeld <Jason@zx2c4.com> wrote:
> 
> > ChaCha is a permutation that requires those constants.
> 
> No. The actual permutation does not use the constants.
> They are used in setting up the state & directly affect
> only the first round. The other 19 rounds do not use
> the constants; they operate on the more-or-less random
> state left by the previous round.

I guess. But that just seems like all the more reason to stick with the
constants in that first round, as chacha lacks round constants like
"hermetic" permutations. Better to give less control over that initial
state. Anyway, we're not going to veer off into lala land and redesign
chacha on lkml.

> There is no such argument for
> memset(&chacha_state[12], 0, sizeof(u32) * 4);
> ChaCha has a counter and a nonce in those
> bits, so setting them to zero is a deviation.

No. There's a new key each time. So the nonce begins at zero. And the
counter begins at zero as well at the beginning like usual. So it's
actually a rather boring by-the-books usage of chacha.

> Dropping the memset() and using whatever
> the existing state has there may not be ideal,
> but it is certainly better than the zeroes.

I'm not so sure about that. For starters, it means that we'll never
actually exceed the first 32 bits, and so the branch for the increment
of the next word is never true, which has some tiny value. And as for
the nonce, I'd like to reserve that for whatever interesting use comes
up in the future (like using the cpu number or something in an
interesting parallel design).

But the larger reason for rejecting your idea wholesale is that I'm
trying to enforce the property that input data goes through our hash
function (via mix_pool_bytes). Full stop! It's time that this
willy-nilly stuff ends where we're feeding in things right and left with
no actual design on which is ingesting what input and how it interacts.
So if you do think that a particular block of memory somewhere at some
point has some entropic value, then by all means call mix_pool_bytes or
add_device_randomness on it. But don't try to stuff it in where it
doesn't belong.

The type of valuable patch I'd like to encourage is this recent one from
LinusW: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=ac9d25557dcc9fe90ed12bfbb6db401e892ca004
This seems like the kind of thing that might really help the situation
on certain devices in a real way. More of that! Less of fake crypto.

Jason

Re: [PATCH] random Remove setting of chacha state to constant values.

[Sandy Harris]

Jason A. Donenfeld <Jason@zx2c4.com> wrote:

> > There is no such argument for
> > memset(&chacha_state[12], 0, sizeof(u32) * 4);
> > ChaCha has a counter and a nonce in those
> > bits, so setting them to zero is a deviation.
>
> No. There's a new key each time. So the nonce begins at zero. And the
> counter begins at zero as well at the beginning like usual. So it's
> actually a rather boring by-the-books usage of chacha.

No. ChaCha has a random nonce.

> But the larger reason for rejecting your idea wholesale is that I'm
> trying to enforce the property that input data goes through our hash
> function (via mix_pool_bytes). Full stop! It's time that this
> willy-nilly stuff ends where we're feeding in things right and left with
> no actual design on which is ingesting what input and how it interacts.

For input data, I agree completely.

> So if you do think that a particular block of memory somewhere at some
> point has some entropic value, then by all means call mix_pool_bytes or
> add_device_randomness on it. But don't try to stuff it in where it
> doesn't belong.

This is not input data but more-or-less random state. I'm not trying
to input it, just to leave it where it belongs rather than overwriting
it with constants.

Re: [PATCH] random Remove setting of chacha state to constant values.

[Jason A. Donenfeld]

On Sat, Jun 18, 2022 at 08:38:23AM +0800, Sandy Harris wrote:
> Jason A. Donenfeld <Jason@zx2c4.com> wrote:
> 
> > > There is no such argument for
> > > memset(&chacha_state[12], 0, sizeof(u32) * 4);
> > > ChaCha has a counter and a nonce in those
> > > bits, so setting them to zero is a deviation.
> >
> > No. There's a new key each time. So the nonce begins at zero. And the
> > counter begins at zero as well at the beginning like usual. So it's
> > actually a rather boring by-the-books usage of chacha.
> 
> No. ChaCha has a random nonce.

Maybe you're thinking of xchacha? Generally it's not recommended to pick
nonces at random when they're only 64 bits. And it's even not great to
do for 96 bits. In this case here, it doesn't matter, because as
mentioned, the key is fresh each time. But if we're just going by the
book on how people generally use chacha, nonces are typically
sequential.

> > But the larger reason for rejecting your idea wholesale is that I'm
> > trying to enforce the property that input data goes through our hash
> > function (via mix_pool_bytes). Full stop! It's time that this
> > willy-nilly stuff ends where we're feeding in things right and left with
> > no actual design on which is ingesting what input and how it interacts.
> 
> For input data, I agree completely.
> 
> > So if you do think that a particular block of memory somewhere at some
> > point has some entropic value, then by all means call mix_pool_bytes or
> > add_device_randomness on it. But don't try to stuff it in where it
> > doesn't belong.
> 
> This is not input data but more-or-less random state. I'm not trying
> to input it, just to leave it where it belongs rather than overwriting
> it with constants.

What's the difference? If you think you've got some "more or less random
state" that would be useful input as something to influence the rng's
output, call mix_pool_bytes on it. (Also, "more or less random" is
probably not a good way to describe uninitialized stack. It's way less
random than more, and sometimes controllable.)

Sorry, but I'm just not interested in complicating the design with
handwavy things like this.

Jason