Cryptography for the Everyday Developer: Understanding DES - The Data Encryption Standard

This is an article in a series on Cryptography for the Everyday Developer. Follow along to learn the basics of modern cryptography and encryption.

The Data Encryption Standard (DES) is based upon the principles of a substitution-permutation network that we learned about in the last post in this series. The design of DES is based on the principles of Feistel ciphers, which are a particular configuration of a substitution-permutation network developed by Horst Feistel at IBM.

Since Feistel networks are foundational to DES (alongside other encryption algorithms), let’s start there.

How Feistel Networks Work

A Feistel network works by applying an encryption function across a number of rounds. The encryption function takes two inputs: a data block and a key. It returns one output: a data block the same size as the input data block. In each round, the data block is split into equal halves, and the encryption function is run on half of the data to be encrypted. The output is then XORed with the other half of the data. The halves are then swapped, and the operation is repeated. Finally, the two data halves are merged to form the final encrypted output block.

The following diagram from Wikipedia provides a simple visual representation of the encryption/decryption scheme:

In each round the substitution-permutation function \(F\) is applied to half of the data, then the result is XORed (\(\oplus\)) with the other half of the data. Subsequent rounds simply flip which half of data the encryption function \(F\) is applied to.

Overview of The DES Algorithm

DES applies a Feistel network with a few standard parameters. In particular, it encrypts data blocks in sizes of 64 bits, with a key size of 64 bits (though effectively 56 bits, as we will see). Each round of the algorithm uses a unique round subkey that is derived for each round from the main encryption key. It runs for 16 rounds before outputting the final result.

Putting this together, the full DES algorithm can be described as follows, with some details to follow:

1. Apply an initial permutation (\(IP\)) to the 64-bit input block
2. Split the 64-bit block into two 32-bit halves, \(L\) and \(R\)
3. Set \(L\) to \(L \oplus F(R) \), where \(F\) is a substitution-permutation network round
4. Swap the values of \(L\) and \(R\)
5. Go to step 2 and repeat 15 times
6. Merge \(L\) and \(R\) to create the 64-bit output block
7. Apply final permutation (\(IP^{-1}\)) to get the final ciphertext

So far, we’ve understood the overall approach to encryption with DES, what’s left is to dive into what, exactly, happens during each step.

The DES Algorithm in Detail

Initial and Final Permutations (IP and IP⁻¹)

Before diving into the core encryption rounds, DES applies an initial permutation \(IP\) to rearrange the bits of the input block. This is a simple bit permutation where each bit position is moved to a different position according to a predefined table. For example:

• Bit position 1 is moved to bit position 40
• Bit position 2 is moved to bit position 8
• And so on…

After all 16 rounds are complete, DES applies the final permutation \(IP^{-1}\), which is simply the inverse of the initial permutation, undoing the bit rearrangement.

Interestingly, these permutations don’t add any cryptographic security to the algorithm. They were included in the original DES design primarily for hardware implementation reasons. In the 1970s, when DES was designed, these permutations made it easier to load data into 8-bit based hardware chips. They essentially acted as a buffer to help with the electrical engineering challenges of getting data into and out of the encryption chip and have stuck around as part of the DES standard since then.

The Round Function (F)

The heart of DES lies in its round function \(F\), which takes two inputs: a 32-bit data half (\(R_i\)) and a 48-bit round key (\(k_i\)). The function consists of four sequential steps:

1. Expansion (E-box)

The expansion step provides diffusion - one of the key principles of good encryption. The goal of diffusion is to spread the influence of each input bit across many output bits. In other words, if you change just one bit in the input, ideally about half of the output bits should change.

With DES, the algorithm takes the 32-bit input and expands it to 48 bits using a predefined expansion table.

32 bits → Expansion box → 48 bits

Here’s a simplified view of how an expansion might work:

Input positions:   1  2  3  4  5  6  7  8  9 10 11 12 ... 32
                   ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓
Output positions: 32  1  2  3  4  5  4  5  6  7  8  9 ... 31

Notice that some input bits are connected to multiple output bits, which is necessary to turn a 32 bit input into a 48 bit output. In our example, input bit 4 3 appears in output position 5 and 7, and input bit 5 appears in output positions 6 and 8. This spreading of input bits across different output positions ensures that if any input bit changes, the output changes in multiple places, helping to diffuse the effect of the change throughout the output. As the DES algorithm progresses, this expansion process happens each round, compounding the impact of diffusion across rounds.

2. XOR with Round Key

This step is straightforward - the 48-bit expanded data is XORed with the 48-bit round key. We will go into more details about the round key later in this post:

Expanded data ⊕ Round key = 48-bit result

3. Substitution (S-box)

The S-box substitution is the confusion part of DES and represents the most critical component of the algorithm. This is where the real cryptographic strength lies.

The 48-bit result from the XOR operation is divided into eight 6-bit chunks, and each chunk is processed through its own substitution box (S-box). Each S-box takes 6 bits as input, and outputs 4 bits. The input to output mapping is done using a simple lookup table with 64 entries.

The lookup table is arranged in 4 rows of 16 columns, the S-box looks up entries in this table using the 6 bit chunks of input to choose an entry. The first and last bits choose one of 4 possible rows, and the middle 4 bites select one of 16 possible columns.

