Feistel Networks, DES & Blowfish

Block ciphers come in two great architectural families: substitution–permutation networks (AES's family) and Feistel networks (DES's family). The Feistel construction solves an elegant problem — how to build an invertible cipher out of a non-invertible scrambling function — and its two most famous members teach the two most durable operational lessons in the field: key length is destiny (DES), and 64-bit blocks are now too small (both).

The Feistel construction #

Split the block into halves $L$ and $R$. One round computes:

$$L_i = R_{i-1}, \qquad R_i = L_{i-1} \oplus F(R_{i-1}, K_i)$$

where $F$ is the round function and $K_i$ the round subkey. Iterate 16 times, swap-free on the last round, done.

flowchart LR
  subgraph round["one Feistel round"]
    L0["L(i-1)"] --> X((XOR))
    R0["R(i-1)"] --> F["F(·, Ki)"]
    F --> X
    R0 --> L1["L(i) = R(i-1)"]
    X --> R1["R(i)"]
  end

Provable backing came later: Luby and Rackoff (1988) showed that 3–4 Feistel rounds with a pseudorandom $F$ yield a pseudorandom permutation — the construction is sound in principle; everything rides on $F$ and the number of rounds.

DES: the canonical cautionary tale #

DES (1977) is a 16-round Feistel cipher on 64-bit blocks with a 56-bit key (64 bits minus 8 parity bits). The infamous initial/final permutations (IP/FP) at either end are cryptographically null — bit-shuffles with no key input, likely a 1970s hardware-layout convenience. The strength lives in $F$: expand 32 bits to 48, XOR with the subkey, push through eight 6→4-bit S-boxes, permute.

Two historical facts carry the lessons:

• The S-boxes were tuned against an attack the public didn't know existed. When Biham and Shamir published differential cryptanalysis in 1990, DES turned out to be strangely resistant. Coppersmith confirmed in 1994 that IBM and NSA knew the technique in 1974 and shaped the S-boxes against it, keeping the criteria secret. Design rationale you cannot audit is a Kerckhoffs problem even when the designers are honest.
• The key was sized to fail. NSA negotiated the key down from Lucifer's 128 bits to 56. The keyspace ($2^{56} \approx 7.2 \times 10^{16}$) fell to organized brute force on schedule:

1. 1977 Diffie & Hellman estimate a $20M machine could break DES daily; dismissed as alarmist.
2. 1998 EFF builds Deep Crack for ~$250k; finds a key in 56 hours.
3. 1999 Deep Crack + distributed.net: 22 hours 15 minutes.
4. 2012+ Commodity FPGA rigs and cloud GPU services crack DES keys in hours for a few thousand dollars.

3DES (EDE: encrypt–decrypt–encrypt with 2–3 keys) patched the key length to 112 effective bits (meet-in-the-middle caps it below the naive 168), but kept the 64-bit block — see the Sweet32 box below. NIST fully disallowed 3DES for encryption after 2023 (SP 800-131A Rev. 2); it survives only in legacy payment hardware.

Blowfish: Feistel with a deliberately expensive key schedule #

Blowfish (Schneier, 1994) was a free, unpatented DES replacement candidate: 16-round Feistel, 64-bit block, key from 32 to 448 bits. Its round function uses four key-dependent 8→32-bit S-boxes:

$$F(x) = \big((S_1[x_1] + S_2[x_2] \bmod 2^{32}) \oplus S_3[x_3]\big) + S_4[x_4] \bmod 2^{32}$$

The interesting part is the key schedule. The 18 subkeys and 4×256 S-box entries (4168 bytes of state) are initialized with the hex digits of $\pi$ (nothing-up-my-sleeve numbers), XORed with the key, then overwritten by running Blowfish on itself 521 times. Key setup costs as much as encrypting ~4 KB — irrelevant for bulk encryption, ruinous for brute force.

Schneier himself has told users to move on ("I'm amazed it's still being used"): Twofish was its 128-bit-block successor, and today the answer is AES or ChaCha20.

Where Feistel designs still live #

The construction is alive; the 64-bit-block instances are not.

Source claims audit #

Seeded from a university lab manual (DES and Blowfish labs, following Applied Cryptography). Status of its load-bearing claims: