ARX Ciphers: Carry Chains as the Only Nonlinearity

Add-rotate-xor designs build everything from three operations: addition modulo $2^n$, rotation by a fixed number of bits, and exclusive or. No lookup tables, no finite-field multiplication, no bit permutations. The appeal is implementation: these three operations exist on every processor, they are fast, and they are naturally constant-time because none of them indexes memory with data. The cost is that the entire nonlinearity of the cipher rests on one operation, and the analysis of that operation is arithmetic rather than algebraic.

Where the nonlinearity comes from

Rotation and XOR are both linear over $\mathrm{GF}(2)$: rotation permutes bit positions, XOR adds bits, and neither mixes them nonlinearly. Addition modulo $2^n$ is the only source of nonlinearity, and it is nonlinear exactly because of the carry. The low bit of a sum is the XOR of the low bits of the operands; the second bit depends on the carry out of the first, which is an AND. That single AND gate per bit position, chained through the word, is what makes the whole structure resistant to linear and differential analysis.

This has a concrete consequence for implementation. A linearised version of an ARX cipher — replacing additions with XORs — would be trivially breakable, so the carry is not an inconvenience but the security. It also means that the security analysis has to reason about carries as a stochastic process, and that reasoning is where ARX design differs most from byte-oriented design.

Consider the difference between two additions, $a + b$ and $a’ + b’$. Write $\Delta a = a \oplus a’$ and $\Delta b = b \oplus b’$. The output difference is not determined by the input differences; it depends on the actual values because the carry propagation depends on them. This is the opposite of the XOR layer, where the difference map is exact. The differential probability of an addition is therefore a probability over the space of operand values, computable exactly for small word sizes and approximated by a Markov chain for large ones.

Carry propagation as a Markov process

Model the carry out of bit position $i$ as a random variable. It is 1 with some probability that depends on whether both input bits at that position are 1, or whether exactly one is 1 and the carry in is 1. The classic model treats the carry as a Markov chain with two states and transition probabilities determined by the difference pattern. For a difference that is zero at a position, the carry either propagates or is absorbed depending on the bit values; for a difference of one, the carry is generated or absorbed.

The result is a characterisation of addition’s differential behaviour: for input differences $\Delta a$ and $\Delta b$, the output difference is determined by the pattern of carries, and the most likely output difference is the one that requires the fewest “unlikely” carry events. A difference that propagates a carry through many positions has probability roughly $2^{-k}$ for $k$ positions of carry chain, which is why the low-probability cases are exactly the long carries.

This gives a usable design heuristic: the rotation constants should be chosen so that a carry chain produced by one addition is spread across bit positions before the next addition, so that the next addition’s carries do not align with the previous one’s. Salsa20’s quarter-round uses rotations of 7 and 9 bits on 32-bit words, and the column and row rounds are arranged so that each word is modified by additions involving words that were rotated in the previous step.

Measuring diffusion in bits

Byte-oriented ciphers measure diffusion by counting active bytes, because the S-box operates on bytes and the linear layer moves bytes. ARX ciphers have no byte structure — a rotation moves bits between byte boundaries — so the natural measure is the number of bit positions a difference has spread to, or equivalently the weight of the difference as a bit vector.

Diffusion in an ARX design comes from two mechanisms. Rotations move difference bits to new positions, and additions spread them within the word through carry propagation. A single-bit difference entering an addition with another word can affect bits above it through carries, but only upward; a rotation is needed to spread it downward as well. This asymmetry is why ARX ciphers alternate additions with rotations in both directions, and why the round structure typically applies the same operation to several word pairs in a pattern that permutes the words.

/* ChaCha quarter-round: four additions, four XORs, two rotations.
   Every rotation moves bits across byte boundaries, which is why
   the design needs no bit-permutation layer. */
static uint32_t rotl32(uint32_t x, int n) { return (x << n) | (x >> (32 - n)); }

static void quarter_round(uint32_t *a, uint32_t *b, uint32_t *c, uint32_t *d)
{
    *a += *b; *d ^= *a; *d = rotl32(*d, 16);
    *c += *d; *b ^= *c; *b = rotl32(*b, 12);
    *a += *b; *d ^= *a; *d = rotl32(*d, 8);
    *c += *d; *b ^= *c; *b = rotl32(*b, 7);
}

