Feistel Network

The trick: a function so you never have to invert

Every block cipher faces the same awkward demand: it has to scramble a plaintext into ciphertext and unscramble it back, perfectly, with no loss. The obvious way is to build a reversible mixing function and then build its inverse — twice the work, twice the bug surface. Horst Feistel, working at IBM in 1971 on the cipher that became DES, found a way to dodge it entirely.

Split the block into a left half L and a right half R. Pick any function F you like — it does not have to be reversible, it does not even have to be injective. Each round, compute:

L' = R
R' = L XOR F(R, K)

That single XOR is the whole secret. XOR is its own inverse: a XOR b XOR b = a. And critically, the value fed into F — the right half R — survives the round untouched as the new left half. So to undo the round, you already have everything you need: take the new left half (the old R), recompute F(R, K), and XOR it back out of the new right half to recover the old L. You never invert F. You can use a one-way hash as your round function and the cipher still decrypts flawlessly.

How a round actually works

A full encryption runs n rounds, each with its own subkey (or round key) derived from the master key by a key schedule. Writing the state after round i as (L_i, R_i):

L_i = R_{i-1}
R_i = L_{i-1} XOR F(R_{i-1}, K_i)

After the final round, most ciphers omit the last swap (or perform an explicit final swap) so that the network becomes a clean involution — this is the detail that lets the same code path run both ways. To decrypt, you feed the ciphertext through the identical rounds but with the subkeys in reverse order, K_n, K_{n-1}, …, K_1. Let's verify one round of decryption undoes one round of encryption. After encryption we hold (L_i, R_i) = (R_{i-1}, L_{i-1} XOR F(R_{i-1}, K_i)). The decryption round computes:

recovered_R = L_i                                  = R_{i-1}        ✓
recovered_L = R_i XOR F(L_i, K_i)
            = (L_{i-1} XOR F(R_{i-1}, K_i)) XOR F(R_{i-1}, K_i)
            = L_{i-1}                                                ✓

The two F terms cancel because F is called on the same input both times. That is the entire mathematical content of a Feistel network. Everything else — DES's expansion-permutation, its eight S-boxes, the P-permutation — lives inside F and exists only to provide diffusion and nonlinearity. The structure around F guarantees reversibility for free.

How many rounds buy security

One round is laughably weak: half the block (the old R, now sitting in L) is exposed in plaintext. Two rounds still leak structure. The landmark result is the Luby-Rackoff theorem (1988): if F is a secure pseudorandom function, then a 3-round Feistel network is a secure pseudorandom permutation against chosen-plaintext attacks, and 4 rounds resist the stronger chosen-ciphertext (adaptive) attacks. This is why people say "three rounds is provably enough" — but only relative to an idealized random F.

Real round functions are not ideal, so production ciphers add a large safety margin against differential and linear cryptanalysis. DES runs 16 rounds precisely because 16-round DES resists differential cryptanalysis — a fact IBM and the NSA knew in the 1970s, years before Biham and Shamir publicly rediscovered the technique in 1990. Each extra round roughly squares the work an attacker must do to push a useful differential through the cipher.

When the Feistel structure is the right choice

• Constrained hardware and firmware — one round function, used in both directions, halves your code or gate footprint versus an SPN that needs separate inverse tables.
• Your mixing primitive is one-way or hard to invert — a hash-based or table-lookup F drops straight in, since it is never inverted.
• Format-preserving encryption — unbalanced Feistel (FF1, FF3-1) is how you encrypt a credit-card number into another valid card number, or a 9-digit SSN into a 9-digit SSN.
• Designs needing a clean security proof — Luby-Rackoff gives a provable reduction to the round function's strength, which SPNs lack a comparable form of.

Reach for an SPN like AES instead when you want maximum throughput on modern CPUs (AES-NI does a whole round in a couple of instructions), full-block diffusion in fewer rounds, and natural parallelism. Most new ciphers since 2000 are SPNs for exactly these reasons; Feistel's heyday was the era when hardware was scarce and code size mattered more than cycles.

