Thilan Dissanayaka Cryptography May 17, 2020

DES - The First Modern Cipher

If you are interested in cryptography, you must have heard about the AES algorithm. AES stands for Advanced Encryption Standard, and today it is one of the most widely used encryption algorithms. Before AES came into play, DES was the primary algorithm used for data encryption.

In this tutorial, we are going to study how DES works. After that, we can move on to AES and other modern algorithms. Understanding a cryptographic algorithm can be a bit challenging, so let’s start with the basics.

Feistel Cipher Networks

A Feistel cipher is a design model used to build block ciphers. It takes a plaintext block as input, processes it through several rounds, and produces a ciphertext block as output.

Let’s assume we have a plaintext of n bits. The first step is to divide it into two halves, each of n/2 bits (a Left half and a Right half).

Then, the data goes through a sequence of transformation rounds.

In each round, one half of the data is transformed using a round function, and then it is combined with the other half.

We will focus on encryption first.

Structure Overview

The input block size is n bits.
Both the left and right halves contain n/2 bits.
The algorithm runs for r rounds.

We use the following notation throughout the explanation:

Step numbers go from 0 to r. In step i, the left and right halves are denoted as L_i and R_i.

Also in each step we have to use a key. We denotes that as K_i

For example:

At the start, we have L₀ and R₀.
At round 7, we compute L₇ and R₇.
At the final round, we compute L_r and R_r.

What happens in a single round?

Let’s take a closer look at what happens in one round of a Feistel cipher. Assume we are currently at round i.

At the start of this round, we have:

Left half: L_i−1
Right half: R_i−1

In a Feistel cipher, the left part for the next round becomes just the previous right part:

L_i = R_(i-1)

That part is simple.

Building the New Right Part is somewhat complex.

The right part is computed using both halves of the previous step.

We take the right half R_i−1, pass it through a round function f, and XOR the result with the previous left half.

So:

R_i = L_(i-1) XOR f(R_(i-1), K_i)

It would be easy to understand this concept using a diagram. Refer to the bellow diagram.

Assume we at the step 1. We have L₀ and R₀ as the initial values. We are going to make L₁ and R₁ from those. The key, K₁ will be used for this.

L_1 = R_0
R_1 = L_0 XOR f(R_0, K_1)

I hope it is now clear. BTW, Lets consider the second round also. After the last round, we have L₁ and R₁.

Here we are going to get L₂ and R₂ from those values.

For this round we need a completly different key. That is kL₂

The same process is happening though the set of rounds. That means we need r number of unique keys for the r rounds.

In above we mentioned that we have r number of rounds right? Lets consider the last round. In that case i should be equal to r.

At the end or r number of rounds, we have L_r and R_r.

Our next task is to get the final outcome. That means the cipher text. For that we simply swap these last values.

L_(r+1) = R_(r)
R_(r+1) = L_(r)

This means:

The right output of the final round becomes the left half of the ciphertext. The left output of the final round becomes the right half of the ciphertext.

The pair (L_r+1, R_r+1) forms the final encrypted block.

How decryption happens?

In a Feistel cipher, encryption and decryption share the exact same structure. The only difference is that the round keys are applied in reverse order.

Suppose we have a ciphertext split into two halves,

L_r+1 R_r+1

These are the outputs after the final swap during encryption.

The first thing we do in the decryption process is undoing the Final Swap.

The first step of decryption is to swap the halves back.

R_r = L_(r+1) L_r = R_(r+1)

Now L_r and R_r correspond to the state at the end of the last encryption round, before the final swap.

After that we apply the Feistel Rounds in Reverse.

We now run the r rounds again, but using the round keys in reverse order: K_r, K_r−1, …, K₁.

For each round (from i = r down to 1):

Compute the new right half:

R_(i-1) = L_i XOR f(R_i, K_i)

Copy the current right half to the new left half:

L_(i-1) = R_i

Notice: These are the same equations as encryption, just with keys applied in reverse order. That’s why Feistel ciphers are symmetric.

Step 2: Repeat Until the First Round

After completing all rounds, you will have:

L₀

R₀

These are exactly the original plaintext halves.

Finally, combine L₀ and R₀ to recover the full plaintext block.

Summary

Encryption: Apply r rounds with keys K₁ -> K_r, then final swap.
Decryption: Undo final swap, then apply r rounds with keys K_r -> K₁.
The structure is identical; only the order of keys changes.

This is what makes Feistel ciphers so elegant. You don’t need to design two separate algorithms for encryption and decryption. The same circuit, the same code, the same hardware — just feed the keys in reverse. This property made Feistel networks the foundation for DES and many other block ciphers.

