ISE Cryptography — Reference

Probability and Security Definitions

Why Probability in Crypto?

Every security game is a probability experiment.

The Adversary is a Coin-Flipper

What does it mean for a cipher to be “secure”? It means no efficient adversary can break it
- “No efficient adversary can distinguish PRG output from random with non-negligible advantage”
Every attack game is a probability experiment:
- A challenger generates a secret (key, seed, random string)
- An adversary interacts with the challenger and outputs a guess
- We measure the probability that the guess is correct
The advantage is how much better the adversary does than random guessing
- If the advantage is tiny (negligible), we call the scheme secure
- If the advantage is large, the scheme is broken
See the Attack Games reference for diagrams of each game

Probability Refresher

A sample space \(\Omega\) is the set of all possible outcomes of an experiment
An event \(A \subseteq \Omega\) is a set of outcomes we care about
\(\Pr[A]\) is the probability that event \(A\) occurs, always in \([0, 1]\)
Key rules:
- Complement: \(\Pr[\overline{A}] = 1 - \Pr[A]\)
- Union bound: \(\Pr[A \text{ or } B] \leq \Pr[A] + \Pr[B]\)
- Independence: \(\Pr[A \text{ and } B] = \Pr[A] \cdot \Pr[B]\) if \(A, B\) are independent
The union bound is the single most-used probability tool in this course
- “The probability that at least one bad thing happens is at most the sum of each bad thing’s probability”
- It’s an overestimate, but it’s simple and always valid

The Security Parameter

One number controls everything.

\(\lambda\): The Master Dial

The security parameter \(\lambda\) is a positive integer that scales the entire system
- Keys are \(\lambda\) bits: \(k \in \{0,1\}^\lambda\)
- Key space: \(|\mathcal{K}| = 2^\lambda\)
- Brute-force search: \(2^\lambda\) operations
As \(\lambda\) grows:
- Legitimate operations (encrypt, decrypt, sign) stay polynomial in \(\lambda\)
- Adversary’s work to break the scheme grows exponentially in \(\lambda\)
- This gap is what computational security relies on
Typical values: \(\lambda = 128\) (AES-128), \(\lambda = 256\) (AES-256, ChaCha20)
- \(2^{128} \approx 3.4 \times 10^{38}\) – more than the number of atoms on Earth

Negligible Functions

A function \(f(\lambda)\) is negligible if it shrinks faster than any inverse polynomial
- Formally: for every positive integer \(d\), there exists \(\lambda_0\) such that for all \(\lambda > \lambda_0\): \(f(\lambda) < 1/\lambda^d\)
Intuition: negligible means vanishingly small
- Smaller than \(1/\lambda\), smaller than \(1/\lambda^2\), smaller than \(1/\lambda^{100}\)
- Eventually smaller than \(1/\lambda^d\) for ANY \(d\) you pick
Examples:
- \(1/2^\lambda\) is negligible (exponential decay)
- \(1/\lambda^{100}\) is NOT negligible (it’s an inverse polynomial)
- \(2^{-\sqrt{\lambda}}\) is negligible (sub-exponential still beats any polynomial)

Super-Polynomial Functions

\(Q(\lambda)\) is super-polynomial if it grows faster than any polynomial
- Formally: \(Q\) is super-poly if and only if \(1/Q\) is negligible
Examples:
- \(2^\lambda\) is super-poly (exponential growth)
- \(\lambda^{100}\) is NOT super-poly (it IS a polynomial)
Why this matters:
- The key space \(|\mathcal{K}| = 2^\lambda\) is super-poly, so brute-force probability \(1/2^\lambda\) is negligible
- An efficient adversary runs in polynomial time
- A super-poly key space means no efficient adversary can enumerate it
The master security statement:
- “For all efficient adversaries \(\mathcal{A}\), \(\text{Game}_\text{adv}[\mathcal{A}, \text{Scheme}]\) is negligible in \(\lambda\)”

Concrete Security

What the numbers actually mean in practice.

\(b\)-Bit Security

Saying “negligible” tells us security scales correctly as \(\lambda\) grows
- But we deploy at a fixed \(\lambda\), so we need concrete bounds
\(b\)-bit security: the best known attack requires \(\approx 2^b\) operations
- For brute-force key search: \(T\) trials give advantage \(\approx T / 2^\lambda\)
Calibration (for a 128-bit key):

