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:

and it is invertible:

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.“:

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:

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.