Modern cryptography

The Feistel Network

How one construction solved an old encryption problem — and became the basis of DES, Russia’s Magma, and dozens of other algorithms

⏱️ 5 min read

📊 Intermediate level

🔑 Foundation of DES and Magma

The problem Feistel solved

To decrypt a block cipher you have to somehow undo whatever scrambling encrypted it. Coming up with one good scrambling function is hard enough. Coming up with a clean mathematical inverse as well, and implementing both, doubles the work — and doubles the chances of getting something wrong.

In the early 1970s at IBM, Horst Feistel proposed a structural trick: cut the data block in half into L and R, run one half — together with a round key — through a function F that can be as complicated and irreversible as you like, add the result to the other half, then swap the halves. Repeat several times.

Key takeaway: The trick isn’t in the function F, it’s in the structure itself. XOR undoes itself, and swapping halves is trivially reversible. So the whole round is reversible — even when F itself isn’t. Decryption is the exact same algorithm, just with the round keys applied in reverse order.

How a Feistel network is built

Broken down into steps, the whole construction turns out to be surprisingly simple:

Splitting the block

The data block is cut in half into a left half L and a right half R. In DES that’s 32 and 32 bits out of a 64-bit block; in the Ludus Lab game it’s 4 and 4 bits out of a single byte.

The round function

The right half R is combined with this round’s subkey and run through function F — in DES and Magma that’s a set of S-boxes, substitution tables, which give the cipher its non-linearity.

Adding and swapping

F’s result is XORed with the left half L, producing the new right half. Then the halves are swapped.

Repeat for many rounds

The whole thing repeats over and over, each time with a new subkey: 16 times in DES, 32 times in Magma. More rounds make it harder to find any pattern between plaintext and ciphertext.

Final swap and decryption

After the last round the halves are swapped one more time — and this is what gives a Feistel network its main property: to decrypt, Bob runs the exact same algorithm, just feeding in the subkeys in reverse order.

One round of a Feistel network

L, R

The block’s halves

→

F(R, K)

R + subkey → S-boxes

→

L ⊕ F

Add to L

→

R, L'

Halves are swapped

F can be as complicated and irreversible as you like — it’s the "split, mix, swap" scheme itself that is reversible.

From Lucifer to today

Feistel’s idea didn’t stay theoretical — a large share of 20th-century symmetric cryptography is built on it:

Lucifer (IBM, early 1970s)

The first cipher built on a Feistel structure, created by Horst Feistel and his team at IBM.

The direct ancestor of DES

DES (NBS, 1977)

A refined Lucifer became the US standard for a quarter century — a 64-bit block, a 56-bit key, 16 rounds.

Key: 56 bits — not enough today

GOST 28147-89 "Magma" (USSR, 1989)

An independent Soviet design on the same idea: a 64-bit block, but a 256-bit key and 32 rounds.

Today: GOST R 34.12-2015

The Feistel scheme turned out to be so successful that it became the basis of several more generations of ciphers:

DES 3DES MAGMA (GOST) Blowfish CAST-128 Twofish Camellia KASUMI

What ISN’T a Feistel network? AES and Russia’s "Kuznyechik" are built differently — they’re substitution-permutation networks (SP-networks), not Feistel networks. Both ideas solve the same problem, just in different ways.

Try a Feistel network yourself

In the Ludus Lab interactive demo you can:

🔤
Turn text into bits — see how UTF-8 splits your message into bytes, and pick one to encrypt
🔑
Set a shared key and watch, step by step, how it produces four different round subkeys
🌊
Check the avalanche effect of the S-box — see how one changed input bit changes several output bits at once
🔄
Walk through all 4 encryption rounds bit by bit — with XOR, the S-box, and swapping halves
✅
Decrypt the result with the same algorithm and the subkeys in reverse order — and confirm the message comes back intact

The game’s main lesson: Decryption works not because someone undoes the function F, but because the structure itself of a Feistel network is symmetric with respect to the order of the subkeys. Work through it on a single byte, and the principle behind DES, Magma, and dozens of other ciphers becomes clear.

For the curious

DES and Magma side by side

Both algorithms are Feistel networks, but at very different scales and with very different fates:

Parameter	DES	Magma (GOST 28147-89)
Country of origin	USA	USSR / Russia
Year adopted	1977	1989 (today GOST R 34.12-2015)
Architecture	Feistel network	Feistel network
Block size	64 bits	64 bits
Key length	56 bits	256 bits
Number of rounds	16	32
S-boxes	Fixed by the standard since 1977	Originally an agency secret; a single fixed set only arrived in 2015
Regulator	NIST (USA)	FSB of Russia

The secret of the S-boxes and differential cryptanalysis

In 1990, cryptographers Eli Biham and Adi Shamir published differential cryptanalysis, a powerful attack on block ciphers. The community was stunned: DES’s S-boxes turned out to already be remarkably resistant to exactly this attack.

The explanation came later: according to IBM engineer Don Coppersmith, IBM’s team had known about differential cryptanalysis since the early 1970s and deliberately designed DES’s S-boxes to resist it — but at the NSA’s request kept it secret for nearly two decades.

The end of DES: cracked by brute force

A 56-bit DES key has about 7×10¹⁶ possible values — plenty in 1977. By 1998 the Electronic Frontier Foundation had built a dedicated machine, "Deep Crack," costing about $250,000, that found a key by brute force in roughly 56 hours.

That publicly proved 56 bits was no longer enough. The stopgap was 3DES (DES applied three times), followed in 2001 by AES, chosen through an open international competition.

Blowfish and Twofish

Open, patent-free alternatives to DES, designed by Bruce Schneier in the 1990s

Camellia

A joint development by Japanese companies, an international ISO/IEC standard, used in TLS

KASUMI

A Feistel network at the core of the 3G/UMTS confidentiality algorithms

Interesting facts

The original Lucifer used a 128-bit key; the NSA insisted on shrinking it to 56 bits before DES was adopted
DES remained the official US standard for over 20 years, until AES replaced it in 2001
The S-boxes of the original GOST 28147-89 weren’t part of the public standard — different agencies could set their own
AES and "Kuznyechik" are not Feistel networks — they are substitution-permutation networks (SP-networks)
Decryption in a Feistel network uses the exact same scheme as encryption — just with the subkeys in reverse order

A philosophical note: The Feistel network is a rare case where a simple structural idea turned out to be more powerful than complex mathematics. Over half a century it has outlived entire eras — from mechanical cipher machines to the dawn of post-quantum cryptography — and it’s still used wherever a time-tested construction is needed.

Now you understand why the function F doesn’t have to be invertible, and how that one idea grew into DES, Magma, and dozens of other ciphers

🚀 Launch the Feistel network demo ← Back to the topic list

In the demo you’ll walk a single byte all the way from plaintext to ciphertext and back — and see exactly why this structure works