Does ChaCha20/Salsa have the same bit strength as AES for identical key sizes?

Question

Does ChaCha20/Salsa have the same bit strength as AES for identical key sizes? In other words, does ChaCha20 with a 128-bit key theoretically require 2^128 attempts to brute force, as with AES-128?

PS: Notwithstanding that ChaCha is a stream cipher.

Answer 1

Yes, all modern symmetric ciphers strife to offer (approximately) x bits of key strength for an x-bit key size, just like AES. If they don't, we presume they are broken.

---

Although there have been attacks on Salsa / ChaCha using fewer rounds, it doesn't seem that any attack has reduced the bit strength of the full cipher. Furthermore, differential cryptanalysis doesn't seem to make a dent in the security claims either.

---

The best attacks on AES ever so slightly bring down the security of AES to something near 126.2 bits. Also, attacks on ChaCha seem to be over fewer rounds relative to the total number of - but it is unclear if that tells anything about future attacks on the full cipher (if any).

So you could argue that a 128 bit ChaCha20 may be ever so slightly more secure when it comes to the algorithm itself.

Generally ciphers such as ChaCha20 are also less prone to side channel attacks, but if and how much they are susceptible is implementation specific (and system specific) in the end.

---

Note that I make these claims using Wikipedia as source (see further below for the ChaCha variant), so you may want to verify the source material and look for more recent developments.

Some ciphers modes like SIV mode do not play fair and indicate a combined key size for encryption and authentication. In that case the encoded key size doesn't represent the key strength.

Answer 2

Attacks on a cryptosystem with a 128-bit key are often much cheaper than $2^{128}$. If you have the strings $\operatorname{AES}_{k_1}(812738)$, $\operatorname{AES}_{k_2}(812738)$, $\dots$, $\operatorname{AES}_{k_{1000000}}(812738)$, it costs only about $2^{128}/1000000 \approx 2^{108}$ AES evaluations to find one of the $k_i$ keys if you can parallelize it $p \geq n^2$ ways, and it will take the time for about $2^{128}/np \leq 2^{128}/n^3$ sequential AES evaluations.

You should use 256-bit keys, whether with ChaCha or AES or HKDF-SHA256 or KMAC128 or anything else. The only reason ChaCha supports 128-bit keys at all, on paper, is that eSTREAM wanted to support 128-bit keys, so Salsa20 was made to support 128-bit keys, on paper, and the design carries over to ChaCha. Hardly anyone ever actually does this. The eSTREAM profile also specifically selected Salsa20/12, the 12-round version instead of the full 20-round Salsa20/20, also known as just Salsa20; similarly, ChaCha12 formally exists, but hardly anyone uses it instead of ChaCha20, also known as just ChaCha.

---

Now that we've gotten the generic issue of key size out of the way, there are a number of substantive advantages of ChaCha over AES that don't fit neatly into the glib ‘bits of security’ framework.

1. AES essentially cannot be computed efficiently in software without timing side channels. ChaCha was designd for fast software implementation without timing side channels.

   To match ChaCha's level of side channel security, AES requires hardware support—and that means you need to audit your entire software stack all the way down from the high-level protocols to the assembly code you're actually executing on all the physical machines you might be using, from spiffy x86 servers to years-old laptops to ARM phones to MIPS tablets.

2. AES is a pseudorandom permutation family of 128-bit blocks. ChaCha is a pseudorandom function family from 128-bit inputs to 512-bit outputs.

   This is mostly jargon that application developers don't need to concern themselves with, but these different shapes have a significant consequence: In most protocols, it is unsafe to use a single AES key for anywhere near ${\approx}2^{64}$ blocks of data, whereas there are no practical data volume limits per key on ChaCha.

   For example, probably the most widespread use of AES is in AES-GCM, which uses it in the forward direction only, to approximate one-time pads, just like the ChaCha stream cipher. The fact that AES is invertible is not helpful—in fact it makes AES appreciably worse at approximating one-time pads than ChaCha, thanks to the birthday paradox.

3. AES has a substantial key setup cost. ChaCha has zero key setup cost.

   To mitigate the data volume limits under a single key, or just to make key management simpler for complex applications, you can derive subkeys from a master key with a key derivation function or KDF. This is how, for example, the XChaCha stream cipher supports a 192-bit nonce: it derives a subkey from 128 bits of the nonce, and then uses ChaCha with that subkey and the remaining 64 bits of nonce. This is also how AES-GCM-SIV provides reasonable security bounds in spite of AES's $2^{64}$ birthday bound.

   AES's high key setup cost means subkeys are expensive, while ChaCha's zero key setup cost means subkeys are essentially free. For example, AES-GCM-SIV was designed under the premise that you are Google and you can afford to audit your entire software stack all the way down from the high-level protocols to the assembly code you're actually executing on all the servers in data centers that you care about, so you can reliably use hardware support for AES both to mitigate side channel attacks and to ameliorate the key setup cost with subkeys. For the rest of us who are not Google—and even within Google on the teams that do Android and Chromebook development on a variety of platforms—the tradeoff of relying on AES hardware is not so clear.

4. The highest number of rounds broken by an attack cheaper than brute force for AES-256 seems to be 7, and for ChaCha also seems to be 7. (The standard biclique attacks on full AES-128 are not obviously cheaper when you consider space and communication costs.) But AES-256 has only 14 rounds, while ChaCha has 20. So ChaCha has a higher ‘security margin’ than AES, which is a very rough fuzzy notion that you shouldn't worry too much about because neither one is broken; it just makes ChaCha come out looking a little sprightlier than AES.