Block Ciphers and the PRP Abstraction

A block cipher is a keyed function

written $E_K(x) = E(K, x)$, such that for every fixed key $K \in \{0,1\}^k$, the map $E_K(\cdot)$ is a bijection (permutation) on $\{0,1\}^n$. Here $k$ is the key length and $n$ is the block length; for AES, $n = 128$ and $k \in \{128, 192, 256\}$. Because $E_K$ is a bijection, there is always a well-defined inverse $D_K = E_K^{-1}$, called decryption, satisfying $D_K(E_K(x)) = x$ for all $x$. This invertibility requirement is the defining structural difference between a block cipher and, say, a cryptographic hash function or a generic pseudorandom function: a PRF need not be injective at all, while a block cipher must be a permutation for every key. The security goal is not "hard to invert without the key" in some vague sense — it is made precise by the pseudorandom permutation (PRP) definition. Fix the block length $n$. Let $\mathrm{Perm}(n)$ denote the set of all bijections on $\{0,1\}^n$ — there are $2^n!$ of them. A block cipher family $\{E_K\}$ is a secure PRP if, when $K$ is sampled uniformly at random and kept secret, the function $E_K$ is computationally indistinguishable from a function $\pi$ sampled uniformly at random from $\mathrm{Perm}(n)$, to any efficient adversary given oracle (black-box, input/output) access. Note the shift in scale: $\mathrm{Perm}(n)$ has $2^n!$ elements while the block cipher's keyspace has only $2^k$ elements — a PRP construction manages to make a tiny keyed family "look like" it was drawn from an unimaginably larger space. A closely related notion, the pseudorandom function (PRF), drops the bijectivity requirement: $F_K$ need only be indistinguishable from a uniformly random function $\{0,1\}^n \to \{0,1\}^n$ (of which there are $(2^n)^{2^n}$, allowing collisions and non-surjectivity). It turns out PRFs are easier to reason about in security proofs (many reductions only need "unpredictable, independent-looking outputs"), while block ciphers are naturally PRPs (they must be invertible to decrypt). The PRF/PRP switching lemma, developed below, bridges the two, showing that as long as an adversary makes few queries relative to $2^{n/2}$, a random permutation and a random function are themselves nearly indistinguishable — so security proofs can freely substitute one abstraction for the other.

The PRP security game

Security is defined via an indistinguishability game between a challenger and an adversary $\mathcal{A}$. ``` PRP-GAME(A, E, n, k): b <- uniform random bit in {0, 1} K <- uniform random key in {0,1}^k pi <- uniform random permutation from Perm(n) // The adversary gets oracle access to ONE of these two functions, // chosen according to b, and must guess which. define ORACLE(x): if b == 0: return E(K, x) // "real" world: the actual cipher else: return pi(x) // "ideal" world: a truly random permutation b' <- A^ORACLE(1^n) // A may query ORACLE adaptively, q times return 1 if b' == b else 0 // A "wins" if it guesses b correctly ``` The adversary's PRP-advantage is defined as

Equivalently, this is $2 \Pr[\text{A wins}] - 1$. $E$ is a secure PRP if, for every probabilistic polynomial-time adversary $\mathcal{A}$ making at most $q$ queries and running in time at most $t$, the advantage $\mathrm{Adv}^{\mathrm{prp}}_E(\mathcal{A})$ is negligible in $n$ (or, in the concrete-security view used for real ciphers, bounded by some small explicit function of $q$, $t$, and $n$). Nothing here is asymptotic magic: the game is a concrete, simulatable experiment. This is what makes PRP security falsifiable — an attack is exactly an adversary strategy achieving non-negligible advantage, and a proof of security is exactly a reduction showing that any such adversary would break some other assumed-hard problem.

Building a PRP from small pieces: Feistel networks

No one can write down a lookup table of size $2^{128}$, so real ciphers construct $E_K$ as an iterated composition of many simple, efficiently computable rounds. Two dominant paradigms exist; the first is the Feistel network, used by DES. A Feistel network splits the $n$-bit block into two halves $L, R$ of $n/2$ bits each, and applies a round function $f$ (which need not itself be invertible) as follows: ``` FEISTEL-ROUND(L, R, roundKey): L' <- R R' <- L XOR f(R, roundKey) return (L', R') FEISTEL-ENCRYPT(x, K, numRounds): (L, R) <- split(x) // x = L || R for i in 1 .. numRounds: roundKey_i <- deriveRoundKey(K, i) // key schedule (L, R) <- FEISTEL-ROUND(L, R, roundKey_i) return L || R FEISTEL-DECRYPT(y, K, numRounds): (L, R) <- split(y) for i in numRounds downTo 1: roundKey_i <- deriveRoundKey(K, i) // Invert the round: undo the swap and the XOR R_prev <- L L_prev <- R XOR f(R_prev, roundKey_i) (L, R) <- (L_prev, R_prev) return L || R ``` The beautiful fact is that decryption reuses the exact same round function $f$, run with round keys in reverse order — even if $f$ itself is not invertible. This is because each round only ever adds $f(R)$ to $L$ via XOR (which is its own inverse) and swaps halves; undoing a round requires no inverse of $f$, only re-computing it. This lets designers pick a highly nonlinear, deliberately "messy" $f$ without worrying about how to invert it.