The rotation amounts 16, 12, 8, and 7 are not arbitrary. The first two are multiples of 4 and the last two are not, which means the sequence alternates between moving bits by whole nibbles and moving them by non-aligned amounts. The 16-bit rotation swaps the two halves of the word, moving high bits to low positions; 8 moves bytes; 12 and 7 break the byte alignment that the earlier rotations establish. The result is that a difference spreads to all 32 bit positions within a few quarter-rounds.

Rotational cryptanalysis and the price of symmetry

ARX designs have a structural weakness that byte-oriented designs do not: they are invariant under rotation of the entire state, in a probabilistic sense. If every word in the state is rotated left by one bit, and every constant is also rotated by one bit, the computation commutes with the rotation. For a cipher with no constants, or with constants that are themselves rotationally symmetric, this yields a distinguisher: a plaintext and its rotation produce ciphertexts that are rotations of each other.

Khovratovich and Nikolić turned this into a general attack framework. The probability that a rotation of the input produces a rotation of the output is not one, because addition does not commute exactly with rotation — the carry at the top bit is lost or gained. The probability is $1/2$ per addition for a rotation by one, and it can be computed exactly for a given rotation amount. For larger rotation amounts the probability drops, which is why designs choose constants that are not rotationally symmetric and rotation amounts that are not all equal.

Salsa20 and ChaCha include constants specifically to break this symmetry. The constant is the ASCII string “expand 32-byte k” split into four 32-bit words, and it is injected into the state at initialisation. Since the constant is fixed and not rotation-invariant, a rotated state does not correspond to a valid state, and the rotational attack does not apply to the full cipher. Designs that omit such constants — some lightweight ARX proposals — are exposed to the attack, and the analysis of those proposals generally includes a rotational distinguisher as a matter of course.

Why not use ARX everywhere

The comparison with AES is instructive because the trade is not close in either direction; it depends on the platform.

On a processor with AES instructions, the byte-oriented design wins by a wide margin, because the S-box and the linear layer execute in dedicated hardware. On a processor without them, ARX wins on code size and on the absence of table lookups: a ChaCha implementation is a few dozen instructions with no data-dependent memory access, whereas a table-based AES implementation has 16 table lookups per round and the cache-timing exposure that comes with them.

The security margins differ in character. AES’s resistance is argued from the wide-trail bound, which is a proof about characteristics over four rounds and an extrapolation beyond. ARX resistance is argued from the absence of known distinguishers over the specified round count, supported by automated search for differential and linear trails. Neither argument is a proof of security, but the ARX argument is more empirical: the round count is set by what the search tools fail to find, plus margin.

ARX designs also have a wider design space with fewer guide rails. The rotation amounts, the word permutation, and the number of rounds all interact, and there is no branch number to compute. Designers rely on automated trail search — tools that enumerate differential characteristics up to a weight bound — to choose parameters, and the parameters that survive are not obviously optimal. This is why ARX ciphers tend to be specified with generous round counts and why their designers publish trail-search results alongside the specification.

The two families also differ in how they fail. A byte-oriented cipher with a badly chosen linear layer fails catastrophically and detectably: the branch number drops and the active S-box count collapses, which is visible in a table of counts. An ARX cipher with badly chosen rotations fails subtly: the trail search finds a characteristic of moderate weight that no one expected, and the margin is smaller than believed. The first failure is caught by construction; the second by search.

There is a middle ground worth noting. Some designs use addition modulo $2^{32}$ for nonlinearity but keep a byte-oriented structure for diffusion, combining the constant-time property of ARX with the provable diffusion of a byte permutation. The choice is a genuine engineering trade rather than a matter of fashion, and it usually comes down to whether the target platform has hardware support for table-based substitution.

The contrast with substitution-based designs is sharpest when the nonlinearity is a lookup table. An ARX round has no table at all, which is why it needs no protection against cache timing; a table-based round has one, which is why the constant-time fixes in constant-time AES implementations exist. The S-box properties that make a table worth using are the subject of S-box construction. The stream-cipher side of the ARX family, where the same primitives generate a keystream rather than permute a block, is covered in LFSR and shift-register keystream generators.