08 — Symmetric
DES & Feistel Cipher
A Feistel network makes reversible encryption possible from any round function — even if F itself is not invertible.
Feistel structure
Split the block into halves L and R. Each round:
L_i = R_(i-1)
R_i = L_(i-1) ⊕ F(R_(i-1), K_i)
Theory — why decryption works (invertibility proof)
Given (L_i, R_i), recover the previous halves without inverting F:R_(i-1) = L_i # by first equation
L_(i-1) = R_i ⊕ F(R_(i-1), K_i)
= R_i ⊕ F(L_i, K_i) # substitute — F runs FORWARD
So the same circuit decrypts by feeding round keys in reverse K₁₆…K₁. F can be arbitrary (S-boxes, expansion) — reversibility comes from the XOR construction, not from F.DES description
- 64-bit block, 56-bit effective key (8 of 64 bits are parity), 16 rounds
- Initial Permutation IP — bit reorder (cosmetic; no security value)
- 16 Feistel rounds, final swap + IP⁻¹ → ciphertext
- 3DES fix:
C = E_K3(D_K2(E_K1(m)))(EDE, 112/168-bit effective)
Parity bits — which 8 are dropped?
Bits 8,16,24,32,40,48,56,64 (LSB of each key byte) are odd-parity, never enter PC-1. Example key 133457799BBCDFF1: byte 0x13=00010011 has three 1s (odd ✓), so bit 8 = 1 is parity. PC-1's 56 picks skip exactly these positions — that's why 64→56.F-function (per round)
Expansion E — 32-bit R → 48 bits (16 bits duplicated)
XOR with 48-bit subkey K_i
8 S-boxes — 6 bits → 4 bits each → 32 bits (the only non-linear step)
Permutation P — bit-shuffle for diffusion
S-box example (S1)
Input 6 bits 011011: outer bits 01=row 1, inner 1101=col 13. S1[1][13]=5 → output 0101. Each S-box is a different 4×16 lookup; this non-linearity is what breaks linear/differential attacks.# Expansion E (32→48): each output bit = input bit at listed position
32 1 2 3 4 5 | 4 5 6 7 8 9 | 8 9 10 11 12 13 | 12 13 14 15 16 17
16 17 18 19 20 21 | 20 21 22 23 24 25 | 24 25 26 27 28 29 | 28 29 30 31 32 1
# Permutation P (32-bit shuffle after S-boxes)
16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10
2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25
One Feistel round — diagram
One Feistel round: Lᵢ = Rᵢ₋₁, Rᵢ = Lᵢ₋₁ ⊕ F(Rᵢ₋₁, Kᵢ)
1st-round key generation — full math
Test key (64 bits, hex)
Key = 133457799BBCDFF1 (bits 8,16,24,…,64 are parity — discarded by PC-1)Step 1 · Key to binary
# 1 3 3 4 5 7 7 9 9 B B C D F F 1
0001 0011 0011 0100 0101 0111 0111 1001
1001 1011 1011 1100 1101 1111 1111 0001
Step 2 · PC-1 (64 → 56 bits) → C₀, D₀
C0 picks: 57 49 41 33 25 17 9 / 1 58 50 42 34 26 18 / 10 2 59 51 43 35 27 / 19 11 3 60 52 44 36
D0 picks: 63 55 47 39 31 23 15 / 7 62 54 46 38 30 22 / 14 6 61 53 45 37 29 / 21 13 5 28 20 12 4
Step 3-4 · C₀, D₀ values
C0 = 1111000 0110011 0010101 0101111 (28 bits)
D0 = 0101010 1011001 1001111 0001111 (28 bits)
Step 5 · Left shift by 1 (round-1 schedule)
C1 = 1110000 1100110 0101010 1011111 # drop leading 1, append
D1 = 1010101 0110011 0011110 0011110 # drop leading 0, append
Step 6-8 · PC-2 (56 → 48) → K₁
# PC-2 picks 48 of 56 bits (see FIPS table); assembling gives:
K1 (binary): 00011011 00000010 11101111 11111100 01110000 01110010
K1 (hex): 1B 02 EF FC 70 72 ✓ textbook vector
Shift schedule (all 16 rounds)
Rounds 1,2,9,16 → shift 1. Others → shift 2. Total = 4×1+12×2 = 28, so C₁₆=C₀ — decryption reuses the schedule in reverse.| Round | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Shift | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 1 |
| Cumul. | 1 | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 28 |
Deep-dive → 08B
PC-1 pick-by-pick (all 56 bits with values), C/D shifts for every round, and PC-2 pick-by-pick to K₁ are traced on 08B · DES Key Expansion Every Bit Traced.Encryption vector (preserved here)
Key 133457799BBCDFF1, plaintext 0123456789ABCDEF: IP gives L0=CC00CCFF R0=F0AAF0AA; Round 1: E(R0)=7A15557A1555 ⊕ K1 → 6117BAAB0A67, S1 011000→0101, f=234A5044, R1=EF4A9CBB L1=F0AAF0AA; after 16 rounds + IP⁻¹ → 85E813540F0AB405 ✓Why DES is dead
56-bit → 2⁵⁶ ≈ 7.2×10¹⁶. EFF Deep Crack (1998) brute-forced it in ~22h. Successor: AES.Exam one-liner: Feistel decrypts with reversed keys; DES = 16 Feistel rounds + broken 56-bit key (K₁=
1B02EFFC7072).