Helpful context:

A pseudorandom generator gives us a long pseudorandom string from a short key - which can be XOR’d with a message like a one-time pad. But that only works for messages shorter than the keystream, and it cannot encrypt two messages under the same key (reuse breaks XOR-security). A block cipher processes fixed-length blocks and can be run in various modes to handle arbitrary messages. But the choice of mode matters enormously: the same block cipher used in different modes has wildly different security properties.

This post builds the precise security definitions and traces the path from eavesdropper security to chosen-plaintext security to chosen-ciphertext security, explaining why each upgrade was needed. The definitions are not just bureaucratic formalism - each one was introduced because the previous one was shown to be insufficient for real-world adversaries who can do more than passively observe. Understanding what breaks at each level tells you exactly what property the next definition is buying.

Eavesdropper Security (EAV)

The weakest security definition asks: can an eavesdropper learn anything about the message from the ciphertext?

Definition (EAV security / semantic security). A private-key encryption scheme is EAV-secure if for all PPT adversaries $A$, the advantage in the following experiment is negligible:

  1. $A$ outputs two equal-length messages $m_0, m_1$.
  2. A bit $b \leftarrow \{0,1\}$ is chosen; $c \leftarrow \text{Enc}_k(m_b)$ is given to $A$.
  3. $A$ outputs $b'$. $A$ wins if $b' = b$.

