Block Ciphers and DES

A block cipher operates on a fixed-length block of plaintext $m$ of $n$ bits, mapping it to a ciphertext block $c$ of the same length under a secret key $k$, both drawn from $\{0,1\}^n$.

For a fixed key $k$, the encryption function $e_k$ is a bijection on $\{0,1\}^n$, so it is invertible via $d_k$.

Block Cipher as a PRP

A block cipher’s key design objective is to behave like a family of pseudorandom permutations (PRP) indexed by $k$.

Large messages are divided into blocks and encrypted independently per block:

Per Kerckhoffs’s principle, $e$ and $d$ are public. Only $k$ is secret.

Attacking a Block Cipher

• Ciphertext only
  Attacker has only $c$ and searches the key space exhaustively for a $k$ giving a meaningful $d_k(c)$. Requires $|K| > 2^{64}$ to make this infeasible.
• Chosen plaintext (IND-CPA)
  Attacker submits chosen plaintexts to an encryption oracle and must not be able to distinguish encryptions of chosen messages better than a coin toss.
• Chosen ciphertext (IND-CCA)
  Attacker has access to an encryption oracle, a decryption oracle (except for the challenge ciphertext), and a left-right oracle producing $c^* = e_k(m_b)$ for $b \in \{0,1\}$. Wins by guessing $b$. A secure scheme limits this to probability 0.5.

A block cipher is only a building block. The specific design combining a block cipher into a usable encryption scheme is its mode of operation.

Iterated Block Cipher Design

Security comes from repeated application of a round function to the block, over $r$ rounds. Increasing $r$ increases security up to a stable level.

Feistel Cipher

Named after Horst Feistel. Splits the plaintext block into halves $(L_0, R_0)$ and iterates a round function $F$, keyed by $k_i$, over $r$ rounds, swapping the final halves to produce the ciphertext.

Each encryption round:

Each decryption round, using the round keys in reverse order:

Design parameters of a Feistel cipher:

• Block length $n$.
• Number of rounds $r$.
• Definition of the round function $F$.
• Key schedule generating each round key $k_i$ from $k$.
• Length of the secret key $k$.

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.

Double and Triple DES

• 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 of DES

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}$).

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).
• 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.

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$.
• 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$.
• Permuted Choice 2 (PC-2)
  Rejoins $C_i, D_i$ into 56 bits, drops 8 fixed bit positions, and permutes the remaining 48 bits to produce round key $k_i$.