Symmetric encryption: from Caesar to AES, modes of operation

Cryptography is the engine of network security. The goals of confidentiality, integrity and authentication all end up resting on an encryption, hash or signature operation. This week has two pages: on this page, symmetric encryption; on the next page, public key, hash functions, signatures and TLS. From this page the exam asks hand encryption (Caesar, Vigenère, XOR), mode traces and key-space calculations. Golden rules:

1. Symmetric = one shared key. The one who encrypts and the one who decrypts know the same key.
2. Convert letters to numbers, take mod 26. A = 0, B = 1, …, Z = 25.
3. XOR cancels itself. $P \oplus K \oplus K = P$.
4. Don’t use ECB. The same block gives the same output, and patterns leak.
5. Don’t reuse the key. In OTP and CTR the keystream is used once.

Basic concepts

The plaintext $P$ is turned into ciphertext $C$ by the encryption algorithm $E$ and key $K$: $C = E_K(P)$. Decryption: $P = D_K(C)$. In symmetric encryption both sides have the same $K$.

Kerckhoffs’s principle: the algorithm is not secret; all the security lies in the secrecy of the key. Security that relies on hiding the algorithm (security through obscurity) collapses at the first reverse engineering.

Depending on what the attacker has, the kinds of cryptanalysis are: ciphertext-only, known-plaintext, chosen-plaintext. The crudest attack is brute force: trying all the keys. For a $k$-bit key, the worst case is $2^k$ attempts and the average is $2^{k-1}$.

Classical ciphers

The Caesar (shift) cipher

Each letter is shifted $k$ steps in the alphabet:

$C = (P + k) \bmod 26 \qquad P = (C - k) \bmod 26$

Example: NETWORK, $k = 3$.

N(13)+3=16 Q   E(4)+3=7 H   T(19)+3=22 W   W(22)+3=25 Z
O(14)+3=17 R   R(17)+3=20 U   K(10)+3=13 N
NETWORK → QHWZRUN

There are only 25 meaningful keys; trying all of them takes seconds.

Monoalphabetic substitution and frequency analysis

If you map each letter to a random permutation of the alphabet, there are $26! \approx 4 \times 10^{26}$ keys. Brute force is impossible, but the cipher is still broken: letter frequencies in a language are stable (in English E, T, A are the most frequent). The most frequent letter in the ciphertext is most likely E. Lesson: a large key space alone does not mean security.

The Vigenère cipher

A keyword is repeated and each letter is shifted by the key letter beneath it. The same plaintext letter is encrypted differently in different positions, and the frequency distribution flattens.

Example: SECURE, key KEY (K = 10, E = 4, Y = 24).

plain    S(18) E(4)  C(2)  U(20) R(17) E(4)
key      K(10) E(4)  Y(24) K(10) E(4)  Y(24)
sum      28    8     26    30    21    28
mod 26   2     8     0     4     21    2
cipher   C     I     A     E     V     C

SECURE → CIAEVC. The two E letters came out differently (I and C). If the key length is found (from repeating patterns), the cipher is still broken by splitting it into Caesar pieces.

XOR and the one-time pad

On a computer we work with bits instead of letters. XOR ($\oplus$): 0 if the bits are the same, 1 if different.

P = 1011 0110
K = 0110 1101
C = 1101 1011      (P ⊕ K)
C ⊕ K = 1011 0110 = P

One-time pad (OTP): the key is completely random, as long as the message, and used once. Under these conditions it is theoretically unbreakable. In practice, distributing the key is very hard. If the key is used twice, $C_1 \oplus C_2 = P_1 \oplus P_2$ and security collapses.

Stream ciphers imitate the OTP: from a short key they produce a long pseudorandom keystream and XOR it with the plaintext.

Modern block ciphers: DES and AES

A block cipher turns a fixed-size block into another block by a key-dependent permutation. Over several rounds, substitution (confusion) and permutation (diffusion) are repeated. The goal: when a single bit of the plaintext or key changes, about half of the output changes (avalanche).