Feistel vs other block-cipher structures

	Balanced Feistel	Unbalanced Feistel	SPN (AES)	Lai-Massey (IDEA)	ARX (ChaCha-like)
Block touched per round	Half	Unequal split	Whole block	Half (via difference)	Whole state
Round function invertible?	No	No	Yes (needs inverse S-box)	No	Yes (add/rotate/XOR)
Encrypt = decrypt circuit?	Yes (reverse subkeys)	Yes (reverse subkeys)	No (separate inverse)	Nearly	No (subtract instead of add)
Typical rounds	16 (DES, Blowfish)	32 (Skipjack), 8–10 (FF)	10–14 (AES)	8.5 (IDEA)	20 (ChaCha20)
Provable security model	Luby-Rackoff	Luby-Rackoff variants	Heuristic / wide-trail	Limited	Heuristic
Hardware/code footprint	Small (shared F)	Small	Larger (two paths)	Small	Tiny (no tables)
Named users	DES, 3DES, Blowfish, Twofish, GOST, Camellia	Skipjack, FF1, FF3-1, RC2	AES, Serpent, PRESENT	IDEA, FOX	ChaCha20, Salsa20, Speck

The defining contrast is the decrypt path. A Feistel cipher gets its inverse for free by reversing the key schedule, so a single piece of silicon or one function serves both encryption and decryption. An SPN must implement inverse S-boxes and an inverse linear layer, which is why AES decryption hardware is measurably larger than its encryption hardware — though "equivalent inverse cipher" rearrangements claw some of that back.

What the numbers actually say

• DES: 64-bit block, 56-bit effective key, 16 rounds. The 56-bit key is the fatal flaw, not the structure — 2^56 ≈ 7.2 × 10^16 keys. The EFF's Deep Crack machine ($250,000 in 1998) brute-forced a DES key in 56 hours; a modern GPU cluster or FPGA rig does it in well under a day for a few thousand dollars.
• Triple-DES (3DES) chains three DES operations (encrypt-decrypt-encrypt) for an effective key strength of 112 bits after the meet-in-the-middle attack — still a Feistel cipher, just stacked. NIST deprecated it for new use in 2023 mainly because its 64-bit block invites Sweet32 birthday collisions after roughly 2^32 blocks (~32 GB).
• Luby-Rackoff bound: a 3-round balanced Feistel on a 2n-bit block is secure until about 2^(n/2) queries — the birthday bound on the n-bit halves.
• Blowfish/Twofish: 16 rounds. Blowfish's key schedule is deliberately expensive (it derives 4 KB of S-box state), making brute-force key search ~few-hundred-times slower per trial than DES — bcrypt weaponizes exactly this.

JavaScript implementation

A toy 8-bit-half Feistel to make the symmetry concrete. The round function is deliberately simple (a keyed mix) so the structure stands out — a real cipher swaps in DES-style S-boxes here. Note that encrypt and decrypt call the same core loop; only the subkey order flips.

const MASK = 0xff;                       // each half is 8 bits

// Round function — need NOT be invertible. Any mixing works.
const F = (half, key) => {
  let x = (half ^ key) & MASK;
  x = ((x << 3) | (x >> 5)) & MASK;       // rotate left 3
  x = (x * 0x9d + 0x2b) & MASK;          // nonlinear-ish mix
  return x & MASK;
};

// One Feistel pass over [L, R] given an ordered subkey list.
function feistel(L, R, subkeys) {
  for (const k of subkeys) {
    const newR = L ^ F(R, k);            // R' = L XOR F(R, K)
    L = R;                               // L' = R
    R = newR;
  }
  return [L, R];                         // no final swap; we undo it in decrypt
}

function encrypt(L, R, subkeys) {
  return feistel(L, R, subkeys);
}

function decrypt(L, R, subkeys) {
  // Same network, subkeys reversed — but account for the missing final swap
  // by swapping halves in and out.
  [R, L] = feistel(R, L, [...subkeys].reverse());
  return [L, R];
}

