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.