Now that we understand the Feistel structure, let’s see how DES implements it.

From Feistel Ciphers to DES

DES (Data Encryption Standard) is a specific implementation of a Feistel cipher. It was developed by IBM in the early 1970s, adopted as a US federal standard in 1977 (FIPS 46), and dominated cryptography for over two decades.

Here are its core properties:

Property	Value
Block size	64 bits
Key size	64 bits (but only 56 bits are used — 8 bits are parity)
Structure	Feistel network
Number of rounds	16
Type of cipher	Symmetric block cipher
Encryption & Decryption	Same process, reverse key order

DES takes a 64-bit plaintext block and a 64-bit key as input, and produces a 64-bit ciphertext block. The algorithm has three main phases:

Initial Permutation (IP) — Rearranges the bits of the plaintext
16 Feistel Rounds — The core encryption, using 16 different 48-bit subkeys
Final Permutation (FP) — The inverse of the initial permutation

Let’s walk through each phase.

Step 1: Initial Permutation (IP)

Before the Feistel rounds begin, DES rearranges the 64 input bits according to a fixed permutation table. Bit 58 of the input becomes bit 1 of the output, bit 50 becomes bit 2, and so on.

Initial Permutation Table (IP):
50 42 34 26 18 10  2
52 44 36 28 20 12  4
54 46 38 30 22 14  6
56 48 40 32 24 16  8
49 41 33 25 17  9  1
51 43 35 27 19 11  3
53 45 37 29 21 13  5
55 47 39 31 23 15  7

This means: take bit 58 of the original plaintext and put it in position 1. Take bit 50 and put it in position 2. And so on for all 64 bits.

Does this add any cryptographic strength? No. The initial permutation doesn’t make DES more secure — it was included for hardware implementation reasons in the 1970s. It made it easier to load data into the encryption chip one byte at a time. But it’s part of the standard, so every DES implementation includes it.

After the initial permutation, the 64-bit block is split into two 32-bit halves: L₀ (left) and R₀ (right). Now we’re ready for the 16 Feistel rounds.

Step 2: The 16 Feistel Rounds

This is the core of DES. Each round follows the exact Feistel structure we discussed earlier:

L_i = R_(i-1)
R_i = L_(i-1) XOR f(R_(i-1), K_i)

The magic is in the round function f. This is where all the cryptographic strength comes from. Let’s break it down step by step.

The Round Function f(R, K)

The round function takes the 32-bit right half and a 48-bit subkey, and produces a 32-bit output. It has four stages:

R (32 bits)
    |
    v
[Expansion (E)] ──> 48 bits
    |
    v
[XOR with subkey K_i] ──> 48 bits
    |
    v
[S-box substitution] ──> 32 bits
    |
    v
[Permutation (P)] ──> 32 bits
    |
    v
f(R, K) output

Stage 1: Expansion (E)

The right half is 32 bits, but the subkey is 48 bits. We can’t XOR values of different sizes. So first, we expand the 32-bit half to 48 bits using the expansion permutation table.

Expansion Table (E):
1  2  3  4  5
5  6  7  8  9
9 10 11 12 13
13 14 15 16 17
17 18 19 20 21
21 22 23 24 25
25 26 27 28 29
29 30 31 32  1

Notice that some bits appear twice — bits 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, and 32 are each used in two positions. This is intentional — it creates diffusion, meaning a change in one input bit affects multiple output bits. This is critical for security.

Stage 2: XOR with the Subkey

Now we have 48 bits from the expansion and a 48-bit subkey K_i. We simply XOR them together:

expanded_R XOR K_i = 48-bit result

This is where the key material is mixed into the data. Without this step, the cipher would be the same regardless of the key — and that’s obviously useless.

Stage 3: S-Box Substitution (The Heart of DES)

This is the most important part of DES. The 48-bit XOR result is divided into eight 6-bit groups, and each group is fed into one of eight S-boxes (Substitution boxes). Each S-box takes 6 bits in and produces 4 bits out.

48 bits = 6 bits × 8 groups

Group 1 → S-box 1 → 4 bits
Group 2 → S-box 2 → 4 bits
Group 3 → S-box 3 → 4 bits
Group 4 → S-box 4 → 4 bits
Group 5 → S-box 5 → 4 bits
Group 6 → S-box 6 → 4 bits
Group 7 → S-box 7 → 4 bits
Group 8 → S-box 8 → 4 bits

Total output: 4 × 8 = 32 bits

