28-03 — Symmetric Encryption: DES and AES

Phase: Cryptography | Subject: 28-03 Prerequisites: 28-02-classical-ciphers.md, 28-01-modular-arithmetic-review.md Next subject: 28-04-asymmetric-encryption.md

Learning Objectives

By the end of this subject, you will be able to:

1. Explain the Feistel network structure and how it enables encryption/decryption with the same hardware
2. Describe the DES algorithm: key schedule, S-box substitution, and permutation
3. Compare DES, Triple DES, and AES in terms of security and structure
4. Distinguish block cipher modes: ECB, CBC, CTR, and GCM
5. Understand the design principles behind AES (Rijndael)

Core Content

Block Ciphers vs Stream Ciphers

• Block cipher: encrypts fixed-size blocks (64 bits for DES, 128 bits for AES)
• Stream cipher: encrypts bit-by-bit or byte-by-byte (like a digital one-time pad)

Block ciphers are the workhorses of modern symmetric encryption.

Feistel Networks

A Feistel network is a structure that makes encryption and decryption nearly identical. Given a block split into two halves $(L, R)$:

Round $i$: $$L_{i+1} = R_i$$ $$R_{i+1} = L_i \oplus F(R_i, K_i)$$

where $F$ is the round function and $K_i$ is the round key.

Decryption: just reverse the order of round keys. The XOR property means: $$R_i = L_{i+1}$$ $$L_i = R_{i+1} \oplus F(L_{i+1}, K_i)$$

Key insight: $F$ does NOT need to be invertible. The Feistel structure handles invertibility.

DES (Data Encryption Standard)

Published 1977, DES dominated for 25+ years.

Parameters: - Block size: 64 bits - Key size: 56 bits (+ 8 parity bits = 64) - Rounds: 16 - Structure: Feistel network

DES round operations: 1. Expansion: 32-bit half-block expands to 48 bits 2. Key mixing: XOR with 48-bit round key 3. Substitution: 8 S-boxes, each maps 6 bits → 4 bits (nonlinear — crucial for security!) 4. Permutation: fixed P-box shuffles 32 bits

The S-boxes are the heart of DES security. They are carefully designed to be: - Nonlinear (resists linear cryptanalysis) - Not close to linear functions (resists differential cryptanalysis) - Each output bit depends on multiple input bits (avalanche effect)

⚠️ CRITICAL: The 56-bit key space ($2^{56} \approx 7.2 \times 10^{16}$) is now too small. DES can be brute-forced in under 24 hours with specialized hardware. This is why DES was deprecated.

DES key schedule: the 56-bit key is permuted and split into two 28-bit halves. Each round, the halves are rotated left by 1 or 2 bits, then 48 bits are selected via compression permutation.

Triple DES (3DES)

To extend DES security without a new cipher:

$$C = E_{K_3}(D_{K_2}(E_{K_1}(P)))$$

• 168 bits of key (three 56-bit keys)
• Using E-D-E mode enables backward compatibility with single DES ($K_1 = K_2 = K_3$)
• Effective security ~112 bits (due to meet-in-the-middle attack)
• Slower than AES, block size still 64 bits

AES (Advanced Encryption Standard)

Chosen in 2001 after a public competition. Rijndael (by Joan Daemen and Vincent Rijmen) was selected.

Parameters: - Block size: 128 bits - Key sizes: 128, 192, or 256 bits - Rounds: 10 (AES-128), 12 (AES-192), 14 (AES-256) - Structure: Substitution-Permutation Network (SPN), not Feistel

AES round operations (operating on a 4×4 byte state matrix):

The last round omits MixColumns (so encryption and decryption are not identical, unlike Feistel ciphers).

AES-128 key schedule: - 128-bit key → 11 round keys (one for initial AddRoundKey + 10 rounds) - Uses S-box, rotation, and round constants derived from $x^{i-1}$ in $\mathbb{F}_{2^8}$

Block Cipher Modes of Operation

⚠️ CRITICAL: ECB mode should NEVER be used for structured data. The famous "ECB penguin" shows why — the image outline remains visible because identical blocks encrypt identically.

CBC encryption: $$C_1 = E_K(P_1 \oplus IV)$$ $$C_i = E_K(P_i \oplus C_{i-1}), \quad i \geq 2$$

CTR encryption: $$C_i = P_i \oplus E_K(\text{counter} + i)$$

CTR is widely preferred for its simplicity and parallelism.

Key Terms

• Feistel Network — round structure where $F$ need not be invertible
• DES — 56-bit key, 64-bit block, 16-round Feistel cipher
• S-box — nonlinear substitution, DES's primary source of security
• AES (Rijndael) — 128-bit block, SPN structure, 128/192/256-bit keys
• Substitution-Permutation Network (SPN) — AES's structural alternative to Feistel
• ECB Mode — insecure; identical plaintext blocks produce identical ciphertext
• CBC Mode — blocks chained; requires random IV
• CTR Mode — counter-based; parallelizable stream-cipher mode
• GCM — authenticated encryption mode (encryption + integrity)
• Meet-in-the-Middle Attack — attack on double/triple encryption trading time for space

Worked Examples

Example 1: Feistel Round

Given $L_0 = 1010_2$, $R_0 = 0110_2$, and round function $F(R, K) = R \oplus K$ with $K_1 = 0011_2$, compute $L_1, R_1$ and then decrypt.

Solution:

$L_1 = R_0 = 0110$ $R_1 = L_0 \oplus F(R_0, K_1) = 1010 \oplus (0110 \oplus 0011) = 1010 \oplus 0101 = 1111$

Decrypt: $R_0 = L_1 = 0110$, $L_0 = R_1 \oplus F(L_1, K_1) = 1111 \oplus (0110 \oplus 0011) = 1111 \oplus 0101 = 1010$. ✓

Example 2: ECB vs CBC

Encrypt "AB AB AB AB" (4 identical blocks) with a hypothetical block cipher. Show ECB and CBC output.

Solution:

ECB: $C = E_K(A) | E_K(A) | E_K(A) | E_K(A)$. Four identical ciphertext blocks! An observer knows the plaintext repeats.

CBC: $C_1 = E_K(A \oplus IV)$, $C_2 = E_K(A \oplus C_1)$, $C_3 = E_K(A \oplus C_2)$, $C_4 = E_K(A \oplus C_3)$. All four ciphertext blocks differ (with high probability), hiding the repetition.

Example 3: AES S-box in $\mathbb{F}_{2^8}$

The AES S-box computes $y = A(x^{-1}) + b$ in $\mathbb{F}_{2^8}$, where $x^{-1}$ is the multiplicative inverse (with $0^{-1} = 0$), $A$ is an affine transformation, and $b$ is the constant $0x63$. For input $0x53$:

Solution:

In $\mathbb{F}_{2^8}$ with irreducible polynomial $m(x) = x^8 + x^4 + x^3 + x + 1$: $0x53$ corresponds to polynomial $x^6 + x^4 + x + 1$.

Use Extended Euclidean in $\mathbb{F}_{2^8}$: inverse of $x^6 + x^4 + x + 1$ mod $m(x)$ is $x^7 + x^6 + x^3 + x$ ($0xCA$).

Apply affine transform $A$ (matrix multiplication + $0x63$): result is $0xED$.

So S-box$(0x53) = 0xED$.

Quiz

Q1: What does the concept of Feistel network primarily refer to in this subject?

A) A historical anecdote about Feistel network B) A visual representation of Feistel network C) A computational error related to Feistel network D) The definition and application of Feistel network

Correct: D)

• If you chose A: This is incorrect. Feistel network is defined as: the definition and application of feistel network. The other options describe different aspects that are not the primary focus.
• If you chose B: This is incorrect. Feistel network is defined as: the definition and application of feistel network. The other options describe different aspects that are not the primary focus.
• If you chose C: This is incorrect. Feistel network is defined as: the definition and application of feistel network. The other options describe different aspects that are not the primary focus.
• If you chose D: Feistel network is defined as: the definition and application of feistel network. The other options describe different aspects that are not the primary focus. Correct!

Q2: Which of the following is the key formula discussed in this subject?

A) A simplified version of L_{i+1} = R_i... B) The inverse operation of the formula in question C) An unrelated formula from a different topic D) L_{i+1} = R_i

Correct: D)

• If you chose A: This is incorrect. The formula L_{i+1} = R_i is central to this subject. The other options are either simplified versions or unrelated.
• If you chose B: This is incorrect. The formula L_{i+1} = R_i is central to this subject. The other options are either simplified versions or unrelated.
• If you chose C: This is incorrect. The formula L_{i+1} = R_i is central to this subject. The other options are either simplified versions or unrelated.
• If you chose D: The formula L_{i+1} = R_i is central to this subject. The other options are either simplified versions or unrelated. Correct!

Q3: What is the primary purpose of AES round operations?

A) It is primarily a historical notation system B) It is used only in advanced research contexts C) It replaces all other methods in this domain D) It is used to aes round operations in mathematical analysis

Correct: D)

• If you chose A: This is incorrect. AES round operations serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose B: This is incorrect. AES round operations serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose C: This is incorrect. AES round operations serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose D: AES round operations serves the purpose described in the correct answer. The other options misrepresent its role. Correct!

Q4: Which statement about The last round omits MixColumns is TRUE?

A) The last round omits MixColumns is an advanced topic beyond this subject's scope B) The last round omits MixColumns is a fundamental concept covered in this subject C) The last round omits MixColumns is mentioned only as a historical footnote D) The last round omits MixColumns is not related to this subject

Correct: B)

• If you chose A: This is incorrect. The last round omits MixColumns is a fundamental concept covered in this subject. This subject covers The last round omits MixColumns as part of its core content.
• If you chose B: The last round omits MixColumns is a fundamental concept covered in this subject. This subject covers The last round omits MixColumns as part of its core content. Correct!
• If you chose C: This is incorrect. The last round omits MixColumns is a fundamental concept covered in this subject. This subject covers The last round omits MixColumns as part of its core content.
• If you chose D: This is incorrect. The last round omits MixColumns is a fundamental concept covered in this subject. This subject covers The last round omits MixColumns as part of its core content.

Q5: Based on the worked examples in this subject, what is the correct result?

A) The inverse of the correct answer B) ECB vs CBC C) An unrelated numerical value D) A different result from a common mistake

Correct: B)

• If you chose A: This is incorrect. The worked examples show that the result is ECB vs CBC. The other options represent common errors.
• If you chose B: The worked examples show that the result is ECB vs CBC. The other options represent common errors. Correct!
• If you chose C: This is incorrect. The worked examples show that the result is ECB vs CBC. The other options represent common errors.
• If you chose D: This is incorrect. The worked examples show that the result is ECB vs CBC. The other options represent common errors.

Q6: How are The last round omits MixColumns and INSECURE related?

A) The last round omits MixColumns is the inverse of INSECURE B) The last round omits MixColumns is a special case of INSECURE C) The last round omits MixColumns and INSECURE are closely related concepts D) The last round omits MixColumns and INSECURE are completely unrelated topics

Correct: C)

• If you chose A: This is incorrect. Both The last round omits MixColumns and INSECURE are covered in this subject as interconnected topics.
• If you chose B: This is incorrect. Both The last round omits MixColumns and INSECURE are covered in this subject as interconnected topics.
• If you chose C: Both The last round omits MixColumns and INSECURE are covered in this subject as interconnected topics. Correct!
• If you chose D: This is incorrect. Both The last round omits MixColumns and INSECURE are covered in this subject as interconnected topics.

Q7: What is a common pitfall when working with S-box?

A) The main error with S-box is using it when it is not needed B) A common mistake is confusing S-box with a similar concept C) S-box is always computed the same way in all contexts D) S-box has no common misconceptions

Correct: B)

• If you chose A: This is incorrect. Students often confuse S-box with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose B: Students often confuse S-box with similar-sounding or related concepts. Pay attention to the precise definitions. Correct!
• If you chose C: This is incorrect. Students often confuse S-box with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose D: This is incorrect. Students often confuse S-box with similar-sounding or related concepts. Pay attention to the precise definitions.

Q8: When should you apply AES (Rijndael)?

A) Apply AES (Rijndael) to solve problems in this subject's domain B) Use AES (Rijndael) only in pure mathematics contexts C) AES (Rijndael) is not practically useful D) Avoid AES (Rijndael) unless explicitly instructed

Correct: A)

• If you chose A: AES (Rijndael) is a practical tool used throughout this subject to solve relevant problems. Correct!
• If you chose B: This is incorrect. AES (Rijndael) is a practical tool used throughout this subject to solve relevant problems.
• If you chose C: This is incorrect. AES (Rijndael) is a practical tool used throughout this subject to solve relevant problems.
• If you chose D: This is incorrect. AES (Rijndael) is a practical tool used throughout this subject to solve relevant problems.

Practice Problems

1. In a Feistel network, if $F$ is a constant function (always returns 0), what does encryption do?
   

   Click for answer

   $L_1 = R_0$, $R_1 = L_0 \oplus 0 = L_0$. After two rounds: $L_2 = L_0$, $R_2 = R_0$ — the original block! This demonstrates why the round function must be nontrivial.

2. How many possible DES keys are there? How long to brute force at $10^{12}$ keys/second?
   

   Click for answer

   $2^{56} \approx 7.2 \times 10^{16}$ keys. At $10^{12}$ keys/sec: $7.2 \times 10^{16} / 10^{12} = 72000$ seconds ≈ 20 hours. This is why DES is considered broken.

3. AES-256 uses how many rounds?
   

   Click for answer

   14 rounds (plus initial AddRoundKey). AES-128: 10 rounds. AES-192: 12 rounds. More rounds for longer keys.

4. Why does AES omit MixColumns in the last round?
   

   Click for answer

   It makes encryption and decryption symmetric (with different round keys in reverse order). Without this, decryption would need an additional step. It doesn't affect security since there's no next round to diffuse into.

5. In CBC mode, what happens if the IV is predictable?
   

   Click for answer

   If an attacker can predict the IV, they can potentially mount chosen-plaintext attacks. The BEAST attack on TLS 1.0 exploited predictable CBC IVs. IV must be unpredictable (random).

Summary

Key takeaways:

• Feistel networks enable encryption and decryption with the same circuit ($F$ need not be invertible)
• DES (56-bit key) is deprecated; brute force is practical with modern hardware
• AES uses an SPN structure (SubBytes, ShiftRows, MixColumns, AddRoundKey)
• Block cipher modes matter: ECB is dangerous; CBC, CTR, and GCM are standard
• AES-128 remains secure; AES-256 for high-security applications

Pitfalls

• Using ECB mode for structured data. ECB encrypts each block independently, so identical plaintext blocks produce identical ciphertext blocks. This leaks patterns (the "ECB penguin" is the classic demo). Use CBC, CTR, or GCM instead.
• Thinking DES has a 64-bit key. DES takes a 64-bit input, but 8 bits are parity (discarded). The effective key is only 56 bits — small enough to brute-force today. This is why DES was deprecated, not because of any mathematical flaw in the Feistel structure.
• Confusing Feistel networks with SPN structures. DES uses a Feistel network (half the block passes through unchanged each round; $F$ need not be invertible). AES uses a Substitution-Permutation Network (the entire state is transformed each round; each operation must be invertible).
• Assuming AES-256 is always better than AES-128. AES-256 has a weaker key schedule than AES-128 (related-key attacks exist against AES-256 that don't affect AES-128). For most applications, AES-128 is sufficient and arguably has a stronger security margin in its key schedule.
• Forgetting that CBC needs an unpredictable IV, not just a unique one. A predictable CBC IV enables chosen-plaintext attacks (e.g., the BEAST attack on TLS 1.0). The IV must be generated by a cryptographically secure random number generator.

Next Steps

Next up: 28-04-asymmetric-encryption.md — public-key cryptography and the RSA revolution.