ChaCha20 ARX Quarter-Round Operations Explained

This article explores how the ChaCha20 stream cipher uses ARX (Addition, Rotation, and XOR) primitives within its quarter-round function to transform binary data. It details the structure of ChaCha20’s 512-bit internal state, breaks down the mathematical and binary mechanics of the four-step quarter-round modification, and explains how repeated alternating rounds achieve cryptographic diffusion and non-linearity on binary systems without vulnerable lookup tables.

The ChaCha20 State Matrix

ChaCha20 operates on an internal state defined as a 4x4 matrix containing 16 32-bit unsigned integers (words), totaling 512 bits. The state is initialized with:

• Constants (Words 0–3): Four fixed 32-bit words that prevent symmetry and eliminate all-zero states (0x61707865, 0x3320646e, 0x79622d32, 0x6b206574).
• Key (Words 4–11): An eight-word (256-bit) secret key.
• Block Counter (Words 12): A 32-bit block counter that increments for every 64-byte block generated.
• Nonce (Words 13–15): A 96-bit unique initialization vector (three 32-bit words).

The ARX Primitive Set

The cipher relies strictly on three low-level binary operations, collectively known as ARX, to ensure constant-time execution on standard CPU hardware:

1. Modular Addition (\(a \boxplus b\)): Adds two 32-bit words modulo \(2^{32}\). In binary, this is standard integer addition with overflow discarded. The carry bits propagate from least significant bits to most significant bits, introducing algebraic non-linearity.
2. Bitwise Exclusive-OR (\(a \oplus b\)): Standard binary XOR applied bit-by-bit. It provides fast linear mixing and ensures changes in one input invert corresponding bits in the output.
3. Bitwise Left Rotation (\(a \lll n\)): Shifts all 32 bits to the left by \(n\) positions, wrapping overflowed high-order bits back to the lowest positions. This disperses the influence of specific bit positions across the entire 32-bit register.

The Quarter-Round Transformation

The fundamental transformation in ChaCha20 is the quarter-round function (\(\text{QR}\)). It accepts four state words \((a, b, c, d)\) and updates them in place through four distinct steps:

1. \(a \leftarrow a \boxplus b;\quad d \leftarrow (d \oplus a) \lll 16\)
2. \(c \leftarrow c \boxplus d;\quad b \leftarrow (b \oplus c) \lll 12\)
3. \(a \leftarrow a \boxplus b;\quad d \leftarrow (d \oplus a) \lll 8\)
4. \(c \leftarrow c \boxplus d;\quad b \leftarrow (b \oplus c) \lll 7\)

Mechanics of the Four Steps

• Step 1: Word \(a\) absorbs \(b\) via modular addition, causing carry bit propagation. The updated \(a\) is XORed into \(d\), and \(d\) is rotated by 16 bits. This immediately swaps the upper and lower 16-bit halves of the binary word.
• Step 2: Word \(c\) absorbs the newly modified \(d\). The result is XORed into \(b\), followed by a 12-bit left rotation.
• Step 3: Word \(a\) absorbs the newly modified \(b\). The updated \(a\) is XORed into \(d\), which is then rotated left by 8 bits, shifting individual bytes across register boundaries.
• Step 4: Word \(c\) absorbs \(d\). The result is XORed into \(b\), and \(b\) is rotated left by 7 bits, ensuring that no repeated power-of-two alignment remains.

The specific rotation constants \((16, 12, 8, 7)\) ensure rapid binary diffusion across all 32 bit positions within minimal cycles.

Full Rounds: Column and Diagonal Passes

ChaCha20 runs 20 rounds of quarter-round applications, grouped as 10 iterations of a “double round”:

1. Column Round (Odd Rounds): Applies \(\text{QR}\) simultaneously to the four vertical columns of the state matrix:
   • \(\text{QR}(0, 4, 8, 12)\)
   • \(\text{QR}(1, 5, 9, 13)\)
   • \(\text{QR}(2, 6, 10, 14)\)
   • \(\text{QR}(3, 7, 11, 15)\)
2. Diagonal Round (Even Rounds): Applies \(\text{QR}\) to four distinct diagonals of the matrix:
   • \(\text{QR}(0, 5, 10, 15)\)
   • \(\text{QR}(1, 6, 11, 12)\)
   • \(\text{QR}(2, 7, 8, 13)\)
   • \(\text{QR}(3, 4, 9, 14)\)

Alternating between columns and diagonals ensures that every bit in the 512-bit state interacts with and influences every other bit after just a few rounds.

Final Keystream Generation

After 20 rounds, the resulting 512-bit state is added word-by-word (modulo \(2^{32}\)) to the original, un-modified initial state matrix. This final addition makes the round function non-invertible, preventing an attacker who observes the keystream from running the ARX operations backward to compute the secret key. The final output is serialized into a 64-byte keystream block and XORed with plaintext to produce ciphertext.