Why a Feistel Round Function Need Not Be Invertible

A block cipher is a permutation: for each key it maps every $n$-bit string to a distinct $n$-bit string, and the map must be reversible by anyone holding the key. The obvious way to build such a thing is to compose many small invertible pieces, since a composition of permutations is a permutation. The Feistel construction does something stranger. It builds the permutation out of a function that has no inverse at all, and in the standard case is not even one-to-one.

The trick is that the non-invertible function never touches the data directly. It is used only to produce a mask, and masks can be removed by repeating the same XOR.

The round that loses information

Split the block into two halves of $n/2$ bits, written $L$ and $R$. A single round with round key $k$ computes

$$(L, R) \mapsto \big(R,; L \oplus F(R, k)\big)$$

where $F$ is an arbitrary function from $n/2$ bits to $n/2$ bits. Nothing is required of $F$ beyond being computable. It may collapse many inputs to one output; it may be built from lookup tables that are not permutations; it may be a hash of its arguments. The round as a whole is nevertheless invertible, because the ciphertext pair $(L’, R’)$ still contains $R$ verbatim in its left half. Given $(L’, R’)$, the recovery step is

$$R = L’, \qquad L = R’ \oplus F(L’, k)$$

which is the same expression evaluated at a different point. One evaluation of $F$ suffices in each direction, and both directions run the identical code path with the operands swapped.

This is worth stating plainly because it is the whole idea: the round function is used as a one-way mask generator, and XOR is its own inverse. The Feistel network is a permutation on $2n$ bits for every choice of $F$, including the constant function $F(x) = 0$, for which the network degenerates into a half-block swap. That is a permutation too, just a useless one. Invertibility is free; secrecy is what costs rounds.

In the Data Encryption Standard the halves are 32 bits, the block is 64, and $F$ expands the right half to 48 bits, XORs a 48-bit subkey, passes the result through eight S-boxes that each map 6 bits to 4, and permutes the 32 output bits. The 48-to-32 compression inside $F$ means the function is wildly non-injective: each output has $2^{16}$ preimages. The construction does not care. DES also illustrates how little structure $F$ needs to be invertible — the S-boxes are specified as arbitrary tables, chosen for their differential and linear properties rather than for having inverses.

Decryption with the same circuit

Because the inverse of a round is the same round with the halves exchanged, a Feistel cipher can be decrypted by running the encryption datapath backwards, feeding subkeys in reverse order. Hardware that implements DES for encryption implements decryption with no additional gates; a multiplexer selects whether subkeys are consumed in forward or reverse order. The same property holds in software, where the round loop is shared and only the key schedule iterator differs.

/* One Feistel round; the inverse round is the same computation with the
   operands swapped, so decryption needs no separate inverse function. */
static void feistel_round(uint32_t *l, uint32_t *r, uint32_t subkey)
{
    uint32_t t = *l ^ f(*r, subkey);
    *l = *r;
    *r = t;
}

/* Encrypt: rounds 0..n-1. Decrypt: rounds n-1..0 with the same function. */
void feistel_crypt(uint32_t *l, uint32_t *r, const uint32_t *subkeys,
                   int rounds, int decrypt)
{
    for (int i = 0; i < rounds; i++) {
        int j = decrypt ? rounds - 1 - i : i;
        feistel_round(l, r, subkeys[j]);
    }
}

The pattern generalises beyond two branches. Unbalanced Feistel networks split the block unevenly, applying $F$ to the wider part and combining into the narrower one; this appears in ciphers built for word-oriented software and in format-preserving constructions where the domain size is not a power of two. The invertibility argument survives as long as the split is consistent and the modified part is carried forward unchanged.

What the construction costs

The price of the trick is throughput per round. In an SPN such as AES, a single round applies a byte substitution to all 16 state bytes and then diffuses across the entire 128-bit state; one round moves every bit into a position that depends on many others. In a Feistel round only half the state passes through $F$. A bit that enters $F$ in round $i$ can influence at most the other half by round $i+1$, so reaching full diffusion takes roughly twice as many rounds for the same block width. DES needs 16 rounds to diffuse across 64 bits; AES reaches comparable diffusion in 4 rounds across 128 bits, though it uses 10, 12, or 14 rounds for margin.

