Does ChaCha20 counter actually increment through iterations?

Question

RFC defines:

state = constants | key | counter | nonce

Suggested on multiple places is to set counter to 0 or 1.

It is still unclear to me what the function of counter is. Why not just use larger 128bit nonce, instead of a 32bit counter + 96bit nonce?

Does the counter at position of 13th byte actually increment by one? Can I extract the number of iterations from the state of ChaCha20? From the specification, Id say that the state gets randomized after as much as one iteration.

This brings me to a 2nd question - if it is customary to set counter to 0 or 1, we can consider this is public. Does this mean then that nonce can also be made public (just like IV for block ciphers) without compromising the security? (of course provided that key stays confidential)

Thank you all for answers!

Answer 1

It is still unclear to me what the function of counter is. Why not just use larger 128bit nonce, instead of a 32bit counter + 96bit nonce?

Technically you could, but only a constantly repetative key stream would pop out. As you imply, you could make the block function iteratable so what you would be doing is simply repeating the function with no further inputs, like $ state_{n+1} \leftarrow \operatorname{ChaCha}(state_{n}) $. There would be a (small) risk that a cycle developed $j$ iterations long, and you got another repetitive output. Perhaps $ \operatorname{ChaCha}(\operatorname{ChaCha}(state))= state $ with $j=2$. This would be disastrous.

The possibility of a cycle/fixed point is avoided by the inclusion of a counter. It's a mitigation to increase the security bounds over an pure iterated construct such as OFB mode. Have counter, have smaller nonce to fit. You see exactly the same principle in AES & SHA CSPRNGs and CTR mode encryption. There's further similar discussion at Why is there a counter in CSPRNGs? as they and stream ciphers are not a million miles apart.

It also allows you to position the key stream arbitrarily in $O(1)$ time, but not all constructs require that.

Answer 2

You seem a bit confused about how the various parts of the ChaCha20 cipher actually fit together, so let me start from the top down and see if I can clarify things.

At the highest level, the ChaCha20 encryption algorithm is a synchronous stream cipher: given a secret key and a (possibly) public nonce, it generates a pseudorandom keystream which is bitwise XORed with the message to be encrypted. Repeating this process (i.e. XORing the encrypted message with the same pseudorandom bitstream again) then lets the receiver reveal the original message again.