Attack effort	Example	Advantage
\(2^{56}\) operations	DES crack (1998)	\(2^{-72}\)
\(2^{64}\) operations	Feasible on modern hardware	\(2^{-64}\)
\(2^{80}\) operations	Well-funded adversary	\(2^{-48}\)
\(2^{128}\) operations	Beyond foreseeable classical computers	\(\approx 1\)

128 bits is the minimum for new systems

Where Security Bits Come From

Different constructions lose security bits in different ways:
- Key search: \(\lambda\)-bit key gives \(\lambda\)-bit security (1 operation per guess)
- Birthday attacks: \(n\)-bit output gives \(n/2\)-bit security (collisions at \(\sqrt{2^n}\))
- PRF/PRP switching: 128-bit block cipher loses security after \(2^{64}\) queries (birthday bound on \(2^{128}\) domain)
The weakest link dominates:
- AES-128 in CTR mode: 128-bit key security, but PRF switching at \(2^{64}\) queries
- In practice: re-key before \(2^{64}\) blocks (\(\approx 256\) exabytes)
Collision resistance of an \(n\)-bit hash: \(n/2\) bits of security
- SHA-256: 128-bit collision resistance
- SHA-1 (160-bit): theoretical 80 bits, practically broken at 63 bits

Why 128 Bits is the Minimum

Grover’s quantum algorithm halves symmetric security: \(2^\lambda \to 2^{\lambda/2}\)
- AES-128: 128-bit classical, 64-bit quantum (below the threshold!)
- AES-256: 256-bit classical, 128-bit quantum (still safe)
ChaCha20 uses a 256-bit key: 128-bit quantum margin built in
Rule of thumb for new designs:
- \(\lambda \geq 128\) for classical security
- \(\lambda \geq 256\) for quantum margin (if using symmetric primitives)
- RSA/DH need much larger parameters (3072+ bits for 128-bit classical)

The Birthday Bound

The most useful collision formula in cryptography.

The Birthday Paradox

In a room of 23 people, there’s a \(> 50\%\) chance two share a birthday
- Intuition: there are \(\binom{23}{2} = 253\) pairs to check, and only 365 days
General result: \(Q\) samples from a domain of size \(N\)
- Collision probability \(\approx Q^2 / 2N\) (when \(Q \ll N\))
- 50% collision at \(Q \approx 1.2 \sqrt{N}\)

Domain size \(N\)	50% collision at \(Q\)	Security bits
\(2^{64}\) (DES block)	\(2^{32}\)	32
\(2^{96}\) (GCM nonce)	\(2^{48}\)	48
\(2^{128}\) (AES block)	\(2^{64}\)	64
\(2^{256}\) (SHA-256 output)	\(2^{128}\)	128

Birthday Bound: PRF/PRP Switching

A pseudorandom function (PRF) maps each input to an independent random output
- Two different inputs CAN map to the same output (with probability \(1/|\mathcal{Y}|\))
A pseudorandom permutation (PRP) is a bijection: no two inputs share an output
- After \(Q\) queries, this difference becomes detectable (birthday bound)
The PRF/PRP switching lemma (from the Block Ciphers lecture):
- \(\text{PRF}_\text{adv}[\mathcal{A}, E] \leq \text{BC}_\text{adv}[\mathcal{B}, E] + Q^2 / (2|\mathcal{X}|)\)
- For AES (\(|\mathcal{X}| = 2^{128}\)): the gap is negligible until \(Q \approx 2^{64}\) queries
This is why 64-bit block ciphers (DES, 3DES) are insecure as PRFs in practice
- Only \(2^{32}\) queries before the birthday gap becomes detectable

Birthday Bound: Hash Collisions

A hash function \(H : \{0,1\}^* \to \{0,1\}^n\) has \(2^n\) possible outputs
Finding a collision requires \(\approx 2^{n/2}\) evaluations (birthday bound)
- SHA-256 (\(n = 256\)): 128-bit collision resistance
- SHA-1 (\(n = 160\)): theoretical 80 bits, broken in practice (\(2^{63}\) operations, 2017)
This is why 256-bit output is the minimum for new hash functions
- It provides 128-bit collision resistance, matching AES-128

Birthday Bound: Nonce Collisions

