Tutorial 2.5: Data Encryption Standard (DES) and Triple DES

Learning Objectives

After completing this tutorial, you should be able to:

• Describe the historical context and development of the Data Encryption Standard (DES).
• Explain the Feistel network structure of DES and the role of each component: initial/final permutation, round function, key schedule, and S-boxes.
• Analyze the security of DES in terms of its 56-bit key, brute-force resistance, and vulnerability to cryptanalytic attacks (differential and linear).
• Identify weak and semi-weak keys and the complementation property of DES.
• Compare different variants of Triple DES (2-key vs 3-key) and explain their effective key lengths and security.
• Evaluate the reasons for the deprecation of DES and the transition to AES.
• Apply knowledge of DES to understand real-world cryptographic standards and their evolution.
• Assess the impact of the DES cracker and the importance of key length in encryption.

Overview

The Data Encryption Standard (DES) is one of the most historically significant cryptographic algorithms. Developed in the 1970s and adopted as a federal standard in 1977, DES was the first publicly available encryption standard and became the de facto standard for commercial and government encryption for nearly two decades. Its design introduced the Feistel network to the wider cryptographic community and set the stage for modern block cipher design.

Despite its eventual replacement by the Advanced Encryption Standard (AES), DES remains important for several reasons: it provides a clear example of a Feistel cipher; its cryptanalysis (differential and linear) advanced the field significantly; and its successor, Triple DES, is still in use in legacy systems. Understanding DES gives you a concrete understanding of how symmetric block ciphers are constructed and analyzed.

In this tutorial, we dissect DES in detail: from its historical origins and design principles to its internal structure—the initial permutation, the 16 Feistel rounds, the key schedule, and the S-boxes. We then examine its security, including the 56-bit key space, weak keys, and known attacks. Finally, we discuss Triple DES (3DES), which extended DES's life by increasing the key length, and the reasons for its eventual deprecation.

Relationship to the Tutorial Series

In Tutorial 2.4, we introduced symmetric encryption fundamentals, including the Feistel structure. This tutorial brings that structure to life with a specific algorithm. Tutorial 2.6 will cover AES, the successor to DES, allowing you to compare the two important standards. Understanding DES also provides context for block cipher modes (Tutorial 2.7) and key management (Tutorial 2.8).

History of DES

Origins and Adoption

In 1973, the U.S. National Bureau of Standards (NBS, now NIST) issued a public call for an encryption algorithm to serve as a national standard. IBM submitted a cipher called Lucifer, designed by Horst Feistel. After modifications by IBM and the National Security Agency (NSA), the algorithm was adopted as the Data Encryption Standard in 1977 (FIPS 46). The modifications included a reduction in key size from 128 bits to 56 bits (to fit on a single chip) and changes to the S-boxes.

Controversy: The NSA's involvement in the design of the S-boxes raised concerns of a "trapdoor" that would allow the NSA to decrypt messages. These suspicions were later allayed when researchers discovered that the S-boxes were specifically designed to resist differential cryptanalysis—a technique that was not publicly known at the time but was apparently known to the NSA/IBM team. This illustrates the principle of designing ciphers to resist future attacks.

DES was the first commercial-grade cipher to be standardized and was widely adopted in banking, finance, and government (for unclassified data). In 1998, FIPS 46-3 reaffirmed DES, but also specified Triple DES (3DES) as a stronger alternative.

Designers and Key Personnel

• Horst Feistel – Developed the Feistel network architecture at IBM.
• Don Coppersmith – One of the IBM team members who worked on DES and later published research on its design criteria.
• NSA – Provided guidance on S-box design and reduced the key size.

DES Overview

DES operates on 64-bit blocks of plaintext, producing 64-bit ciphertext blocks under the control of a 56-bit key. The algorithm consists of an initial permutation (IP), 16 rounds of a Feistel network, and a final inverse permutation (IP⁻¹). The key is used to derive 16 round keys, one for each round.

Figure 1: Overall DES encryption process.

The Feistel Structure of DES

As described in Tutorial 2.4, a Feistel cipher splits the block into two halves (L and R) and applies the round function to one half, XORing the result with the other half. DES follows this structure precisely.

After the initial permutation, the 64-bit block is split into a 32-bit left half (L₀) and a 32-bit right half (R₀). For each of the 16 rounds, the following operations are performed:

Li = Ri−1
Ri = Li−1 ⊕ F(Ri−1, Ki)

where K_i is the 48-bit round key for round i, and F is the round function (described below). After the 16th round, the final swap is performed (L₁₆ and R₁₆ are not swapped; they are passed as is to the inverse permutation).

Figure 2: One round of DES (round i).

Key Schedule

The DES key schedule takes the 64-bit key (including 8 parity bits) and generates 16 round keys, each of 48 bits. The steps are:

1. Parity drop (PC-1): Remove the 8 parity bits from positions 8, 16, ..., 64, producing a 56-bit key. Also permutes the remaining bits.
2. Split the 56 bits into two 28-bit halves, C₀ and D₀.
3. For round i = 1 to 16:
   • Perform a left circular shift on C_i−1 and D_i−1 by 1 or 2 positions (depending on the round; rounds 1,2,9,16 use 1 shift; others use 2).
   • Combine C_i and D_i to form a 56-bit block.
   • Apply a compression permutation (PC-2) to select 48 bits for round key K_i.

The PC-1 and PC-2 tables are fixed and standardized. The shift schedule is:

The Round Function (F)

The round function F takes a 32-bit input (the right half R) and a 48-bit round key K, and produces a 32-bit output. It consists of four steps:

1. Expansion (E-box): The 32-bit R is expanded to 48 bits by duplicating some bits according to a fixed expansion table. This makes the output depend on a wider set of input bits and also matches the key size.
2. XOR with round key: The 48-bit expanded block is XORed with the 48-bit round key K_i.
3. S-box substitution: The 48-bit result is divided into eight 6-bit chunks. Each 6-bit chunk is fed into a corresponding S-box (S1 through S8), which outputs 4 bits. Each S-box is a 4×16 table (row and column) mapping 6-bit input to 4-bit output. This is the only non-linear step in DES and provides confusion.
4. Permutation (P-box): The resulting 32 bits (8×4) are permuted according to a fixed permutation table, spreading the output bits.

The output of the P-box is the output of F, which is then XORed with the left half.

S-boxes and Their Significance

The S-boxes are the heart of DES's security. They are the only non-linear component, providing confusion. Each S-box is a lookup table with 4 rows (2 bits) and 16 columns (4 bits). The 6-bit input selects a row (using the first and last bits) and a column (using the middle four bits), and the output is the 4-bit value at that cell.

For example, S1 is defined as:

Properties of DES S-boxes:

• Each S-box is non-linear.
• They were designed to resist differential cryptanalysis (minimizing the maximum difference probability).
• They are balanced (each output value appears roughly equally often).
• Changing one input bit generally changes several output bits.

Decryption

Because DES uses a Feistel network, decryption uses the same algorithm as encryption, but with the round keys applied in reverse order. That is, to decrypt a ciphertext block, one applies the same 16 rounds with keys K₁₆, K₁₅, ..., K₁ (the inverse of the key schedule). The initial and final permutations are also applied (they are inverses of each other).

This property simplifies implementation—the same hardware/software can be used for both encryption and decryption by reversing the key schedule.

Security Analysis of DES

Brute-Force Attack (Key Space)

The primary weakness of DES is its short key length: 56 bits. This gives a key space of 2⁵⁶ ≈ 7.2×10¹⁶ keys. In 1998, the Electronic Frontier Foundation (EFF) built a custom machine, "Deep Crack," that could break DES in about 56 hours, costing around $250,000. Today, with FPGA and GPU clusters, a DES key can be broken in seconds or minutes.

Brute-force feasibility over time:

Cryptanalytic Attacks

• Differential Cryptanalysis: Discovered in the 1990s (Biham and Shamir). Uses chosen plaintext differences to find key bits. DES's S-boxes were designed to resist this; the attack requires 2⁴⁷ chosen plaintexts, which is impractical.
• Linear Cryptanalysis: Developed by Matsui in 1993. Uses linear approximations to derive key bits. For DES, it requires 2⁴³ known plaintexts, which is feasible in some scenarios. Matsui broke DES in 1993 using this method with 2⁴³ known plaintexts on a computer.
• Complementation Property: If C = E_K(P), then E_K̄(P̄) = C̄ (where K̄, P̄, C̄ are bitwise complements). This reduces the effective key space by half for a brute-force attack using chosen plaintext.

Weak and Semi-Weak Keys

Due to the key schedule, certain keys lead to weak encryption. These include:

• Weak keys: Keys that are their own inverse (i.e., E_K(E_K(P)) = P). There are 4 such keys. They cause the round keys to be identical (all rounds use the same subkey), which greatly weakens the cipher.
• Semi-weak keys: Pairs of keys where each encrypts what the other decrypts (K₁ and K₂ such that E_K1(E_K2(P)) = P). There are 12 such key pairs.

These keys are a minor issue; modern implementations avoid them by checking and rejecting them, but they illustrate the importance of key schedule design.

Triple DES (3DES)

To extend the life of DES while mitigating its key-size weakness, Triple DES (3DES) was introduced. It applies DES three times with either two or three independent keys.

2-Key 3DES (3DES with K1, K2)

The standard mode is EDE (Encrypt-Decrypt-Encrypt):

C = EK1(DK2(EK1(P)))
P = DK1(EK2(DK1(C)))

Using decryption in the middle is a historical artifact that allows compatibility with single DES (if K1 = K2, then it reverts to DES).

Effective key length: With two keys, the effective key length is 112 bits (2×56). This is because the meet-in-the-middle attack reduces the security to about 2¹¹² operations, which is still infeasible. However, there are better attacks (e.g., 2⁸⁰ with known plaintext) that slightly reduce security, but 3DES with 2 keys is still considered secure for many applications.

3-Key 3DES (3DES with K1, K2, K3)

C = EK3(DK2(EK1(P)))

Effective key length is 168 bits (3×56). Provides a high margin of security.

Security of 3DES

• Meet-in-the-Middle: For 2-key 3DES, the meet-in-the-middle attack reduces the key space to O(2¹¹²), which is still infeasible.
• Block size: 3DES still uses a 64-bit block. This makes it vulnerable to birthday attacks in certain modes (e.g., CBC) when encrypting more than 2³² blocks (~32 GB). For large data, this is a concern.
• Performance: 3DES is much slower than AES (about 3 times slower than DES, which itself is slower than AES).

Current Status

NIST has deprecated 3DES for new applications (SP 800-131A, 2015). It is being phased out in favor of AES. The 64-bit block size and the availability of more efficient and secure algorithms make 3DES obsolete.

Current Status and Deprecation

DES is no longer considered secure for new applications. The small key size makes it vulnerable to brute-force attacks, and the cryptanalytic attacks (linear and differential) are practical. NIST officially withdrew FIPS 46-3 (DES) in 2005. Triple DES was allowed for legacy systems but is now deprecated; NIST SP 800-131A (2015) disallows 3DES for new cryptographic use after 2023.

For modern symmetric encryption, AES (Advanced Encryption Standard) is the recommended algorithm. AES offers 128, 192, or 256-bit keys, a 128-bit block, and is significantly more efficient in both hardware and software.

Case Study: The EFF DES Cracker

In 1998, the Electronic Frontier Foundation (EFF) built a machine called "Deep Crack" to demonstrate the vulnerability of DES. The machine consisted of 1,856 custom ASICs, each capable of searching 25 million keys per second. The total cost was about $250,000. It could find a DES key in about 56 hours on average, using a known plaintext-ciphertext pair.

