The design of Chacha20

Thank you. Adding a quick reference to ARX designs right away.

Edit: added these paragraphs:

Quick summary: Chacha20 is ARX-based hash function, keyed, running in counter mode. It embodies the idea that one can use a hash function to encrypt data.

The expert will immediately notice this quarter-round is an ARX based design (ARX stands for, Addition, Rotation, Xor) which despite its simplicity can be made as good as a regular permutation-substitution network.

No, it does not. You're taking this notion of constrained values out of context. ASCII strings in crypto constructions are very common; for instance, they provide domain isolation in hash constructions (where you have a single hash function applied to inputs of different sensitivity, and want to mint multiple logically unrelated hash functions from the one you have). They're also common in versions.

The ASCII we're looking at here is conceptually a hash input. It's not a part of the design of the hash core itself.

Err, the key can be 256-bits. This is the preferred key size these days.

If you enjoyed the style of this article, I would also recommend you have a look at the brilliant explanation of Earley parsing by the same author: http://loup-vaillant.fr/tutorials/earley-parsing/

> A good place to start understanding why you want rotation and nonlinearity is the Wikipedia page for SP Networks:

I guess the real story requires knowing a little bit about linear and differential cryptanalysis, which are conceptually quite simple in their genesis, from a mathematical perspective.

XOR and n-bit addition are both forms of addition over different finite fields, GF(2) and GF(2^n). Multiplication in GF(2) is AND, so any linear function on a vector space over GF(2) is some kind of "masked parity" function, with functions only distinguished by their mask.

You can back-solve for inputs given enough independent outputs using Gaussian elimination and other standard linear algebra algorithms. Linear cryptanalysis is based on finding combinations of output bits that behave close enough to linear as a function of input bits to make this kind of strategy yield usable information. That is, just as in computational mathematics more generally, we approximate non-linear functions by linear functions and apply linear algebra techniques to the linear functions.

Differential cryptanalysis is the same general idea but with GF(2^n) as the scalar field instead of GF(2). If f is a linear function then f(x + y) = f(x) + f(y) and f(a x) = a f(x), so it's likewise true that f(x - y) = f(x) - f(y) by taking a = -1. That is, reading this last equation backwards, if f is truly linear then for any pair of vectors x and y with the same difference x - y, we should expect f(x) - f(y) to have the same exact value. If f is an encryption function (assume the key is baked into it), then all we have is f(x) and f(y), so we can't compute f(x - y) without knowing x and y, but we can certainly try to feed lots of plaintext pairs x and y with the same difference and see how the differences f(x) - f(y) of their ciphertexts relate to each other. If we can find a large family of plaintext pairs that have nearly the same difference in ciphertexts (by an appropriate measure of "nearly"), then this reveals an approximate linearity in the encryption function, and at that point we're back to being able to use linear algebra techniques to gain information about f and hence the key baked into f.

ARX attempts to foil such techniques by mixing both XOR and addition, which would individually create linear functions over their respective fields, but in combination help a little bit to break up the linearity over both finite fields. And the R in ARX is bitwise rotation, which is actually linear over GF(2) vector spaces (it's just a permutation of the vector's entries) but strongly nonlinear over GF(2^n) vector spaces.