# Block Cipher

## Block Cipher

Such as 3DES, and AES. The idea is to use PRG to expand the k, and encrypt the message m in various rounds to get encrypted c.

### PRP and PRF

The pseudo random function PRF is defined: $F: K \times X \to Y$ The pseudo random permutation is defined: $F: K \times X \to X$ PRP also requires the E is one-to-one, and exists efficient inversion algorithm D.

The PRF is secure if it non-distinguishable from a true random function.

## Data Encryption Standard(DES)

Based on the Feistel Network: Given arbitrary functions, $f_1, ..., f_d: \{0, 1\}^n \to \{0, 1\}^n$, the forward functions are:

$\begin{equation} \begin{cases} R_{i+1} = f_{i+1}(R_i) \oplus L_i \\ L_{i+1} = R_i \end{cases} \end{equation}$

$\begin{equation} \begin{cases} R_{i} = L_{i+1} \\ L_{i} = f_{i+1}(L_{i+1}) \oplus R_{i+1} \end{cases} \end{equation}$

The $f1, ... f_{16}$ has to be secure PRF, with independent keys to get secure DES.

DO NOT use linear function for S-box, otherwise, DES becomes linear, too.

The weakness of DES is the key is only 56bit.

• COPACOBANA takes 7 days with 10K\$, 120 FPGA to crack in 2006.

## Triple-DES

Define 3E: $K^3 \times M \to M$ as:

$3E((k_1, k_2, k_3), m) = E(k_1, D(k2, E(k3, m)))$

It use E, D, E thus 3DES is degrades to DES if $k_1 = k_2 = k_3$ for backward compatibility.

What is the problem of double DES?

$E(k_2, m) = D(k_1, c)$

We can use “meet-in-the-middle attack.“:

1. Build a table for all $2^{56}$ entries, and sort on the second column.
2. For all $2^{56}$ possible $k_1$ to decrypt the $c$, and lookup the table.

The time complexity is the $n\log{n} + n\log{n} < 2^{63}$.

## DESX

Define EX:

$EX((k_1, k_2, k_3), m) = k_1 \oplus E(k_2, m\oplus k_3)$

The key-length is $64 + 56 + 64 = 184$ bits, but attack time is $2^{64+56} = 2^{120}$.

## Attacks on Block Ciphers

• Side channel attacks
• Fault attacks
• Linear and differential attacks

Give many $(m, c)$ pairs, if the subset of message bits xored compared with subset of ct bits xored, and show some linear relationship, $\epsilon$, for DES, a tiny bit of linearity is $S_5$ leads to: $\epsilon = \frac{1}{2^{21}}$ Roughly speaking: can find 14 key “bits” in time $2^{42}$.

We can then brutal force for 42 bits, and the total time is $2^{43}$.

Use subs-perm network:

The perm network MUST be invertible.

### AES-128

10 rounds, with 11 keys expanded from key(16 bytes -> 176 bytes.) Each round the input is hashed to 4x4 matrix, and use ByteSub, ShiftRow, MixColumn(except the last round), and output $\oplus$ with the round key.

The AES allows code size/performance trade-off.

Intel Westmere supports instructor, 14x speedup in OpenSSL.

• aesenc, aesenclast for AES round.
• aeskeygenassist perform AES key expansion.

Key Recovery attack: 4x better than brutal force.

## Block Ciphers from PRGs

GGM PRF can recursively invoke the PRG to extend 1-bit PRG. With Luby-Rackoff theorem: PRG -> GGM PRF -> PRP, aka block cipher

It is considerably slow as each round only generate 1-bit!

Block cipher is essentially a PRP. It is regarded as secure if the PRF is secure. A concrete example about AES: $Adv_{PRP}[A, AES] < 2^{-40}$ Secure PRP is also a secure PRF if $|X|$ is sufficient large, with q-queries: $|Adv_{PRF}[A, E] - Adv_{PRP}[A, E]| < \frac{q^2}{2|X|}$

Electric Code Book, ECB encrypt the same message as same CT, which leaks the information to the adversary.

Semantic Security: the adversary should not distinguish two messages with same length encrypted by the cipher.

We can use AES to generate OTP for stream encryption.

## Use Block Cipher with many-time key

Chosen-plaintext attack(CPA) The adversary gains advantage 1 if he can detect the same message are encrypted to the same PT, that breaks the semantic security!

• Randomized encryption: add random bits, aka salt, to the message on the expense of longer CT size.
• nonce-based encryption: nonce is public, can use counter or random. The E and D include the nonce.

### Cipher Block Chaining(CBC)

CBC with random Initial Vector(IV). IV is the size the block. The output is fed into the next block.

The chosen-plain text attack against CBC is: $Adv_{CBA}[A, E_{CBC}] \leq 2 \cdot Adv_{PRP}[B, E] + \frac{2 q^2L^{2}}{|X|}$ CBC is only secure if $q^2L^2 \ll |X|$.

For AES, if the threshold is $\frac{1}{2^{32}}$, $|X| = 2^{128}$, then $qL < \sqrt{2^{128 - 32}} = 2^{48}$. So after $2^{48}$ AES blocks, MUST change key.

3DES: $qL < 2^{16}$.

### nonce-based CBC

The IV MUST be random to ensure CPA-secure!

Use key space $(k, k_1)$, nonce is not random, but unique. It is crucial to encrypt nonce with $k_1$, otherwise, CBC is not CBA-secure!

CBC use padding, for n byte pad, just use padding with byte n. The decryptor will remove last n byte. For no-padding, add a block with byte 16 .

## Randomized Counter Mode(CTR)

IV is a counter, the F is a secure PRF, — completely parallelizable.
The q-query adversary A attacking $E_{CTR}$: $Adv_{CPA}[A, E_{CTR}] \leq 2 \cdot Adv_{PRF}[B, F] + \frac{2 q^2L}{|X|}$ Better than CBC!