The project successfully broke a DES-encrypted message that was part of a public challenge (the "DES Challenge") within 56 hours. This demonstrated that DES was no longer secure against determined adversaries with moderate resources. It accelerated the adoption of Triple DES and the subsequent AES competition.

Lessons:

• Key length must be sufficient to resist brute-force attacks with foreseeable technology.
• Cryptographic standards must evolve with technological advances.
• Public challenges can help validate the security of algorithms.

Key Takeaways

Section Summaries

• History: DES was the first public encryption standard, developed by IBM with NSA input, adopted in 1977. Its S-boxes were designed to resist differential cryptanalysis.
• Structure: DES is a 16-round Feistel cipher with a 64-bit block and a 56-bit key. It uses initial and final permutations, a key schedule that produces 48-bit round keys, and a round function consisting of expansion, XOR, S-boxes, and permutation.
• Security: The 56-bit key is too short; brute-force attacks are feasible. Differential and linear cryptanalysis are theoretical but practical with sufficient data. Weak keys and the complementation property are minor weaknesses.
• Triple DES: 3DES applies DES three times (EDE) with two or three keys, increasing effective key length to 112 or 168 bits. It is secure but slow and has a 64-bit block limitation.
• Deprecation: Both DES and 3DES are deprecated. AES is the recommended symmetric cipher for modern applications.

Quiz

1. What is the effective key length of DES, and why is it considered insecure today?
Answer
DES has an effective key length of 56 bits. It is considered insecure because modern hardware can perform a brute-force search over 2⁵⁶ keys in a very short time (seconds to minutes), making it feasible for attackers.
2. What is the block size of DES, and how many rounds does it use?
Answer
DES uses a 64-bit block and performs 16 rounds of encryption.
3. Explain the role of the S-boxes in DES and why they are essential for security.
Answer
The S-boxes are the only non-linear component of DES. They provide confusion by mapping 6-bit inputs to 4-bit outputs in a non-linear way, making it difficult to express the cipher as a linear system. Without them, DES would be easily broken using linear algebra.
4. What is the complementation property of DES, and how does it affect brute-force attacks?
Answer
If C = E_K(P), then E_K̄(P̄) = C̄ (complementing all bits). This property can reduce the effective key space by a factor of 2 in a chosen-plaintext attack because an attacker can test two keys at once by complementing the plaintext and ciphertext.
5. What is the difference between 2-key and 3-key Triple DES?
Answer
2-key 3DES uses two independent keys (K1 and K2) in an EDE pattern, giving an effective key length of 112 bits. 3-key 3DES uses three independent keys (K1, K2, K3), giving an effective key length of 168 bits. The former is less secure but still adequate for many legacy applications; the latter provides a higher security margin.
6. What is the main vulnerability of 3DES that led to its deprecation?
Answer
3DES still uses a 64-bit block, making it vulnerable to birthday attacks when encrypting large amounts of data (more than about 2³² blocks). Additionally, it is much slower than AES and offers no advantage over modern ciphers.
7. How does the key schedule of DES generate round keys?
Answer
The 56-bit key is split into two 28-bit halves. For each round, the halves are left-shifted by 1 or 2 bits (depending on the round), and then a compression permutation (PC-2) selects 48 bits to form the round key. This process is repeated for 16 rounds.
8. What is a weak key in DES, and how many exist?
Answer
A weak key is one where encryption is its own inverse (i.e., E_K(E_K(P)) = P). There are 4 weak keys in DES. They cause all round keys to be identical, drastically weakening the cipher.
9. What is the avalanche effect in the context of DES?
Answer
The avalanche effect is the property that a small change in the plaintext or key results in a large change in the ciphertext. DES exhibits good avalanche effect: changing one bit of plaintext typically changes about half the ciphertext bits after several rounds.
10. Why was the NSA's involvement in DES design controversial?
Answer
The NSA contributed to the S-box design and reduced the key size from 128 bits to 56 bits. Many suspected that the NSA might have inserted a backdoor or deliberately weakened the cipher. Later research showed that the S-boxes were designed to resist differential cryptanalysis, but the key size reduction was indeed a security concern.