Building a PRP from small pieces: Substitution-Permutation Networks

The second paradigm, used by AES, is the substitution-permutation network (SPN). Each round applies three layers to the entire block (not half of it): ``` SPN-ROUND(state, roundKey): state <- SUBSTITUTE(state, S_BOX) // nonlinear, per-byte/nibble lookup (confusion) state <- PERMUTE(state) // linear mixing across the whole block (diffusion) state <- state XOR roundKey // key injection return state SPN-ENCRYPT(x, K, numRounds): state <- x XOR deriveRoundKey(K, 0) // initial whitening for i in 1 .. numRounds: state <- SUBSTITUTE(state, S_BOX) if i < numRounds: state <- PERMUTE(state) state <- state XOR deriveRoundKey(K, i) return state ``` Here substitution (an S-box) is a small, fixed nonlinear bijection on bytes or nibbles, providing confusion — hiding the algebraic relationship between key and ciphertext. Permutation/linear-mixing spreads the influence of each input bit across many output bits — providing diffusion, so that flipping one input bit eventually flips roughly half the output bits after enough rounds. SPN decryption applies the inverse S-box and inverse permutation layer, in reverse round order — unlike a Feistel network, each layer here genuinely must be inverted, so every component (S-box, mixing layer) is chosen to be an explicit bijection.

Confusion and diffusion as the design compass

Claude Shannon's 1949 paper identified confusion and diffusion as the two properties a good cipher needs to defeat statistical cryptanalysis: confusion makes the relationship between key and ciphertext as complex as possible (typically via nonlinear S-boxes), and diffusion spreads each plaintext/key bit's influence over the whole ciphertext (via linear mixing layers), so local statistical biases wash out. Neither property alone suffices — a purely diffusive cipher is just a fixed linear map (trivially invertible without the key by linear algebra), and a purely confusing cipher applied to small independent chunks leaves each chunk separately attackable. Iterating rounds that alternate confusion and diffusion is exactly what turns a small nonlinear building block into something that, after enough rounds, looks like a uniformly random permutation to a bounded adversary.

Time and space for the cipher itself. A single call to $E_K$ or $D_K$ costs $O(r)$ where $r$ is the number of rounds, each round doing $O(n)$ work (S-box lookups and linear mixing over an $n$-bit block), so overall encryption/decryption of one block is $O(rn)$ time and $O(n + k)$ space (state plus key schedule). For AES-128, $r = 10$ rounds over a 128-bit state — a small constant, making block ciphers extremely fast in practice, often a handful of CPU cycles per byte with hardware support (e.g., AES-NI instructions).

Time and space for attacking the PRP game. The relevant complexity is the adversary's, not the defender's. An adversary distinguishing $E_K$ from a random permutation using exhaustive key search runs in time $O(2^k)$ (try every key, check consistency against a few observed input/output pairs) — trivial in time-complexity terms but infeasible in practice for $k \geq 128$ because $2^{128}$ operations vastly exceeds any conceivable computational budget. This is why key length, not some abstract "hardness," is the concrete security parameter: security against key search scales exactly as $2^k$.

Correctness of the invertibility structure (Feistel). Claim: `FEISTEL-DECRYPT` correctly inverts `FEISTEL-ENCRYPT` for any function $f$, invertible or not. Proof sketch by induction on rounds, working backward. After one Feistel round, $(L', R') = (R, \, L \oplus f(R, k))$. Given $(L', R')$ and knowledge of the round key $k$ (hence able to recompute $f$), decryption recovers $R = L'$ immediately, then recovers $L = R' \oplus f(R, k) = R' \oplus f(L', k)$ — using only XOR's self-inverse property $a \oplus a = 0$, never an inverse of $f$. Chaining this argument round by round (each round's output is the next round's input) shows the full multi-round decryption exactly undoes the full multi-round encryption, regardless of how nonlinear or non-invertible $f$ is internally. This is precisely why Feistel networks were historically attractive: they let designers use arbitrarily "ugly," non-injective round functions while still guaranteeing a clean overall bijection.