AES-GCM uses a 96-bit nonce. If nonces are chosen randomly:
- After \(Q\) messages, nonce collision probability \(\approx Q^2 / 2^{97}\)
- At \(Q = 2^{32}\) messages: probability \(\approx 2^{-33}\) (safe)
- At \(Q = 2^{48}\) messages: probability \(\approx 2^{-1}\) (50%… danger)
A nonce collision in GCM is catastrophic (leaks the authentication key)
- This is why GCM has message-count limits, and why XChaCha20 uses a 192-bit nonce
The birthday bound governs nonce-size decisions across all AEAD schemes

Advantage and Reductions

Reading and composing security statements.

Reading Advantage Expressions

The general template: \(\text{Game}_\text{adv}[\mathcal{A}, \text{Scheme}]\)
- \(\mathcal{A}\): the adversary (a specific efficient algorithm)
- Scheme: the cryptographic construction being attacked
- Game: the security definition (SS, PRG, PRF, MAC, CCA, …)
Examples from the course:
- \(\text{SS}_\text{adv}[\mathcal{A}, \mathcal{E}]\): how well \(\mathcal{A}\) breaks semantic security of cipher \(\mathcal{E}\)
- \(\text{PRG}_\text{adv}[\mathcal{A}, G]\): how well \(\mathcal{A}\) distinguishes PRG \(G\) from random
- \(\text{MAC}_\text{adv}[\mathcal{A}, \mathcal{I}]\): probability \(\mathcal{A}\) forges a valid MAC on \(\mathcal{I}\)
- \(\text{CCA}_\text{adv}[\mathcal{A}, \mathcal{E}]\): how well \(\mathcal{A}\) breaks CCA security of \(\mathcal{E}\)
Secure means: “for all efficient \(\mathcal{A}\), the advantage is negligible in \(\lambda\)”

The Reduction Template

A reduction proves security by showing: “if you can break Scheme, you can break Primitive”
Structure: given any adversary \(\mathcal{A}\) attacking Scheme, build adversary \(\mathcal{B}\) attacking Primitive, with:
- \(\text{Scheme}_\text{adv}[\mathcal{A}] \leq \text{Primitive}_\text{adv}[\mathcal{B}]\)
Since Primitive is assumed secure (right side negligible), Scheme must be secure too
This pattern recurs throughout the course:
- Stream cipher security reduces to PRG security (Lecture 02)
- CBC-MAC security reduces to PRF security (Lecture 04)
- CCA security of encrypt-then-MAC reduces to CPA + MAC security (Lecture 06)
The point: we never prove security “from scratch”… we always reduce to something we already trust

Composing Bounds

Real security bounds often have multiple terms:
- \(\text{PRF}_\text{adv}[\mathcal{A}, E] \leq \text{BC}_\text{adv}[\mathcal{B}, E] + Q^2 / (2|\mathcal{X}|)\)
Each term has a source:
- \(\text{BC}_\text{adv}\): the block cipher could be broken (assumed negligible)
- \(Q^2 / (2|\mathcal{X}|)\): the PRF/PRP switching gap (birthday bound)
The weakest link dominates: security is only as good as the largest term
- For AES-128 (\(|\mathcal{X}| = 2^{128}\)) with \(Q = 2^{48}\) queries:
- Advantage \(\leq \epsilon + 2^{96}/2^{129} = \epsilon + 2^{-33}\)… still negligible
When reading security theorems, identify each term and what degrades it

Notation Summary

Notation	Meaning	Used in
\(\lambda\)	Security parameter (key length in bits)	All lectures
Negligible	Shrinks faster than any \(1/\lambda^d\)	Security definitions
Super-poly	Grows faster than any \(\lambda^d\)	Key space size
\(b\)-bit security	Best attack requires \(\approx 2^b\) operations	Concrete security
\(\text{Game}_\text{adv}[\mathcal{A}, S]\)	Advantage of \(\mathcal{A}\) in Game against \(S\)	All security proofs
Birthday bound	\(Q\) samples from \(N\): collision \(\approx Q^2/2N\)	PRF/PRP, hashing, nonces
Union bound	\(\Pr[A \cup B] \leq \Pr[A] + \Pr[B]\)	Proof technique
Reduction	“Break Scheme \(\Rightarrow\) break Primitive”	All security proofs