Introduction

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.

Try It: Encrypt and Decrypt

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>Message byte (0–255):
    <input id="msgInput" type="number" min="0" max="255" value="42" />
  </label>
  <div class="btns">
    <button id="btnEncrypt" type="button">Encrypt</button>
    <button id="btnDecrypt" type="button" disabled>Decrypt</button>
    <button id="btnReset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Simplified 4-round Feistel cipher on an 8-bit block (two 4-bit halves).
// Round keys are fixed constants for demo purposes.
// Round function F(x, k) = ((x * 3 + k) ^ (x << 1 | x >> 3)) & 0xF
// Encryption: (L, R) -> (R, L ^ F(R, K_i))  for each round
// Decryption: same rounds in reverse order with same keys, using the inverse identity.

const ROUNDS = 4;
const ROUND_KEYS = [5, 11, 3, 9]; // 4-bit keys (0-15)

function F(x, k) {
  // A simple keyed mixing function on 4-bit values — not invertible in general.
  return ((x * 3 + k) ^ ((x << 1 | x >> 3) & 0xF)) & 0xF;
}

function feistelEncrypt(msg) {
  // msg is 8-bit; split into two 4-bit halves
  let L = (msg >> 4) & 0xF;
  let R = msg & 0xF;
  const steps = [{ L, R, label: `Input`, xorInfo: '' }];
  for (let i = 0; i < ROUNDS; i++) {
    const fVal = F(R, ROUND_KEYS[i]);
    const newL = R;
    const newR = (L ^ fVal) & 0xF;
    steps.push({ L: newL, R: newR, label: 'R' + (i + 1), xorInfo: `F=${hex(fVal)}` });
    L = newL; R = newR;
  }
  return { ciphertext: (L << 4) | R, steps };
}

function feistelDecrypt(cipher) {
  // Same rounds, reversed key order; inversion identity: L_prev = R_curr ^ F(L_curr, K_i), R_prev = L_curr
  let L = (cipher >> 4) & 0xF;
  let R = cipher & 0xF;
  const steps = [{ L, R, label: `Input`, xorInfo: '' }];
  for (let i = ROUNDS - 1; i >= 0; i--) {
    const fVal = F(L, ROUND_KEYS[i]);
    const newR = L;
    const newL = (R ^ fVal) & 0xF;
    steps.push({ L: newL, R: newR, label: 'D' + (ROUNDS - i), xorInfo: `F=${hex(fVal)}` });
    L = newL; R = newR;
  }
  return { plaintext: (L << 4) | R, steps };
}

function hex(v) { return '0x' + v.toString(16).toUpperCase().padStart(2, '0'); }

function renderSteps(steps, title) {
  const viz = document.getElementById('roundsViz');
  viz.innerHTML = '';

  // Header
  const hdr = document.createElement('div');
  hdr.className = 'header-row';
  hdr.innerHTML = fmt(`<div class="header-label">%title%</div>
    <div class="header-half">Left (H)</div>
    <div class="header-half"></div>
    <div class="header-half">Right (L)</div>`, { title: title });
  viz.appendChild(hdr);

  steps.forEach((s, idx) => {
    const row = document.createElement('div');
    row.className = 'round-row';
    const prevL = idx > 0 ? steps[idx - 1].L : null;
    const prevR = idx > 0 ? steps[idx - 1].R : null;
    const lChanged = prevL !== null && s.L !== prevL;
    const rChanged = prevR !== null && s.R !== prevR;
    row.innerHTML = `
      <div class="round-label">${s.label}</div>
      <div class="half left${lChanged ? ' changed' : ''}">${hex(s.L)}</div>
      <div class="arrow">⇌</div>
      <div class="half right${rChanged ? ' changed' : ''}">${hex(s.R)}</div>
      ${s.xorInfo ? `<div class="xor-info">${s.xorInfo}</div>` : ''}
    `;
    viz.appendChild(row);
  });
}

let lastCipher = null;

document.getElementById('btnEncrypt').addEventListener('click', () => {
  const msg = parseInt(document.getElementById('msgInput').value, 10);
  if (isNaN(msg) || msg < 0 || msg > 255) {
    setStatus(`Enter a number between 0 and 255.`, '');
    return;
  }
  const { ciphertext, steps } = feistelEncrypt(msg);
  lastCipher = ciphertext;
  renderSteps(steps, `Enc`);
  setStatus(fmt(`Encrypted %hex% → %hex2%`, { hex: hex(msg), hex2: hex(ciphertext) }), 'enc');
  document.getElementById('btnDecrypt').disabled = false;
  console.log(fmt(`Feistel encrypt: %msg% → %ciphertext% (steps: %stringify%)`, { msg: msg, ciphertext: ciphertext, stringify: JSON.stringify(steps) }));
});

document.getElementById('btnDecrypt').addEventListener('click', () => {
  if (lastCipher === null) return;
  const { plaintext, steps } = feistelDecrypt(lastCipher);
  renderSteps(steps, `Dec`);
  const orig = parseInt(document.getElementById('msgInput').value, 10);
  const match = plaintext === orig;
  setStatus(fmt(`Decrypted %hex% → %hex2%%v%`, { hex: hex(lastCipher), hex2: hex(plaintext), v: match ? ' ✓ matches original!' : ' ✗ mismatch!' }), match ? 'ok' : '');
  console.log(fmt(`Feistel decrypt: %lastCipher% → %plaintext% (match=%match%)`, { lastCipher: lastCipher, plaintext: plaintext, match: match }));
});

document.getElementById('btnReset').addEventListener('click', () => {
  document.getElementById('roundsViz').innerHTML = '';
  document.getElementById('status').textContent = '';
  document.getElementById('btnDecrypt').disabled = true;
  lastCipher = null;
});

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + cls;
}
Result
Console

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

The Real Complexity

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 FF 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 FF 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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/feistel-networks/Content licensed under CC BY-NC 4.0.