# 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:

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:

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?

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

- Build a table for all $2^{56}$ entries, and sort on the second column.
- 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:

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}$.

## Advanced Encrypt Standard(AES)

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!

The block ciphers can be interpreted as PRP or PRF.