0
$\begingroup$

I wonder the Stream Cipher ChaCha20 only changes 96 bits each block, why it can produce 512 bits keystream block, I mean in the concept of a random number generator, the entropy should be at least equal to the output. However, change 96 bits to produce 512 bits keystream seems have some secure problem.

$\endgroup$
2
  • 3
    $\begingroup$ What 96 bits? Isn't the block counter for ChaCha20 64-bit? Yes, that's the only change in input of the ChaCha20 "core" from one 512-bit message block to the other, and most often that's a single-bit change from an earlier block. But why would that be an issue? There's the same effect for any block cipher in CTR mode with incremental counter. I'm more concerned with the likelihood of 64-bit nonce collisions. $\endgroup$
    – fgrieu
    May 13 '20 at 4:37
  • $\begingroup$ In RFC 7539, ChaCha requires nonce not to be repeated with the same key. Thus every block will have different nonce. Plus counter increment, there will be 128 bits input varies. (Though the counter may change one byte only.) We can use the counter with a hash function to generate the needed nonce, thus to avoid nonce collisions.\nMy question is similart to using a small entropy to get a large random number output. Is it secure? $\endgroup$
    – MrQ.
    May 14 '20 at 7:14
2
$\begingroup$

The fact that few bits change at the input of ChaCha's "core" function does not compromise the security of the ChaCha20 stream cipher.


The design principle of the stream ciphers Salsa and Chacha is to use a "core" function $C:\,\{0,1\}^{512}\to\{0,1\}^{512}$ over the set of 512-bit bitstring (equivalently the set fo 16 words each 32-bit). Among the 512 input bits, 128 are set to arbitrary public constant values $c$, turning the remaining into some function $C_c:\,\{0,1\}^{384}\to\{0,1\}^{512}$.

$C_c$ behaves essentially like a function chosen at random in the set of functions with such input and output domains. In particular, it is conjectured that not knowing $k$ of the 384 input bits chosen at random, the function $C_c$ can't be distinguished from a random function with works less than $2^k$ operations (each requiring a sizable number of CPU cycles), for $k$ up to some comfortable limit (like 160 to 256).

Of the 384 input bits of $C_c$, $k=$256 are for the key, 64 for the nonce/IV, 64 for the counter. The full 512-bit output forms the keystream. As long as the key is random and secret, and the combination of IV and counter value does not repeat, the above conjecture demonstrably implies security of the stream cipher in all common security models, including for related keys.

That's even though, for most blocks of a large keystream, the input of the core function differs by a single bit from the input for another block, and 256 bits (including all those that vary) at the input of the core function are public.


The supporting argument for the stated security conjecture is the design of the core function per $C(x)\gets G^r(x)\boxplus x$ where $G$ is a bijection iterated for $r$ rounds, and $\boxplus$ is a group operation on $\{0,1\}^{512}$. Bijection $G$ is optimized for fast diffusion when iterated.

Note: diffusion is the main area where ChaCha improves (slightly) on Salsa. Another it is that it removes a harmless class of collisions in $C$, see this.

$\endgroup$
3
  • $\begingroup$ I can realize the concept you express. However, could you give a more formal mathematic proof? $\endgroup$
    – MrQ.
    May 15 '20 at 0:47
  • $\begingroup$ @MrQ: The proof that if the stated security conjecture on $C_c$ holds, then the Chacha20 stream cipher is secure, is basic to the point of being boring; would that really help? I can't make a proof that the conjecture holds, and AFAIK nobody can, for any symmetric cipher. $\endgroup$
    – fgrieu
    May 15 '20 at 6:35
  • $\begingroup$ We need more useful and theoretical proof, we discuss the topic in a crypt conference. We had studied many differential cryptanalysis about Chacha, so we don't think it's boring. In contrast, we need more supportive proofs. $\endgroup$
    – MrQ.
    May 16 '20 at 9:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.