(The purpose of the secret key is to ensure that no-one else can generate the same keystream, and thus decrypt the messages. The purpose of the nonce is to ensure that we never use the same keystream for encrypting two different messages, since that would allow an attacker to cancel out the keystream by XORing the encrypted messages together, leaving them with the bitwise XOR of the original plaintext messages. So, no, the nonce doesn't need to be secret — all it needs to be is unique.)

---

The keystream is generated by concatenating a sequence of 512-bit blocks, each of which is generated by applying the ChaCha20 block function to an initial 512-bit input block consisting of the key, the nonce, a block counter and a fixed 128-bit constant. The reason why the block counter is needed is because the ChaCha20 block function is deterministic, and would thus always produce the same output block if given the same input. We don't want the keystream to consist of just the same 512-bit block repeated over and over, so we include a counter in the input block to make sure that every input to the ChaCha20 block function is different.

(This is essentially the same as the CTR mode construction for making a synchronous stream cipher out of a block cipher, except with the ChaCha20 block function used in place of the block cipher.)

---

Finally, going one level deeper yet, the ChaCha20 block function scrambles its input by iteratively applying 10 "column rounds" and 10 "diagonal rounds" to it, in alternating order (and then finally XORing the scrambled result with the original input to make the whole thing non-reversible). Each of these column rounds and diagonal rounds, in turn, consist of four (possibly) parallel applications of the ChaCha20 quarter round function, which takes a 128-bit slice of the full 512-bit block and scrambles it in a particular way, as described in the linked RFC.

All that iterated scrambling ensures that even tiny changes to the input block (like, say, incrementing the block counter by one) will cause the output of the block function to look completely different. Thus, even though the successive inputs to the block function for any given message are all the same except for the counter, the keystream obtained by concatenating the scrambled output blocks is effectively indistinguishable from random, unless one knows all the inputs that went into generating it (including, in particular, the secret key).

---

Of course, to deterministically generate the keystream from a given key and a nonce, we need to decide how to choose the initial counter value for the first block, and how to increment it for the later blocks. (If we don't do it consistently when encrypting and decrypting, the keystreams will be different and we won't get the original message back!) The obvious choice would be to number the blocks consecutively as 0, 1, 2, 3, 4, …, but in principle other methods could work just as well.

Indeed, the RFC you linked to describes the ChaCha20 encryption algorithm as taking the initial counter value as an input, in addition to the key, the nonce and the message to be encrypted (or decrypted), and describes it as follows:

• A 32-bit initial counter. This can be set to any number, but will usually be zero or one. It makes sense to use one if we use the zero block for something else, such as generating a one-time authenticator key as part of an AEAD algorithm.

Note that this is the initial counter value, used to generate the first 512-bit block of keystream, and incremented by one for every subsequent block. So if the initial counter value is set to 0, the blocks will be numbered as 0, 1, 2, 3, 4, …, whereas if it's set to 1, the blocks will be numbered 1, 2, 3, 4, 5, … instead.

So why would you choose to set the initial counter value to something other than 0? Well, probably because you want to start the keystream at some later block number, e.g. because you already used block 0 for something else.

In particular, the AEAD_CHACHA20_POLY1305 authenticated encryption scheme works by using block 0 of the ChaCha20 keystream to generate the one-time Poly1305 key for protecting the integrity of the encrypted message, and then using the rest of the keystream starting from block 1 to actually encrypt the message as described above.

Answer 3

Let's review the design of ChaCha to see how the nonce, the counter, and te number of rounds all fit into it.

How do we encrypt a sequence of messages $m_1, m_2, \dots, m_\ell$? One way is to pick a sequence of message-length pads $p_1, p_2, \dots, p_\ell$ independently and uniformly at random, and encrypt the $n^{\mathit{th}}$ message $m_n$ with the $n^{\mathit{th}}$ pad $p_n$ as the ciphertext $$c_n = m_n \oplus p_n,$$ where $\oplus$ is xor. If the adversary can guess a pad, you lose; if you ever repeat a pad for two different messages, you lose. Otherwise, this model, called the one-time pad, has a very nice security theorem, but choosing and agreeing on independent uniform random pads message-length $p_n$ is hard.

Can we make do with a short uniform key $k$, say 256 bits long? Approximately, yes: if we had a deterministic function $F_k$ from message sequence numbers $n$ to message-length pads $F_k(n)$ which are hard to distinguish from independent uniform random when $k$ is uniformly distributed, then we could pick $$p_n = F_k(n)$$ and we only need to choose and agree on a 256-bit secret key $k$. We call $F_k$ a pseudorandom function family. This makes our job easier without making it much easier for any adversary even if they could spend humanity's entire energy budget on breaking it.

How do we design our short-input, long-output PRF $F_k(n)$? If we had a short-input, short-output PRF $f_k(n, c)$ which computed a fixed-size block given a message sequence number and an extra input $c$, we could simply generate a lot of blocks for each message, using a block counter for the extra input $c$, and concatenate them: $$F_k(n) = f_k(n, 0) \mathbin\| f_k(n, 1) \mathbin\| f_k(n, 2) \mathbin\| \cdots.$$ How do we design our short-input, short-output function $f_k(n, c)$? If $\pi$ were a uniform random permutation, then the function $S(x) = \pi(x) + x$ would be hard to distinguish from a uniform random function, and almost certainly be noninvertible. We could define $$f_k(n, c) = S(k \mathbin\| n \mathbin\| c \mathbin\| \sigma).$$ Of course, we don't have a uniform random permutation, but if $\delta$ is a permutation without much structure, and if we define $\pi$ by iterating $\delta$ many times, $$\pi(x) = \delta(\delta(\cdots(\delta(x))\cdots)) = \delta^r(x),$$ then $\pi(x)$ will have even less structure than $\delta$—with any luck, so little structure that it will destroy any patterns a cryptanalyst could look for within humanity's energy budget.

---

Recapitulating, the design of the ChaCha$(2r)$ is as follows:

1. Start with a permutation $\delta$ of 512-bit blocks that doesn't have much structure. The permutation $\delta$ is called the ChaCha doubleround. (Why a ‘doubleround’? ChaCha alternates between ‘row rounds’ and ‘column rounds’; $\delta$ does one row round, and one column round.)
2. Define the permutation $$\pi(x) = \delta^r(x),$$ the $r$-fold iteration of $\delta$. The number $2r$ is the number of rounds. For instance, in ChaCha20 (the default), we iterate $\delta$ ten times; in ChaCha8 (the smallest unbroken number of rounds), we iterate $\delta$ four times.
3. Define the function $$S(x) = \pi(x) + x.$$ This function $S$ is called the ChaCha core.
4. Define the short-input, short-output pseudorandom function family $$f_k(n, c) = S(k \mathbin\| n \mathbin\| c \mathbin\| \sigma),$$ where $\sigma$ is a fixed constant with moderate Hamming weight. When unambiguous, $f_k$ is sometimes just called ChaCha, or the ChaCha PRF.
5. Define the short-input, long-output pseudorandom function family $$F_k(n) = f_k(n, 0) \mathbin\| f_k(n, 1) \mathbin\| f_k(n, 2) \mathbin\| \cdots.$$ Here we use the $c$ parameter of $f_k$ as a block counter. When unambiguous, $F_k$ is sometimes just called ChaCha, or the ChaCha stream cipher.
6. For the $n^{\mathit{th}}$ message, compute the pad $$p_n = F_k(n).$$ Here we use the $n$ parameter of $F_k$ as a nonce.
7. Encrypt the $n^{\mathit{th}}$ message $m_n$ by computing the ciphertext $$c_n = m_n \oplus p_n.$$

When you are using ChaCha, as in the NaCl crypto_stream_chacha_xor(output, msg, len, n, k), your obligations are to choose $k$ uniformly at random and never reuse the nonce $n$ with the same key $k$. The counter is an implementation detail that does not concern you in most protocols.

Note 1: You almost certainly shouldn't use ChaCha directly either; you should use an authenticated cipher like ChaCha/Poly1305 or NaCl crypto_secretbox_xsalsa20poly1305. Unauthenticated data is pure evil—don't touch it!

Note 2: That ChaCha's counter enables random access to blocks within a message also shouldn't concern you; your messages should be short enough that a forgery won't waste much memory before you are guaranteed to realize it's a forgery and drop it on the floor. Use the nonce for random access to a sequence of authenticated messages instead so you're not tempted to reach inside a box of pure evil.

---

To address the specific questions you asked:

Does the counter at position of 13th byte actually increment by one? Can I extract the number of iterations from the state of ChaCha20?

The counter increments for each block within a single message, as illustrated above.

The number of iterations (or ‘rounds’) is not encoded into the state. The number of iterations for ChaCha20 is always 20. If you have ciphertexts under ChaCha12 and ChaCha20 with an unknown key, you can't tell whether they were made with ChaCha12 or ChaCha20 either.

In particular, the ChaCha20 core, $\operatorname{ChaCha20}_{\mathit{key}}(\mathit{nonce}, \mathit{counter})$ permutes the 512-bit state $(\mathit{key}, \mathit{nonce}, \mathit{counter}, \mathit{constant})$ (encoded in some bit order) with 20 rounds to produce a single 512-bit block of pad at a time; the ChaCha20 cipher then moves on to using $\operatorname{ChaCha20}_{\mathit{key}}(\mathit{nonce}, \mathit{counter} + 1)$ for the next block, and then $\mathit{counter} + 2$, and so on.

From the specification, I'd say that the state gets randomized after as much as one iteration.

There's an illustration of the diffusion of a change in a single byte of the Salsa20 core here: https://cr.yp.to/snuffle/diffusion.html (Salsa20 is closely related to ChaCha; they have almost the same security.)

Does this mean then that nonce can also be made public (just like IV for block ciphers) without compromising the security? (of course provided that key stays confidential)

Yes. Not only can it be public, but it can be predictable in advance—unlike a CBC IV.

The security contract for ChaCha20 obliges you never to repeat a nonce with the same key, and obliges you to limit the messages to at most $2^\ell\cdot 512$ bits long, where $\ell$ is the number of bits reserved for the counter—in NaCl, $\ell = 64$ so messages can be of essentially arbitrary length, while in RFC 7539 as used in, e.g., TLS, $\ell = 32$ so messages are limited to 256 GB which is more than enough for sensible applications which break messages into bite-sized pieces to be authenticated anyway—you are using this as a part of the authenticated cipher ChaCha/Poly1305 or similar, right?

Neither the nonce nor the counter need be secret in the security contract; normally they are prescribed by the protocol and algorithm, e.g. to be a message sequence number starting at 0, and a block sequence number starting at 0, respectively.

It is still unclear to me what the function of counter is. Why not just use larger 128bit nonce, instead of a 32bit counter + 96bit nonce?

If you used a 128-bit nonce, your messages would be limited to 32 bytes long.