Feistel Networks

In 1973, IBM engineer Horst Feistel published a paper describing how to build a strong block cipher — a function that scrambles a fixed-size block of data using a secret key, and that can be undone exactly given the same key. The problem he solved was elegant: your round function can be a complete black box — non-invertible, ugly, arbitrarily complex — yet the overall cipher remains perfectly invertible.

The key insight is structural, not mathematical. Instead of finding a function whose inverse you can compute, Feistel's construction arranges any function so that decryption follows automatically from the same machinery used for encryption. Run the rounds forward to encrypt; run the same rounds backward with the keys in reverse order to decrypt.

This was the foundation of DES (Data Encryption Standard), adopted by NIST in 1977, and it influenced virtually every block cipher designed in the following two decades. Understanding the Feistel structure means understanding the skeleton of modern symmetric cryptography.

The demo below runs a simplified 4-round Feistel cipher on an 8-bit block. Type your own message byte (0–255), hit Encrypt, and watch the two halves swap and mix through each round. Then hit Decrypt to see the same rounds run in reverse — landing back on the original value.

<div class="controls">
  <label>{{lbl_message}}
    <input id="msgInput" type="number" min="0" max="255" value="42" />
  </label>
  <div class="btns">
    <button id="btnEncrypt" type="button">{{btn_encrypt}}</button>
    <button id="btnDecrypt" type="button" disabled>{{btn_decrypt}}</button>
    <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>
<div id="roundsViz" class="rounds-viz"></div>
<div id="status" class="status"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.controls { display: flex; align-items: center; gap: 1rem; flex-wrap: wrap; margin-bottom: .8rem; }
label { font-weight: 600; font-size: .9rem; }
input[type=number] { width: 70px; padding: .3rem .5rem; border: 1px solid #adb1b8; border-radius: 6px;
                     font-size: 1rem; margin-left: .4rem; }
.btns { display: flex; gap: .5rem; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button:disabled { opacity: .4; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }
.rounds-viz { display: flex; flex-direction: column; gap: .5rem; }
.round-row { display: flex; align-items: center; gap: .5rem; }
.round-label { font: 700 12px ui-monospace, monospace; color: #555; width: 56px; flex-shrink: 0; }
.half { display: flex; align-items: center; justify-content: center; min-width: 54px; padding: .3rem .5rem;
        border-radius: 6px; font: 700 13px ui-monospace, monospace; border: 1.5px solid #cdd9e3;
        background: #e8eef3; color: #1d3557; }
.half.left { background: #d6eaf8; border-color: #9abdd6; }
.half.right { background: #fef9e7; border-color: #d4a820; }
.half.changed { outline: 2px solid #e63946; outline-offset: 1px; }
.arrow { color: #888; font-size: .9rem; }
.xor-info { font: 12px ui-monospace, monospace; color: #555; margin-left: .3rem; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin-top: .5rem; }
.status.ok { color: #0a7d33; }
.status.enc { color: #1d3557; }
.header-row { display: flex; align-items: center; gap: .5rem; margin-bottom: .2rem; }
.header-label { font: 700 11px system-ui; color: #888; width: 56px; }
.header-half { font: 700 11px system-ui; color: #888; min-width: 54px; text-align: center; }

// Code not found

Notice what the round function $F$ never needs to be: it does not need an inverse. The XOR trick guarantees that decryption always works, no matter what $F$ does internally. That is the core of the Feistel insight.

The Feistel network solves a problem at two distinct levels:

Invertibility by construction. Each round maps (L, R) to (R, L ⊕ F(R, $K_{i}$)). To invert it you simply recover L = R' ⊕ F(L', $K_{i}$) and R = L' — no inverse of $F$ needed. The XOR is its own inverse. This is not an approximation: it is an exact algebraic identity.

Security from rounds. Invertibility comes for free; security does not. A classic result by Luby and Rackoff (1988) proved that:

• 2 rounds of a Feistel with a truly random round function produce a pseudorandom permutation secure against chosen-plaintext attacks.
• 3 rounds extend security to chosen-ciphertext attacks.
• DES uses 16 rounds for a large safety margin; Blowfish uses 16; Twofish uses 16.

The round function $F$ can be anything — a lookup table (S-box), a polynomial, a hash — as long as it is keyed and hard to invert without the key. The Feistel structure wraps it into something both invertible and (with enough rounds) cryptographically strong. This separation of concerns — structure guarantees invertibility, function provides confusion — is what makes Feistel networks so powerful and so widely copied.

It is worth noting that the security of DES fell not because of the Feistel structure but because of its 56-bit key, which became brute-forceable as hardware improved. The structure itself was so sound that it was kept intact in 3DES, which simply applied DES three times.

The Feistel structure shows up wherever you need a keyed, invertible scrambler and the round function is easier to design than to invert:

• DES and 3DES: the original and most famous application, using 16 rounds with 8 S-boxes as the round function. DES was the global standard for two decades; 3DES extended its life by tripling the key and running the structure three times.
• Blowfish and Twofish: Bruce Schneier's 1993 Blowfish and the AES finalist Twofish both use Feistel networks. Blowfish is still widely deployed in bcrypt password hashing.
• CAST and many others: CAST-128, used in PGP and SSH, is Feistel-based. The family is large.
• Format-preserving encryption (FPE): when you need to encrypt a credit-card number and get back a number (not random bytes), Feistel networks applied over small domains are the standard approach.
• Hash function internals: some hash functions (e.g., early designs) borrow the Feistel mixing structure for their compression functions.

Understanding Feistel networks is prerequisite knowledge for reading the literature on discrete logarithms, key exchange, and the history of standardised factoring-based public-key cryptography — because Feistel ciphers are what public-key cryptography wraps around in hybrid encryption.

Horst Feistel's insight was that invertibility is a property of structure, not of function. By splitting a block into two halves, mixing with XOR, and swapping, you guarantee that the cipher can always be undone — regardless of how complicated, one-way, or opaque the round function is.

That idea gave us DES, 3DES, Blowfish, and a long lineage of ciphers. It showed that you could standardise the shape of a cipher while leaving the heart of it open to improvement. Even as AES (which is not Feistel-based) displaced DES, the Feistel structure lives on in countless deployed systems and in the theoretical toolbox of every cryptographer.

The next time you log into a server protected by a legacy cipher, or hash a password with bcrypt, you are trusting in a 1970s structural idea so clean that no one has found a reason to discard it.