Why iterating small nonlinear rounds can approximate a random permutation. There is no proof that any specific real cipher (DES, AES) is a secure PRP in an absolute sense — PRP security of concrete ciphers is a hardness assumption, verified only by the community's inability, after decades of public cryptanalysis, to find a distinguishing attack better than brute-force key search. What can be proven is relative/structural: for an "ideal cipher" model where each round function is modeled as an independent truly random function, sufficiently many Feistel rounds provably yield a permutation indistinguishable from a uniformly random one (the Luby–Rackoff result: 3 rounds of a Feistel network with independent random round functions already give a secure PRP against non-adaptive adversaries, and 4 rounds give security against fully adaptive chosen-plaintext/ciphertext adversaries). Real ciphers use many more rounds than this theoretical minimum, both for a margin of safety against cryptanalytic shortcuts and because real round functions are far cheaper (and less "ideal") than truly random functions.

The PRF/PRP switching lemma. Because $\mathrm{Perm}(n)$ is a small subset of "all functions" (bijections only), a random permutation and a random function agree with high probability on any fixed set of $q$ distinct queries, differing only when the adversary would observe a collision that a permutation structurally forbids. A standard birthday-style argument gives, for any adversary making at most $q$ distinct queries:

where $\pi$ is a random permutation and $f$ a random function on $\{0,1\}^n$. Reasoning: condition on the event that all of $f$'s $q$ outputs happen to be distinct — in that case $f$'s query-answer behavior is distributed identically to $\pi$'s, so the adversary's output distribution is exactly the same; the only remaining discrepancy is the probability that $f$ produces at least one collision among $q$ outputs, which a union bound over $\binom{q}{2}$ pairs, each colliding with probability $2^{-n}$, bounds by $\binom{q}{2}/2^n = q(q-1)/2^{n+1}$. This term is the reason PRP-based security proofs eventually degrade once query counts $q$ approach $2^{n/2}$ (the "birthday bound") — a recurring, honest caveat that shows up again when discussing modes of operation built on top of block ciphers.

Honest tradeoffs. Larger block size $n$ pushes the birthday bound further out (good for security) but increases per-round hardware/state cost; more rounds increase confidence against cryptanalysis but cost raw throughput; smaller S-boxes are cheap to implement but may leave exploitable algebraic structure (as later differential and linear cryptanalysis attacks on reduced-round DES demonstrated). No block cipher is "provably secure" in the way a one-time pad is — PRP security is an empirically-supported assumption, not a theorem.

Rather than run full AES arithmetic by hand (36 rounds of GF(2⁸) math obscures the concept), trace a tiny toy 8-bit-block, 2-round Feistel cipher to see the PRP machinery concretely: 4-bit halves $L, R$, round function $f(R, k) = (R \lll 1) \oplus k$ (left-rotate by 1 bit, XOR with a 4-bit round key), two rounds, keys $k_1 = 1011_2$, $k_2 = 0110_2$. Plaintext $x = L\,\|\,R = 0110\,\|\,1101$ (i.e., $L=0110$, $R=1101$).

Decryption check, using round keys in reverse ($k_2$ then $k_1$), confirms invertibility:

This confirms the Feistel structure round-trips correctly — the whole point of the correctness argument above, made concrete. Note also that $f$ here (rotate-then-XOR) is trivially invertible on its own, yet the proof of correctness never needed that; it works purely from the XOR/swap structure, exactly as the induction argument predicted. To connect this to the PRP game: an adversary who queries this toy cipher on all $2^8 = 256$ possible inputs and tabulates outputs can trivially distinguish it from a random permutation (a random 8-bit permutation, viewed globally, has no algebraic pattern; this toy cipher's rotate-XOR structure produces a very regular, low-diffusion map). This is exactly why real ciphers need many more rounds and much more complex, carefully vetted round functions — a 2-round toy is pedagogically clear but cryptographically worthless, which is itself a useful lesson about the gap between "invertible" and "PRP-secure."

Block ciphers are the deterministic, invertible "engine" underneath nearly every symmetric cryptographic system in production use. AES, wrapped in a mode of operation such as GCM or CBC, secures TLS connections behind HTTPS, disk encryption (BitLocker, FileVault, LUKS), Wi-Fi (WPA2/WPA3), VPN tunnels (IPsec, WireGuard's underlying primitives), and payment-card processing. Hardware vendors (Intel AES-NI, ARM Cryptography Extensions) bake block cipher rounds directly into CPU instructions because their fixed, small-round structure is uniquely well-suited to pipelined hardware acceleration, unlike variable-length stream cipher state machines. The PRP abstraction itself is the load-bearing assumption cited in every security proof for these modes: a proof that "CBC mode is secure" is really a proof of the form "if the underlying block cipher is a secure PRP, then CBC-encryption is IND-CPA secure," reducing the security of an entire deployed system down to the single, carefully scrutinized assumption discussed here. Block ciphers are also repurposed as building blocks for other primitives — hash function compression functions (Davies–Meyer construction), message authentication codes (CMAC), and key-derivation functions — all inheriting their security guarantees from the same PRP indistinguishability game.

Ask the tutor: How does the PRP security of a block cipher translate into an IND-CPA security proof for a specific mode of operation like CBC or CTR?