DES

The Data Encryption Standard, published 1975, standardized 1977. Superseded by AES (1998/2001).

Design Parameters

• Block length $n = 64$ bits.
• Number of rounds $r = 16$.
• Round function combining substitution and permutation.
• 16 round keys of 48 bits each, from a subkey generation algorithm.
• Secret key length 56 bits.

Attacking DES

A brute-force known-plaintext attack averages $2^{55}$ steps given the 56-bit key.

Variations

Double DES

Encrypting twice with the same key ($c_2 = E_k(E_k(m))$) is broken by the meet-in-the-middle attack, which encrypts $m$ forward and decrypts $c_2$ backward over all keys, matching where results agree, in $2^{56}$ steps.

Double DES with 2 keys

$c_2 = E_{k_2}(E_{k_1}(m))$ gives an effective key length of 112 bits.

Triple DES (3DES)

$c = E_{k_3}(D_{k_2}(E_{k_1}(m)))$, effective key length 168 bits. Setting $k_1 = k_2 = k_3$ reduces it to plain DES.

2-key 3DES

Setting $k_1 = k_3$ gives $c = E_{k_1}(D_{k_2}(E_{k_1}(m)))$, effective key length 112 bits.

Internal Structure

1. Initial permutation (IP) of the 64-bit input block.
2. Split into left and right halves.
3. 16 Feistel rounds.
4. Rejoin the halves.
5. Final inverse permutation ($IP^{-1}$).

$IP$ shifts all even-positioned input bits to the left half and all odd-positioned bits to the right half.

58 50 42 34 26 18 10  2
60 52 44 36 28 20 12  4
62 54 46 38 30 22 14  6
64 56 48 40 32 24 16  8
57 49 41 33 25 17  9  1
59 51 43 35 27 19 11  3
61 53 45 37 29 21 13  5
63 55 47 39 31 23 15  7

$IP^{-1}$:

40  8 48 16 56 24 64 32
39  7 47 15 55 23 63 31
38  6 46 14 54 22 62 30
37  5 45 13 53 21 61 29
36  4 44 12 52 20 60 28
35  3 43 11 51 19 59 27
34  2 42 10 50 18 58 26
33  1 41  9 49 17 57 25

Round Function

Per round, the 32-bit right half is processed:

1. Expansion permutation $E$, 32 bits to 48 bits.
2. XOR with the 48-bit round key.
3. Split into 8 blocks of 6 bits.
4. Substitution via 8 S-boxes, each 6-bit input to a 4-bit output.
5. Combine the 8 outputs into 32 bits.
6. Permutation via the P-box.

• Expansion permutation
  Diffuses input bits. The first and last bits of each 6-bit S-box input select a row (of 4) in that S-box, and the middle 4 bits select a column (of 16).

  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

• Avalanche effect
  16 of the 32 input bits each affect both a row and column selection across 2 different S-boxes, spreading dependencies. A single plaintext bit difference should flip about 50% of ciphertext bits.

• S-boxes
  Provide the cipher’s non-linearity, the most security-critical component of DES.

• P-box
  Permutes the combined 32-bit S-box output, providing further diffusion of input bits among the output bits.

  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

Key Schedule

The 64-bit input key has every 8th bit as a parity bit, so the effective key length is 56 bits.

• Permuted Choice 1 (PC-1)
  Permutes the 56-bit key, splitting the result into two 28-bit halves $C_0, D_0$.

  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
  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

• Rotation
  Each round left-rotates $C_{i-1}$ and $D_{i-1}$ by $p_i$ positions (1 or 2, per a fixed schedule) to get $C_i, D_i$.

  $i$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
  $p_i$	1	1	2	2	2	2	2	2	1	2	2	2	2	2	2	1

• Permuted Choice 2 (PC-2)
  Rejoins $C_i, D_i$ into 56 bits, drops the 8 bits at positions 9, 18, 22, 25, 35, 38, 43, and 54, and permutes the remaining 48 bits to produce round key $k_i$.

  14 17 11 24  1  5
   3 28 15  6 21 10
  23 19 12  4 26  8
  16  7 27 20 13  2
  41 52 31 37 47 55
  30 40 51 45 33 48
  44 49 39 56 34 53
  46 42 50 36 29 32