There is a compensating advantage: $F$ can be made much heavier than an SPN round would allow, since only half the state is processed, and its internals need not be invertible, which widens the design space for S-boxes, key mixing, and cheap arithmetic. Blowfish, CAST-128, Camellia, and the TEA family all exploit this freedom.

The security argument is quantifiable in the ideal-model sense. Luby and Rackoff showed that a three-round Feistel network built from pseudorandom functions is a pseudorandom permutation — indistinguishable from a random permutation under chosen-plaintext attack — while four rounds are needed to resist chosen-ciphertext attacks, that is, to be a strong pseudorandom permutation. The gap between three and four rounds is not cosmetic: with three rounds the inverse direction is distinguishable, because the last operation is a plain XOR of a function output into the left half, and an attacker who can query the inverse can detect the asymmetry.

Where the argument stops holding

Invertibility is structural and unconditional; security is neither. Several failure modes recur.

A round function that ignores its input makes the network a key-dependent sequence of swaps. So does a round function with output independent of some input bits, which is why designers specify avalanche criteria for $F$ rather than trusting the Feistel shell to provide them. The shell guarantees only that the map is a permutation.

Short blocks hit the birthday bound regardless of round count. With a 64-bit block, roughly $2^{32}$ blocks under one key produce a collision with probability near one half, and a repeated block in a mode that should never repeat reveals equality of plaintext. This is why 64-bit-block ciphers are deprecated for high-volume use and why the same cipher with a 128-bit block changes the bound to $2^{64}$ blocks.

Round count is chosen against the best known attack, not against the ideal-model bound. Slide attacks, impossible differentials, and integral attacks all exploit the regularity that makes Feistel networks attractive: the same $F$ is applied repeatedly with only the subkey varying. Key schedules that derive subkeys by a simple rotation can create equivalent keys or related-key behaviour, which is a separate failure axis from the round function’s quality. Key schedules and their diffusion treats that problem directly.

Finally, the Feistel structure hides nothing about its own shape. The two halves are public, so a distinguisher only has to find a property of $F$ that survives several rounds. Differential and linear attacks against DES exploited exactly this, using the S-box tables’ deviation from perfect nonlinearity rather than any flaw in the network topology. The analysis that turned those deviations into a practical attack is covered in differential and linear cryptanalysis.

Round counts and the cost of the shell

The round count in a Feistel cipher is a statement about how many independent mask evaluations an attacker must penetrate. Two facts push it upward relative to an SPN. The first is the halved diffusion rate: a difference entering $F$ in round $i$ reaches the other half in round $i+1$, so full-state mixing requires at least as many rounds as there are bits to move, which is why sixteen rounds for sixty-four bits sits near the minimum for DES’s block size and why a wider Feistel block needs more.

The second is that only half the state receives the nonlinear transform per round, so each round contributes roughly half an SPN round’s nonlinearity. Designers compensate either by adding rounds or by making $F$ heavier than a single SPN round would be. Blowfish’s $F$ passes through four 32-bit S-box lookups and combines them with additions and XORs, which is more work per round than AES’s byte substitution, and Blowfish uses sixteen rounds on a 64-bit block.

The hardware argument runs the other way. Because encryption and decryption share gates, the area for both directions equals the area for one, which matters where the silicon budget is fixed. The round function’s invertibility requirement is also relaxed, so S-boxes can be chosen for differential and linear properties alone and need not be permutations. DES’s S-boxes exploit this: each is a 6-to-4 map, and the design could not have used them if the shell demanded invertible components.

The software picture is less favourable. A 64-bit-block Feistel on a 64-bit machine processes a block at half the machine’s width, and the bit permutations that are free in hardware become shifts and masks. That is why DES implementations on general-purpose processors are slower than their gate counts suggest, and why the AES competition’s evaluation penalised ciphers whose structure matched hardware but not available instructions.

The construction’s real legacy is architectural: it decouples the question “is this a permutation?” from “is this hard to invert?”, and answers the first with algebra so that design effort can go entirely into the second.