Block Ciphers

Advanced Encryption Standard

• AES is an SPN where the permutation operation consists of two linear transformations.
• All operations are byte oriented.
• The block size is 128 bites
• Each round key is 128 bites
• A key schedule is used to generate the round keys
• AES accepts three different key lengths (128, 192, 256 bits)
• 128 bits -> 10 rounds
• 192 bits -> 12 rounds
• 256 bits -> 14 rounds

General Structure

• The substitution operation (S-Box) is the only non-linear component of the cipher.
• The permutation operations spread out the non-linearities in each round.

Round Operation

• Each round updates a variable called State which consists of a 4x4 array of bytes (4*4*8=128 bits)
• State is initialized with the 128-bit plaintext
• After h rounds are completed, one final additional round key is XORed with State to produce the ciphertext (key whitening)
• AES round function uses four operations:
• AddRoundKey (key mixing)



• SubBytes (S-Box)



• ShiftRows (permutation)



• MixColumns (matrix mult./linear transformation)

AES Encryption

• From the key k, derive h+1 round keys k₀, k₁, ..., k_h via the key schedule.
• Encryption function proceeds as:
  State ← plaintext
  for i = 1, 2, ..., h-1:
    State ← State ⊕ k_i-1
    State ← SubBytes(State)
    State ← ShiftRows(State)
    State ← MixColumns(State)
 State ← State ⊕ k_h-1
 State ← SubBytes(State)
 State ← ShiftRows(State)
 State ← State ⊕ k_h
 ciphertext ← State

Note: In the final round, MixColumns is not applied and XORed with k_h (key whitening).

AES Key Schedule (for 128-bit keys)

• For 128-bit keys, AES has ten rounds, so we need eleven subkeys (last one for key whitening).
• Each k_i is a 32-bit word
• Each group of 4 k_i's forms a 128-bit subkey.
• The first round subkey (k₀, k₁, k₂, k₃) equals the actual AES key.

• The function f_i:{0,1}³²→ {0,1}³² are defined as follow:
• Left Shift the input cyclically by 8 bits. (RotWord)
• Apply the AES S-box to each byte. (SubWord)
• Bitwise XOR the left-most byte with a constant (Rcon) which varies by round accodring to the following table:

Data Encryption Standard

The Data Encryption Standard (DES) is a symmetric-key block cipher published by the National Institute of Standards and Technology (NIST). DES was widely used in the 1970s and 1980s but has since been replaced by more secure algorithms like AES due to its shorter key length and vulnerability to brute-force attacks.

Structure of DES

Block cipher with 64-bit blocks, 56-bit key and 16 rounds:

Plaintext (64 bits)
→ Initial Permutation
→ Feistel Network (16 rounds) with 56-bit key from Key Schedule
→ Inverse of Initial Permutation
→ Ciphertext (64 bits)

Feistel Network

Components of a Feistel Cipher

• Parameters: n (half the block length), h (# of rounds), l (key size)
• C = M = {0,1}²ⁿ, K = {0,1}^l
• Key scheduling algorithm to determine subkeys from given key.
• Each subkey defines a component function F_i: {0,1}^l x {0,1}ⁿ → {0,1}ⁿ

Design of the Feistel Network

• Plaintext is divided into two halves (LE₀, RE₀)
• Key is used to generate subkeys k₁,k₂,...,k_h.
• F is a component function whose output is depending on RE_i and k_i.

Notes on Feistel Cipher

• No restrictions on F in order for the encryption to be invert.
• Underlying Principle: Take something 'simple' and use it several times; hope that the result is complicated.
• Implementation:
  • Encryption: One round implementation is enough. The same code can be used for each round.
  • Decryption: Use the same code as encryption.

DES Encryption and Decryption

Encryption (with h rounds):

• Plaintext m = (m₀, m₁) (= LE₀, RE₀)
• Round 1: (m₀, m₁) → (m₁, m₂); where m₂ = m₀ ⊕ F(k₁, m₁)
• Round 2: (m₁, m₂) → (m₂, m₃); where m₃ = m₁ ⊕ F(k₂, m₂)
• ...
• Round h: (m_h-1, m_h) → (m_h, m_h+1); where m_h+1 = m_h-1 ⊕ F(k_h, m_h)
• Ciphertext c = (m_h, m_h+1)

Decryption

• Given c = (m_h, m_h+1) and k:
  • m_h-1 = m_h+1 ⊕ F(k_h, m_h)
  • ...
  • m₀ = m₂ ⊕ F(k₁, m₁)
  • m = (m₀, m₁)

Structure of the Component Function

• E:{0,1}³² → {0,1}⁴⁸ is an expansion table where it takes 32-bit block (m_i) and returns 48-bit word.
• The S-box S:{0,1}⁶ → {0,1}⁴ takes 6-bit word and returns 4-bit word.
• The permutation P:{0,1}³² → {0,1}³² is then applied at the end and returns the output F(m_i).

DES S-box

• S-boxes are only non-linear component in DES.
• Without S-box, changing one plaintext bit would change very few ciphertext bits.
• Security of DES crucially depends on their choice.
• DES with randomly selected S-boxes is easy to break.

Problems in DES

1. Small key size

• Exclusive key search: 2⁵⁶

2. Small block size

• If plaintext blocks are distributed "uniformly at random", then the expected number of ciphertext blocks observed before a collision occurs is about 2³² (by Birthday paradox)
• Small block length is also damaging to some authentication applications.

Attacks on DES

• Differential Cryptanalysis [Biham & Shamir 1989]:
  • Recovers key given 2⁴⁷ chosen plaintext/ciphertext pairs.
  • DES was designed to resist this attack
  • Differential cryptanalysis has been more efficient on some other block ciphers.
• Linear Cryptanalysis [Matsui 1993]:
  • Recovers key given 2⁴³ chosen plaintext/ciphertext pairs.
  • Storing these key pairs takes 131,000 GB.
  • Implemented in 1993: 10 days on 12 machines.

Improved DES

1. Mitigating Short Keys: encrypt multiple times

• Multiple Encryption:
  • Re-encrypt the ciphertext one or more times using independent keys, and hope that this increases the effective key length.
• Multiple encryption does not always increase security.
  • Think of E_π the simple substitution cipher with key π and consider E_π1 ∘ E_π2.

2. Double Encryption (Double-DES)

• Double-DES; key k = (k₁, k₂) for k₁, k₂ ∈ {0,1}⁵⁶
  • Encryption: c = E_k2(E_k1(m))
  • Decryption: m = E_k1^-1(E_k2^-1(c))
• Key size l = 112
• Block length is unchanged.
2.1 Attack on Double-DES (Main Idea: If c = E_k2(E_k1(m)), then E_k2^-1(c) = E_k1(m))
• Given: konwn plaintext/ciphertext pairs (m_i, c_i) for i = 1, 2, ...
• For each h₂ ∈ {0,1}⁵⁶:
  • Compute E_h2^-1(c) and store [E_h2^-1(c), h₂] in a table.
• For each h₁ ∈ {0,1}⁵⁶:
  • Compute E_h1(m₁)
  • Search for E_h1(m₁) in the table.
  • If E_h1(m₁) = E_h2^-1(c):
    • Check E_h1(m_i) = E_h2^-1(c_i) for all i ≥ 2.
• The complexity is about 2⁵⁷ ≈ 2⁵⁶ + 2⁵⁶ + 2·2⁴⁸.
• Space requirements: 2⁵⁶(64+56) bits ≈ 1,080,863 Tbytes.

3. Triple-DES

• Triple-DES; key k = (k₁, k₂) for k₁, k₂ ∈ {0,1}⁵⁶
  • Encryption: c = E_k3(E_k2(E_k1(m))
  • Decryption: m = E_k1^-1(E_k2^-1(E_k3^-1(c))
• Key size l = 168
3.1 Notes on Triple-DES
• MITM attack takes about 2¹¹² operations.
• Hence the effective key length against key search is ≤ 112 bits.
• No proof that Triple-DES is more secure than DES.
• Block length is still 64 bits, and now forms the weak link:
  • Adversary stores a large table (of size ≤ 2⁶⁴) of (m, c) pairs. (Dictionary Attack)
  • To prevent this attack, change secret keys frequently.
• Triple-DES is widely deployted today.
• Some variants of Triple-DES includes: EDE Triple-DES, Two-key (EDE) Triple-DES, etc.