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.

Block cipher diagram
Block cipher diagram


The pseudo random function PRF is defined: F:K×XYF: K \times X \to Y The pseudo random permutation is defined: F:K×XXF: 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, f1,...,fd:{0,1}n{0,1}nf_1, ..., f_d: \{0, 1\}^n \to \{0, 1\}^n, the forward functions are:

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

DES diagram
DES diagram
and it is invertible:

{Ri=Li+1Li=fi+1(Li+1)Ri+1\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}

Inverse DES diagram
Inverse DES diagram

The f1,...f16f1, ... 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.


Define 3E: K3×MMK^3 \times M \to M as:

3E((k1,k2,k3),m)=E(k1,D(k2,E(k3,m)))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 k1=k2=k3k_1 = k_2 = k_3 for backward compatibility.

What is the problem of double DES?

E(k2,m)=D(k1,c)E(k_2, m) = D(k_1, c)

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

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

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


Define EX:

EX((k1,k2,k3),m)=k1E(k2,mk3)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=18464 + 56 + 64 = 184 bits, but attack time is 264+56=21202^{64+56} = 2^{120}.

Attacks on Block Ciphers

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

Give many (m,c)(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 S5S_5 leads to: ϵ=1221\epsilon = \frac{1}{2^{21}} Roughly speaking: can find 14 key “bits” in time 2422^{42}.

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

Advanced Encrypt Standard(AES)

Use subs-perm network:

AES Diagram
AES Diagram

The perm network MUST be invertible.


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: AdvPRP[A,AES]<240Adv_{PRP}[A, AES] < 2^{-40} Secure PRP is also a secure PRF if X|X| is sufficient large, with q-queries: AdvPRF[A,E]AdvPRP[A,E]<q22X|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.

CBC Diagram
CBC Diagram

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

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

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

nonce-based CBC

The IV MUST be random to ensure CPA-secure!

Nonce based CBC diagram
Nonce based CBC diagram

Use key space (k,k1)(k, k_1), nonce is not random, but unique. It is crucial to encrypt nonce with k1k_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)

CTR based CBC diagram
CTR based CBC diagram

IV is a counter, the F is a secure PRF, — completely parallelizable.

The q-query adversary A attacking ECTRE_{CTR}: AdvCPA[A,ECTR]2AdvPRF[B,F]+2q2LXAdv_{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.