$\text{Adv}_{\text{EAV}}(A) = |\Pr[b' = b] - 1/2|$ must be negligible.

EAV security is equivalent to semantic security: no PPT adversary can compute any partial information about the message from the ciphertext.

Stream ciphers. A stream cipher uses a PRG $G: \{0,1\}^n \to \{0,1\}^{\ell}$ to produce a pseudorandom stream: $\text{Enc}_k(m) = G(k) \oplus m$. This is EAV-secure - the output of $G$ is computationally indistinguishable from a one-time pad. But it fails badly under the next definition.

CPA Attack on Deterministic Encryption

EAV security assumes the adversary sees only one ciphertext. The moment an adversary can make multiple encryption queries - a realistic model since Alice may send many messages - deterministic encryption breaks.

CPA (chosen-plaintext attack) experiment:

  1. Adversary gets oracle access to $\text{Enc}_k(\cdot)$.
  2. $A$ queries the oracle adaptively, then outputs $m_0, m_1$.
  3. Challenge: $c^* \leftarrow \text{Enc}_k(m_b)$.
  4. $A$ continues querying, then outputs $b'$.

Claim: any deterministic encryption scheme is CPA-insecure. $A$ queries $\text{Enc}_k(m_0)$ before the challenge. When it receives $c^$, it checks if $c^ = \text{Enc}_k(m_0)$. If yes, $b' = 0$; else $b' = 1$. Determinism means $\text{Enc}_k(m_0)$ is always the same, so this wins with probability 1.

Fix: randomized encryption. $\text{Enc}$ must be randomized - using fresh randomness each call. The same message encrypts to different ciphertexts on different calls.

Pseudorandom Functions and Permutations

Pseudorandom function (PRF). A keyed function $F: \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$ is a PRF if it is computationally indistinguishable from a truly random function: for all PPT $D$: $$|\Pr[D^{F_k(\cdot)}(1^n) = 1] - \Pr[D^{f(\cdot)}(1^n) = 1]| \leq \varepsilon(n)$$ where $k \leftarrow \{0,1\}^n$ and $f$ is a uniformly random function. The distinguisher has oracle access but cannot distinguish $F_k$ from a random function.

Pseudorandom permutation (PRP). Same as PRF but $F_k$ must be a bijection, and the distinguisher also gets access to an inversion oracle $F_k^{-1}(\cdot)$ in the “strong PRP” variant. Block ciphers (AES, DES) are modeled as PRPs.

PRFs exist if OWFs exist (via the Goldreich-Goldwasser-Micali construction). PRPs exist if PRFs exist - Luby-Rackoff: a 3-round Feistel network with PRF round functions gives a PRP.

Modes of Operation

A block cipher $F_k: \{0,1\}^n \to \{0,1\}^n$ encrypts one $n$-bit block. To encrypt a variable-length message $m = m_1 | m_2 | \cdots | m_\ell$, choose a mode of operation.

ECB (Electronic Codebook) - Broken

$c_i = F_k(m_i)$. Each block encrypted independently with the same key.

Why it fails: Deterministic. Identical plaintext blocks produce identical ciphertext blocks. The famous ECB penguin: an image encrypted block-by-block in ECB retains its visual structure because pixel blocks with the same values encrypt identically. Never use ECB for more than one block.

CBC (Cipher Block Chaining)

Choose a random initialization vector $\text{IV} \leftarrow \{0,1\}^n$. $$c_0 = \text{IV}, \quad c_i = F_k(m_i \oplus c_{i-1})$$ Decryption: $m_i = F_k^{-1}(c_i) \oplus c_{i-1}$.

The IV must be fresh and uniform for each encryption (it is sent as part of the ciphertext). With a uniform IV, CBC is CPA-secure. The chaining means each block depends on all previous blocks - identical plaintext blocks produce different ciphertext. Weakness: requires sequential processing; IV predictability breaks CPA security.

OFB (Output Feedback)

$$z_0 = \text{IV}, \quad z_i = F_k(z_{i-1}), \quad c_i = m_i \oplus z_i$$ The keystream $z_1, z_2, \ldots$ is computed from $F_k$ applied to itself, independently of the message. Encryption reduces to XOR with a pseudorandom stream. This turns the block cipher into a stream cipher. The keystream can be precomputed. Error propagation: a bit flip in $c_i$ corrupts only $m_i$ (unlike CBC where a flip in $c_i$ also scrambles $m_{i+1}$).

CTR (Counter Mode)

$$c_i = m_i \oplus F_k(\text{IV} | i)$$ The keystream is $F_k(\text{IV}|1), F_k(\text{IV}|2), \ldots$ - the block cipher applied to a counter. Fully parallelizable (unlike CBC). Standard and widely used (AES-CTR).

CTR and OFB are CPA-secure. For multi-message security, the IV must be unique (not necessarily random) - no two encryptions under the same key should use the same counter block.

CPA Security from PRF

Theorem. CTR mode using a PRF is CPA-secure.

Proof sketch. The keystream from $F_k(\text{IV}|i)$ with a random IV is indistinguishable from a truly random string. XOR with a random string gives a one-time-pad-secure encryption. Any distinguisher for CTR output can be used to distinguish $F_k$ from a random function - contradicting PRF security. $\square$

The formal proof uses a hybrid: replace $F_k$ with a truly random function, show security under the random function (direct argument), then argue the replacement was undetectable (PRF security).

Chosen-Ciphertext Security (CCA)

CPA security assumes the adversary can only encrypt. A stronger model - and necessary for most real applications - allows the adversary to also decrypt.

CCA experiment:

  1. $A$ gets oracle access to both $\text{Enc}_k(\cdot)$ and $\text{Dec}_k(\cdot)$.
  2. $A$ outputs $m_0, m_1$; receives challenge $c^* \leftarrow \text{Enc}_k(m_b)$.
  3. $A$ continues with both oracles (but cannot query $\text{Dec}_k(c^*)$).
  4. $A$ outputs $b'$.

Why CCA matters. Consider an e-commerce server that decrypts received ciphertexts and returns an error message (“decryption failed” or “padding error”). An adversary who can submit modified ciphertexts and observe the server’s response has a decryption oracle. Bleichenbacher’s 1998 attack on PKCS#1 v1.5 exploited exactly this: the server’s “invalid PKCS” error message allowed the adversary to decrypt RSA-encrypted messages via roughly 1 million adaptive queries.

Pure CBC or CTR mode is not CCA-secure - a modified ciphertext will decrypt to a related plaintext with no detection. CCA security requires authentication on top of encryption. Authenticated encryption (AE) schemes (like AES-GCM) provide both CPA-style confidentiality and ciphertext integrity - ensuring that tampered ciphertexts are rejected before decryption.

The correct paradigm: Encrypt-then-MAC - encrypt the message, then compute a MAC over the ciphertext. Never MAC-then-Encrypt. This gives CCA security from any CPA-secure cipher and any secure MAC.

Summary

Mode Security Notes
ECB Broken Deterministic; equal blocks give equal ciphertexts
CBC CPA-secure (with uniform IV) Sequential; IV must be random
OFB CPA-secure Stream cipher from block cipher; parallelizable keystream
CTR CPA-secure Fully parallelizable; standard choice
AES-GCM CCA-secure (AE) CTR + Galois MAC; AEAD standard
Concept Key idea
EAV security Ciphertext hides message from passive eavesdropper
CPA security Secure even when adversary can encrypt chosen messages
CCA security Secure even when adversary can decrypt (except challenge)
PRF Keyed function indistinguishable from random
PRP / block cipher Bijective PRF; modeled by AES
Encrypt-then-MAC Correct composition for CCA security

Read next: