Mar 5 Block Ciphers & Modes of Operation

Design of Symmetric-key Ciphers: Confusion & Diffusion

Confusion
make the relation between the key, plaintext and ciphertext as complex as possible. Ideally, each digit of the key influences the correspondence between pxt and cxt letters in a non-predictable way

Ciphers that do not offer effective confusion are vulnerable to frequency analysis
Diffusion
Refers to the property that the statistical distribution of “groups of pxt letters” frequencies (due to the redundancy of the ptx language) should be dissipated, as much as possible, into flat distribution statistics, i.e. the ctx should appear as random data.

Diffusion spreads (diffuse) the influence of a single plaintext letter over many (or every) cxt letters

Ciphers suffering from poor diffusion can usually be broken by means of Known Plaintext Attacks (e.g., simple permutation ciphers)

Block Ciphers

Block ciphers operate on a block of plaintext m∈M (m = , with m_i∈{0, 1}), to produce a block of ciphertext (c = ∈ C, with c_i∈{0, 1}) through a key-parametric transformation (either E_k () or D_k ())

The block size n is in the [64, 256] bit range

ptx size might not be multiple a of block size → PADDING

For ptxs longer than a single block, the scheme used to apply E_k () (or D_k ()) is called mode of operation

Basic Terminologies

Cipher State: The result of each operation performed by the cipher (Initialized with the ptx; contains the ctx at the end of the computation)

Round: basic sequence of operations applied to the cipher state, a number of times (involves blending the key into the state)

Key Schedule: procedure expanding the original user key into key material to be used in each round

Modern Block Ciphers

Feistel Networks

Invented by Horst Feistel (in ’50-’60), it splits the cipher state in two parts and acts on one of them per round

A Feistel network transforms an n-bit ptx block m=, into an n-bit ctx block c= through an r-round process (r≥1); where the sub-blocks Li , Ri are n/2-bit long.
```
  Feistel(<L, R>, k)
      1 for i ← 0 to r − 1
      2   temp ← L
      3   L ← R
      4   R ← temp ⊕ F(ki, R) // Li = Ri−1, Ri = Li−1 ⊕ F(ki, Ri−1)
      5 R ← R ⊕ F(kr, L)
      6 return <R, L> // Note: the last round block halves are swapped
```
Properties

L_i = R_i-1, R_i = L_i-1 ⊕ F(k_i , R_i-1)

R_i-1 = L_i , L_i-1 = R_i ⊕ F(k_i, L_i)

Ciphers based on a Feistel Network

DES, Blowfish, Twofish, CAST5
DES

16-round Feistel cryptosystem with 64-bit wide cipher state

DES round: F(ki, Ri−1) = P-box(S-box(ki ⊕ E-box(Ri−1))
1. E-box(Ri−1) expands Ri−1 from 32 (4 8) into 48 (6 8) bits
2. Adds (XOR) the 48-bit round key ki
3. Map the 48-bit word into a 32-bit one via applying 8 fixed S-boxes. Each S-box map a 6 bit word to a 4 bit one
4. Apply a fixed bitwise permutation specified by the P-box
  
  Weak Keys: Encrypting a ptx twice with a weak key k, yields the original ptx. DES(k, DES(k, m)) = m, ∀ m ∈ M
  
  Semi-Weak Keys: Also a Semi-Weak key pair causes the composition of two DES encryptions employing k and k0 to compute the original ptx DES(k, DES(k 0, m)) = m, ∀ m ∈ M
  
  Not Closed: ∀m not exists k3 s.t. DES(k3, m) = DES(k2, DES(k1, m))
  
  The composition of two DES with distinct keys is still a permutation Sn, but in general it cannot be thought as computed by a DES with another key.
  
  DES in wiki
  
  DES support material)
2DES

Double DES cipher consists of applying the DES primitive twice: c = 2DES(k1, k2, m) def as DES(k1, DES(k2, m))
Triple DES/TDES

c = 3DES(k1, k2, k3, m) def as = DES(k1, DES−1 (k2, DES(k3, m)))

m = 3DES−1(k1, k2, k3, m) def. = DES−1(k3, DES(k2, DES−1(k1, c)))
Substitution Permutation Networks (SPNs)

The round of a SPN acts on the whole cipher state with:

A “non-linear” function providing Confusion represented as a lookup table, a.k.a.: Substitution-Box (S-box)

A “linear” function providing Diffusion, i.e., a bitwise permutation, or pairs of rotate & xor operations The addition of a part of the key schedule

Modes of Operation

A Mode of operation specifies the way to encrypt a message m∈M of arbitrary length through employing a block cipher

Currently, there are modes of operations to guarantee

Confidentiality of messages:

Electronic CodeBook mode (ECB)

Cipher Block Chaining mode (CBC)–most popular–not entirely secure

Output FeedBack mode (OFB)

Cipher FeedBack mode (CFB)

Counter mode (CTR)
Authentication of messages:
CMAC
Both confidentiality and authentication:
CCM and GCM

CBC

Encryption

c₀ = IV
c_i = E_k (m_i ⊕ c_i-1), for i ≥ 1

The Initialization Vector (IV) ensures that two encryptions of the same ptx produce different ctxs

Decryption

m_i = D_k (c_i) ⊕ c_i-1, for i ≥ 1

Stream Based Models

Given a plaintext message m∈M as a sequence of blocks m= the CFB, OFB and CTR modes of operation generate a key stream k1, k2, k3 . . . (each key has the size of a block) to mask the ptx m: ci = mi ⊕ ki , for i ≥ 1