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.