This is a note of week 2 of the Coursera course Cryptography I.

1 What are Block Ciphers?

A block cipher uses k-bit keys to encrypt an n-bit input block and generate an n-bit output block. It often works in iterations with n rounds using a round function R(k, m). The original k is expanded in n rounds to generte k1, k2, …, kr working as the first input of R in each round. Therefore a block cipher is defined by the key expansioin function and the round function.

Abstractly, a Pseudo Random Function (PRF) defined over (K, X, Y): F: K * X -> Y such that exists an efficient algorithm to evaluate F(k, x).

One of PRF special case is Pseudo Random Permutation(PRP), also called block cipher, defined over (K, X): E: K * X -> X such that:

  • Exists efficient deterministic algorithm to evaluate E(k, x)
  • The function E(k, x) is one to one
  • Exists efficient inversion algorithm D(k, y).

Examples PRPs are 3DES defined over K = X = {0, 1}^128 and AES defined over X = {0, 1}^64, K = {0, 1}^168.

Let F: K * X -> Y be a PRF and Funs[X, Y] be the set of all functions from X to Y, then the size of Funs[X, Y] is |Y| ^ |X|. Let S = {F(k, _) s.t. k in K} that is a subset of Funs[X, Y]. The size of S is the size of K. Intuitively, a PRF is secure if a random function in Funs is indistinguishable from a random function in S.

An easy application is to generate a secure PRG from a secure PRF. Let F: K * {0, 1}^n -> {0, 1}^n be a secure PRF, then the following G: K -> {0, 1}^(n*t) is a secure PRG: G(k) = F(k, 0) || F (k, 1) || ... || F(k, t). The intuition is that if we use a truely random function F(x), then the output of F(0) || F(1) || ... || F(t) is indistinguishable from the PRF F(k, _).

2 The DES

Givne functions f1, f2, ..., fd: {0, 1}^n -> {0, 1}^n, the goal is to build invertible Feistel network functions F: {0, 1}^(2n) -> {0, 1}^(2n). The inputs are n-bit R0 and n-bit L0, then for each i=1, ..., d, we have Ri = f(Ri-1) XOR Li and Li = Ri-1. The inversion is basically the same circuit with f1, f2, ..., fd applied in reverse order. Feistel network is used in many block ciphers but not AES.

Luby-Rackoff proved in 1985 that if f is a secure PRF, then 3-round Fiestel network of f using 3 independent keys is a secure PRP.

DES uses a 16-round Feistel network. Each f function is defined as fi(x) = F(ki, x) wheree ki is a random key used in round i. The input is 64 bit data (splitted into two 32-bit) and a random key is 48 bit.

First, the 32-bit data goes through an expansion function that generates 48-bit data. It just replicates some bits. Then find the XOR of the 48-bit data and 48-bit key. The result 48-bit is divided into eight 6-bit groups. Then apply an S function (called S-box) to each group to get eight 4-bit outputs that are combined into a 32-bit result. The 32-bit is transformed again using function P to get 32-bit function output.

The S function is defined in a lookup table that avoids a linear transformation because if S-box is linear, then the cipher would be linear. The XOR and bit permutation are linear functions. Both S and P function should not be linear to make DES secure. A tiny bit of linearly in S5 leads to a 2^42 time attack.

DES is not secure, then we have 3DES that is safe and fast enough.

There are also side channel (time, power, cache) attacks and fault attacks. Don’t design ciphers yourself.

There is also a quantum attack. If a classical computer takes O(|X|) to run, a quantum computer takes O(|X|^0.5). It means a quantum computer can find a key in O(|K|^0.5). For 56-bit DES, it is 2^28, for AES-128, it is 2^64, for AES-256, it is 2^128. Only the last one is secure even for quantum computers.