Exercises

1. Key Size Comparison

   Compare the number of possible keys for DES (56-bit), 2-key 3DES (112-bit), and 3-key 3DES (168-bit). How many times larger is the 3-key 3DES key space compared to DES?

Sample Solution

DES: 2⁵⁶ ≈ 7.2×10¹⁶ keys.

2-key 3DES: 2¹¹² ≈ 5.2×10³³ keys.

3-key 3DES: 2¹⁶⁸ ≈ 3.7×10⁵⁰ keys.

Ratio (3-key vs DES): 2¹⁶⁸ / 2⁵⁶ = 2¹¹² ≈ 5.2×10³³ times larger.

2. Feistel Round Calculation

   In a simplified Feistel cipher with a 16-bit block (split into L and R of 8 bits), suppose L₀ = 0xAB, R₀ = 0xCD, and the round function F(R, K) = R ⊕ K. If K₁ = 0x5, compute L₁ and R₁.

Sample Solution

L₁ = R₀ = 0xCD.

R₁ = L₀ ⊕ F(R₀, K₁) = 0xAB ⊕ (0xCD ⊕ 0x05) = 0xAB ⊕ 0xC8 = 0x63.

So L₁ = 0xCD, R₁ = 0x63.

3. Understanding S-boxes

   Using the S1 table provided in the tutorial, determine the 4-bit output for the following 6-bit inputs: (a) 001011, (b) 111100, (c) 100101.

Sample Solution

For each 6-bit input, the first and last bits form the row (2 bits), and the middle four bits form the column.

(a) 001011: bits = 0 0 1 0 1 1 → row = 01 (binary) = 1, column = 0101 = 5. From S1 row 1, col 5 = 2 (binary 0010).

(b) 111100: row = 10 (2), col = 1110 (14). Row 2, col 14 = 5 (0101).

(c) 100101: row = 11 (3), col = 0010 (2). Row 3, col 2 = 8 (1000).

4. Weak Key Analysis

   If a DES key is weak, the round keys are all identical. How does this affect the security of the cipher? Explain why such keys should be avoided.

Sample Solution

When all round keys are identical, the Feistel rounds do not provide the intended variability. The cipher reduces to a simple substitution-permutation network with the same key each round, which can be broken much more easily. In particular, the effective key space shrinks to one key (or a few). Such keys must be avoided by implementations, typically by checking and rejecting weak keys during key setup.

5. Meet-in-the-Middle Attack on 2-key 3DES

   Explain the concept of a meet-in-the-middle attack on 2-key 3DES. What is the effective key space reduction achieved by this attack?

Sample Answer

In 2-key 3DES (EDE with keys K1 and K2), the meet-in-the-middle attack works by storing intermediate values from the first encryption (E_K1) and then matching them with the decryption of the ciphertext (D_K2) to find the pair of keys. The complexity is O(2⁵⁶) time and O(2⁵⁶) memory, which is less than the 2¹¹² brute force. Thus, the effective security is about 112 bits (since the attack requires about 2⁵⁶ operations, not 2¹¹²). However, this is still infeasible with current technology.

Homework

1. Research: Differential and Linear Cryptanalysis

   Write a 600-word report on differential and linear cryptanalysis. Focus on how they were applied to DES, including the approximate complexity of the attacks and why DES was designed to resist them. Discuss the historical significance of these attacks.

Sample Answer

