Feistel Networks: Building Blocks of Modern Ciphers

In the early 1970s, Horst Feistel at IBM Research was working on the Lucifer cipher when he developed a fundamental insight: you can build an invertible cipher using a non-invertible round function.

This was revolutionary because designing invertible functions that are also secure is hard. Feistel's construction sidesteps this requirement entirely, allowing the use of arbitrarily complex, one-way round functions.

In a Feistel cipher, the input block is split into two equal halves: L (left) and R (right). Each round applies the round function F to R, XORs the result with L, then swaps the halves.

After n rounds, the two halves are recombined to produce the ciphertext. The swapping ensures both halves are processed in alternating rounds, mixing them thoroughly.

The round function F in a Feistel network takes the right half and the round subkey as inputs and produces an output that is XORed with the left half. Crucially, F does not need to be invertible.

F can be arbitrarily complex: any combination of substitutions, permutations, XORs, and modular arithmetic. The more complex and non-linear F is, the stronger the cipher, because decryption never needs to invert F.

Decryption in a Feistel cipher uses the exact same structure as encryption, but applies the round subkeys in reverse order. This is possible because XOR is its own inverse: if A XOR B = C, then C XOR B = A.

Since decryption never calls F^-1 (the inverse of F), the round function can be an irreversible hash, a lookup table, or any complex operation without affecting the cipher's invertibility.

The mathematical elegance of Feistel networks is that the XOR structure guarantees invertibility regardless of what F does. Even if F is a one-way function like SHA-256, the overall Feistel cipher remains invertible.

This makes Feistel ciphers extremely flexible. Cryptographers can focus entirely on making F as confusing and diffusing as possible, knowing the invertibility is handled by the network structure itself.

The Data Encryption Standard (DES), published in 1977, is a 16-round Feistel cipher operating on 64-bit blocks with a 56-bit key. Each round uses a different 48-bit subkey derived from the main key.

The round function in DES includes expansion permutation, XOR with the subkey, eight S-boxes providing non-linearity, and a P-box permutation. The combination provides both confusion and diffusion as required by Shannon's cipher design principles.

Blowfish, designed by Bruce Schneier in 1993, is a variable key length (32-448 bits) Feistel cipher with 16 rounds. It uses key-dependent S-boxes, making precomputed attacks impractical.

Twofish, a finalist in the AES competition, extends Blowfish ideas with 128-bit blocks and 16 rounds. Both remain unbroken and are used in applications like bcrypt password hashing, which uses a modified Blowfish.

A balanced Feistel cipher splits the block into two equal halves. An unbalanced Feistel uses unequal halves, such as a 3/4 and 1/4 split.

Unbalanced Feistel networks can offer security advantages in certain contexts and are used in some specialized ciphers. The CAST family of ciphers uses a balanced 64-bit Feistel structure.

In 1988, Michael Luby and Charles Rackoff proved that a 3-round Feistel network using pseudorandom round functions is a secure pseudorandom permutation (PRP), and a 4-round version is a strong PRP.

This theoretical result gave Feistel networks a solid provable security foundation, not just empirical confidence. It confirmed that the Feistel structure itself contributes to security beyond just the round function.

The Substitution-Permutation Network (SPN) used by AES applies substitution and permutation to the entire block simultaneously, rather than half the block per round. This provides faster diffusion.

AES achieves full diffusion in just 4 rounds, while DES's Feistel structure needs more rounds for comparable diffusion. AES's SPN also maps better to modern processor architectures with SIMD instructions.

The Luby-Rackoff theorem treats the round function F as a truly random function. In practice, F is a pseudorandom function (a keyed cipher or hash), not a true random oracle.

This gap between theoretical proofs and practical implementations is a recurring theme in cryptography. Proofs provide confidence but are based on idealized models. Real-world security also depends on secure implementations free from side-channel vulnerabilities.

Test your understanding of Feistel network design.

Feistel networks are block cipher structures that use a round function that does not need to be invertible. Decryption works by running the same structure in reverse with subkeys in reversed order.

DES, Blowfish, and Twofish are all Feistel ciphers. The Luby-Rackoff theorem provides theoretical security guarantees. AES uses an SPN structure instead, offering better diffusion per round.