Input: 1 0 1 0 1 1
       ↑ ─ ─ ─ ─ ↑
       │         │
    First bit  Last bit
       │         │
       └─────────┘
       These select the ROW

       1 0 1 0 1 1
         ↑ ↑ ↑ ↑
         │ │ │ │
         └─┴─┴─┘
    These 4 middle bits select the COLUMN

For example, if the input is 101011 (decimal 37):

• Outer bits: 11 (binary) → row 3 (decimal)
• Middle bits: 0101 (binary) → column 5 (decimal)

We then get the entry in row 3, column 5 of the S-box table. For example, this is an actual S-box table from the DES algorithm.

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

Selecting row 3 and column 5 returns the value 9 (decimal), which results in the output 1001 (binary). Going through this transformation, we have substituted the input 101011 to get the output 1001.

4. Permutation (P-box)

The final step applies a permutation to the 32-bit output from the S-boxes. This permutation rearranges the bits according to a fixed permutation table, further contributing to diffusion by ensuring that the output of each S-box affects multiple bits in the next round.

The Key Schedule

Since DES runs for 16 rounds, we need to generate 16 different round keys from our original 64-bit encryption key. The key schedule algorithm works as follows:

Step 1: Permuted Choice 1 (PC-1)

The original 64-bit key is put through PC-1, which:

• Drops 8 bits (positions 8, 16, 24, 32, 40, 48, 56, 64)
• Rearranges the remaining 56 bits according to a permutation table
• Splits the result into two 28-bit halves (\(C_0\) and \(D_0\))

Because DES drops 8 bits from the 64-bit key, the effective strength of the algorithm is 56 bits, not 64.

Step 2: Left Rotation

For each round \(i\) (1 to 16), both 28-bit halves are rotated left by a specified number of positions:

• 1 position for rounds 1, 2, 9, and 16
• 2 positions for all other rounds (3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15)

Step 3: Permuted Choice 2 (PC-2)

The rotated 56-bit key \(C_1 + D_1\) is put through PC-2, which:

• Drops 8 more bits
• Permutes the remaining 48 bits
• Outputs the 48-bit round key \(k_i\)

Each round key is simply a permutation and selection of the original 56 bits. There’s no complex mathematical operation - just bit shifting and dropping, which makes it relatively easy to implement in hardware.

Decryption Process

One of the elegant features of Feistel ciphers is that decryption uses the same algorithm as encryption, just with the round keys applied in reverse order.

To decrypt a DES ciphertext:

1. Apply the initial permutation \(IP\)
2. Run 16 rounds of the Feistel network using round keys \(k_{16}\), \(k_{15}\), …, \(k_1\)
3. Apply the final permutation \(IP^{-1}\)

This works because the Feistel structure is inherently reversible. In round \(i\) of decryption, we’re undoing what was done in round \(17-i\) of encryption.

A Complete Example

Let’s again trace through the algorithm overview see how all the pieces fit together:

1. Input: 64-bit plaintext block
2. IP: Rearrange bits according to initial permutation table
3. Split: Divide into \(L_0\) (32 bits) and \(R_0\) (32 bits)
4. Round 1:
   • Generate \(k_1\) from the key schedule
   • Compute \(F(R_0, k_0)\) using expansion, XOR, S-boxes, and permutation
   • Set \(L_1 = R_0\) and \(R_1 = L_0 \oplus F(R_0, k_1)\)
5. Rounds 2-16: Repeat with appropriate round keys
6. Combine: Merge \(L_{16}\) and \(R_{16}\)
7. IP⁻¹: Apply final permutation to get ciphertext

Security Considerations and Why We Don’t Use DES Today

While DES was groundbreaking for its time, it’s no longer considered secure for modern applications. The primary weakness lies in its effective 56-bit key length, which is simply too short by today’s standards. With modern computing power, DES keys can be brute-forced in a matter of hours or days. This vulnerability was dramatically demonstrated in 1999 when a DES key was cracked in just 22 hours using specialized hardware.

Beyond brute force attacks, DES has proven vulnerable to sophisticated cryptanalytic techniques that weren’t fully understood when it was designed. Differential cryptanalysis exploits patterns in how input differences affect output differences, allowing attackers to recover keys faster than brute force. Similarly, linear cryptanalysis uses linear approximations to find correlations between plaintext, ciphertext, and key bits, providing another avenue for attack.

These vulnerabilities led to DES being replaced by the Advanced Encryption Standard (AES), which addresses DES’s shortcomings in several key ways. AES supports much larger key sizes of 128, 192, or 256 bits, making brute force attacks computationally infeasible. It also demonstrates better resistance to the known cryptanalytic attacks that can break DES, and provides more efficient implementation on modern hardware architectures.

Understanding DES provides valuable insight into the fundamentals of symmetric encryption. While we no longer use DES for securing sensitive data, its design principles - particularly the Feistel network structure and the balance between confusion and diffusion - continue to influence modern cryptographic algorithms.

The transition from DES to AES represents not just an increase in key size, but a fundamental evolution in cryptographic design philosophy. However, the lessons learned from DES’s strengths and weaknesses continue to inform how we build and evaluate encryption systems today.

In our next post, we’ll explore how these principles evolved into the Advanced Encryption Standard (AES), which forms the backbone of modern symmetric encryption.