Received-SPF: pass (google.com: domain of linux-kernel+bounces-163326-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) client-ip=2604:1380:45d1:ec00::1;
Date: Mon, 29 Apr 2024 22:41:10 -0600
From: Aaron Toponce <aaron.toponce@gmail.com>
To: Eric Biggers <ebiggers@kernel.org>
Cc: Theodore Ts'o <tytso@mit.edu>, "Jason A. Donenfeld" <Jason@zx2c4.com>,
	Herbert Xu <herbert@gondor.apana.org.au>,
	"David S. Miller" <davem@davemloft.net>,
	linux-kernel@vger.kernel.org, linux-crypto@vger.kernel.org
Subject: Re: [PATCH] random: add chacha8_block and swtich the rng to it
Message-ID: <ZjB2ZjkebZyC7FZp@hercules>
References: <20240429134942.2873253-1-aaron.toponce@gmail.com>
 <20240430031105.GA10165@sol.localdomain>
Precedence: bulk
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20240430031105.GA10165@sol.localdomain>

On Mon, Apr 29, 2024 at 08:11:05PM -0700, Eric Biggers wrote:
> I don't think there is consensus on ChaCha8 being recommended.  Adiantum uses
> ChaCha12, but even that received some pushback.
> 
> The Linux RNG is also usually used only for small amounts of data, and its
> security (and the perception of its security) is extremely important.
> 
> So just staying with ChaCha20 seems appropriate.

The 7-round attack does indeed fall short of the required 256-bits of security
per the stated goals of the ChaCha stream cipher, coming in at ~237 bits.
However, this attack is not catastrophic and of theoretical interest only. It's
well outside of practical reach. The 8-round version however reaches our
required security goal and is currently unbroken.

An interesting note in that paper is how we got ChaCha20 to begin with. ChaCha
is an evolution of Salsa20 which was included in the final eSTREAM portfolio [1]
The final eSTREAM portfolio recommends Salsa20/12, which is the 12 round
Salsa20. but with better diffusion [2]. In the "Too Much Crypto" paper, it
states [3]:

> "Regarding ChaCha, the eSTREAM actually recommended Salsa20/12, or ChaCha's
> predecessor with 12 rounds instead of 20, but ChaCha was de facto standardized
> with 20 rounds."

ChaCha20 is 13 additional rounds for extra security margin, more than have been
demonstrated for ChaCha to be secure.

[1]: https://www.ecrypt.eu.org/stream/
[2]: https://cr.yp.to/chacha/chacha-20080128.pdf
[3]: https://eprint.iacr.org/2019/1492

The reduced-round analysis of ChaCha is actually *better* than Salsa20.
Salsa20/8 has a known attack complexity with ~249 bits and Salsa20/7 has a known
attack complexity of ~153 bits. No known attacks exist against ChaCha8, and the
complexity against ChaCha7 is ~237 bits. This demonstrates to me that ChaCha's
security is very robust, and ChaCha8 is solid choice for a CSPRNG.

> Note also that currently the Linux RNG is using a portable C implementation of
> ChaCha20.  If there is actually a desire to accelerate large reads (which
> again, aren't the main use case of the Linux RNG), it would be possible to use
> a SIMD implementation of ChaCha20, which already exists in the kernel.  That
> would speed up ChaCha20 by roughly 2-5x depending on the CPU.

If ChaCha8 makes us uncomfortable, even though defensible, ChaCha12 is a good
compromise. As you mentioned, Google implemented ChaCha12 in Adiantum. It offers
a 1.67x speedup over ChaCha20 while still providing 5 additional rounds of
security over the best known attack.

-- 
 o .   o . o   . . o   o . .   . o .
 . o   . o o   o . o   . o o   . . o
o o o   . o .   . o o   o o .   o o o