Each S-box is a lookup table with 4 rows and 16 columns. Here’s S-box 1:

S-box 1:
 1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
[ 14   4  13   1   2  15  11   8   3  10   6  12   5   9   0   7 ]
[  0  15   7   4  14   2  13   1  10   6  12  11   9   5   3   8 ]
[  4   1  14   8  13   6   2  11  15  12   9   7   3  10   5   0 ]
[ 15  12   8   2   4   9   1   7   5  11   3  14  10   0   6  13 ]

How to look up a value: take the 6 input bits b1 b2 b3 b4 b5 b6.

Row = b1 b6 (the first and last bits, forming a 2-bit number: 0-3)
Column = b2 b3 b4 b5 (the middle four bits, forming a 4-bit number: 0-15)

For example, if the 6-bit input is 101101:

Row = b1 b6 = 1 1 = row 3
Column = b2 b3 b4 b5 = 0110 = column 6
S-box 1, row 3, column 6 = 1
Output: 0001 (4 bits)

The S-boxes are the only nonlinear component in DES. Everything else — permutations, expansions, XORs — is linear. Without the S-boxes, DES could be broken with simple linear algebra. The S-boxes provide confusion — they make the relationship between the key and the ciphertext as complex as possible.

The specific values in the S-boxes were carefully chosen by IBM’s cryptographers (with input from the NSA). They were designed to resist differential cryptanalysis — an attack technique that wasn’t publicly known until 1990, but which the DES designers apparently knew about in the 1970s.

Stage 4: Permutation (P)

The 32-bit output from the S-boxes is rearranged using another fixed permutation:

P-box Permutation:
7 20 21
12 28 17
15 23 26
18 31 10
8 24 14
27  3  9
13 30  6
11  4 25

This spreads the output bits of each S-box across multiple S-box inputs in the next round. Combined with the expansion permutation, this ensures that after a few rounds, every bit of the plaintext and every bit of the key influence every bit of the ciphertext. This property is called the avalanche effect — change one input bit, and roughly half the output bits change.

The 32-bit P-box output is the final result of the round function f(R, K).

Step 3: Final Permutation (FP)

After all 16 rounds, the left and right halves are swapped (as in any Feistel cipher), and then the 64-bit block goes through the Final Permutation — which is simply the inverse of the Initial Permutation.

Final Permutation Table (FP = IP⁻¹):
8 48 16 56 24 64 32
7 47 15 55 23 63 31
6 46 14 54 22 62 30
5 45 13 53 21 61 29
4 44 12 52 20 60 28
3 43 11 51 19 59 27
2 42 10 50 18 58 26
1 41  9 49 17 57 25

The output of the final permutation is the 64-bit ciphertext.

Key Schedule — Generating 16 Subkeys

We’ve been using subkeys K₁ through K₁₆ in the 16 rounds, but the user only provides one 64-bit key. How do we generate 16 different 48-bit subkeys from it?

Step 1: Parity Drop (PC-1)

The 64-bit key has 8 parity bits (one per byte, used for error detection). The Permuted Choice 1 (PC-1) table removes these 8 bits, leaving 56 effective key bits.

PC-1 Table (64 bits → 56 bits):
49 41 33 25 17  9
58 50 42 34 26 18
2 59 51 43 35 27
11  3 60 52 44 36
55 47 39 31 23 15
62 54 46 38 30 22
6 61 53 45 37 29
13  5 28 20 12  4

Step 2: Split and Rotate

The 56-bit key is split into two 28-bit halves: C₀ (left) and D₀ (right).

For each round i (1 to 16), both halves are left-rotated by either 1 or 2 positions:

Round	Rotations
1, 2, 9, 16	1 position
All others	2 positions

After rotation, we have C_i and D_i.

Step 3: Compression (PC-2)

The two 28-bit halves are concatenated (56 bits) and passed through Permuted Choice 2 (PC-2), which selects 48 of the 56 bits to form the round subkey K_i.

PC-2 Table (56 bits → 48 bits):
17 11 24  1  5
28 15  6 21 10
19 12  4 26  8
7 27 20 13  2
52 31 37 47 55
40 51 45 33 48
49 39 56 34 53
42 50 36 29 32

This process repeats for all 16 rounds, producing 16 unique 48-bit subkeys.

For decryption, the same 16 subkeys are generated but applied in reverse order: K₁₆ first, K₁ last. This is the Feistel property in action.

The Complete DES Picture

Putting it all together:

Plaintext (64 bits)
      |
      v
[Initial Permutation (IP)]
      |
      v