const keys = [0x3a, 0x7c, 0x11, 0xd4];   // 4-round key schedule
const [cL, cR] = encrypt(0x12, 0x34, keys);
const [pL, pR] = decrypt(cL, cR, keys);
console.log(pL.toString(16), pR.toString(16)); // "12 34" — round-trips exactly

The fiddly part is the final-swap bookkeeping. Many textbook implementations perform a swap after every round including the last, then make decryption symmetric by swapping the input halves before the loop and the output halves after — the version above folds that into feistel(R, L, …). Pick one convention and test the round-trip; mismatched swap handling is the single most common Feistel bug.

Python implementation

MASK = 0xFF                                # 8-bit halves

def F(half, key):                         # round function, NOT invertible
    x = (half ^ key) & MASK
    x = ((x << 3) | (x >> 5)) & MASK        # rotate left 3
    x = (x * 0x9D + 0x2B) & MASK           # nonlinear mix
    return x & MASK

def feistel(L, R, subkeys):
    for k in subkeys:
        L, R = R, L ^ F(R, k)             # (L', R') = (R, L XOR F(R, K))
    return L, R

def encrypt(L, R, subkeys):
    return feistel(L, R, subkeys)

def decrypt(L, R, subkeys):
    R, L = feistel(R, L, list(reversed(subkeys)))
    return L, R

keys = [0x3A, 0x7C, 0x11, 0xD4]
cL, cR = encrypt(0x12, 0x34, keys)
pL, pR = decrypt(cL, cR, keys)
assert (pL, pR) == (0x12, 0x34)           # exact round-trip, any F
print(hex(cL), hex(cR))

The Python tuple-swap L, R = R, L ^ F(R, k) is a faithful one-line transcription of the round equations and avoids the temporary-variable mistake of overwriting R before computing F(R, k). The assert is the whole proof in one line: whatever F does, the network round-trips.

Variants worth knowing

Unbalanced Feistel. Split the block into two unequal parts. Skipjack (the Clipper-chip cipher, declassified in 1998) processes a 16-bit word against the rest each round across 32 rounds. The format-preserving schemes FF1 and FF3-1 (NIST SP 800-38G) use unbalanced Feistel over a custom radix so that a 16-digit card number encrypts to another 16-digit number.

Generalized / Type-1, Type-2, Type-3 Feistel. Slice the block into k > 2 sub-blocks and rotate the round function through them. CAST-256 and the lightweight cipher CLEFIA use generalized Feistel for better parallelism than the strictly serial classic structure.

Alternating / key-dependent F. Blowfish makes its S-boxes — and therefore F — depend on the key, computed by an expensive setup. That setup cost is the foundation of the bcrypt password hash, where deliberately slow key scheduling resists offline cracking.

Lai-Massey (IDEA). A close cousin that mixes the halves through their difference rather than copying one half forward; it is also near-involutional but built on modular multiplication instead of S-boxes.

Common bugs and edge cases

• Mishandling the final swap. Encrypt and decrypt must agree on whether the last round swaps. Get it wrong and the cipher encrypts fine but decryption returns garbage. Always test a full round-trip on random inputs.
• Reversing the wrong thing. Decryption reverses the subkey order, not the bytes of each subkey and not the round function. Reversing the bits of F breaks everything.
• Computing F on the already-updated half. In an imperative language, overwriting R before computing F(R, K) feeds the wrong value in. Use a temporary or a tuple-swap.
• Too few rounds. One or two rounds leave half the block essentially in the clear. Never ship a "fast" 2-round Feistel; honor the Luby-Rackoff minimum of 3–4 and add margin.
• DES weak keys. Four DES keys produce identical subkeys in every round, making encryption an involution (E_k(E_k(x)) = x); twelve more are semi-weak pairs. Reject them in a key generator.
• 64-bit block birthday limit. Any 64-bit-block Feistel (DES, 3DES, Blowfish) leaks via collisions after ~2^32 blocks under CBC/CTR — the Sweet32 attack. For bulk data use a 128-bit-block cipher.