THE GARDEN

Invertible Permutation via Missing Feed-Forward (ARX Stream Ciphers)

Updated 13 Sep 2026

• •

  What it is

  • •

    ChaCha20 (and Salsa20) build a keystream block by running a fixed number of ARX rounds (Add, Rotate, XOR — all individually invertible operations) over an initial state (constants, key, counter, nonce), then critically ADD the pre-round state back onto the post-round state (word-by-word, mod $2^{32}$) before using it as keystream. That final feed-forward addition is what makes the construction one-way: without it, the round function alone is just a fixed, invertible permutation, and an attacker who recovers one full keystream block (e.g. via known-plaintext XOR) can run the ARX rounds in reverse and land exactly back on the original state — constants, key, counter and nonce included.

• •

  When to apply

  • •

    A hand-rolled ARX stream cipher implementation is missing the final state-addition feed-forward step (compare against a reference implementation's output[i] = working_state[i] + original_state[i], mod $2^{32}$). If a known plaintext (even from an unrelated message encrypted with the same key) lets you recover a full keystream block, the permutation can be run backwards to recover the key directly.

• •

  Math

  • •

    Each ChaCha20 quarter-round is 4 steps: $a \mathrel{+}= b;\ d \oplus= a;\ d = \text{rotl}(d,n)$, repeated with different word groupings — every step is exactly invertible ($a \mathrel{-}= b$, undo the rotate then the XOR, applied in reverse order for the round, and the 8 quarter-rounds applied in reverse order for the full inner-block reversal, all 10 times).

• •

  Worked example

  • •

    Given a known-plaintext message and its ciphertext under iv1, XORing them recovers the first 64-byte keystream block directly. Feeding that block through 10 rounds of inverted quarter-rounds landed exactly back on the original 16-word state — the first 4 words matched the fixed ChaCha20 constants (0x61707865, 0x3320646e, 0x79622d32, 0x6b206574), confirming the inversion, and words 4-11 were the raw 32-byte key.

• •

  Python

  • •

    def inv_qr(x, a, b, c, d):
        x[b] = rotr(x[b], 7);  x[b] ^= x[c];  x[c] = (x[c] - x[d]) & 0xffffffff
        x[d] = rotr(x[d], 8);  x[d] ^= x[a];  x[a] = (x[a] - x[b]) & 0xffffffff
        x[b] = rotr(x[b],12);  x[b] ^= x[c];  x[c] = (x[c] - x[d]) & 0xffffffff
        x[d] = rotr(x[d],16);  x[d] ^= x[a];  x[a] = (x[a] - x[b]) & 0xffffffff
    
    def inv_inner_block(x):
        for args in reversed([(0,4,8,12),(1,5,9,13),(2,6,10,14),(3,7,11,15),
                               (0,5,10,15),(1,6,11,12),(2,7,8,13),(3,4,9,14)]):
            inv_qr(x, *args)
    
    state = bytes_to_words(recovered_keystream_block)
    for _ in range(10):
        inv_inner_block(state)
    key = words_to_bytes(state[4:12])
    

• •

  Related

• •

  Cards

  • •

    What construction step makes a normal ARX stream cipher's round function irreversible to attackers, even with a known keystream block?

    • •

      The final feed-forward addition of the pre-round state onto the post-round state — without it, the rounds are just an invertible permutation.

  • •

    If a hand-rolled ChaCha20 is missing feed-forward, what can a single recovered keystream block give you?

    • •

      The entire original internal state — constants, key, counter, and nonce — by running the rounds in reverse.

◌ Explore connections in Graph view