Split into L₀ (32 bits) and R₀ (32 bits)
      |
      v
┌─── Round 1 ──────────────────────┐
│  L₁ = R₀                         │
│  R₁ = L₀ XOR f(R₀, K₁)          │
│       f = Expand → XOR K → S-box → P-box  │
└───────────────────────────────────┘
      |
      v
┌─── Round 2 ──────────────────────┐
│  L₂ = R₁                         │
│  R₂ = L₁ XOR f(R₁, K₂)          │
└───────────────────────────────────┘
      |
      v
      ... (rounds 3 through 15) ...
      |
      v
┌─── Round 16 ─────────────────────┐
│  L₁₆ = R₁₅                       │
│  R₁₆ = L₁₅ XOR f(R₁₅, K₁₆)      │
└───────────────────────────────────┘
      |
      v
[Final Swap: R₁₆ || L₁₆]
      |
      v
[Final Permutation (FP = IP⁻¹)]
      |
      v
Ciphertext (64 bits)

Why DES is No Longer Secure

DES served the world well for over 20 years, but it has a fatal flaw: the 56-bit key is too short.

In 1977, 2⁵⁶ possible keys (about 72 quadrillion) seemed unbreakable. But computing power grows exponentially.

1997 — The DESCHALL Project brute-forced a DES key in 96 days using thousands of volunteered computers
1998 — The EFF built “Deep Crack,” a custom hardware machine that cracked DES in 56 hours for about $250,000
1999 — Deep Crack combined with distributed.net cracked DES in 22 hours

Today, DES can be brute-forced in hours or even minutes with modern hardware. A key space of 2⁵⁶ is simply too small.

Beyond brute force, DES is also vulnerable to:

Differential cryptanalysis — Requires 2⁴⁷ chosen plaintexts (theoretically faster than brute force)
Linear cryptanalysis — Requires 2⁴³ known plaintexts (also faster than brute force)

These attacks are academic (they require impractical amounts of data), but they demonstrate that DES’s internal structure isn’t as strong as a modern cipher should be.

3DES — A Temporary Fix

When DES’s key length became a concern, the industry needed a quick fix. The solution was Triple DES (3DES) — applying DES three times with different keys:

Ciphertext = E_K3(D_K2(E_K1(Plaintext)))

Notice it’s Encrypt-Decrypt-Encrypt (EDE), not Encrypt-Encrypt-Encrypt. This was done for backward compatibility — if K1 = K2 = K3, 3DES reduces to single DES.

3DES with three independent keys (3TDEA):

Effective key length: 168 bits (3 x 56)
Much more secure than DES, but three times slower

3DES with two keys (2TDEA):

K1 = K3, K2 is different
Effective key length: 112 bits
Common in financial systems

3DES is still used today in payment systems and legacy infrastructure, but it’s being phased out. It’s slow (three DES operations per block) and its 64-bit block size creates vulnerabilities in protocols that encrypt large amounts of data (the Sweet32 attack).

The Road to AES

By the late 1990s, it was clear that DES and even 3DES wouldn’t be enough long-term. NIST (the US National Institute of Standards and Technology) launched a public competition in 1997 to find a replacement.

The requirements were:

128-bit block size (double DES’s 64 bits)
128, 192, and 256-bit key sizes
Efficient in both hardware and software
Royalty-free, publicly available

After three years of analysis, the winner was announced in 2000: Rijndael, designed by Belgian cryptographers Joan Daemen and Vincent Rijmen. It was standardized as AES (Advanced Encryption Standard) in 2001.

AES is not a Feistel cipher. It uses a substitution-permutation network (SPN) — a different design that applies substitution and permutation to the entire block in each round, rather than splitting it in half. We’ll explore AES in depth in the next article.

Final Thoughts

DES is a beautiful piece of cryptographic engineering. It took the theoretical Feistel structure and turned it into a practical, standardized algorithm that protected data for decades. The S-boxes, the key schedule, the permutations — every piece was carefully designed to maximize security within the constraints of 1970s hardware.

But DES also teaches us an important lesson: security is not permanent. An algorithm that was unbreakable in 1977 became a weekend project by 1999. The 56-bit key that seemed impossibly large became trivially small. This is why modern algorithms use 128-bit or 256-bit keys — they’re designed to remain secure even as computing power grows exponentially.

If you want to understand modern cryptography, DES is the foundation. The concepts here — Feistel networks, S-boxes, key schedules, diffusion, confusion — appear in every block cipher that followed. Master these, and AES will make much more sense.

Thanks for reading!