3
$\begingroup$

Wikipedia reports the following information about the ChaCha20 algorithm:

An implementation reference for ChaCha20 has been published in RFC 7539. The IETF's implementation modified Bernstein's published algorithm by changing 64-bit nonce and 64-bit block counter to 96-bit nonce and 32-bit block counter[34]. The name was not changed when the algorithm was modified and it could be the source of confusion for developers. Because of the reduced block counter, maximum message length that can be safely encrypted by the IETF's variant is 2^(32)-1 blocks of 64 bytes (about 256 GiB). For usages where this is not enough, such as file or disk encryption, RFC 7539 proposes using the original algorithm with 64-bit nonce.

My questions are:

In this sentence

... maximum message length that can be safely encrypted ... is 2^(32)-1 blocks of 64 bytes (about 256 GiB)

I've got the following related questions about this:

  1. Is it being implied that that using the same block counter repeatedly is a risk?

  2. How is that risk calculated? What is the formula for the risk?

  3. If it is a question of repeating blocks counters, then shouldn't the block size be the same as the nonce? 96 bits = 12 bytes?

  4. If it is not repeating block counters that is the source of risk, then is the risk just based on the total length of encoded data? What is the formula for that risk?

$\endgroup$
6
$\begingroup$

From the RFC you can see that a ChaCha20 block is constructed as follows:

state = constants | key | counter | nonce

Which is then processed in a number of rounds. So lets keep that in mind for the following Q/As.

1. Is it being implied that that using the same block counter repeatedly is a risk?

Yes. If you use a 32 bit counter then it is presumed to be used in modular fashion, using modulo $2^{32}$ calculations. That means $\operatorname{inc}(2^{32} - 1) = 0 \mod 2^{32}$. I.e. it overflows and resets to the initial counter 0.

That would mean that the state would get the same value (none of the other components changes for the same nonce), which means that the key stream starts to repeat itself. The processing of the state is otherwise deterministic, so you would get the same key stream block.

2. How is that risk calculated? What is the formula for the risk?

In the calculations below $P_x$ is a block of the plaintext message, $S_x$ is a block of the key stream generated by processing the state with the ChaCha20 rounds and $C_x$ are the blocks of the ciphertext (where the last block may be a partial block depending on the size of the message). $x$ is the position of the block within the plaintext / key stream / ciphertext.

This is basically a so called many-time-pad. If you have two blocks of the message $P_0$ and $P_{2^{32}}$ then you would have $C_0 = P_0 \oplus S_0$ and $C_{2^{32}} = P_{2^{32}} \oplus S_{2^{32}}$. But because $S_0 = S_{2^{32}}$ you can see rewrite that to $C_{2^{32}} = P_{2^{32}} \oplus (C_0 \oplus P_0)$ or, after a bit of rearrangement $P_0 \oplus P_{2^{32}} = C_0 \oplus C_{2^{32}}$, i.e. you leak the XOR of two plaintext blocks of the message by XORing the ciphertext at the same position.

This risk is 100%. How much information is leaked depends on the contents of the blocks of the message. Note that much more information becomes available if the same limit is crossed multiple times, as you can now XOR multiple blocks together in a pairwise fashion.

3. If it is a question of repeating blocks counters, then shouldn't the block size be the same as the nonce? 96 bits = 12 bytes?

That would not fit in the state; ChaCha20 is specified with a specific state size where state consists of sixteen 32 bit words, or 512 bits.

4. If it is not repeating block counters that is the source of risk, then is the risk just based on the total length of encoded data? What is the formula for that risk?

This is about repeating counters, so this question is not applicable.


Note that a correct implementation should fail rather than overflow. Unfortunately for online implementations, where the size of the plaintext message is not known in advance, that would be after encrypting $2^{32}$ blocks.

$\endgroup$

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.