Complete answer would include: Differential cryptanalysis (Biham and Shamir, 1990) uses chosen plaintext pairs with a fixed difference; it requires 2⁴⁷ chosen plaintexts for DES. Linear cryptanalysis (Matsui, 1993) uses known plaintext linear approximations; it requires 2⁴³ known plaintexts and was the first practical attack on DES. The S-boxes were designed to minimize these vulnerabilities (high non-linearity and low differential probability). The attacks showed that DES was not broken, but its margins were thin, encouraging the move to AES.

2. Compare DES and AES

   Create a table comparing DES and AES across the following dimensions: key size, block size, number of rounds, structure (Feistel vs SPN), S-box properties, and current security status. Write a summary of the key advantages of AES over DES.

Sample Answer

Table:

Feature	DES	AES
Key size	56 bits	128, 192, 256 bits
Block size	64 bits	128 bits
Rounds	16	10, 12, 14 (based on key size)
Structure	Feistel	SPN
S-box	8 S-boxes (6×4)	1 S-box (8×8) with algebraic structure
Security	Insecure; deprecated	Secure; current standard

Advantages: Larger key and block sizes, more efficient in software/hardware, stronger resistance to cryptanalysis, and simpler implementation in some aspects.

3. Analyze the DES Key Schedule

   If the DES key schedule used a fixed shift of 1 bit per round instead of the variable shifts, how would that affect the distribution of round keys and the security of the cipher?

Sample Answer

Fixed 1-bit shifts would cause the round keys to be more regular; in particular, the same key bits would appear in multiple round keys with predictable patterns, potentially making the cipher vulnerable to related-key attacks. The variable shifts were designed to ensure that all key bits are used in every round and that the round keys are as independent as possible.

4. Security of 3DES

   Why is 3DES still considered secure for legacy applications despite its 64-bit block size? What are the primary risks of using 3DES for new systems?

Sample Answer

3DES is secure against brute-force attacks due to its 112-bit or 168-bit effective key length. However, the 64-bit block size leads to birthday collisions after about 2³² blocks, which is a concern when encrypting large volumes of data (e.g., >32 GB). For new systems, AES provides better security, performance, and larger block size, making 3DES unnecessary and riskier.

5. Mini-Project: Implement DES (optional)

   Implement DES encryption and decryption in your preferred language (or a simplified version). Test it with a known test vector (e.g., from NIST). Submit a report with your code, test results, and observations about performance and implementation complexity.

Sample Answer

Provide a high-level description of a successful implementation, perhaps using a library or custom code. Report that the implementation passed known test vectors, and discuss the complexity of managing bit-level permutations and S-box tables. Observations might include the importance of correct table values and the relatively slow performance compared to AES.

Summary

This tutorial provided a comprehensive examination of the Data Encryption Standard (DES) and its successor, Triple DES. We traced the history of DES from its development at IBM and adoption by NIST to its eventual replacement by AES. We dissected the DES algorithm in detail, examining its Feistel structure, key schedule, and round function, with special emphasis on the S-boxes that provide non-linearity.

We analyzed DES's security, highlighting the 56-bit key as its primary weakness, and discussed cryptanalytic attacks (differential and linear) that, while not practical for breaking DES, demonstrate its design strengths. We also reviewed weak keys and the complementation property.

Triple DES (3DES) was introduced as a stopgap to extend DES's life by increasing key length. We covered the 2-key and 3-key variants, their effective key lengths, and the meet-in-the-middle attack. We also discussed the limitations of 3DES, including its 64-bit block size and performance overhead, leading to its deprecation.

The case study of the EFF DES cracker illustrated the practical vulnerability of DES to brute-force attacks and underscored the importance of adequate key length in cryptographic design. The lessons learned from DES and 3DES have informed the design of modern ciphers like AES.

Connection to the Next Tutorial

In Tutorial 2.6: Advanced Encryption Standard (AES), we will study the successor to DES—a modern block cipher that is now the global standard. AES builds on the principles we have covered: it is an SPN (not Feistel), with a larger block (128 bits) and key sizes up to 256 bits. Understanding DES will help you appreciate the design choices and improvements in AES.