โ† Wiki Index / Computation & Algorithms / Feistel Cipher
๐Ÿ’ป Computation & Algorithms

Feistel Cipher

A Feistel cipher is a symmetric block cipher design where data blocks are partitioned into two halves and processed through iterative rounds of non-invertible subfunctions, guaranteeing symmetric invertibility during decryption.

Feistel Cipherโ€”also termed a Feistel networkโ€”is a fundamental symmetric block cipher structural design in computation and algorithms that partitions an input data block into two equal halves and processes them through iterative cycles of non-linear transformations and permutations. Conceived by German-American physicist and cryptographer Horst Feistel during his work on the Lucifer cipher at IBM in the early 1970s, the Feistel structure served as the architectural foundation for the Data Encryption Standard (DES) and influenced three decades of symmetric cipher engineering.

The primary architectural triumph of the Feistel design is its operational symmetry between encryption and decryption: the underlying round function F does not require mathematical invertibility. Regardless of whether F is a bijection, non-linear S-box lookup, or one-way compression function, the overall cipher remains an exact invertible permutation, allowing the identical hardware or software implementation to execute both encryption and decryption merely by reversing the order of the round subkeys.

Algorithmic Mechanics and Round Topology

Let the input block length be 2w bits, partitioned into a left half L0 and right half R0 of w bits each. For a cipher with r total rounds and round subkeys K1, K2, ..., Kr derived from a master key schedule:

In round i (for 1 โ‰ค i โ‰ค r):

  • The right half of the previous round becomes the left half of the current round:

Li = Riโˆ’1

  • The right half of the current round is computed by passing the previous right half through the round function F with subkey Ki and XORing the output into the previous left half:

Ri = Liโˆ’1 โŠ• F(Riโˆ’1, Ki)

After r rounds, a final swap operation is traditionally omitted (or reversed) to yield the output ciphertext (Rr, Lr).

Exact Decryption Proof

Decryption operates by taking the ciphertext block (Rr, Lr) and applying the identical round mechanics in reverse, applying subkeys in backward order (Kr, Krโˆ’1, ..., K1).

For any round i:

  • The previous right half is recovered directly:

Riโˆ’1 = Li

  • The previous left half is recovered by exploiting the self-inverting property of the bitwise XOR operation (A โŠ• B โŠ• B = A):

Liโˆ’1 = Ri โŠ• F(Riโˆ’1, Ki) = Ri โŠ• F(Li, Ki)

Because F(Riโˆ’1, Ki) is evaluated on known inputs and cancelled via XOR, the function F never requires an inverse Fโˆ’1, eliminating the necessity of engineering dual forward and inverse cryptographic primitives in resource-constrained hardware.

Theoretical Soundness: The Lubyโ€“Rackoff Theorem

In 1988, Michael Luby and Charles Rackoff provided the first rigorous mathematical foundation for symmetric cipher security by analyzing idealized Feistel networks where each round function Fi is replaced by an independent truly random function:

  • 1 or 2 Rounds: Insecure; can be distinguished from a random permutation with high probability using only a few chosen-plaintext queries.
  • 3 Rounds: Proven to be a secure Pseudorandom Permutation (PRP) against adaptive chosen-plaintext attacks (CPA). No polynomial-time adversary can distinguish the 3-round network from a truly random permutation without making O(2w/2) queries (the birthday bound).
  • 4 Rounds: Proven to be a Strong Pseudorandom Permutation (SPRP) secure against adaptive chosen-ciphertext attacks (CCA), where the adversary has simultaneous access to both forward encryption and inverse decryption oracles.

This formal resultโ€”often termed the Lubyโ€“Rackoff Theoremโ€”established that Feistel networks provide mathematically sound security bounds under the assumption of independent, pseudo-random round functions.

Variations and Structural Offshoots

While classical Feistel networks divide blocks into two equal halves, several structural variations address specific performance constraints:

  • Unbalanced Feistel Networks: The input block is divided into unequal segments, such as 32 bits and 96 bits, or split into k > 2 sub-blocks. In each round, only one sub-block is modified by a function applied to the remaining sub-blocks, as implemented in Skipjack and the SMS4/SM4 block cipher.
  • Alternating Feistel Schemes: Employs multiple alternating round functions or key addition mechanisms to foil slide attacks and meet specific memory constraints in smart cards.
  • Comparison with Substitution-Permutation Networks: While Feistel networks update only half of the data block per round, Advanced Encryption Standard and other SPN ciphers update every byte in the block in every round, achieving full avalanche diffusion in fewer iterations at the cost of requiring explicit inverse transformations.

Prominent Feistel Ciphers in Computing History

CipherDesignersBlock / Key SizeRoundsHistorical Significance
LuciferHorst Feistel / IBM (1971)64-bit / 128-bit16The experimental progenitor of modern Feistel architectures
DESIBM / NSA (1977)64-bit / 56-bit16The global commercial standard for more than two decades
BlowfishBruce Schneier (1993/1994)64-bit / 32โ€“448 bit16Pioneer of key-dependent S-boxes; extremely fast in software
TwofishSchneier et al. (1998)128-bit / 128โ€“256 bit16Finalist in the NIST AES competition; robust Feistel cipher
CamelliaMitsubishi / NTT (2000)128-bit / 128โ€“256 bit18 or 24Standardized Japanese and European cipher with FL-layer filtering

References

  1. Feistel, H. (1973). Cryptography and computer privacy. Scientific American, 228(5), 15-23.
  2. Luby, M., & Rackoff, C. (1988). How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 17(2), 373-386.
  3. Schneier, B. (1994). Description of a new variable-length key, 64-bit block cipher (Blowfish). In Fast Software Encryption, Lecture Notes in Computer Science, 809, 191โ€“204.
  4. Coppersmith, D. (1994). The Data Encryption Standard (DES) and its strength against attacks. IBM Journal of Research and Development, 38(3), 243-250.
๐Ÿงฌ Support Open Science
Explore interactive science games on LowKey Games or browse scientific apparel & accessories in the CRV Science Shop.
๐Ÿ’ก Spot an inaccuracy or have primary literature to expand this article?
Submit a citation or revision note using your shared CRV Science / LowKey Games profile ID.
Suggest Revision