One round of AES has four steps: SubBytes (byte-by-byte substitution with an S-box), ShiftRows (shifting the rows), MixColumns (mixing the columns) and AddRoundKey (XOR with the round key). You aren’t expected to memorize the details; it is enough to know the order and the purpose.

Brute-force comparison ($10^{12}$ attempts per second):

DES      2^56  ≈ 7.2 × 10^16  →  ≈ 72 058 s  ≈ 20 hours
AES-128  2^128 ≈ 3.4 × 10^38  →  ≈ 1.1 × 10^19 years

Modes of operation

A block cipher encrypts a single block. For a long message a mode of operation is needed. To demonstrate, let us use a toy 4-bit cipher: $E_K(x)$ = rotate $x \oplus K$ left by 1 bit. $K = 0110$, plaintext blocks $1010,\ 1010,\ 0011$.

ECB (electronic codebook)

Each block is independent: $C_i = E_K(P_i)$.

E(1010): 1010 ⊕ 0110 = 1100 → rotate → 1001
E(1010): same                        → 1001
E(0011): 0011 ⊕ 0110 = 0101 → rotate → 1010
ECB: 1001 1001 1010

The first two blocks are the same, and so are their ciphertexts. The attacker learned that “these two blocks are the same”. In images the pattern stays visible.

CBC (cipher block chaining)

Before each block is encrypted, it is XORed with the previous ciphertext block. For the first block a random initialization vector (IV) is used: $C_i = E_K(P_i \oplus C_{i-1})$, $C_0 = IV$. $IV = 1001$:

C1 = E(1010 ⊕ 1001) = E(0011) = rotl(0101) = 1010
C2 = E(1010 ⊕ 1010) = E(0000) = rotl(0110) = 1100
C3 = E(0011 ⊕ 1100) = E(1111) = rotl(1001) = 0011
CBC: 1010 1100 0011

The same two plaintext blocks are now encrypted differently. Decryption: $P_i = D_K(C_i) \oplus C_{i-1}$. CBC encryption is sequential (it cannot be parallelized), while decryption can be parallel. The IV doesn’t have to be secret but must be unpredictable.

CTR (counter)

The block cipher encrypts a counter value, and the resulting keystream is XORed with the plaintext: $C_i = P_i \oplus E_K(\text{nonce} + i)$. The block cipher becomes a stream cipher. Let the counter start at $0100$:

E(0100) = rotl(0010) = 0100     C1 = 1010 ⊕ 0100 = 1110
E(0101) = rotl(0011) = 0110     C2 = 1010 ⊕ 0110 = 1100
E(0110) = rotl(0000) = 0000     C3 = 0011 ⊕ 0000 = 0011

(In the toy cipher the last keystream block came out as 0000; in real AES this possibility is negligible.) CTR is fully parallel and needs only $E$ for decryption. The cost: the same nonce/counter with the same key must never be repeated, otherwise you fall into the OTP’s key-reuse problem.

PITFALL · what is XORed in CBC? The plaintext is XORed with the previous ciphertext block, not with the previous plaintext block. The first block is XORed with the IV. In an exam, anyone who uses the previous plaintext block gets the whole chain wrong.

TIP · tell the modes apart in one sentence. ECB: independent, patterns leak. CBC: chain, random IV. CTR: encrypt the counter and XOR, unique nonce. Modern systems use modes like GCM that combine encryption with integrity.

The key distribution problem

Symmetric encryption is fast, but the two sides must share the same key in advance. If $n$ people each want a separate key for every pair:

$\frac{n(n-1)}{2} \text{ keys} \qquad n = 50 \Rightarrow 1225, \quad n = 100 \Rightarrow 4950$

And these keys must be distributed over a secure channel. How do you share a key with a server you have never met on the Internet? The answer is on the next page: public-key cryptography and Diffie-Hellman. In practice the two are used together: a session key is established with the public key, and the data is encrypted with a fast symmetric cipher (AES).

Common mistakes

P = 1 1 0 0 1 0 1 0
K = 0 1 0 1 0 0 1 1
C = 1 0 0 1 1 0 0 1