3. Cryptography

Cryptography is the engineering discipline that converts a security requirement into a mathematical guarantee: it is how you obtain confidentiality over an untrusted network, integrity against an active attacker, and authenticity without a trusted courier. This chapter builds from the vocabulary and classical ciphers up through symmetric and asymmetric primitives, hashing, and the certificate infrastructure that makes public keys usable at internet scale. The emphasis throughout is on how primitives fail when composed badly, because in practice almost no system is broken by breaking the cipher.

<a id="31-cryptographic-fundamentals"></a>

3.1 Cryptographic Fundamentals

This section establishes the terminology, the assumptions a cryptosystem is allowed to make, and the single resource every cryptosystem consumes: unpredictability. The classical ciphers here are not useful for protecting anything, but they are the cheapest way to build intuition for what "breaking a cipher" actually means.

Terminology: Plaintext, Ciphertext, Keys

Theory

Every discussion of cryptography collapses into confusion unless four terms are kept strictly apart. Plaintext is the data you care about, in a form that is useful. Ciphertext is that data transformed so it is useless to anyone who lacks a specific secret. The algorithm (or cipher) is the public, published procedure for transforming between them. The key is the secret parameter that selects one specific transformation out of the enormous family the algorithm describes.

The analogy that holds up best is a combination lock. The mechanism of a combination lock is a published, mass-produced design that anyone can study, buy, and disassemble. Its security does not come from the mechanism being secret; it comes from the setting — your particular combination — being secret, and from the number of possible settings being large enough that trying them all is impractical. The algorithm is the mechanism; the key is the combination.

This separation has a direct operational consequence: algorithms are chosen once and rarely change; keys are generated constantly and must be rotated, protected, and destroyed. Most real-world cryptographic failure is key-management failure. The cipher held; the key was in a Git repository.

A further distinction that matters later: the keyspace is the set of all possible keys, and its size is what resists brute force. A 128-bit key means 2^128 possibilities. Key length is not security by itself — it is an upper bound on security, and an algorithm with a structural weakness delivers far less than its key length suggests.

Two more terms complete the working vocabulary:

• Encoding (Base64, hex, URL-encoding) is a reversible format change with no key. It provides zero confidentiality. Treating Base64 as encryption is a recurring real-world finding.
• Cryptanalysis is the study of breaking cryptosystems, as distinct from brute force, which is merely exhausting the keyspace. An attack is interesting when it is faster than brute force.

Examples

  PLAINTEXT              ALGORITHM (public)             CIPHERTEXT
  "transfer 500"  ──►  ┌──────────────────────┐  ──►  a3 9f 2c 71 ...
                       │  E(key, plaintext)   │
                       └──────────┬───────────┘
                                  │
                              KEY (secret)
                           0x8f3a...e21b
                                  │
  PLAINTEXT              ┌────────┴───────────┐        CIPHERTEXT
  "transfer 500"  ◄──    │  D(key, ciphertext)│  ◄──  a3 9f 2c 71 ...
                         └────────────────────┘

  Kept secret: the KEY only.      Assumed known to the attacker:
                                  the algorithm, the implementation,
                                  and often parts of the plaintext.

import base64
import os

from cryptography.hazmat.primitives.ciphers.aead import AESGCM

plaintext = b"transfer 500 to account 12345"

# ENCODING: no key, no secrecy. Trivially reversible by anyone.
encoded = base64.b64encode(plaintext)
print(base64.b64decode(encoded) == plaintext)  # True, for everyone

# ENCRYPTION: the key selects one transformation out of 2**256.
key = AESGCM.generate_key(bit_length=256)   # the secret parameter
nonce = os.urandom(12)                      # public, but must never repeat
ciphertext = AESGCM(key).encrypt(nonce, plaintext, None)

# Without `key`, ciphertext is indistinguishable from random bytes.
recovered = AESGCM(key).decrypt(nonce, ciphertext, None)
assert recovered == plaintext

Term	Secret?	Changes often?	Failure if exposed
Algorithm	No	No	None, by design
Key	Yes	Yes	Total loss of confidentiality
IV / nonce	No	Every message	Catastrophic only if reused
Ciphertext	No	Every message	None, by design
Encoding scheme	No	No	None; it was never a secret

Key Takeaways

• Secrecy lives in the key, never in the algorithm; this is a design requirement, not an accident.
• Keyspace size bounds brute-force resistance, but structural weaknesses mean effective security can be far below the nominal key length.
• Encoding is not encryption: Base64, hex, and URL-encoding have no key and provide no confidentiality.
• Most breaches attributed to "weak crypto" are key-management failures, not algorithm failures.
• Nonces and IVs are public values whose only requirement is uniqueness; this is a different requirement from secrecy and is violated far more often.

🧪 Practice

1. Take the string attack at dawn, Base64-encode it, and explain in two sentences why handing that output to an untrusted party leaks the message completely.
2. A system uses a 256-bit key but derives it from a user-chosen 6-character password. Estimate the real keyspace and explain why the "256-bit" claim is misleading.
3. Classify each of the following as plaintext, ciphertext, key, or neither: a TLS session ticket, a password hash in a database, a JWT payload, an SSH private key file, a Base64 HTTP basic-auth header.
4. Interview-style: "A developer says their data is safe because it is Base64-encoded before being stored. How do you respond?" Hint: separate the concepts of reversibility-without-a-secret and reversibility-with-a-secret, and consider what the developer may actually be trying to achieve (transport safety for binary data) versus what they claim.

Kerckhoffs's Principle

Theory

In 1883 Auguste Kerckhoffs wrote down a set of requirements for military ciphers, and one of them became the organizing assumption of the entire field: a cryptosystem should remain secure even if everything about it except the key is public knowledge.

The "why" is a claim about how secrets behave over time. Secrets that live in many places — in source code, in shipped hardware, in the heads of everyone who implemented the system — leak. They leak through reverse engineering, through staff turnover, through subpoena, through a single misconfigured repository. A key, by contrast, is a small value that can be generated per-user, rotated on a schedule, and revoked. Designing so that only the small, rotatable, compartmentalized thing must stay secret is simply good engineering risk management.

The opposite approach is security through obscurity: relying on the attacker not knowing how the system works. The decisive argument against it is not that obscurity never helps, but that you cannot measure it. You can state that AES-128 requires roughly 2^128 operations to brute force. You cannot state how long it will take someone to disassemble your binary, and the moment they do, your security drops to zero with no warning and no recovery path short of redesigning the product.

Two nuances are worth holding onto, because the principle is frequently overstated:

1. Obscurity is not forbidden as a supplementary layer. Not publishing your internal network diagram raises attacker cost. The rule is that obscurity may never be the load-bearing control.
2. Open source is not the same as Kerckhoffs compliance. The principle is about where security resides, not about licensing. A closed-source implementation of AES is Kerckhoffs-compliant; an open-source system whose security depends on a hardcoded "secret" constant is not.

The practical test is a thought experiment: if an attacker had my complete source code, my full design documents, and my hardware, but not my keys, what could they do? If the answer is "nothing," the design is sound. If the answer is "everything," the system has a secret that cannot be rotated.

Examples

  SECURITY THROUGH OBSCURITY            KERCKHOFFS-COMPLIANT
  ───────────────────────────           ────────────────────────
  Secret: the algorithm                 Secret: a 256-bit key
  Shared by: every copy shipped         Shared by: two endpoints
  Rotatable: no (requires redesign)     Rotatable: yes (seconds)
  Compromise scope: ALL users forever   Compromise scope: one key, one period
  Measurable strength: none             Measurable strength: 2**256
  Detection of leak: none               Detection: audit log, revocation

  Leak event ──► product is dead        Leak event ──► rotate, carry on

# ANTI-PATTERN: the secret is the code. Every shipped binary contains it,
# so one reverse-engineer compromises every deployment, permanently.
def obscure_encrypt(data: bytes) -> bytes:
    secret_offset = 0x5A              # discoverable in minutes with a debugger
    return bytes((b ^ secret_offset) for b in data)


# KERCKHOFFS-COMPLIANT: the code may be published in full. Security rests
# on a per-deployment key that can be rotated without changing the program.
from cryptography.hazmat.primitives.ciphers.aead import AESGCM
import os


def sound_encrypt(data: bytes, key: bytes) -> tuple[bytes, bytes]:
    nonce = os.urandom(12)
    # Publishing this entire function costs the defender nothing.
    return nonce, AESGCM(key).encrypt(nonce, data, None)

Question	Obscurity-based design	Kerckhoffs-based design
What must stay secret?	Design, code, constants	A key
How many parties hold it?	Everyone who has the product	The communicating parties
Can it be rotated?	No	Yes
Can strength be stated numerically?	No	Yes
What happens on disclosure?	Unrecoverable	Rotate the key

Key Takeaways

• Assume the attacker knows the algorithm, the implementation, and the protocol; design so that this knowledge does not help them.
• The core argument is rotatability: keys can be changed cheaply, designs cannot.
• Obscurity is acceptable as a defense-in-depth layer but never as the primary control, because its strength is unmeasurable and its failure is undetectable.
• Proprietary or closed-source does not imply non-compliance; depending on a shipped hardcoded secret does.
• Apply the test: "attacker has everything but the keys — what now?"

🧪 Practice

1. Find a hardcoded secret in any codebase you have access to (an API key, a default password, a salt constant) and write down the blast radius if the repository leaked.
2. Argue both sides: does hiding the version banner of a web server provide meaningful security? Distinguish between raising attacker cost and reducing attacker capability.
3. Redesign the obscure_encrypt function above so that it remains secure after publication, and state explicitly what new operational requirement your fix introduces.
4. Interview-style: "A vendor refuses to disclose their encryption algorithm, calling it a trade secret. What is your assessment?" Hint: separate the business reason for non-disclosure from the security reliance on non-disclosure, and consider what independent evidence (certification, published cryptanalysis, standard primitives) you would ask for instead.

Classical Ciphers: Caesar, Vigenere, Substitution

Theory

Classical ciphers protect nothing today, but they are the fastest route to understanding two ideas that still govern modern design: confusion (the relationship between key and ciphertext should be complex) and diffusion (a change in one plaintext character should affect many ciphertext characters). Classical ciphers have almost none of either, which is exactly why studying them is instructive.

The Caesar cipher shifts every letter by a fixed amount. The key is that amount, so the keyspace is 25 useful values. It is breakable by hand in seconds. Its lesson: a keyspace small enough to exhaust is no keyspace at all, regardless of how clever the transformation looks.

The monoalphabetic substitution cipher generalizes this: each plaintext letter maps to an arbitrary distinct ciphertext letter. The keyspace is 26! (about 2^88) — larger than a DES key — and yet it falls to a schoolchild with a pencil. This is the single most important lesson in the section: keyspace size is necessary but not sufficient. The cipher preserves the statistical fingerprint of the language, so the attacker never needs to guess the key directly; they reconstruct it piece by piece from frequency structure.

The Vigenere cipher was the first serious attempt to destroy that fingerprint. It uses a keyword, applying a different Caesar shift to each successive position and repeating the keyword cyclically. Because e is now encrypted differently depending on position, single-letter frequencies flatten out. This defeats naive frequency analysis — and it held a reputation as unbreakable for roughly three centuries. Its fatal flaw is the repetition: a keyword of length m means the cipher is really m interleaved Caesar ciphers. Once you determine m (via Kasiski examination of repeated ciphertext segments, or by the index of coincidence), you split the ciphertext into m columns and solve each as a trivial Caesar.

The structural lesson generalizes directly to modern cryptography: Vigenere is a stream cipher whose keystream repeats with period m. Keystream reuse is the vulnerability, and it is the same flaw that breaks a reused one-time pad, a reused AES-CTR nonce, and WEP. The cipher changed; the bug did not.

Examples

CAESAR (shift = 3)            keyspace = 25
  plain  A B C D E ... X Y Z
  cipher D E F G H ... A B C
  "ATTACK" -> "DWWDFN"

SUBSTITUTION (arbitrary bijection)   keyspace = 26! ~ 2**88
  plain  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
  cipher Q W E R T Y U I O P A S D F G H J K L Z X C V B N M
  "ATTACK" -> "QZZQEA"      ... yet broken by frequency analysis

VIGENERE (key = "KEY", repeating)    keyspace = 26**len(key)
  plain   A T T A C K A T D A W N
  key     K E Y K E Y K E Y K E Y     <-- period 3 == the weakness
  shift  10 4 24 10 4 24 10 4 24 ...
  cipher  K X R K G I K X B K A L

  Equivalent to three independent Caesar ciphers:
    positions 0,3,6,9  -> shift 10
    positions 1,4,7,10 -> shift 4
    positions 2,5,8,11 -> shift 24

import string
from collections import Counter

ALPHA = string.ascii_uppercase


def caesar(text: str, shift: int) -> str:
    """Encryption and decryption differ only in the sign of `shift`."""
    return "".join(
        ALPHA[(ALPHA.index(c) + shift) % 26] if c in ALPHA else c
        for c in text.upper()
    )


def break_caesar(ciphertext: str) -> tuple[int, str]:
    """Brute force: 25 candidates is not a keyspace. Score each candidate by
    how closely its letter frequencies match English, then take the best."""
    english_freq = "ETAOINSHRDLCUMWFGYPBVKJXQZ"
    best = max(
        range(26),
        key=lambda s: sum(
            # reward candidates whose common letters are English common letters
            (26 - english_freq.index(c)) if c in english_freq else 0
            for c in Counter(caesar(ciphertext, -s)).elements()
        ),
    )
    return best, caesar(ciphertext, -best)


def vigenere(text: str, key: str, decrypt: bool = False) -> str:
    sign = -1 if decrypt else 1
    letters = [c for c in text.upper() if c in ALPHA]
    out = []
    for i, c in enumerate(letters):
        # The key index cycles -- this modulo IS the structural weakness.
        shift = ALPHA.index(key.upper()[i % len(key)]) * sign
        out.append(ALPHA[(ALPHA.index(c) + shift) % 26])
    return "".join(out)


ct = vigenere("ATTACKATDAWN", "KEY")
print(ct)                                  # KXRKGIKXBKAL
print(vigenere(ct, "KEY", decrypt=True))   # ATTACKATDAWN
print(break_caesar(caesar("MEETATNOON", 7)))

Cipher	Key	Keyspace	Breaks via	Modern analogue of the flaw
Caesar	1 shift	25	Exhaustion	Insufficient key length
Substitution	Permutation of 26	26!	Frequency analysis	No diffusion; structure survives
Vigenere	Keyword, length m	26^m	Kasiski, index of coincidence	Keystream reuse / nonce reuse
Transposition	Permutation of positions	varies	Anagramming, bigram stats	Reordering is not confusion

Key Takeaways

• A large keyspace does not imply security: substitution has a 2^88 keyspace and is broken by hand.
• Caesar's lesson is exhaustion; substitution's lesson is preserved statistical structure; Vigenere's lesson is keystream repetition.
• Vigenere is literally a stream cipher with a short period, and its break is the same break as nonce reuse in AES-CTR.
• Classical ciphers lack diffusion: changing one plaintext letter changes exactly one ciphertext letter, which hands the attacker a per-character oracle.
• These ciphers belong in CTFs and teaching, never in production, and recognizing them quickly is a genuine practical skill.

🧪 Practice

1. Implement break_caesar yourself without looking at the version above, and test it on a 40-character English sentence and then on a 10-character one. Explain why the short case fails more often.
2. Encrypt the same plaintext with Vigenere using keys of length 1, 3, and 20. Compute the letter-frequency distribution of each ciphertext and describe how it changes.
3. Given the ciphertext LXFOPVEFRNHR and the knowledge that the key is three letters and the plaintext begins with ATT, recover the key. (This is a known-plaintext attack; note how little plaintext you needed.)
4. Interview-style: "Why was Vigenere considered unbreakable for 300 years, and what single property defeated it?" Hint: focus on what repeating the keyword does to the relationship between distant ciphertext positions, and how an attacker could detect the period without knowing the key.

Frequency Analysis and Cryptanalysis Basics

Theory

Cryptanalysis is the art of finding a shortcut — any method faster than trying every key. The foundational technique, and the mental model behind most others, is frequency analysis: natural-language plaintext is wildly non-uniform, and any cipher that preserves that non-uniformity leaks the plaintext even while hiding the key.

English letter frequencies are stable and well known (e around 12.7 percent, t 9.1 percent, a 8.2 percent, down to z at 0.07 percent). Digraphs (th, he, in) and trigraphs (the, and) are even more distinctive. A monoalphabetic cipher permutes the labels on this distribution but not its shape, so the attacker sorts ciphertext symbols by frequency, aligns the shape, and reads the message. The key is never guessed; it is derived.

The index of coincidence (IC) formalizes "how lumpy is this distribution" into one number: the probability that two randomly chosen characters from a text are identical. English runs about 0.067; uniform random text over 26 letters runs 0.038. This single statistic is powerful because it is key-independent — it tells you whether you are facing a monoalphabetic cipher (IC near 0.067), a polyalphabetic one (IC closer to 0.038), or properly random output, and for Vigenere it lets you recover the key length by testing candidate periods.

Beyond frequency, cryptanalysis is classified by what the attacker can obtain. This taxonomy matters because a cipher that is secure in one model may be broken in another, and modern standards demand security in the strongest models:

• Ciphertext-only: the attacker sees ciphertext. Weakest attacker, hardest attack.
• Known-plaintext: the attacker has some plaintext/ciphertext pairs. Realistic — file headers, HTTP boilerplate, and protocol fields are known plaintext.
• Chosen-plaintext (CPA): the attacker can get plaintexts of their choosing encrypted. Realistic whenever an attacker can trigger encryption, e.g. a web form echoed into an encrypted cookie.
• Chosen-ciphertext (CCA): the attacker can submit ciphertexts for decryption and observe the result — even just whether it errored. This is the model that padding-oracle attacks live in, and it is why modern systems require authenticated encryption.

Two classes of attack transcend the mathematics entirely. Side-channel attacks extract keys from physical behavior — timing, power draw, electromagnetic emission, cache occupancy — and they are the reason production code must use constant-time comparison and library-provided primitives. Brute force remains the baseline every attack is measured against: an attack "breaks" a cipher if it beats exhaustion, even if it is still computationally infeasible.

Examples

ENGLISH LETTER FREQUENCY (the shape a cipher must destroy)

 e |############# 12.7
 t |######### 9.1
 a |######## 8.2
 o |####### 7.5
 i |####### 7.0
 n |####### 6.7
 s |###### 6.3
 h |###### 6.1
 r |###### 6.0
 ...
 q |. 0.10
 z |. 0.07

Monoalphabetic substitution only RELABELS the bars:
 Q |############# 12.7   <- must be 'e'
 Z |######### 9.1        <- must be 't'

INDEX OF COINCIDENCE as a cipher classifier
  ~0.067  English plaintext, or monoalphabetic substitution
  ~0.045  Vigenere, short key
  ~0.038  Vigenere long key / random / modern cipher output

from collections import Counter


def index_of_coincidence(text: str) -> float:
    """Probability that two characters drawn at random are equal.
    Key-independent, so it classifies a cipher without breaking it."""
    letters = [c for c in text.upper() if c.isalpha()]
    n = len(letters)
    if n < 2:
        return 0.0
    counts = Counter(letters)
    # sum of f*(f-1) over all symbols, normalised by n*(n-1)
    return sum(f * (f - 1) for f in counts.values()) / (n * (n - 1))


def guess_vigenere_key_length(ciphertext: str, max_len: int = 20) -> int:
    """Split the ciphertext into m columns. If m is the true key length,
    each column is a Caesar cipher of English, so its IC jumps to ~0.067."""
    letters = [c for c in ciphertext.upper() if c.isalpha()]
    best_len, best_ic = 1, 0.0
    for m in range(1, max_len + 1):
        columns = ["".join(letters[i::m]) for i in range(m)]
        avg_ic = sum(index_of_coincidence(c) for c in columns) / m
        if avg_ic > best_ic:
            best_len, best_ic = m, avg_ic
    return best_len


# Side-channel awareness: this comparison leaks the position of the
# first differing byte through its runtime, which is enough to forge a MAC.
def insecure_compare(a: bytes, b: bytes) -> bool:
    if len(a) != len(b):
        return False
    for x, y in zip(a, b):
        if x != y:
            return False          # early return == timing leak
    return True


import hmac

# Constant-time: runtime depends on length only, never on content.
def secure_compare(a: bytes, b: bytes) -> bool:
    return hmac.compare_digest(a, b)

Attack model	What the attacker has	Real-world example
Ciphertext-only	Intercepted ciphertext	Passive network capture
Known-plaintext	Matching plaintext/ciphertext pairs	Fixed file headers, protocol magic bytes
Chosen-plaintext	Encryption of arbitrary chosen data	Attacker-controlled field inside an encrypted cookie (CRIME, BEAST)
Chosen-ciphertext	Decryption results or error signals	Padding oracle, Bleichenbacher RSA
Side-channel	Timing, power, EM, cache state	Key recovery from a non-constant-time compare
Brute force	Nothing but compute	DES exhaustion

Key Takeaways

• Frequency analysis works because plaintext is non-uniform; a modern cipher's output must be statistically indistinguishable from random.
• The index of coincidence classifies a cipher and recovers Vigenere key length without ever guessing a key.
• Attack models are ordered by attacker power; modern ciphers are required to resist chosen-plaintext and chosen-ciphertext attacks, not merely ciphertext-only.
• Known-plaintext is not an exotic assumption: headers, boilerplate, and protocol fields hand it to the attacker for free.
• Side channels bypass the mathematics entirely, which is why constant-time primitives and vetted libraries are non-negotiable.
• Any method faster than exhaustion counts as a break, even when it remains computationally out of reach.

🧪 Practice

1. Compute the index of coincidence for a paragraph of English, the same paragraph with a Caesar shift, and 500 bytes from os.urandom mapped to letters. Explain the three results.
2. Use guess_vigenere_key_length on a ciphertext you generate with a 7-letter key and at least 600 characters of plaintext. Then shorten the plaintext to 60 characters and explain why the estimate degrades.
3. Write a timing harness that distinguishes insecure_compare from secure_compare on 32-byte inputs, and describe what an attacker would do with that signal to forge a 32-byte tag byte by byte.
4. Interview-style: "Why do modern standards insist on chosen-ciphertext security when a real attacker usually only sees ciphertext?" Hint: think about what an error message, a response-time difference, or an HTTP status code reveals, and how an attacker who can replay modified ciphertexts to a live server effectively becomes a decryption oracle.

Entropy and Randomness

Theory

Every cryptographic guarantee reduces to one scarce resource: unpredictability. A 256-bit key is strong only if an attacker genuinely has 2^256 candidates to consider. If your "random" key came from rand() seeded with the current second, the attacker has a few million candidates, and the algorithm's strength is irrelevant. Entropy is how we measure that unpredictability.

In the information-theoretic sense (Shannon entropy), entropy measures the average uncertainty of a random variable in bits. For cryptography the more useful notion is min-entropy: the uncertainty of the most likely outcome, because an attacker guesses the most likely candidate first. A distribution where one value occurs 50 percent of the time has at most 1 bit of min-entropy no matter how many other values exist.

The crucial and frequently misunderstood point is that entropy is a property of the generating process, not of the output string. The 128-bit value 00000000000000000000000000000000 is exactly as likely as any other output of a good generator; it is not "low entropy." Conversely, a password like Tr0ub4dor&3 looks random but came from a predictable human process and carries perhaps 28 bits of real entropy. The question is never "does this look random?" but "how many guesses would an attacker need, given everything they know about how it was produced?"

The practical entropy formula for a value chosen uniformly from a known set is log2(size of set). This is why:

• A 4-digit PIN has log2(10^4) which is about 13.3 bits — exhaustible instantly.
• A 12-character password from a 94-character printable set has about 78 bits — if truly uniform, which human-chosen passwords never are.
• Four words from a 7,776-word Diceware list has log2(7776^4) which is about 51.7 bits — and unlike the password, this figure is honest, because the selection really was uniform.

Operating systems collect entropy from physical processes that are hard to predict or observe: interrupt timings, disk seek jitter, thermal noise in dedicated hardware generators (Intel RDRAND, ARM RNDR). This raw entropy is then fed into a cryptographically secure pseudo-random number generator (CSPRNG) that stretches a small seed into an unlimited stream. This is the right architecture: physical entropy is slow and of uncertain quality, so you harvest enough of it once to seed a fast deterministic generator whose output is computationally indistinguishable from random.

Two failure modes dominate in practice. Insufficient seeding happens on embedded devices and freshly booted VMs that generate keys before the entropy pool has filled — a 2012 study found tens of thousands of internet hosts sharing RSA keys for exactly this reason. Entropy reuse happens when a VM image or container template is cloned after seeding, so every instance produces the identical "random" stream.

Examples

ENTROPY IS A PROPERTY OF THE PROCESS, NOT THE STRING

  Process: os.urandom(16)                  Process: "pick a word + year"
  Output:  3f a1 00 00 00 00 7c 9b ...     Output:  Summer2024!
  Looks:   random                          Looks:   complex
  Entropy: 128 bits                        Entropy: ~16 bits
  Guesses: 2**128                          Guesses: a few thousand

SEEDING AND STRETCHING

  PHYSICAL ENTROPY          CSPRNG                 OUTPUT
  interrupt timing  ──┐
  disk jitter       ──┤──► [ pool ] ──seed──► [ ChaCha20 ] ──► unlimited
  RDRAND noise      ──┤      (slow,            (fast,          keystream
  key/mouse timing  ──┘     collected once)   deterministic)

  FAILURE: if the seed has only 20 bits of real entropy, the CSPRNG
  output has only 20 bits of entropy, no matter how many bytes you read.

import math
import os
import secrets
import string


def entropy_bits(alphabet_size: int, length: int) -> float:
    """Honest entropy for a UNIFORM selection. Using this formula on a
    human-chosen password overstates its strength by 40+ bits."""
    return length * math.log2(alphabet_size)


print(f"{entropy_bits(10, 4):.1f} bits")    # 4-digit PIN      -> 13.3
print(f"{entropy_bits(94, 12):.1f} bits")   # 12 printable     -> 78.7
print(f"{entropy_bits(7776, 4):.1f} bits")  # 4 Diceware words -> 51.7

# WRONG: `random` is a Mersenne Twister. It is excellent for simulations
# and useless for secrets: 624 consecutive outputs reveal its entire state,
# after which every future and past value is computable.
import random
weak_token = "".join(random.choice(string.ascii_letters) for _ in range(32))

# RIGHT: `secrets` draws from the OS CSPRNG, which is seeded from
# physical entropy and designed to resist state recovery.
strong_token = secrets.token_urlsafe(32)        # ~256 bits of entropy
strong_key = os.urandom(32)                     # raw bytes for a key

# Uniform selection from a wordlist: entropy you can actually defend.
words = ["anchor", "bramble", "cinder", "dovetail"]   # a real list has 7776
passphrase = "-".join(secrets.choice(words) for _ in range(4))

Source	Suitable for keys?	Why
random / Math.random() / rand()	No	Predictable from observed output; state recoverable
time()-derived values	No	Tiny search space; often guessable to the second
Process ID, MAC address, UUIDv1	No	Low entropy, frequently enumerable
os.urandom / /dev/urandom / getrandom(2)	Yes	OS CSPRNG, properly seeded after boot
secrets (Python), crypto.randomBytes (Node), SecureRandom (Java)	Yes	Documented CSPRNG wrappers over the above
Hardware RNG (RDRAND, TPM)	Yes, as a seed contributor	Fast but opaque; best mixed into the OS pool

Key Takeaways

• Entropy measures how many guesses an attacker needs; it is a property of the generating process, never of how random the output looks.
• Min-entropy is the security-relevant measure because attackers try the most likely candidate first.
• log2(alphabet^length) is only valid for uniform selection; applying it to human-chosen passwords systematically overstates strength.
• Non-cryptographic PRNGs such as the Mersenne Twister leak their entire state after enough observed output, making all past and future values computable.
• The standard architecture is slow physical entropy seeding a fast CSPRNG; the dominant real-world failures are early-boot under-seeding and cloned-image seed reuse.
• Use the platform's documented cryptographic source and nothing else.

🧪 Practice

1. Compute the honest entropy of your own password-construction habit (describe the process first, then count the choices), and compare it to a four-word Diceware passphrase.
2. Generate 1,000 values with Python's random.random() after random.seed(1), then do it again in a fresh process. Explain what the identical output implies for any system that used random to issue session tokens.
3. Explain why /dev/urandom is the correct choice on a long-running Linux server but why an IoT device generating a TLS key three seconds after first boot is a genuine risk. Name the syscall that solves it.
4. Interview-style: "A code review shows session tokens generated with Math.random(). How severe is this, and how would you demonstrate the impact?" Hint: consider whether an attacker who collects several legitimate tokens can recover generator state, and what that lets them do to other users' sessions — frame the severity in terms of account takeover, not "weak randomness."

Cryptographically Secure Random Number Generation

Theory

A CSPRNG is a deterministic algorithm that turns a short seed into a long stream which no computationally bounded adversary can distinguish from true randomness. Understanding what "cryptographically secure" adds over an ordinary PRNG makes the choice of API obvious rather than arbitrary.

An ordinary PRNG is designed for statistical quality: the output should pass tests for uniformity and independence so that simulations are unbiased. That is all. The Mersenne Twister is superb at this and is completely insecure, because statistical quality says nothing about an adversary who is trying to predict the next value.

A CSPRNG must satisfy two additional properties, and they are the whole point:

1. Next-bit unpredictability. Given the first k output bits, no efficient algorithm can predict bit k+1 better than guessing. This is what the Mersenne Twister spectacularly fails: 624 consecutive 32-bit outputs fully determine its internal state.
2. State compromise resilience, in two directions. Backtracking resistance (forward secrecy) means that an attacker who steals the current state cannot recover previously generated output — crucial because yesterday's output was yesterday's session keys. Prediction resistance means that after a state compromise, mixing in fresh entropy restores security going forward.

Modern CSPRNGs are built from the primitives in the rest of this chapter. Linux's generator uses ChaCha20 keyed from the entropy pool; others use AES in counter mode (CTR_DRBG) or a hash construction (Hash_DRBG, HMAC_DRBG) as specified in NIST SP 800-90A. The design is the same in each case: an internal state, a cryptographic function that stretches it into output, and a rule for ratcheting the state forward so old output cannot be recomputed.

On the API question, modern guidance is unambiguous and contradicts a lot of older internet advice:

• Use the OS generator. On Linux, getrandom(2) or /dev/urandom. The historical advice to prefer /dev/random for "real" randomness is obsolete: since Linux 5.6 /dev/random blocks only before the pool is initialized, and the two are cryptographically equivalent afterwards. The genuine concern was only ever pre-initialization use, and getrandom(2) solves it correctly by blocking exactly once at early boot.
• Never roll your own, and never seed a CSPRNG from a timestamp, a PID, or a hash of several weak values. Mixing weak sources does not create entropy.
• Beware of fork and VM cloning. Any userspace generator with its own cached state can emit identical streams in parent and child, or across cloned VM instances. This is the main argument for calling the kernel each time rather than maintaining your own pool.

The last practical trap is modulo bias. Reducing a uniform random integer with % to get a value in a range skews the distribution toward low values whenever the range does not divide the generator's output space evenly. For a shuffle this is a subtle statistical flaw; for generating a one-time passcode or a nonce it is a real reduction in entropy. Use rejection sampling, or the standard library function that already does it.

Examples

PRNG vs CSPRNG

  Mersenne Twister                      ChaCha20-based CSPRNG
  ────────────────                      ─────────────────────
  Passes statistical tests: yes         Passes statistical tests: yes
  Next-bit unpredictable:  NO           Next-bit unpredictable:  yes
  State recoverable:  from 624 outputs  State recoverable:  no
  Backtracking resistant:  no           Backtracking resistant:  yes
  Use for: simulation, games            Use for: keys, tokens, nonces, IVs

STATE RATCHET (why old output stays secret)

  seed ──► [state0] ──► output0
              │
              └─ ratchet (one-way) ──► [state1] ──► output1
                                          │
                                          └─ ratchet ──► [state2] ──► ...

  Attacker steals state2:  can compute output2, output3, ...
                           CANNOT compute output1 or output0.

import os
import secrets

# --- Correct generation for each common need -------------------------------
key = secrets.token_bytes(32)          # 256-bit symmetric key
session_id = secrets.token_urlsafe(32) # URL-safe session token
nonce = os.urandom(12)                 # AES-GCM nonce
otp = secrets.randbelow(1_000_000)     # 6-digit code, NO modulo bias

# --- Modulo bias, demonstrated --------------------------------------------
# A byte is uniform over 0..255. Taking % 10 maps six extra values
# (250..255) onto digits 0..5, so low digits are ~2.4% more likely.
def biased_digit() -> int:
    return os.urandom(1)[0] % 10       # WRONG for anything security-relevant


def unbiased_digit() -> int:
    """Rejection sampling: discard the values that would cause the skew."""
    limit = 256 - (256 % 10)           # 250: the largest clean multiple
    while True:
        b = os.urandom(1)[0]
        if b < limit:
            return b % 10


# --- The fork/clone hazard -------------------------------------------------
# A userspace generator caching state will produce IDENTICAL output in both
# processes. Calling the kernel per request avoids the problem entirely.
pid = os.fork()
value = os.urandom(8)                  # safe: different in parent and child
if pid == 0:
    os._exit(0)

Need	Python	Node.js	Java	Go
Random bytes	secrets.token_bytes(n)	crypto.randomBytes(n)	SecureRandom.getInstanceStrong()	crypto/rand.Read
Bounded integer	secrets.randbelow(n)	crypto.randomInt(n)	SecureRandom.nextInt(n)	rand.Int(rand.Reader, max)
URL-safe token	secrets.token_urlsafe(n)	randomBytes(n).toString('base64url')	encode SecureRandom bytes	encode crypto/rand bytes
UUID for secrets	secrets.token_hex(16)	crypto.randomUUID() (v4)	UUID.randomUUID() (v4)	crypto/rand based v4
Never use	random	Math.random()	java.util.Random	math/rand

Key Takeaways

• A CSPRNG adds next-bit unpredictability and state-compromise resilience to ordinary statistical quality; those two properties are the entire security difference.
• Backtracking resistance protects yesterday's keys when today's state leaks, which is why the internal state is ratcheted one-way.
• Call the OS generator (getrandom(2), /dev/urandom, or the language's documented wrapper); the old /dev/random versus /dev/urandom debate is resolved and only ever concerned early boot.
• Never seed from timestamps, PIDs, or combinations of weak values: mixing weak sources does not manufacture entropy.
• Userspace generators with cached state break under fork and VM cloning; stateless kernel calls do not.
• Avoid modulo bias by using rejection sampling or the standard bounded-integer function.

🧪 Practice

1. Generate one million digits with biased_digit and one million with unbiased_digit, tabulate the counts, and quantify the skew. State how many bits of entropy are lost per digit.
2. For your primary language, find the documented cryptographic random API and the non-cryptographic one, then grep a codebase you work on for uses of the latter in security-relevant positions.
3. Explain, in terms of backtracking resistance, why a long-lived server process that caches a seeded generator in memory is a worse design than calling getrandom(2) per request.
4. Interview-style: "Your team builds a VM image that pre-seeds the application's random generator at build time to speed up boot. What is your concern?" Hint: consider what every instance launched from that image shares, and which secrets get generated in the first seconds of a machine's life.

One-Time Pad and Perfect Secrecy

Theory

The one-time pad (OTP) is the only cipher proven to be unbreakable — not "unbroken so far," but mathematically impossible to break regardless of the attacker's computing power. Studying it is worthwhile for two reasons: it defines the theoretical ceiling that practical cryptography deliberately trades away, and its failure mode under key reuse is the single most common real-world crypto bug.

The construction could not be simpler. Take a key that is truly random, exactly as long as the plaintext, and never reused. XOR it with the plaintext. That is the entire cipher.

The security claim is perfect secrecy (Shannon, 1949): the ciphertext is statistically independent of the plaintext, so P(plaintext | ciphertext) = P(plaintext). Observing the ciphertext teaches the attacker nothing at all. The reason is that for any ciphertext of length n, every possible plaintext of length n has a corresponding key that produces it. A 10-character ciphertext is equally consistent with ATTACKDAWN, RETREATNOW, and BUYMILKNOW. Brute force does not fail because it is slow; it fails because it produces every possible message with equal validity, and nothing distinguishes the right one.

Shannon also proved the cost: perfect secrecy requires the key to have at least as much entropy as the message. This is not an artifact of the XOR construction; it is a hard bound. And it makes OTP almost useless in practice, because you face a strictly harder problem than the one you started with — securely distributing n bytes of key in order to securely send n bytes of message. OTP has seen genuine use where that trade is acceptable: diplomatic cables, the Moscow-Washington hotline, numbers-station broadcasts to field agents given a pad in advance.

Practical cryptography therefore abandons perfect secrecy for computational security: AES with a 128-bit key does not hide the plaintext from an attacker with infinite compute, but it hides it from every attacker who will ever exist. A fixed-size key protecting unlimited data is worth the theoretical downgrade.

The failure mode is where OTP earns its place in a security curriculum. Reuse one pad for two messages and the key cancels out:

C1 = P1 XOR K
C2 = P2 XOR K
C1 XOR C2 = P1 XOR P2        <- the key is gone

The attacker now holds the XOR of two plaintexts, which is readily solvable by crib dragging: guess a probable word, slide it along, and when the guess is correct at that position the output reveals fragments of the other message. This is exactly the attack that broke the Soviet cables in the VENONA project (duplicated pad pages), and exactly the attack behind reused AES-CTR nonces, reused stream-cipher keystreams, and WEP's 24-bit IV collisions. A second critical weakness: XOR provides no integrity whatsoever. An attacker who knows the plaintext at some offset can flip any bit of it with a matching flip in the ciphertext, undetected — which is why authenticated encryption exists.

Examples

PERFECT SECRECY: every plaintext remains possible

  ciphertext:  7f 3a 91 ...
     with key K1  ->  "ATTACK AT DAWN"
     with key K2  ->  "RETREAT TO BASE"
     with key K3  ->  "BUY MORE COFFEE"
  All keys equally likely => ciphertext carries ZERO information.

KEY REUSE: the key cancels, the plaintexts remain

  C1 = P1 (+) K
  C2 = P2 (+) K
  ────────────────
  C1 (+) C2 = P1 (+) P2        (+) = XOR, K has vanished

  Crib dragging on P1 (+) P2, guessing " the ":
    offset 0:  "?#x!"   nonsense -> wrong position
    offset 7:  "ance"   English  -> correct, reveals both messages

import os


def otp(data: bytes, key: bytes) -> bytes:
    """Encryption and decryption are the same operation. The security rests
    entirely on the three conditions on `key`, not on this function."""
    if len(key) < len(data):
        raise ValueError("key must be at least as long as the data")
    return bytes(d ^ k for d, k in zip(data, key))


# Used correctly: one random pad, one message, pad destroyed afterwards.
message = b"ATTACK AT DAWN"
pad = os.urandom(len(message))          # truly random, message-length
ciphertext = otp(message, pad)
assert otp(ciphertext, pad) == message

# Used incorrectly: the same pad twice. This is a total break.
m1 = b"ATTACK AT DAWN"
m2 = b"RETREAT AT WILL"
shared = os.urandom(max(len(m1), len(m2)))
c1, c2 = otp(m1, shared), otp(m2, shared)

# The attacker needs no key at all:
xor_of_plaintexts = bytes(a ^ b for a, b in zip(c1, c2))


def crib_drag(xored: bytes, crib: bytes) -> None:
    """Slide a probable word along P1^P2. A correct guess at the right
    offset emits readable text from the OTHER message."""
    for offset in range(len(xored) - len(crib) + 1):
        window = xored[offset:offset + len(crib)]
        candidate = bytes(x ^ c for x, c in zip(window, crib))
        if all(32 <= b < 127 for b in candidate):   # printable => promising
            print(f"offset {offset:2d}: {candidate!r}")


crib_drag(xor_of_plaintexts, b"ATTACK")

# Malleability: no integrity, so targeted modification is undetectable.
# Knowing the plaintext starts with "ATTACK", rewrite it to "DEFEND":
forged = bytes(c ^ a ^ b for c, a, b in zip(c1, b"ATTACK", b"DEFEND"))
# The recipient decrypts `forged` with the correct pad and sees "DEFEND".

Property	One-time pad	AES-256-GCM
Security notion	Perfect (information-theoretic)	Computational
Secure against unlimited compute	Yes	No (but infeasible in practice)
Key size	Equal to total plaintext	32 bytes, unlimited plaintext
Key reuse consequence	Total break via XOR	Total break (GCM nonce reuse leaks the auth key)
Integrity protection	None	Built in (authentication tag)
Practical for internet traffic	No	Yes

Key Takeaways

• OTP achieves perfect secrecy: the ciphertext is statistically independent of the plaintext, so unlimited compute does not help.
• The three conditions — truly random, message-length, never reused — are all mandatory, and violating any one destroys the guarantee.
• Shannon's bound makes perfect secrecy impractical: the key must carry at least as much entropy as all the data it will ever protect.
• Real systems deliberately accept computational security in exchange for short, reusable keys.
• Key or keystream reuse cancels the key and yields P1 XOR P2, solvable by crib dragging; this is the same bug as nonce reuse in modern stream ciphers and GCM.
• XOR alone is malleable and offers no integrity, which is why authenticated encryption is mandatory in practice.

🧪 Practice

1. Encrypt two different English sentences of equal length with the same random pad, then recover both using only the two ciphertexts and crib dragging with the word the.
2. Explain precisely why brute-forcing an OTP ciphertext is futile, using a 5-byte example and counting both the number of keys and the number of plausible plaintexts.
3. Demonstrate malleability: given an OTP ciphertext of Transfer 100 USD and knowledge of that plaintext, produce a ciphertext that decrypts to Transfer 900 USD without knowing the pad.
4. Interview-style: "A vendor advertises 'unbreakable one-time-pad encryption' in a messaging app. What do you ask them?" Hint: focus on how pad material is generated, how it is distributed to both endpoints, how much of it exists, and what happens when it runs out — the answer to the last question is usually where the real cipher is hiding.

<a id="32-symmetric-cryptography"></a>

3.2 Symmetric Cryptography

Symmetric cryptography is where the actual bulk encryption of the world happens: every TLS session, every encrypted disk, every VPN tunnel protects its payload with a symmetric cipher. The algorithms are mature and essentially unbroken, so this section concentrates on the layer where real systems fail — modes of operation, IVs, nonces, padding, and key distribution.

Block Ciphers vs. Stream Ciphers

Theory

A symmetric cipher uses the same key to encrypt and decrypt. There are two structural families, and the distinction determines which failure modes you must guard against.

A block cipher is a keyed permutation on fixed-size blocks: AES maps 16 bytes to 16 bytes, invertibly, with the key selecting one permutation out of an astronomically large family. The key property is that it is a permutation — bijective, so decryption is possible — and that it behaves like a randomly chosen one. The limitation is obvious: real messages are not exactly 16 bytes. Handling arbitrary lengths requires a mode of operation (the next topics), and essentially all block-cipher vulnerabilities in practice live in the mode, not in the cipher.

A stream cipher generates a pseudo-random keystream from the key and a nonce, then XORs it with the plaintext byte by byte. Conceptually it is a one-time pad where the pad is produced by a CSPRNG instead of being shipped in advance. This buys length flexibility (no padding, ciphertext is exactly plaintext length) and low latency (a byte can be encrypted and sent immediately), which is why stream ciphers suit voice, video, and constrained hardware.

The trade-offs follow directly from the structures:

	Block cipher	Stream cipher
Unit of operation	Fixed block (AES: 128 bits)	Byte or bit
Ciphertext length	Padded up to a block multiple	Exactly plaintext length
Random access	Yes, in CTR-like modes	Yes, if the keystream is seekable
Padding needed	Yes (ECB, CBC)	No
Dominant failure mode	Mode misuse (ECB, padding oracle)	Keystream reuse
Examples	AES, 3DES, Camellia, Blowfish	ChaCha20, RC4 (broken), Salsa20

The unifying insight is that the line between the two families is blurry in practice. A block cipher in counter mode (CTR) is a stream cipher: it produces a keystream by encrypting successive counter values and XORs that with the plaintext. AES-CTR and ChaCha20 are used interchangeably in TLS. So the useful question is not "block or stream?" but "what does this construction require of me, and what happens if I get it wrong?"

For stream constructions, the requirement is always the same and always absolute: never reuse a (key, nonce) pair. The consequence of violating it is the XOR-of-plaintexts break from the one-time pad topic. For block modes with padding, the requirement is to authenticate before decrypting, or padding becomes a decryption oracle.

Examples

BLOCK CIPHER: a keyed permutation on fixed-size blocks

   16 bytes in                              16 bytes out
  ┌──────────────┐    ┌─────────────┐     ┌──────────────┐
  │ 54 68 69 73..│──► │ AES-128(k)  │ ──► │ a7 3f 91 0c..│
  └──────────────┘    └─────────────┘     └──────────────┘
   Needs a MODE to handle messages that are not exactly 16 bytes.

STREAM CIPHER: generate a keystream, XOR it in

  key + nonce ──► [ keystream generator ] ──► e3 a1 77 2b 9f ...
                                                 (+)  XOR
  plaintext                                 "Hello, world!"
                                                  ║
  ciphertext                                ab cd ef ...
   No padding. Ciphertext length == plaintext length.
   ABSOLUTE RULE: never repeat (key, nonce).

CTR MODE: a block cipher BECOMING a stream cipher

  nonce||1 ─►[AES(k)]─► ks1 ─┐
  nonce||2 ─►[AES(k)]─► ks2 ─┤── XOR with plaintext blocks
  nonce||3 ─►[AES(k)]─► ks3 ─┘

import os

from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes

key = os.urandom(32)
plaintext = b"Symmetric ciphers do the bulk work."   # 35 bytes

# BLOCK CIPHER in CBC: output must be a multiple of 16, so padding is needed.
from cryptography.hazmat.primitives import padding as sym_padding

iv = os.urandom(16)
padder = sym_padding.PKCS7(128).padder()
padded = padder.update(plaintext) + padder.finalize()      # 35 -> 48 bytes
enc = Cipher(algorithms.AES(key), modes.CBC(iv)).encryptor()
cbc_ct = enc.update(padded) + enc.finalize()
print(len(plaintext), len(cbc_ct))                         # 35 48

# STREAM CIPHER (ChaCha20): no padding, length preserved.
nonce = os.urandom(16)
enc = Cipher(algorithms.ChaCha20(key, nonce), mode=None).encryptor()
stream_ct = enc.update(plaintext)
print(len(plaintext), len(stream_ct))                      # 35 35

# BLOCK CIPHER BEHAVING AS A STREAM CIPHER (AES-CTR): also length-preserving.
ctr_nonce = os.urandom(16)
enc = Cipher(algorithms.AES(key), modes.CTR(ctr_nonce)).encryptor()
ctr_ct = enc.update(plaintext)
print(len(plaintext), len(ctr_ct))                         # 35 35

Key Takeaways

• A block cipher is a keyed permutation on a fixed block size and requires a mode of operation to handle real messages.
• A stream cipher XORs a generated keystream into the plaintext, giving exact-length ciphertext and no padding.
• CTR mode turns a block cipher into a stream cipher, so the categories overlap in practice.
• Stream constructions fail catastrophically on (key, nonce) reuse; padded block modes fail via padding oracles when unauthenticated.
• Choose based on operational constraints (length preservation, latency, hardware) and then satisfy that construction's non-negotiable requirement.
• RC4 is the canonical broken stream cipher and must never be used; ChaCha20 is the modern default where AES hardware acceleration is unavailable.

🧪 Practice

1. Encrypt the same 20-byte plaintext with AES-CBC, AES-CTR, and ChaCha20. Record each ciphertext length and explain the differences.
2. Explain why AES-CTR needs no padding even though AES is a block cipher, by describing what the cipher is actually applied to in CTR mode.
3. For each of these use cases, choose block or stream and justify it: full-disk encryption with random-access reads, a real-time VoIP stream, encrypting a 40-byte database field, a firmware update blob on a microcontroller with no AES hardware.
4. Interview-style: "You see AES-CTR in a design document with no mention of nonces. What do you ask?" Hint: establish how the nonce is generated and whether any key is ever used for more than one message — then describe what you would be able to do with two ciphertexts sharing a nonce.

DES, 3DES, and Their Weaknesses

Theory

DES (Data Encryption Standard) was standardized in 1977 and dominated commercial cryptography for two decades. It matters today for three reasons: it is still encountered in legacy systems and payment hardware, its demise is the clearest case study in key-length economics, and 3DES's specific flaws explain several modern design rules.

DES is a 16-round Feistel network with a 64-bit block and a 56-bit effective key (the 64-bit key includes 8 parity bits). The Feistel structure is elegant: split the block in half, apply a round function to one half, XOR it into the other, swap. Because the XOR is self-inverting, decryption is the same circuit with the round keys reversed, so the round function need not be invertible. This mattered enormously for 1970s hardware cost, and the pattern reappears in many later ciphers.

DES's fatal flaw was never its structure — differential and linear cryptanalysis reduced its strength somewhat, but the S-boxes turned out to be remarkably well designed. The flaw was 56 bits. This was already contentious at standardization, and Moore's law did the rest:

• 1977: Diffie and Hellman estimate a 20 million dollar machine could break DES in a day.
• 1998: the EFF builds "Deep Crack" for about 250,000 dollars; it recovers a key in 56 hours.
• 1999: Deep Crack with distributed.net does it in 22 hours.
• Today: a 56-bit keyspace falls to rented cloud compute or an FPGA cluster for a trivial sum.

3DES (Triple DES) was the stopgap: apply DES three times as E(k3, D(k2, E(k1, plaintext))). The encrypt-decrypt-encrypt ordering is a backwards-compatibility trick — setting all three keys equal reduces it to single DES, so new hardware could still talk to old. Why three applications rather than two? Because double encryption gains almost nothing against a meet-in-the-middle attack: the attacker encrypts a known plaintext under all 2^56 values of k1, decrypts the ciphertext under all 2^56 values of k2, and looks for a match, bringing 2^112 work down to roughly 2^57 operations with large storage. Triple DES with three independent keys provides about 112 bits of security rather than the nominal 168 — still enough, in key-length terms.

But 3DES is deprecated anyway, and the reason is instructive: its 64-bit block size, not its key. Under CBC, a birthday collision among ciphertext blocks becomes likely after roughly 2^32 blocks (about 32 GB) under one key, and such a collision leaks the XOR of plaintext blocks. The Sweet32 attack (2016) turned this into a practical break of long-lived 3DES TLS and OpenVPN sessions. NIST disallowed 3DES for new applications in 2017 and withdrew it entirely as of 2023.

The design lessons generalize: key length is a floor that erodes predictably with time, block size imposes a hard limit on data per key, and composing a weak primitive multiple times produces less strength than naive arithmetic suggests.

Examples

FEISTEL ROUND (why DES decryption reuses the encryption circuit)

   L(i)            R(i)
    │               │
    │        ┌──────┴──────┐
    │        │  F(R, k(i)) │     F need not be invertible
    │        └──────┬──────┘
    └──── XOR ◄─────┘
      │
      └──► becomes R(i+1);   R(i) becomes L(i+1)

   Inverse: run the same rounds with k(i) applied in reverse order.

3DES: ENCRYPT-DECRYPT-ENCRYPT

  P ─►[ E(k1) ]─►[ D(k2) ]─►[ E(k3) ]─► C
  If k1 == k2 == k3, this collapses to single DES (backwards compatible).

WHY NOT DOUBLE DES -- meet in the middle

  Attacker holds one (P, C) pair:
    forward:  store E(k1, P) for all 2**56 k1      -> a table
    backward: compute D(k2, C) for all 2**56 k2    -> look up in the table
    a match reveals (k1, k2) in ~2**57 work, not 2**112.

SWEET32: the 64-bit block is the real killer
  blocks under one key:  2**32 (~32 GB)  =>  collision likely
  CBC collision C(i) == C(j)  =>  P(i) XOR P(j) leaks

# Legacy-only: modern libraries mark these as deprecated/insecure on purpose.
from cryptography.hazmat.decrepit.ciphers.algorithms import TripleDES
from cryptography.hazmat.primitives.ciphers import Cipher, modes
import os

key = os.urandom(24)        # 3 x 8 bytes = 168 nominal, ~112 effective bits
iv = os.urandom(8)          # 8 bytes: the 64-bit BLOCK is the problem
enc = Cipher(TripleDES(key), modes.CBC(iv)).encryptor()
ct = enc.update(b"legacy!!") + enc.finalize()


def sweet32_safe_bytes(block_bits: int) -> float:
    """Data limit per key before a CBC block collision becomes likely.
    Birthday bound: collisions appear around 2**(n/2) blocks."""
    blocks = 2 ** (block_bits / 2)
    return blocks * (block_bits / 8)


print(f"3DES  (64-bit block): {sweet32_safe_bytes(64) / 2**30:>12,.0f} GiB")
print(f"AES  (128-bit block): {sweet32_safe_bytes(128) / 2**60:>12,.0f} EiB")
# 3DES:  ~32 GiB per key -- reachable in a single long-lived TLS session.
# AES:   ~256 EiB per key -- unreachable in practice.

Cipher	Block	Key (nominal)	Key (effective)	Status	Killed by
DES	64 bits	56 bits	56 bits	Broken	Keyspace exhaustion (1998)
2DES	64 bits	112 bits	~57 bits	Never standardized	Meet-in-the-middle
3DES (3 keys)	64 bits	168 bits	~112 bits	Withdrawn 2023	Sweet32 (block size)
3DES (2 keys)	64 bits	112 bits	~80 bits	Disallowed	Known-plaintext trade-offs
AES-128	128 bits	128 bits	128 bits	Current	—

Key Takeaways

• DES's Feistel structure is sound and influential; it was killed purely by a 56-bit keyspace, exactly as predicted at standardization.
• Double encryption is near-worthless because meet-in-the-middle halves the exponent; this is why 3DES uses three applications.
• 3DES's EDE ordering exists for backwards compatibility with single DES, not for security.
• 3DES is deprecated because of its 64-bit block size, not its key length: Sweet32 exploits birthday collisions after roughly 32 GB under one key.
• Block size caps how much data a single key may protect; AES's 128-bit block raises that cap beyond practical reach.
• Treat any discovery of DES or 3DES in a live system as a finding, and check for 64-bit-block ciphers in long-lived sessions specifically.

🧪 Practice

1. Compute the data-per-key limit for a 64-bit-block and a 128-bit-block cipher using the birthday bound, and explain why one is a practical concern and the other is not.
2. Describe the meet-in-the-middle attack on 2DES precisely, including the storage requirement, and explain why 3DES is not similarly reduced to 2^57.
3. Audit a TLS configuration (for example with nmap --script ssl-enum-ciphers against a host you own) and identify any 3DES or 64-bit-block cipher suites, then write the remediation.
4. Interview-style: "A payment terminal vendor says 3DES is still fine because 112-bit security exceeds your 100-bit policy floor. How do you respond?" Hint: the key-length argument is the wrong axis — redirect to block size, data volume per key, and session lifetime, and ask how much traffic a single key protects.

AES Structure and Key Sizes

Theory

AES (Advanced Encryption Standard) is the symmetric cipher underlying essentially all modern encryption. It was selected in 2001 through an open, five-year, international competition — originally the Rijndael submission by Daemen and Rijmen — and that open process is a large part of why it is trusted. Twenty-five years of public cryptanalysis has produced no attack meaningfully better than brute force on the full cipher.

Unlike DES, AES is not a Feistel network; it is a substitution-permutation network (SPN) operating on the whole 128-bit block at once. The block is arranged as a 4x4 matrix of bytes (the "state"), and each round applies four transformations:

1. SubBytes — each byte is replaced via a fixed 8-bit S-box, built from inversion in the finite field GF(2^8). This provides confusion: a highly non-linear relationship between input and output. The algebraic construction (rather than a hand-tuned table like DES's) is what gives provable resistance to differential and linear cryptanalysis.
2. ShiftRows — row i is rotated left by i bytes. Together with the next step this provides diffusion across columns.
3. MixColumns — each column is multiplied by a fixed matrix in GF(2^8), mixing the four bytes of a column into each other. After two rounds, every output bit depends on every input bit — full diffusion.
4. AddRoundKey — XOR the state with a round key derived from the master key by the key schedule.

The number of rounds scales with key size: 10 rounds for AES-128, 12 for AES-192, 14 for AES-256. The extra rounds exist because a longer key schedule offers more surface for related-key attacks; the designers added margin rather than keeping rounds constant.

On key size selection, the practical guidance is less dramatic than marketing suggests. AES-128 provides 128 bits of security, which is beyond any foreseeable classical brute force: even at a trillion trillion keys per second, exhausting 2^128 takes vastly longer than the age of the universe. AES-256 is chosen for three real reasons: regulatory or policy mandates (NSA CNSA requires it for classified data), protection against hypothetical quantum attacks (Grover's algorithm gives a square-root speedup, so AES-256 retains roughly 128-bit post-quantum security while AES-128 drops to roughly 64), and the fact that the cost difference is only about 40 percent more rounds. Curiously, AES-256 has a slightly weaker key schedule in theoretical related-key models than AES-128, but this has no bearing on correct use.

Finally, a point that cannot be overstated: AES by itself encrypts exactly one 16-byte block. Every security property a real system cares about comes from the mode of operation wrapped around it. "We use AES-256" tells you almost nothing about whether a system is secure.

Examples

AES STATE: 16 bytes as a 4x4 column-major matrix

  bytes:  b0 b1 b2 b3 b4 b5 ... b15

         ┌────┬────┬────┬────┐
         │ b0 │ b4 │ b8 │b12 │
         ├────┼────┼────┼────┤
         │ b1 │ b5 │ b9 │b13 │
         ├────┼────┼────┼────┤
         │ b2 │ b6 │b10 │b14 │
         ├────┼────┼────┼────┤
         │ b3 │ b7 │b11 │b15 │
         └────┴────┴────┴────┘

ONE ROUND

  SubBytes     each byte -> S-box[byte]          CONFUSION (non-linear)
  ShiftRows    row0 <<0  row1 <<1
               row2 <<2  row3 <<3                DIFFUSION (across columns)
  MixColumns   column x fixed GF(2^8) matrix     DIFFUSION (within columns)
  AddRoundKey  state XOR roundkey(i)             KEY MIXING

  Final round omits MixColumns (it adds nothing before output).

ROUNDS BY KEY SIZE
  AES-128 -> 10 rounds, 11 round keys
  AES-192 -> 12 rounds, 13 round keys
  AES-256 -> 14 rounds, 15 round keys

AVALANCHE: flip ONE plaintext bit
  round 1: ~2 bytes differ
  round 2: all 16 bytes differ      <- full diffusion in two rounds
  round 10: ~50% of output bits differ

import os

from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes

key = os.urandom(16)


def aes_block(key: bytes, block: bytes) -> bytes:
    """The raw primitive: exactly one 16-byte permutation, no mode.
    ECB over a single block is the only honest way to expose it."""
    assert len(block) == 16
    enc = Cipher(algorithms.AES(key), modes.ECB()).encryptor()
    return enc.update(block) + enc.finalize()


# Demonstrate the avalanche effect: one flipped input bit.
a = bytes(16)                                 # sixteen 0x00 bytes
b = bytes([0x01]) + bytes(15)                 # single bit difference
ca, cb = aes_block(key, a), aes_block(key, b)

differing_bits = sum(bin(x ^ y).count("1") for x, y in zip(ca, cb))
print(f"input bits differing : 1")
print(f"output bits differing: {differing_bits} / 128")   # expect ~64

# Key size changes rounds and key length, not the interface.
for size in (16, 24, 32):
    k = os.urandom(size)
    rounds = {16: 10, 24: 12, 32: 14}[size]
    print(f"AES-{size * 8}: {rounds} rounds, {len(aes_block(k, a))}-byte block")

# Hardware acceleration is why AES is the default on most platforms:
# AES-NI makes a round a single instruction. Check for it on Linux with:
#   grep -o 'aes' /proc/cpuinfo | head -1

Key size	Rounds	Classical security	Post-quantum (Grover)	When to choose it
AES-128	10	128 bits	~64 bits	Default; ample for commercial data
AES-192	12	192 bits	~96 bits	Rare; specific compliance regimes
AES-256	14	256 bits	~128 bits	Policy mandates, long-lived secrets, PQ hedging

Key Takeaways

• AES is a substitution-permutation network on a 128-bit block, not a Feistel cipher, and achieves full diffusion within two rounds.
• SubBytes supplies confusion via an algebraically constructed S-box; ShiftRows and MixColumns supply diffusion.
• The block size is always 128 bits; only the key length and round count vary (10/12/14).
• AES-128 is computationally unbreakable classically; AES-256 is chosen for compliance, long secret lifetimes, and Grover-resistance, at roughly 40 percent more cost.
• No practical attack on full-round AES exists after 25 years of open cryptanalysis; the open competition process is part of the trust argument.
• AES alone encrypts one block: all real security properties come from the mode of operation, so "we use AES-256" is not a security statement.

🧪 Practice

1. Implement the avalanche test above and run it for AES-128 and AES-256, flipping a single key bit instead of a plaintext bit. Report the average number of differing output bits over 100 trials.
2. Explain why AES-256 uses 14 rounds rather than 10, and why more rounds was the chosen response to a longer key schedule.
3. Check whether your CPU exposes AES-NI, then benchmark AES-128-GCM against ChaCha20-Poly1305 on 10 MB of data. Explain the result in terms of hardware support.
4. Interview-style: "A client insists on AES-256 everywhere and refuses AES-128. Is this worth arguing about?" Hint: separate the technical question (both are far beyond brute force) from the policy and quantum-hedging arguments, and consider where you would actually spend the review effort instead — the mode, the nonce handling, and key storage.

Block Cipher Modes: ECB, CBC, CTR, GCM

Theory

A mode of operation extends a single-block cipher to messages of arbitrary length. This is where virtually all real-world symmetric crypto vulnerabilities live, so the goal is to understand what each mode guarantees and, more importantly, what it does not.

ECB (Electronic Codebook) encrypts each block independently. Because the cipher is deterministic, identical plaintext blocks produce identical ciphertext blocks. This leaks structure — famously visible when an image is "encrypted" with ECB and the outline remains perfectly legible. ECB is never acceptable for data with any structure, which in practice means never.

CBC (Cipher Block Chaining) XORs each plaintext block with the previous ciphertext block before encrypting, with a random IV seeding the first block. Identical plaintexts now produce different ciphertexts, fixing ECB's leak. Its costs: encryption is inherently sequential (cannot be parallelized), it requires padding, a corrupted block destroys that block and garbles the next, and crucially it provides no integrity. Unauthenticated CBC decryption that reports padding errors is a padding oracle.

CTR (Counter) encrypts a nonce-plus-counter sequence to produce a keystream, which is XORed with the plaintext. It needs no padding, is fully parallelizable, and allows random access — ideal for disk encryption and high-throughput networking. Its one absolute requirement is nonce uniqueness per key, and like CBC it provides no integrity: CTR ciphertext is perfectly malleable, since flipping a ciphertext bit flips exactly the corresponding plaintext bit.

GCM (Galois/Counter Mode) is CTR plus an authenticator. It computes a tag using GHASH, a polynomial MAC over GF(2^128), covering both the ciphertext and optional additional authenticated data (AAD) — unencrypted-but-authenticated fields such as headers or routing metadata. GCM is an AEAD mode: it delivers confidentiality, integrity, and authenticity in one pass, it is parallelizable, and it is hardware-accelerated on modern CPUs. It is the correct default. Its sharp edge: nonce reuse is far worse than in plain CTR, because repeating a nonce leaks GHASH's authentication key and permits forgery of arbitrary messages, not merely confidentiality loss. GCM's 96-bit nonce also means random nonces must be rotated before the birthday bound (roughly 2^32 messages per key) becomes a concern.

The practical rule is short: use an AEAD mode — AES-GCM, ChaCha20-Poly1305, or AES-SIV/GCM-SIV when nonce uniqueness cannot be guaranteed — and treat bare CBC or CTR as a finding unless a MAC is correctly applied over the ciphertext.

Examples

ECB -- blocks independent, structure leaks
  P1 ─►[E]─► C1      identical P => identical C
  P2 ─►[E]─► C2
  P3 ─►[E]─► C3

  Original image      ECB "encrypted"
   ████████            ▓░▓░▓░▓░
   ██    ██    ──►     ▓░    ▓░      the shape survives
   ████████            ▓░▓░▓░▓░

CBC -- chained, sequential, needs padding, NO integrity
  IV ──┐
       XOR ─► P1 ─►[E]─► C1 ──┐
                              XOR ─► P2 ─►[E]─► C2 ──┐
                                                     XOR ─► P3 ─►[E]─► C3

CTR -- keystream generator, parallel, no padding, NO integrity
  (nonce||1)─►[E]─► ks1 XOR P1 ─► C1
  (nonce||2)─►[E]─► ks2 XOR P2 ─► C2      all blocks independent
  (nonce||3)─►[E]─► ks3 XOR P3 ─► C3

GCM -- CTR for secrecy + GHASH for integrity  (AEAD)
  (nonce||1)─►[E]─► ks1 XOR P1 ─► C1 ─┐
  (nonce||2)─►[E]─► ks2 XOR P2 ─► C2 ─┤─► [ GHASH(H) ] ─► TAG
  AAD (authenticated, not encrypted) ─┘
  Output: nonce || ciphertext || tag

import os

from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.primitives.ciphers.aead import AESGCM
from cryptography.hazmat.primitives import padding as sym_padding

key = os.urandom(32)

# --- ECB leaks structure: repeated plaintext blocks repeat in ciphertext ---
repeated = b"SECRET_16_BYTES!" * 4
ecb = Cipher(algorithms.AES(key), modes.ECB()).encryptor()
ecb_ct = ecb.update(repeated) + ecb.finalize()
blocks = [ecb_ct[i:i + 16] for i in range(0, len(ecb_ct), 16)]
print("distinct ECB blocks:", len(set(blocks)))      # 1 -> the leak, visible

# --- CBC hides repetition but is MALLEABLE and unauthenticated ------------
iv = os.urandom(16)
padder = sym_padding.PKCS7(128).padder()
cbc = Cipher(algorithms.AES(key), modes.CBC(iv)).encryptor()
cbc_ct = cbc.update(padder.update(repeated) + padder.finalize()) + cbc.finalize()
blocks = [cbc_ct[i:i + 16] for i in range(0, len(cbc_ct), 16)]
print("distinct CBC blocks:", len(set(blocks)))      # all distinct

# --- CTR is perfectly malleable: bit flips pass straight through ----------
ctr_nonce = os.urandom(16)
enc = Cipher(algorithms.AES(key), modes.CTR(ctr_nonce)).encryptor()
ct = enc.update(b"transfer 0100 USD")
# Attacker flips one ciphertext byte to change '1' (0x31) into '9' (0x39):
tampered = bytearray(ct)
tampered[10] ^= 0x31 ^ 0x39
dec = Cipher(algorithms.AES(key), modes.CTR(ctr_nonce)).decryptor()
print(dec.update(bytes(tampered)))       # b'transfer 0900 USD' -- undetected

# --- GCM detects exactly that tampering ----------------------------------
aesgcm = AESGCM(key)
nonce = os.urandom(12)                   # 96 bits, MUST be unique per key
aad = b"account=12345;v=2"               # authenticated, sent in clear
gcm_ct = aesgcm.encrypt(nonce, b"transfer 0100 USD", aad)

bad = bytearray(gcm_ct)
bad[10] ^= 0x08
try:
    aesgcm.decrypt(nonce, bytes(bad), aad)
except Exception as exc:                 # InvalidTag
    print("GCM rejected the forgery:", type(exc).__name__)

Mode	Padding	Parallel	Random access	Integrity	Nonce/IV requirement	Verdict
ECB	Yes	Yes	Yes	No	None	Never use
CBC	Yes	Decrypt only	Decrypt only	No	Random, unpredictable IV	Legacy; needs a MAC
CFB / OFB	No	Varies	No	No	Unique IV	Legacy, rarely justified
CTR	No	Yes	Yes	No	Unique nonce (never reuse)	Only with a MAC
GCM	No	Yes	Yes	Yes	Unique 96-bit nonce (critical)	Default choice
CCM	No	Partly	No	Yes	Unique nonce	Constrained/IoT, 802.11
GCM-SIV / SIV	No	Yes	Yes	Yes	Nonce-misuse resistant	When uniqueness is uncertain

Key Takeaways

• ECB is deterministic per block and leaks plaintext structure; it has no acceptable use for structured data.
• CBC fixes the repetition leak but is sequential, needs padding, and provides no integrity — unauthenticated CBC invites padding-oracle attacks.
• CTR is a stream construction: parallel, no padding, random access, and completely malleable without a MAC.
• GCM is CTR plus GHASH authentication (AEAD), covering ciphertext and AAD, and is the correct default.
• GCM nonce reuse is worse than CTR nonce reuse: it leaks the authentication key and enables arbitrary forgery.
• Use AEAD by default; if you see bare CBC or CTR, the next question is always "where is the MAC, and does it cover the IV?"

🧪 Practice

1. Encrypt a simple BMP or PPM image with AES-ECB and with AES-CBC, then view both. Describe exactly what structural information ECB preserved.
2. Run the CTR bit-flipping example and then repeat it against GCM. Explain the difference in outcome in terms of what each mode authenticates.
3. Take a CBC implementation and add HMAC-SHA256 over IV || ciphertext in encrypt-then-MAC order. Explain why MAC-then-encrypt and encrypt-and-MAC are both worse.
4. Interview-style: "Why is GCM nonce reuse described as catastrophic rather than merely bad?" Hint: separate the confidentiality consequence (shared keystream, as with CTR) from the authentication consequence, and think about what two tags computed under the same nonce reveal about GHASH's key.

Initialization Vectors and Nonces

Theory

An IV or nonce is the value that makes encryption non-deterministic, so that encrypting the same plaintext twice under the same key yields different ciphertexts. Without it, an attacker learns when two messages are identical, which is often all they need. Confusingly, the exact requirement on this value differs by mode, and conflating the requirements causes real vulnerabilities.

There are three distinct properties that may be demanded:

1. Uniqueness — the value must never repeat under a given key. Required by every mode.
2. Unpredictability — the attacker must not be able to guess the next value before it is used. Required by CBC specifically.
3. Secrecy — never required. IVs and nonces are transmitted in the clear alongside the ciphertext.

CBC needs an unpredictable IV, not merely a unique one. If the attacker can predict the next IV and can also influence the plaintext, they can mount a chosen-plaintext attack to confirm guesses about earlier plaintext blocks. This is exactly the BEAST attack against TLS 1.0, which used the previous record's last ciphertext block as the next IV — a unique but entirely predictable value. TLS 1.1 fixed it by requiring an explicit random IV per record.

CTR and GCM need uniqueness only. A counter that increments per message is perfectly acceptable and, for GCM, is actually the preferred construction because it is easier to guarantee than randomness. GCM's nonce is 96 bits; if you choose nonces randomly, the birthday bound makes a collision non-negligible after about 2^32 messages under one key, so high-volume systems should use a deterministic counter (optionally combined with a per-instance random prefix to avoid collisions across parallel senders).

The reuse consequences differ sharply by mode and are worth memorizing:

Mode	Nonce/IV reuse consequence
CBC	Leaks whether two messages share a plaintext prefix
CTR	Keystream reuse: C1 XOR C2 = P1 XOR P2, full confidentiality break
GCM	Keystream reuse and recovery of the GHASH key, enabling arbitrary forgery
GCM-SIV	Degrades gracefully: leaks only message equality

Practical generation guidance: for GCM in a single-writer system, use a 96-bit counter and never reset it; for multi-writer systems, partition the nonce space (for example, 32 bits of instance ID plus 64 bits of counter) or use a random nonce with a documented message limit per key; where uniqueness genuinely cannot be assured — stateless systems, unreliable persistence, forked workers, restored VM snapshots — use a nonce-misuse-resistant mode such as AES-GCM-SIV. The counter approach fails in exactly the scenarios where state is lost, so choose based on whether you can keep a counter honestly.

Examples

WHAT EACH MODE DEMANDS

           unique?   unpredictable?   secret?
  CBC        yes          YES           no      <- BEAST exploited this
  CTR        yes          no            no
  GCM        yes          no            no
  GCM-SIV    preferred    no            no      <- tolerates reuse

NONCE SPACE PARTITIONING for multiple writers (GCM, 96 bits)

  ┌──────────────────┬────────────────────────────────┐
  │ instance id (32) │        counter (64)            │
  └──────────────────┴────────────────────────────────┘
   random at startup   monotonic, persisted
   => two writers can never collide, no coordination needed

BIRTHDAY LIMIT for RANDOM 96-bit nonces
  messages per key │ collision probability
       2**24       │  ~ 2**-49   negligible
       2**32       │  ~ 2**-33   acceptable for most systems
       2**40       │  ~ 2**-17   rotate the key well before here

import os
import struct
import threading

from cryptography.hazmat.primitives.ciphers.aead import AESGCM

key = AESGCM.generate_key(bit_length=256)
aesgcm = AESGCM(key)

# --- WRONG: a fixed nonce. Catastrophic for GCM. -------------------------
FIXED = b"\x00" * 12
c1 = aesgcm.encrypt(FIXED, b"balance 1000", None)
c2 = aesgcm.encrypt(FIXED, b"balance 9999", None)
# Keystream reuse: XOR of ciphertexts == XOR of plaintexts.
leak = bytes(a ^ b for a, b in zip(c1, c2))
print("leaked P1^P2:", leak[:12].hex())
# Worse: two tags under one nonce let an attacker solve for the GHASH key H
# and then forge a valid tag for ANY ciphertext of their choosing.


# --- RIGHT (single writer): a persisted, monotonic counter ---------------
class CounterNonce:
    """Deterministic uniqueness. Preferred for GCM when state is reliable.
    The counter MUST survive restarts, or nonces repeat after a crash."""

    def __init__(self, start: int = 0) -> None:
        self._n = start
        self._lock = threading.Lock()

    def next(self) -> bytes:
        with self._lock:                       # concurrency would duplicate
            self._n += 1
            if self._n >= 2 ** 96:
                raise RuntimeError("nonce space exhausted; rotate the key")
            return self._n.to_bytes(12, "big")


# --- RIGHT (multi writer): partition the nonce space --------------------
INSTANCE_ID = os.urandom(4)                    # 32 bits, chosen at startup


def partitioned_nonce(counter: int) -> bytes:
    """32-bit instance id + 64-bit counter: no cross-instance collision."""
    return INSTANCE_ID + struct.pack(">Q", counter)


# --- RIGHT (stateless): accept reuse risk, use a misuse-resistant mode --
from cryptography.hazmat.primitives.ciphers.aead import AESGCMSIV

siv = AESGCMSIV(AESGCMSIV.generate_key(bit_length=256))
n = os.urandom(12)
a = siv.encrypt(n, b"balance 1000", None)
b = siv.encrypt(n, b"balance 9999", None)
# Reuse here leaks only that the two plaintexts differ -- no keystream
# recovery, no forgery. The correct choice when uniqueness is not provable.

Key Takeaways

• IVs and nonces exist to make encryption non-deterministic; they are always public and never secret.
• CBC requires an unpredictable IV, not just a unique one — predictable IVs enabled BEAST against TLS 1.0.
• CTR and GCM require only uniqueness, so a monotonic counter is acceptable and for GCM generally preferable to randomness.
• Random 96-bit GCM nonces hit a birthday concern around 2^32 messages per key; plan key rotation or use a counter.
• Reuse consequences escalate by mode: prefix leakage in CBC, full confidentiality loss in CTR, and forgery capability in GCM.
• When uniqueness cannot be guaranteed — stateless services, forks, snapshot restores — use AES-GCM-SIV instead of hoping.

🧪 Practice

1. Encrypt two different 16-byte plaintexts with AES-GCM under the same nonce, XOR the ciphertexts, and confirm the result equals the XOR of the plaintexts. State what else the attacker gains beyond this.
2. Explain why a counter is a better GCM nonce source than os.urandom(12) for a service sending a billion messages per key, and then describe the one operational condition that makes the counter worse.
3. Design a nonce scheme for a system with 50 stateless Lambda-style workers sharing one key, and justify it. If you conclude no counter scheme works, say which mode you would use instead.
4. Interview-style: "Why did TLS 1.1 add an explicit per-record IV for CBC suites when TLS 1.0's IVs were already unique?" Hint: distinguish uniqueness from unpredictability, and consider an attacker who can both observe ciphertext and inject chosen plaintext into the same stream.

Padding Schemes and Padding Oracle Attacks

Theory

Block modes like CBC require the plaintext to be an exact multiple of the block size, so shorter messages must be padded. The scheme must be unambiguous — the receiver has to know exactly how many bytes to strip — and the standard answer is PKCS#7: append n bytes each with the value n, where n is the number of bytes needed (1 to 16 for AES). If the message is already block-aligned, a full block of padding is added, because otherwise the last byte of real data could be mistaken for padding.

Padding seems like a trivial formatting detail. It is the source of one of the most elegant and devastating attacks in applied cryptography.

A padding oracle is any mechanism that tells an attacker whether a submitted ciphertext decrypted to valid padding. The oracle does not need to be a helpful error message; it can be an HTTP 500 versus 403, a different response body, or merely a measurable timing difference between "padding invalid" (fail fast) and "padding valid, then MAC check failed" (fail later).

Given such an oracle, an attacker decrypts arbitrary ciphertext without the key. The mechanism follows from CBC decryption: P[i] = D(key, C[i]) XOR C[i-1]. The attacker controls C[i-1] entirely. So they take a target block C[i], prepend a block of their own bytes, and vary the last byte through all 256 values. Exactly one value makes the decrypted last byte equal 0x01 — valid padding — and the oracle says so. From that they solve for the intermediate value, hence the real plaintext byte. Then they target 0x02 0x02, and so on backwards through the block. The cost is at most 256 queries per byte, so about 4,096 queries to recover a 16-byte block. This is linear, not exponential: a fully practical attack.

The real-world record is extensive: Vaudenay published the technique in 2002; Lucky13 (2013) exploited timing differences in TLS's MAC-then-encrypt CBC construction; POODLE (2014) exploited SSL 3.0's unauthenticated padding to force a downgrade and decrypt cookies; Microsoft ASP.NET (2010, MS10-070) suffered full source-file disclosure and forged authentication tickets. The pattern is identical each time.

The fixes, in order of preference:

1. Use AEAD. GCM and ChaCha20-Poly1305 need no padding at all and verify the tag before touching the plaintext. There is no oracle to leak.
2. If CBC is unavoidable, use encrypt-then-MAC: compute a MAC over IV || ciphertext, and verify it before decrypting. An invalid ciphertext is rejected without the padding code ever running.
3. Never let padding validity influence any observable: use a single generic error, a constant-time code path, and identical response timing.

Note that MAC-then-encrypt — TLS's historical choice — does not fix this, because the receiver must decrypt (and therefore unpad) before it can check the MAC. That ordering is precisely what made Lucky13 possible.

Examples

PKCS#7 PADDING (16-byte blocks)

  "HELLO" (5)      48 45 4C 4C 4F | 0B 0B 0B 0B 0B 0B 0B 0B 0B 0B 0B
  13 bytes         ...            | 03 03 03
  16 bytes (full)  ................ + a WHOLE extra block of 10 10 ... 10
                                     (otherwise real data looks like padding)

CBC DECRYPTION -- the attacker controls C[i-1]

   C[i-1]              C[i]
     │                  │
     │            ┌─────┴─────┐
     │            │ D(key, .) │ ──► I[i]  (intermediate, unknown)
     │            └─────┬─────┘
     └──── XOR ◄────────┘
             │
           P[i]  =  I[i] XOR C[i-1]       <-- attacker-chosen C[i-1]

PADDING ORACLE: byte-at-a-time recovery

  Send:  [ attacker block ][ target C[i] ]
  Vary last byte of attacker block over 0x00..0xFF
    255 responses: "invalid padding"
      1 response : "valid padding"   => P'[15] == 0x01
    So  I[15] = guess XOR 0x01
    And real P[15] = I[15] XOR real C[i-1][15]

  Repeat for 0x02 0x02, then 0x03 0x03 0x03, ...
  Cost: <= 256 queries/byte => ~4096 queries per 16-byte block.

import os

from cryptography.hazmat.primitives import hashes, hmac, padding as sym_padding
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes

KEY = os.urandom(32)
MAC_KEY = os.urandom(32)


# --- THE VULNERABILITY: decryption behaviour depends on padding validity --
def vulnerable_decrypt(iv: bytes, ct: bytes) -> bytes:
    dec = Cipher(algorithms.AES(KEY), modes.CBC(iv)).decryptor()
    padded = dec.update(ct) + dec.finalize()
    unpadder = sym_padding.PKCS7(128).unpadder()
    try:
        return unpadder.update(padded) + unpadder.finalize()
    except ValueError:
        # ANY distinguishable signal here is the oracle: this exception, a
        # different status code, a different log line, or just a timing delta.
        raise ValueError("padding error") from None


def padding_oracle(iv: bytes, ct: bytes) -> bool:
    """What the attacker gets: one bit per query. That is sufficient."""
    try:
        vulnerable_decrypt(iv, ct)
        return True
    except ValueError:
        return False


def recover_last_byte(target_block: bytes) -> int:
    """Recover one plaintext byte with at most 256 oracle queries, no key."""
    forged = bytearray(os.urandom(16))
    for guess in range(256):
        forged[15] = guess
        if padding_oracle(bytes(forged), target_block):
            # Decrypted last byte is 0x01, so I[15] = guess XOR 0x01.
            return guess ^ 0x01
    raise RuntimeError("no valid padding found")


# --- FIX 1 (best): AEAD. No padding, tag verified before plaintext use. ---
from cryptography.hazmat.primitives.ciphers.aead import AESGCM

aead = AESGCM(KEY)
nonce = os.urandom(12)
blob = nonce + aead.encrypt(nonce, b"HELLO", None)   # no padding exists


# --- FIX 2: encrypt-then-MAC. Reject before decrypting. ------------------
def etm_encrypt(pt: bytes) -> bytes:
    iv = os.urandom(16)
    padder = sym_padding.PKCS7(128).padder()
    enc = Cipher(algorithms.AES(KEY), modes.CBC(iv)).encryptor()
    ct = enc.update(padder.update(pt) + padder.finalize()) + enc.finalize()
    h = hmac.HMAC(MAC_KEY, hashes.SHA256())
    h.update(iv + ct)                      # the MAC MUST cover the IV too
    return iv + ct + h.finalize()


def etm_decrypt(blob: bytes) -> bytes:
    iv, ct, tag = blob[:16], blob[16:-32], blob[-32:]
    h = hmac.HMAC(MAC_KEY, hashes.SHA256())
    h.update(iv + ct)
    h.verify(tag)                          # constant-time; raises on mismatch
    # Only now do we decrypt. The padding code never sees attacker ciphertext,
    # so there is no oracle to query.
    dec = Cipher(algorithms.AES(KEY), modes.CBC(iv)).decryptor()
    unpadder = sym_padding.PKCS7(128).unpadder()
    padded = dec.update(ct) + dec.finalize()
    return unpadder.update(padded) + unpadder.finalize()

Composition	Order on decrypt	Padding oracle possible?	Used by
Encrypt-then-MAC	Verify MAC, then decrypt	No	IPsec, modern designs
MAC-then-encrypt	Decrypt, unpad, verify MAC	Yes (Lucky13)	TLS 1.0-1.2 CBC suites
Encrypt-and-MAC	Decrypt, unpad, verify MAC	Yes	SSH (legacy modes)
AEAD (GCM, Poly1305)	Verify tag, then release plaintext	No padding exists	TLS 1.3, modern designs

Key Takeaways

• PKCS#7 appends n bytes of value n, and adds a full block when the plaintext is already aligned, to keep unpadding unambiguous.
• A padding oracle is any observable difference between "invalid padding" and "valid padding"; an error code, a response body, or a timing delta all suffice.
• With one bit of feedback per query, an attacker decrypts CBC ciphertext at roughly 256 queries per byte — linear cost, fully practical.
• Vaudenay, Lucky13, POODLE, and MS10-070 are all the same attack against different implementations.
• AEAD eliminates the attack class entirely by removing padding and verifying the tag before any plaintext processing.
• If CBC is mandated, use encrypt-then-MAC over IV || ciphertext and verify before decrypting; MAC-then-encrypt does not close the hole.

🧪 Practice

1. Implement recover_last_byte against the vulnerable function above and confirm you recover a byte without the key. Then extend it to recover an entire 16-byte block and count your queries.
2. Pad the strings A, 0123456789abcde, and 0123456789abcdef with PKCS#7 for a 16-byte block, writing out the hex. Explain why the third case gains 16 bytes.
3. Modify etm_decrypt to verify the MAC over ct only, excluding the IV, then describe what an attacker can now do to the first plaintext block.
4. Interview-style: "A service returns a generic 400 for all decryption failures. Is it safe from padding oracles?" Hint: a generic error closes the obvious channel but not every channel — think about how long each code path takes, what gets written to logs, and whether downstream behaviour differs once padding happens to be valid.

ChaCha20 and Modern Stream Ciphers

Theory

ChaCha20 is the modern stream cipher of record, standardized in RFC 8439 and paired with the Poly1305 MAC to form the AEAD construction ChaCha20-Poly1305. It exists because AES, for all its strengths, has two practical weaknesses: it is slow in software without hardware support, and naive software implementations leak key material through cache-timing side channels.

The history is worth knowing. RC4 was the dominant stream cipher for decades — simple, fast, and used in WEP, WPA/TKIP, and a large share of TLS traffic. It is now comprehensively broken: its keystream has statistical biases in the first bytes (enabling plaintext recovery of repeatedly-sent data such as cookies), and its use in WEP with a 24-bit IV made related-key attacks trivial. RFC 7465 prohibited RC4 in TLS in 2015. ChaCha20 was designed by Daniel Bernstein as the successor, refining his earlier Salsa20.

ChaCha20's construction is a keystream generator built from a hash-like function, not a Feistel or SPN cipher. It initializes a 512-bit state from four constant words, eight key words (256 bits), one counter word, and three nonce words. It then applies 20 rounds of the quarter-round operation — add, rotate, XOR (the "ARX" design) — and adds the result to the original state to produce 64 bytes of keystream. Each 64-byte block is generated independently from the counter, so the cipher is seekable and parallelizable.

The ARX design is the key to its advantages:

• Fast in software. Addition, rotation, and XOR are single-cycle instructions on every CPU, and the structure vectorizes well with SIMD. ChaCha20 typically beats software AES by a factor of three or more.
• Inherently constant-time. There are no table lookups, so there are no data-dependent memory accesses and therefore no cache-timing side channel. Software AES must either use lookup tables (leaky) or bitsliced implementations (slow and complex).

This is why ChaCha20-Poly1305 is preferred on mobile devices and older hardware without AES-NI, and why TLS 1.3 negotiates it widely. Google deployed it in Chrome on Android for precisely this reason. On a modern server with AES-NI, AES-GCM is usually faster, so the two coexist as first-class TLS 1.3 options.

The requirements are those of any stream construction, and they are strict: the (key, nonce) pair must never repeat. RFC 8439 specifies a 96-bit nonce and a 32-bit counter, giving 256 GB per (key, nonce) pair — ample for a message, insufficient for a long-lived stream, which is why protocols rekey. The XChaCha20 variant extends the nonce to 192 bits, making random nonce generation safe without birthday-bound concerns, which is why libraries such as libsodium favor it for file and message encryption.

Examples

CHACHA20 STATE: 16 words of 32 bits = 512 bits

  ┌─────────┬─────────┬─────────┬─────────┐
  │ const 0 │ const 1 │ const 2 │ const 3 │  "expand 32-byte k"
  ├─────────┼─────────┼─────────┼─────────┤
  │  key 0  │  key 1  │  key 2  │  key 3  │
  ├─────────┼─────────┼─────────┼─────────┤  256-bit key
  │  key 4  │  key 5  │  key 6  │  key 7  │
  ├─────────┼─────────┼─────────┼─────────┤
  │ counter │ nonce 0 │ nonce 1 │ nonce 2 │  32-bit ctr + 96-bit nonce
  └─────────┴─────────┴─────────┴─────────┘

QUARTER ROUND -- the entire primitive is Add, Rotate, XOR

  a += b;  d ^= a;  d <<<= 16;
  c += d;  b ^= c;  b <<<= 12;
  a += b;  d ^= a;  d <<<=  8;
  c += d;  b ^= c;  b <<<=  7;

  No S-box, no table lookup  =>  no cache-timing side channel.

20 rounds = 10 x (4 column rounds + 4 diagonal rounds)
Then: keystream_block = initial_state + final_state   (word-wise add)
      64 bytes per counter value; increment counter for the next block.

CAPACITY
  ChaCha20  : 96-bit nonce  + 32-bit counter -> 256 GB per (key,nonce)
  XChaCha20 : 192-bit nonce -> random nonces are safe at any volume

import os

from cryptography.hazmat.primitives.ciphers import Cipher, algorithms
from cryptography.hazmat.primitives.ciphers.aead import ChaCha20Poly1305

# --- Raw ChaCha20: a keystream generator, no integrity ------------------
key = os.urandom(32)
# The `cryptography` API takes a 16-byte value: 4 bytes counter || 12 nonce.
nonce16 = (0).to_bytes(4, "little") + os.urandom(12)
enc = Cipher(algorithms.ChaCha20(key, nonce16), mode=None).encryptor()
ct = enc.update(b"stream ciphers preserve length")
print(len(ct))                      # 30 -- exactly the plaintext length

# Malleable, like every unauthenticated stream cipher:
tampered = bytes([ct[0] ^ 0x20]) + ct[1:]
dec = Cipher(algorithms.ChaCha20(key, nonce16), mode=None).decryptor()
print(dec.update(tampered))         # modified plaintext, no error raised


# --- ChaCha20-Poly1305: the AEAD you should actually use ---------------
aead = ChaCha20Poly1305(ChaCha20Poly1305.generate_key())
nonce = os.urandom(12)              # 96 bits, MUST be unique per key
aad = b"msg-id=7781"
sealed = aead.encrypt(nonce, b"stream ciphers preserve length", aad)
print(len(sealed))                  # 30 + 16-byte Poly1305 tag = 46

bad = bytearray(sealed)
bad[0] ^= 0x20
try:
    aead.decrypt(nonce, bytes(bad), aad)
except Exception as exc:
    print("Poly1305 rejected it:", type(exc).__name__)   # InvalidTag


# --- Seekability: any 64-byte block is computable directly -------------
def keystream_block(key: bytes, nonce12: bytes, counter: int) -> bytes:
    """Random access without processing preceding data -- useful for
    disk encryption and resumable transfers."""
    n = counter.to_bytes(4, "little") + nonce12
    c = Cipher(algorithms.ChaCha20(key, n), mode=None).encryptor()
    return c.update(bytes(64))      # encrypting zeros yields the keystream


n12 = os.urandom(12)
print(keystream_block(key, n12, 1000)[:8].hex())   # block 1000, directly

Cipher	Design	Nonce	Status	Notes
RC4	Table-based state permutation	0-24 bits in practice	Broken, prohibited	Keystream biases; killed WEP
Salsa20	ARX, 20 rounds	64 bits	Secure, superseded	ChaCha20's predecessor
ChaCha20	ARX, 20 rounds	96 bits + 32-bit counter	Current standard (RFC 8439)	256 GB per (key, nonce)
XChaCha20	ChaCha20 + nonce extension	192 bits	Widely used (libsodium)	Random nonces safe
AES-CTR	Block cipher as keystream	Implementation-defined	Current	Fast with AES-NI

Key Takeaways

• ChaCha20 is an ARX keystream generator: addition, rotation, and XOR only, which makes it fast in software and inherently constant-time.
• The absence of table lookups removes the cache-timing side channel that plagues software AES implementations.
• Always use it as ChaCha20-Poly1305; raw ChaCha20 is malleable and provides no integrity.
• The (key, nonce) pair must never repeat; RFC 8439's 96-bit nonce plus 32-bit counter allows 256 GB per pair.
• XChaCha20's 192-bit nonce makes random nonce generation safe, which is the right choice for file and message encryption.
• RC4 is comprehensively broken and prohibited; ChaCha20-Poly1305 and AES-GCM are the two acceptable AEAD defaults, chosen by whether AES hardware is available.

🧪 Practice

1. Benchmark AES-256-GCM against ChaCha20-Poly1305 on 50 MB of data, then check whether your CPU reports AES-NI support. Explain the ordering you observe.
2. Use keystream_block to show that encrypting 64 zero bytes yields raw keystream, then verify that XORing that keystream with a ciphertext block recovers the plaintext.
3. Explain why a table-based AES implementation can leak key bits through cache timing, and why ChaCha20's ARX structure cannot.
4. Interview-style: "When would you choose ChaCha20-Poly1305 over AES-GCM?" Hint: consider the deployment target's instruction set, whether a constant-time software implementation is required, and what nonce guarantees the application can actually provide.

Key Distribution Problem

Theory

Symmetric cryptography has one structural flaw, and it is not mathematical: both parties need the same key, and getting it to them securely is a harder problem than the encryption itself. Every topic in section 3.3 exists to solve this.

The scaling argument makes the problem concrete. If n parties each need to communicate privately in pairs, the number of keys is n(n-1)/2. For 10 people that is 45 keys; for 1,000 people, 499,500; for a million users of a messaging service, roughly 5 x 10^11. Each key must be generated, delivered over an authenticated channel, stored securely at both ends, rotated on a schedule, and destroyed on compromise. The storage and administrative burden becomes the dominant cost long before the cryptography does.

The deeper issue is the bootstrapping paradox: to send a key securely you need a secure channel, but a secure channel is exactly what the key was supposed to create. Historically this was solved physically — trusted couriers, sealed codebooks, diplomatic pouches, pads delivered by hand. This works for a small number of long-lived, high-value relationships and is hopeless for the internet, where you must establish a confidential channel with a server you have never contacted, in under 100 milliseconds, with no prior arrangement.

Three families of solutions exist, and modern systems use all three in different places:

1. Key Distribution Center (KDC). A trusted third party shares a long-term key with every participant and issues short-lived session keys on demand. This reduces key count from O(n^2) to O(n). Kerberos is the canonical implementation and still underpins Active Directory authentication. The costs: the KDC is a single point of total compromise, and it must be online and reachable for anyone to communicate.
2. Asymmetric key exchange. Diffie-Hellman lets two parties derive a shared secret over a public channel with no prior shared secret at all. This is the breakthrough that made the public internet possible. It solves confidentiality against a passive attacker but not authentication — unauthenticated DH is defeated by an active machine-in-the-middle, which is why certificates and PKI (section 3.5) are required to complete the picture.
3. Pre-shared keys (PSK) and key derivation. For constrained or closed systems — IoT fleets, hardware tokens, payment terminals — a key is provisioned at manufacture or enrolment. Good designs derive per-device keys from a master key and a device identifier via a KDF, so that extracting one device's key does not compromise the fleet. Bad designs ship an identical key in every unit, and that key is extracted from a single device's flash within days of release.

Two additional properties shape modern protocol design. Forward secrecy means that compromising a long-term key does not expose past sessions, which requires ephemeral per-session key exchange (ECDHE) rather than static key transport — this is why TLS 1.3 removed static RSA key exchange entirely. And the hybrid cryptosystem pattern, covered in 3.3, is the universal practical answer: use asymmetric cryptography once to establish a symmetric key, then use the fast symmetric cipher for all the data.

Examples

THE SCALING PROBLEM: pairwise symmetric keys

   n parties  │  keys needed n(n-1)/2
      3       │  3
     10       │  45
    100       │  4,950
  1,000       │  499,500
  1,000,000   │  ~5 x 10**11

  Direct pairwise (n=5): 10 keys        KDC (n=5): 5 keys
      A───────B                              A   B
      │╲     ╱│                               ╲ ╱
      │ ╲   ╱ │                                KDC
      │  ╲ ╱  │                               ╱ │ ╲
      E───╳───C                              C  D  E
       ╲ ╱ ╲ ╱                         Each party shares ONE key
        D───┘                          with the KDC. O(n), not O(n^2).

THE BOOTSTRAPPING PARADOX
  To send K securely  ──needs──►  a secure channel
  A secure channel    ──needs──►  K
  Broken by: Diffie-Hellman (no prior secret required)

HYBRID CRYPTOSYSTEM: the universal practical answer
  1. ECDHE key exchange (asymmetric, once, slow)   -> shared secret
  2. HKDF                                          -> session keys
  3. AES-GCM / ChaCha20-Poly1305 (symmetric, fast) -> all the data

import os

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import x25519
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives.ciphers.aead import AESGCM


def pairwise_keys(n: int) -> int:
    """The administrative burden that motivates every alternative."""
    return n * (n - 1) // 2


for n in (10, 1_000, 1_000_000):
    print(f"{n:>9,} parties -> {pairwise_keys(n):>15,} keys")


# --- GOOD PSK DESIGN: derive per-device keys from a master secret -------
def device_key(master: bytes, device_id: bytes) -> bytes:
    """One extracted device key does not compromise the fleet, because the
    KDF is one-way: device_id is public, master is never shipped."""
    return HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=None,
        info=b"device-key-v1|" + device_id,   # domain separation per device
    ).derive(master)


master = os.urandom(32)                       # stays in an HSM, never shipped
k_a = device_key(master, b"serial-0001")
k_b = device_key(master, b"serial-0002")
assert k_a != k_b                             # compromise is contained

# ANTI-PATTERN: the same key flashed into every unit. One teardown of one
# device yields the key for the entire product line, unrotatable in the field.


# --- SOLVING DISTRIBUTION PROPERLY: ephemeral key exchange -------------
alice_sk = x25519.X25519PrivateKey.generate()     # ephemeral: per session
bob_sk = x25519.X25519PrivateKey.generate()

# Public keys are exchanged in the clear; an eavesdropper learns nothing.
alice_shared = alice_sk.exchange(bob_sk.public_key())
bob_shared = bob_sk.exchange(alice_sk.public_key())
assert alice_shared == bob_shared                 # same secret, no prior key

# Never use the raw DH output as a key: run it through a KDF.
session_key = HKDF(
    algorithm=hashes.SHA256(), length=32, salt=None, info=b"tls-like session"
).derive(alice_shared)

# From here on, the fast symmetric cipher does all the work.
nonce = os.urandom(12)
sealed = AESGCM(session_key).encrypt(nonce, b"bulk data", None)

# Discarding alice_sk and bob_sk after the session gives FORWARD SECRECY:
# a later compromise of long-term credentials cannot decrypt this traffic.

Approach	Keys for n parties	Needs prior secret?	Single point of failure	Real-world use
Direct pairwise	n(n-1)/2	Yes	No	Small closed systems
KDC (Kerberos)	n	Yes (one per party)	Yes, the KDC	Active Directory
Diffie-Hellman	0 pre-shared	No	No (but needs authentication)	TLS, SSH, Signal
PSK with per-device KDF	1 master	Yes, provisioned	The master key in an HSM	IoT, payment terminals
Hybrid (ECDHE + AEAD)	0 pre-shared	No	No	TLS 1.3, essentially everything

Key Takeaways

• Symmetric cryptography's structural limitation is distribution, not strength: pairwise keys scale as O(n^2) and the administrative cost dominates.
• The bootstrapping paradox — a secure channel is needed to establish a secure channel — is what Diffie-Hellman solved.
• A KDC reduces key count to O(n) but must be online and becomes a single point of total compromise.
• Diffie-Hellman provides confidentiality against passive attackers only; authentication via PKI is required to resist an active machine-in-the-middle.
• Pre-shared keys must be derived per device from a master held in an HSM, never flashed identically across a product line.
• Forward secrecy requires ephemeral exchange, which is why TLS 1.3 mandates ECDHE and removed static RSA key transport.
• Essentially every modern system is a hybrid cryptosystem: asymmetric once to agree a key, symmetric thereafter for the data.

🧪 Practice

1. Compute the number of pairwise keys required for a 500-person organization, then for the same organization using a KDC, and describe the operational difference in rotating one compromised key.
2. Run the X25519 exchange above, print both public keys and the derived secret, and explain precisely what a passive network observer learns and what they do not.
3. Explain why the raw X25519 output should be passed through HKDF rather than used directly as an AES key. Name two things the info parameter buys you.
4. Interview-style: "An IoT vendor ships 200,000 devices that share one AES key for cloud communication. Describe the risk and your remediation." Hint: consider the cost of a single device teardown, whether the key can be changed in the field, and how a per-device KDF plus a master key in an HSM changes the blast radius.

<a id="33-asymmetric-cryptography"></a>

3.3 Asymmetric Cryptography

Asymmetric cryptography solved the key distribution problem by splitting the key into a public half and a private half, which made secure communication between strangers possible and therefore made the public internet possible. This section covers the number theory you actually need, the three constructions that matter (RSA, Diffie-Hellman, elliptic curves), digital signatures, and what quantum computing does to all of it.

Public and Private Key Pairs

Theory

Every cipher so far has used one key for both directions. Asymmetric cryptography uses a mathematically linked pair: a public key that may be published to the world, and a private key that never leaves its owner. What one key does, only the other can undo.

The analogy that works best is a mailbox with a slot. Anyone can find your address and drop a letter through the slot — that is the public key, and it enables anyone to send you something only you can read. Only you have the key to open the box and retrieve the contents — that is the private key. Crucially, the ability to deposit does not confer the ability to retrieve, and knowing the address does not help you pick the lock.

This asymmetry rests on a one-way function with a trapdoor: a computation that is easy forward and infeasible backward, unless you hold a secret piece of information that makes the backward direction easy. Multiplying two 1,024-bit primes takes microseconds; factoring the 2,048-bit result takes longer than the age of the universe with known classical algorithms. The private key is the trapdoor.

The pair supports two distinct operations, and confusing them is one of the most common conceptual errors in the field:

Operation	Encrypt/verify with	Decrypt/sign with	Provides
Encryption	Recipient's public key	Recipient's private key	Confidentiality
Signature	Signer's public key (verify)	Signer's private key (sign)	Authenticity, integrity, non-repudiation

Note that the key roles swap between the two. For confidentiality, the sender uses the recipient's public key, so anyone can send but only the holder can read. For authenticity, the signer uses their own private key, so only the holder can produce but anyone can check. The common shorthand "signing is encrypting with the private key" is true only for textbook RSA and is false in general — DSA, ECDSA, and EdDSA have no encryption operation at all.

Three operational realities follow:

1. Asymmetric cryptography is slow — roughly 100 to 10,000 times slower than AES per byte — and RSA can only encrypt data smaller than its modulus. It is therefore never used for bulk data; it establishes or wraps a symmetric key (a hybrid cryptosystem).
2. A public key alone proves nothing about identity. It is just a number. Binding a key to a real-world identity requires a certificate signed by a trusted authority, which is the entire purpose of PKI.
3. Private key compromise is unrecoverable for past data unless the protocol used ephemeral keys. This is the motivation for forward secrecy.

Examples

THE MAILBOX MODEL

          PUBLIC KEY                        PRIVATE KEY
       (published freely)                 (never leaves owner)
              │                                   │
     ┌────────▼────────┐                 ┌────────▼────────┐
     │   anyone can    │                 │   only owner    │
     │   DEPOSIT       │ ══════════════► │   RETRIEVE      │
     └─────────────────┘                 └─────────────────┘

TWO OPERATIONS, KEYS SWAP ROLES

  CONFIDENTIALITY (encrypt to Bob)
    Alice ──[ encrypt with BOB'S PUBLIC key ]──► Bob
                                                 └─[ decrypt with his PRIVATE ]
    Anyone can send; only Bob can read.

  AUTHENTICITY (sign as Alice)
    Alice ──[ sign with ALICE'S PRIVATE key ]──► anyone
                                                 └─[ verify with her PUBLIC ]
    Only Alice can produce; anyone can check.

TRAPDOOR ONE-WAY FUNCTION

   p, q  ──── multiply (easy, microseconds) ────►  n = p*q
   p, q  ◄─── factor  (infeasible, 2048-bit) ────  n
          ▲
          └── trapdoor: knowing p lets you recover q instantly

from cryptography.hazmat.primitives import hashes, serialization
from cryptography.hazmat.primitives.asymmetric import padding, rsa

# Generate a pair. The private key CONTAINS the public key; the reverse
# is not true, which is the whole point.
private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key = private_key.public_key()

# --- OPERATION 1: confidentiality. Encrypt with the RECIPIENT'S PUBLIC key.
secret = b"a 32-byte symmetric session key.."
ciphertext = public_key.encrypt(
    secret,
    padding.OAEP(                       # OAEP, never PKCS1v15, for new code
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)
# Only the private key holder can reverse this.
assert private_key.decrypt(ciphertext, padding.OAEP(
    mgf=padding.MGF1(algorithm=hashes.SHA256()),
    algorithm=hashes.SHA256(), label=None)) == secret

# --- OPERATION 2: authenticity. Sign with YOUR OWN PRIVATE key.
message = b"transfer 500 to account 12345"
signature = private_key.sign(
    message,
    padding.PSS(mgf=padding.MGF1(hashes.SHA256()),
                salt_length=padding.PSS.MAX_LENGTH),
    hashes.SHA256(),
)
public_key.verify(                      # raises InvalidSignature on tampering
    signature, message,
    padding.PSS(mgf=padding.MGF1(hashes.SHA256()),
                salt_length=padding.PSS.MAX_LENGTH),
    hashes.SHA256(),
)

# --- The size limit that forces hybrid encryption ---------------------
# A 2048-bit RSA key with OAEP-SHA256 can wrap at most 190 bytes.
max_payload = (2048 // 8) - 2 * 32 - 2
print(f"RSA-2048/OAEP-SHA256 capacity: {max_payload} bytes")   # 190
# This is why RSA wraps an AES key and AES encrypts the actual data.

# --- Serialisation: what you publish vs what you must protect --------
pub_pem = public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)                                        # safe to publish anywhere

priv_pem = private_key.private_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PrivateFormat.PKCS8,
    # ALWAYS encrypt a private key at rest; NoEncryption is a finding.
    encryption_algorithm=serialization.BestAvailableEncryption(b"passphrase"),
)

Key Takeaways

• A key pair is mathematically linked: the public key may be published, the private key never leaves its owner.
• Security rests on a trapdoor one-way function — easy forward, infeasible backward without the private secret.
• Encryption uses the recipient's public key; signing uses the signer's own private key. The roles swap between the two operations.
• "Signing is encrypting with the private key" is a textbook-RSA artifact and is false for DSA, ECDSA, and EdDSA.
• Asymmetric operations are orders of magnitude slower than symmetric ones and are size-limited, so they wrap symmetric keys rather than encrypt data.
• A public key by itself carries no identity; binding it to an identity requires a certificate and a trusted authority.
• Private keys must be encrypted at rest, and ephemeral exchange is what protects past sessions from a future key compromise.

🧪 Practice

1. Generate an RSA-2048 pair and attempt to encrypt 500 bytes with OAEP. Record the error and explain what the limit implies for application design.
2. For each scenario, state which key is used and by whom: sending a confidential file to a colleague, signing a software release, verifying a TLS server's identity, decrypting your own backup.
3. Sign a message, modify one byte of the message, and attempt verification. Then restore the message and modify one byte of the signature. Describe both outcomes.
4. Interview-style: "Explain the difference between signing and encrypting to a developer who thinks they are the same operation run backwards." Hint: use the key-role swap as the anchor, then point out that modern signature schemes like Ed25519 provide no encryption operation at all — which would be impossible if the claim were true.

Modular Arithmetic and Number Theory Basics

Theory

Asymmetric cryptography is built almost entirely on modular arithmetic: arithmetic that wraps around a fixed modulus, like a clock. You do not need to be a number theorist, but four ideas are load-bearing, and without them RSA and Diffie-Hellman are just incantations.

1. Modular arithmetic and the clock analogy. a mod n is the remainder of a divided by n. On a 12-hour clock, 9 + 5 = 2, because arithmetic happens modulo 12. The crucial property for cryptography is that wrapping destroys information about magnitude: knowing that x mod 12 = 2 tells you nothing about whether x was 2, 14, 26, or 2,000,000,002. This loss of information is what hides secrets.

2. Modular exponentiation is cheap; the discrete logarithm is not. Computing g^a mod p for a 2,048-bit p takes microseconds using square-and-multiply (repeated squaring reduces 2,048 multiplications to about 3,000 operations instead of 2^2048). Reversing it — given g, p, and g^a mod p, find a — is the discrete logarithm problem, and no efficient classical algorithm exists. This asymmetry is Diffie-Hellman.

3. Factoring is hard. Given two large primes p and q, computing n = p*q is trivial. Given n, recovering p and q requires the best known classical algorithm (the general number field sieve) to run in sub-exponential but still infeasible time for 2,048-bit n. This asymmetry is RSA.

4. Euler's totient and the inverse relationship. phi(n) counts the integers below n that share no factor with n. For a product of two distinct primes, phi(n) = (p-1)(q-1). Euler's theorem gives a^phi(n) = 1 mod n for a coprime to n, which means exponents can be reduced modulo phi(n). RSA picks e and d such that e*d = 1 mod phi(n); then (m^e)^d = m^1 = m mod n, and encryption and decryption undo each other. Knowing phi(n) is equivalent to knowing the factorization, which is why p and q must be destroyed or protected after key generation.

Two supporting tools complete the toolkit. The extended Euclidean algorithm computes modular inverses efficiently, which is how d is derived from e and phi(n). And the Chinese Remainder Theorem speeds RSA private operations by about four times, by working modulo p and q separately and recombining — which is also why CRT-based implementations need fault-injection countermeasures.

Examples

MODULAR ARITHMETIC AS A CLOCK (mod 12)

         11  12   1
      10           2        9 + 5 = 14 = 2 (mod 12)
     9       ⊙       3
      8            4        Information about magnitude is DESTROYED:
         7   6   5          x mod 12 = 2  =>  x in {2, 14, 26, 38, ...}

THE TWO HARD PROBLEMS

  DISCRETE LOG                     FACTORING
  g^a mod p  ──easy──► result      p * q  ──easy──► n
  result     ──HARD──► a           n      ──HARD──► p, q
  Basis of: Diffie-Hellman, DSA    Basis of: RSA
            ECDH, ECDSA, EdDSA

SQUARE-AND-MULTIPLY: why g^a mod p is fast
  compute 3^13 mod 17,  13 = 1101 binary
    bit 1: r = 1*1*3 = 3
    bit 1: r = 3*3*3 = 27 mod 17 = 10
    bit 0: r = 10*10 = 100 mod 17 = 15
    bit 1: r = 15*15*3 = 675 mod 17 = 12
  4 steps instead of 13 multiplications; for 2048-bit exponents,
  ~3000 operations instead of 2**2048.

RSA'S CORE IDENTITY
  phi(n) = (p-1)(q-1)
  choose e,  find d  with  e*d = 1 (mod phi(n))
  then  (m^e)^d = m^(1 + k*phi(n)) = m * 1^k = m  (mod n)
  Knowing phi(n) == knowing the factorization. Protect p and q.

def egcd(a: int, b: int) -> tuple[int, int, int]:
    """Extended Euclid: returns (g, x, y) with a*x + b*y == g == gcd(a, b).
    The x component is the modular inverse when g == 1."""
    if b == 0:
        return a, 1, 0
    g, x, y = egcd(b, a % b)
    return g, y, x - (a // b) * y


def mod_inverse(a: int, m: int) -> int:
    """Find d such that a*d = 1 (mod m). This is how RSA derives d from e."""
    g, x, _ = egcd(a % m, m)
    if g != 1:
        raise ValueError(f"{a} has no inverse mod {m}")
    return x % m


def mod_exp(base: int, exp: int, mod: int) -> int:
    """Square-and-multiply. Python's pow(base, exp, mod) does this in C and
    is what you should actually call -- this shows the mechanism."""
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:               # current exponent bit is set: multiply in
            result = (result * base) % mod
        base = (base * base) % mod  # square for the next bit position
        exp >>= 1
    return result


# --- A complete toy RSA from the number theory above -------------------
p, q = 61, 53                      # real keys use 1024-bit primes each
n = p * q                          # 3233, the public modulus
phi = (p - 1) * (q - 1)            # 3120
e = 17                             # public exponent, coprime to phi
d = mod_inverse(e, phi)            # 2753, the private exponent

message = 65
cipher = mod_exp(message, e, n)              # 2790
recovered = mod_exp(cipher, d, n)            # 65
print(n, phi, e, d, cipher, recovered)
assert recovered == message

# Why p and q must be destroyed: knowing phi(n) yields d immediately.
leaked_phi = (p - 1) * (q - 1)
print("d recovered from phi:", mod_inverse(e, leaked_phi))   # 2753

# --- The asymmetry, measured -------------------------------------------
import time

big_p = 2 ** 2048 - 1942289          # a large modulus (illustrative)
g, a = 5, 2 ** 500 + 12345
t0 = time.perf_counter()
pow(g, a, big_p)                     # forward: microseconds
print(f"modexp: {(time.perf_counter() - t0) * 1000:.2f} ms")
# Reversing it (finding `a` from the result) has no efficient algorithm.


# --- CRT: how real RSA speeds up private-key operations ---------------
def rsa_decrypt_crt(c: int, d: int, p: int, q: int) -> int:
    """~4x faster than pow(c, d, p*q): two half-size exponentiations.
    Real implementations must add fault-injection checks, because a single
    bit error in one branch leaks the factorization."""
    dp, dq = d % (p - 1), d % (q - 1)
    m1, m2 = pow(c, dp, p), pow(c, dq, q)
    q_inv = mod_inverse(q, p)
    h = (q_inv * (m1 - m2)) % p
    return (m2 + h * q) % (p * q)


assert rsa_decrypt_crt(cipher, d, p, q) == message

Concept	Easy direction	Hard direction	Used by
Multiplication	p * q = n	Factor n	RSA
Modular exponentiation	g^a mod p	Discrete log: find a	Diffie-Hellman, DSA
Elliptic curve scalar mult	a * G = P	ECDLP: find a	ECDH, ECDSA, EdDSA
Modular inverse	Extended Euclid (fast both ways)	—	RSA key generation

Key Takeaways

• Modular arithmetic wraps like a clock, and that wrapping destroys magnitude information — which is how secrets stay hidden.
• Modular exponentiation is fast via square-and-multiply; inverting it (the discrete logarithm) has no efficient classical algorithm.
• Factoring a product of two large primes is the other hard problem, and it is what RSA rests on.
• phi(n) = (p-1)(q-1) for a product of two primes, and knowing phi(n) is equivalent to knowing the factorization.
• RSA works because e and d are modular inverses modulo phi(n), so exponentiating by one undoes the other.
• The extended Euclidean algorithm derives d; the Chinese Remainder Theorem speeds private operations roughly fourfold but introduces fault-injection risk.
• Always use library implementations: the mathematics is simple to write and extremely difficult to write safely.

🧪 Practice

1. Implement mod_exp yourself and verify it against Python's pow(b, e, m) for 1,000 random inputs. Count the loop iterations for a 2,048-bit exponent.
2. Build a toy RSA with p = 101 and q = 113, derive e and d, and encrypt and decrypt the value 42. Then show that leaking phi(n) lets you compute d.
3. Compute mod_inverse(17, 3120) by hand with the extended Euclidean algorithm, showing each step, and check your answer against the code.
4. Interview-style: "Why is it catastrophic if two different RSA keys happen to share one prime factor?" Hint: think about what gcd of the two public moduli gives you, and recall that this exact condition was found across tens of thousands of real internet hosts due to poor entropy at key generation.

RSA Algorithm and Key Generation

Theory

RSA (Rivest-Shamir-Adleman, 1977) was the first practical public-key cryptosystem and remains widely deployed. Its security rests on the difficulty of factoring the product of two large primes, and its longevity means a great deal of legacy infrastructure depends on it — while new designs increasingly prefer elliptic curves.

Key generation proceeds in five steps:

1. Generate two large random primes p and q, each half the desired modulus size (1,024 bits each for RSA-2048). They must be generated independently from a strong CSPRNG and must not be close to each other.
2. Compute the modulus n = p * q. This is public.
3. Compute phi(n) = (p-1)(q-1), or Carmichael's lambda(n) = lcm(p-1, q-1) in modern practice.
4. Choose the public exponent e, coprime to phi(n). In practice e = 65537 universally, because it is prime, has only two set bits (making encryption fast), and is large enough to avoid the small-exponent attacks that plagued e = 3.
5. Compute the private exponent d = e^-1 mod phi(n).

The public key is (n, e); the private key is (n, d) plus, for CRT speedup, p, q, and precomputed values. p, q, and phi(n) must then be treated as secret or destroyed, since any of them yields d.

Encryption is c = m^e mod n and decryption is m = c^d mod n. But textbook RSA as just described is insecure and must never be used, for several reasons:

• It is deterministic: the same plaintext always produces the same ciphertext, so an attacker can encrypt candidate plaintexts and compare. For a small message space (a credit card number, a yes/no vote) this is a complete break.
• It is malleable: (m1^e)(m2^e) = (m1*m2)^e mod n, so ciphertexts can be combined into meaningful new ciphertexts.
• Small messages with small e can be recovered by taking an ordinary integer root when m^e < n.

The fix is padding, which adds randomness and structure. Use OAEP (Optimal Asymmetric Encryption Padding) for encryption and PSS for signatures. The older PKCS#1 v1.5 padding is vulnerable to Bleichenbacher's adaptive chosen-ciphertext attack (1998) — a padding oracle for RSA — which has been rediscovered repeatedly as ROBOT (2017) and in numerous TLS stacks. PKCS#1 v1.5 signatures are still tolerated for compatibility; v1.5 encryption should be considered a vulnerability.

Key size guidance: RSA-1024 is broken in practice and prohibited; RSA-2048 is the current minimum, offering roughly 112 bits of security; RSA-3072 gives about 128 bits and is the choice where RSA must match AES-128; RSA-4096 is common but gains little over 3072 at double the cost. The unfavourable scaling is RSA's core weakness — matching AES-256's 256-bit security would require a roughly 15,360-bit RSA key, while ECC achieves it with 512 bits. This is why new systems prefer elliptic curves.

Examples

RSA KEY GENERATION

  1. p, q         two independent 1024-bit random primes
  2. n = p*q      2048-bit public modulus
  3. phi = (p-1)(q-1)
  4. e = 65537    public exponent (0x10001, two set bits -> fast)
  5. d = e^-1 mod phi

  PUBLIC  (n, e)  ── publish freely
  PRIVATE (n, d)  ── plus p, q, dp, dq, qinv for CRT speedup
  DESTROY  phi, and protect p and q: each one yields d

OPERATIONS
  encrypt: c = m^e mod n          verify: m = s^e mod n
  decrypt: m = c^d mod n          sign:   s = m^d mod n

WHY TEXTBOOK RSA FAILS

  deterministic:  Enc("yes") is always the same ciphertext
                  attacker encrypts "yes" and "no", compares. Broken.

  malleable:      c1 * c2 = (m1 * m2)^e mod n
                  attacker crafts meaningful ciphertexts without the key

  small message:  m=2, e=3, m^e = 8 < n  =>  cube root of c recovers m

  FIX: OAEP padding (randomised + structured)
    ┌──────────────────────────────────────────┐
    │ 00 │ masked seed │ masked DB (m + label) │
    └──────────────────────────────────────────┘
    Fresh random seed per encryption => non-deterministic, non-malleable.

KEY SIZE SCALES BADLY
  security bits │  RSA modulus │  ECC key
       112      │     2048     │    224
       128      │     3072     │    256
       192      │     7680     │    384
       256      │    15360     │    512

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding, rsa

# --- Correct generation: let the library do it ---------------------------
key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
nums = key.private_numbers()
pub = key.public_key().public_numbers()
print(f"n is {pub.n.bit_length()} bits, e = {pub.e}")
print(f"p is {nums.p.bit_length()} bits, q is {nums.q.bit_length()} bits")
assert nums.p * nums.q == pub.n


# --- DEMONSTRATING WHY PADDING IS MANDATORY -----------------------------
# Textbook (unpadded) RSA on a small message space is trivially broken.
n, e = pub.n, pub.e


def textbook_encrypt(m: int) -> int:
    return pow(m, e, n)             # no padding, no randomness


votes = {b"yes": textbook_encrypt(int.from_bytes(b"yes", "big")),
         b"no": textbook_encrypt(int.from_bytes(b"no", "big"))}

intercepted = votes[b"yes"]
# The attacker encrypts every candidate and compares. No key needed.
for candidate in (b"yes", b"no"):
    if textbook_encrypt(int.from_bytes(candidate, "big")) == intercepted:
        print("recovered vote:", candidate)        # b'yes'

# Malleability: combine two ciphertexts into a meaningful third.
c3, c5 = textbook_encrypt(3), textbook_encrypt(5)
assert (c3 * c5) % n == textbook_encrypt(15)       # forged, without d


# --- OAEP fixes both: fresh randomness per encryption -------------------
oaep = padding.OAEP(mgf=padding.MGF1(hashes.SHA256()),
                    algorithm=hashes.SHA256(), label=None)

a = key.public_key().encrypt(b"yes", oaep)
b = key.public_key().encrypt(b"yes", oaep)
print("identical ciphertexts for identical plaintext?", a == b)   # False
assert key.decrypt(a, oaep) == key.decrypt(b, oaep) == b"yes"


# --- Signatures: PSS for new code, v1.5 only for legacy verification ----
pss = padding.PSS(mgf=padding.MGF1(hashes.SHA256()),
                  salt_length=padding.PSS.MAX_LENGTH)
sig = key.sign(b"release v2.1.0", pss, hashes.SHA256())
key.public_key().verify(sig, b"release v2.1.0", pss, hashes.SHA256())

# AVOID for encryption -- Bleichenbacher / ROBOT oracle:
#   padding.PKCS1v15()

Parameter	Value	Why
e	65537	Prime, two set bits (fast), avoids small-exponent attacks
Minimum n	2048 bits	~112-bit security; 1024 is broken and prohibited
Encryption padding	OAEP	Randomised; PKCS#1 v1.5 is a Bleichenbacher oracle
Signature padding	PSS	Provable security; v1.5 tolerated for legacy verification
p, q proximity	Far apart, independent	Close primes allow Fermat factorization
Entropy source	CSPRNG	Shared primes across hosts came from weak entropy

Key Takeaways

• RSA's security is the difficulty of factoring n = p*q; anyone who learns p, q, or phi(n) immediately derives d.
• e = 65537 is the universal choice: prime, cheap to exponentiate, and immune to the small-exponent attacks that broke e = 3.
• Textbook RSA is insecure because it is deterministic and malleable; padding is not optional.
• Use OAEP for encryption and PSS for signatures; PKCS#1 v1.5 encryption is a Bleichenbacher oracle, rediscovered as ROBOT.
• RSA-2048 is the current floor (about 112-bit security) and RSA-3072 matches AES-128; 4096 adds cost without meaningful gain.
• Key size scales badly — 15,360 bits to match AES-256 — which is the main practical argument for migrating to elliptic curves.
• Never implement RSA yourself; the mathematics is easy and the side-channel-free implementation is not.

🧪 Practice

1. Run the deterministic-RSA vote-recovery example and then repeat it with OAEP. Explain in one sentence what the random seed changes.
2. Generate an RSA-2048 key with OpenSSL (openssl genrsa), inspect it with openssl rsa -text -noout, and identify n, e, d, p, q, and the CRT coefficients in the output.
3. Demonstrate RSA malleability by forging the ciphertext of m1*m2 from the ciphertexts of m1 and m2, then confirm OAEP prevents the same trick.
4. Interview-style: "A legacy API uses RSA with PKCS#1 v1.5 encryption. Rate the severity and propose a migration." Hint: identify whether an attacker can distinguish padding-failure responses, name the attack and its modern rediscovery, and consider whether the real fix is OAEP or moving the whole design to a hybrid ECDH-based scheme.

Diffie-Hellman Key Exchange

Theory

Diffie-Hellman (1976) is arguably the single most important result in applied cryptography: it lets two parties who have never met derive a shared secret over a channel that an eavesdropper fully controls, without ever transmitting the secret. It directly solves the bootstrapping paradox from the key distribution topic.

The classic analogy is paint mixing. Alice and Bob publicly agree on a base colour, yellow. Alice secretly adds red; Bob secretly adds blue. They exchange their mixtures in public view. Alice adds her red to Bob's mixture; Bob adds his blue to Alice's. Both now hold yellow-red-blue. An observer saw yellow, yellow-red, and yellow-blue, and cannot produce the final colour because un-mixing paint is hard — they would need to extract red or blue from a mixture.

Mathematically, with a large prime p and generator g (both public):

1. Alice picks secret a, sends A = g^a mod p.
2. Bob picks secret b, sends B = g^b mod p.
3. Alice computes B^a = g^(ba) mod p. Bob computes A^b = g^(ab) mod p. These are equal.
4. The eavesdropper has p, g, A, and B, and needs g^(ab) — which requires solving the discrete logarithm.

Three properties and three pitfalls define its correct use.

Diffie-Hellman provides no authentication. This is the critical limitation. An active attacker sitting in the middle runs a separate exchange with each party, holds two shared secrets, and transparently relays and reads everything. Both parties believe they have a secure channel and they do — with the attacker. Authentication must come from elsewhere: a signature over the exchange (TLS), a certificate (PKI), a pre-shared key, or out-of-band verification of a fingerprint (Signal's safety numbers, SSH's host-key prompt).

Ephemeral Diffie-Hellman gives forward secrecy. If a and b are generated fresh per session and discarded afterwards, then compromising the server's long-term private key later does not decrypt recorded past traffic — the session secrets no longer exist anywhere. This is why TLS 1.3 removed static RSA key transport and mandates (EC)DHE. The distinction in cipher suite names is exactly this: DHE/ECDHE is ephemeral and forward-secret; plain DH/ECDH with a static key is not.

Parameters must be validated. Three real-world failures:

• Small or weak groups. 512-bit export-grade DH fell to Logjam (2015), which also exploited a downgrade. 1,024-bit DH is within reach of state-level precomputation. Use 2,048-bit or larger named groups (RFC 7919), or switch to elliptic curves.
• Invalid public keys. Accepting A = 0, 1, or p-1, or a point off the curve in the EC case, lets an attacker force a predictable shared secret. Libraries must and generally do validate.
• Raw output used as a key. The DH result is a group element with structure and bias, not a uniform key. Always run it through a KDF such as HKDF, with context in the info parameter.

Examples

THE PAINT ANALOGY

  PUBLIC                ALICE                    BOB
  base: yellow     secret: red              secret: blue
                        │                        │
                   yellow+red ────────────► (public wire)
                   (public wire) ◄──────── yellow+blue
                        │                        │
                 +blue  ▼                        ▼  +red
               yellow+red+blue  ==  yellow+red+blue     SHARED SECRET

  Eavesdropper saw: yellow, yellow+red, yellow+blue.
  Cannot un-mix to get the final colour.

THE MATHEMATICS

  public: large prime p, generator g

  ALICE                      WIRE                      BOB
  a = random secret                                    b = random secret
  A = g^a mod p        ──────── A ────────►
                       ◄─────── B ─────────            B = g^b mod p
  s = B^a mod p                                        s = A^b mod p
      = g^(ab) mod p                                       = g^(ab) mod p
                        IDENTICAL

  Eve has p, g, A, B. Needs the DISCRETE LOG to get a or b.

MACHINE-IN-THE-MIDDLE: unauthenticated DH is fully defeated

  ALICE ◄──── g^a | g^m ────► MALLORY ◄──── g^m | g^b ────► BOB
         s1 = g^(am)                  holds s1 AND s2        s2 = g^(mb)

  Both sides have a "secure" channel -- to Mallory. She reads and
  rewrites everything. FIX: authenticate the exchange (signature/cert).

EPHEMERAL vs STATIC
  DHE/ECDHE : a, b fresh per session, discarded  -> forward secrecy
  DH/ECDH   : long-term static key reused        -> NO forward secrecy
              server key stolen in 2030 decrypts traffic recorded in 2024

import os

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import dh, x25519
from cryptography.hazmat.primitives.kdf.hkdf import HKDF

# --- The mechanism, with tiny numbers you can verify by hand ------------
p = 23          # a real deployment uses a 2048-bit safe prime
g = 5
a, b = 6, 15    # secrets, never transmitted

A = pow(g, a, p)                 # 8   -> sent in the clear
B = pow(g, b, p)                 # 19  -> sent in the clear
print(pow(B, a, p), pow(A, b, p))    # 2 2 -> identical shared secret
assert pow(B, a, p) == pow(A, b, p) == pow(g, a * b, p)


# --- Modern practice: X25519 ephemeral exchange + HKDF ------------------
def ephemeral_exchange() -> bytes:
    """Fresh keys per session and discarded afterwards: forward secrecy.
    X25519 validates inputs by construction, avoiding invalid-point attacks."""
    alice = x25519.X25519PrivateKey.generate()
    bob = x25519.X25519PrivateKey.generate()

    shared = alice.exchange(bob.public_key())
    assert shared == bob.exchange(alice.public_key())

    # NEVER use the raw output as a key: it is a biased group element.
    # `info` binds the key to this protocol and role (domain separation).
    return HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=os.urandom(16),
        info=b"myapp/v1 client->server traffic key",
    ).derive(shared)
    # alice and bob go out of scope here -- the secret is unrecoverable.


session_key = ephemeral_exchange()


# --- Finite-field DH: parameter size is the security question ----------
# Generating 2048-bit parameters is slow; production uses named groups
# from RFC 7919 rather than generating fresh ones.
params = dh.generate_parameters(generator=2, key_size=2048)
alice_dh = params.generate_private_key()
bob_dh = params.generate_private_key()
assert alice_dh.exchange(bob_dh.public_key()) == \
       bob_dh.exchange(alice_dh.public_key())


# --- Invalid public key values an implementation must reject -----------
# A = 0 forces s = 0; A = 1 forces s = 1, regardless of the peer's secret.
for bad_A in (0, 1, p - 1):
    print(f"A={bad_A} -> shared secret {pow(bad_A, a, p)}")  # 0, 1, 1 or p-1
# Any of these lets an attacker fix the key to a known value.

Variant	Group	Forward secrecy	Status
DH (static)	Finite field mod p	No	Deprecated
DHE	Finite field, ephemeral	Yes	Acceptable at 2048+ bits; slow
ECDH (static)	Elliptic curve	No	Used in some protocols (e.g. static-static schemes)
ECDHE	Elliptic curve, ephemeral	Yes	Current default (TLS 1.3)
X25519	Curve25519, ephemeral	Yes	Preferred: fast, misuse-resistant

Key Takeaways

• Diffie-Hellman derives a shared secret over a fully observed channel without transmitting it, solving the bootstrapping paradox.
• Security rests on the discrete logarithm problem: the eavesdropper sees g^a and g^b but cannot compute g^(ab).
• It provides no authentication; unauthenticated DH is completely defeated by an active machine-in-the-middle, so signatures or certificates are mandatory.
• Ephemeral variants (DHE, ECDHE, X25519) give forward secrecy, which is why TLS 1.3 removed static key transport.
• Weak groups are a real risk: 512-bit DH fell to Logjam and 1024-bit is within state-level reach; use 2048+ bits or elliptic curves.
• Implementations must reject degenerate public values such as 0, 1, and p-1, and off-curve points in the EC case.
• Never use the raw exchange output as a key — pass it through a KDF with protocol-specific context.

🧪 Practice

1. Work the small-number exchange by hand with p = 23, g = 5, a = 4, b = 3, showing A, B, and both computed secrets. Then brute-force a from A and note how trivial it is at this size.
2. Implement a machine-in-the-middle against the toy exchange: intercept A and B, substitute your own values, and show you can read both directions.
3. Inspect a TLS handshake with openssl s_client -connect example.com:443 and identify whether the negotiated suite provides forward secrecy. Explain how you can tell from the suite name.
4. Interview-style: "Why does TLS 1.3 remove RSA key transport in favour of ECDHE only?" Hint: consider an adversary who records encrypted traffic today and obtains the server's private key three years later, and what each key-establishment method gives them.

Elliptic Curve Cryptography

Theory

Elliptic curve cryptography (ECC) achieves the same goals as RSA and finite-field Diffie-Hellman with dramatically smaller keys. A 256-bit ECC key provides roughly the security of a 3,072-bit RSA key. That difference drives smaller certificates, faster handshakes, less bandwidth, and viability on constrained devices — which is why ECC is the default for all new deployments.

An elliptic curve over a finite field is the set of points satisfying y^2 = x^3 + ax + b mod p. The curve's points, plus a "point at infinity" acting as the identity, form a group under a geometric addition rule: to add two points, draw the line through them, find the third intersection with the curve, and reflect across the x-axis. Doubling a point uses the tangent line instead. These rules translate into exact arithmetic formulas over the finite field, so no geometry is actually computed.

Scalar multiplication is the one-way function: k * G means adding the base point G to itself k times (done efficiently by double-and-add, analogous to square-and-multiply). Given k and G, computing P = k*G is fast. Given P and G, recovering k is the elliptic curve discrete logarithm problem (ECDLP), and it is much harder per bit than the finite-field version. The best general attacks (Pollard's rho) take about sqrt(n) operations, so a 256-bit curve gives 128-bit security — whereas index-calculus attacks against finite fields are sub-exponential, forcing RSA and classical DH to much larger parameters.

The private key is a scalar k; the public key is the point k*G. ECDH mirrors Diffie-Hellman exactly: Alice sends a*G, Bob sends b*G, both compute (ab)*G.

Curve selection matters more than in RSA, because a curve is a large set of parameters that can hide weaknesses:

Curve	Size	Notes
P-256 (secp256r1)	256-bit	NIST standard, ubiquitous in TLS; constants of unexplained provenance
P-384, P-521	384/521-bit	NIST, higher security levels, CNSA-approved
Curve25519 (X25519)	255-bit	Bernstein; designed for safe, fast, constant-time implementation
Ed25519	255-bit	Edwards form of the same curve, for signatures
secp256k1	256-bit	Bitcoin and Ethereum; Koblitz curve, rarely used elsewhere

The practical criticism of the NIST curves is that their seed constants were never explained, and their implementation is error-prone: point validation, special cases in the addition law, and non-constant-time scalar multiplication have all caused real vulnerabilities. Curve25519 and Ed25519 were designed specifically to be hard to implement wrongly — every 32-byte string is a valid public key, the arithmetic has no exceptional cases, and reference implementations are naturally constant-time. Where you have the choice, prefer them.

Two implementation hazards deserve naming. Invalid curve attacks feed the victim a point from a different, weaker curve; if the implementation does not verify that the point satisfies the curve equation, the resulting secret can be solved for and the private key recovered. And nonce reuse in ECDSA (next topic) leaks the private key outright. Both are reasons to use vetted libraries and misuse-resistant schemes.

Examples

ELLIPTIC CURVE over the reals (the picture; real crypto uses mod p)

        y
        │        ╭───────────
        │      ╭─╯                y^2 = x^3 - 3x + 5
        │   ╭──╯
   ─────┼──╯──────────────── x
        │  ╰──╮
        │     ╰─╮
        │       ╰───────────

POINT ADDITION: P + Q = R
   draw the line through P and Q, take the third intersection,
   reflect it across the x-axis.

        │     P
        │    ╱│╲
        │   ╱ │ ╰─ Q
   ─────┼──╱──┼──────────── x
        │ ╱   │
        │     R'   <- third intersection
        │     R    <- reflection = P + Q

POINT DOUBLING: P + P uses the TANGENT at P.

SCALAR MULTIPLICATION = the one-way function
   k * G = G + G + ... + G   (k times, via double-and-add)

   k, G  ──── easy  ────►  P
   P, G  ──── ECDLP ────►  k      no efficient algorithm

KEY SIZE EQUIVALENCE
  security bits │  RSA/DH  │  ECC   │ ratio
       112      │   2048   │  224   │  9x
       128      │   3072   │  256   │ 12x
       192      │   7680   │  384   │ 20x
       256      │  15360   │  512   │ 30x

import os

from cryptography.hazmat.primitives import hashes, serialization
from cryptography.hazmat.primitives.asymmetric import ec, ed25519, x25519
from cryptography.hazmat.primitives.kdf.hkdf import HKDF

# --- Scalar multiplication on a toy curve: y^2 = x^3 + 2x + 3 mod 97 ----
P_MOD, A_COEF = 97, 2


def point_add(p1, p2):
    """Group law over a finite field. Production code must also be
    constant-time and handle every special case -- hence: use a library."""
    if p1 is None:
        return p2
    if p2 is None:
        return p1
    (x1, y1), (x2, y2) = p1, p2
    if x1 == x2 and (y1 + y2) % P_MOD == 0:
        return None                               # point at infinity
    if p1 == p2:
        s = (3 * x1 * x1 + A_COEF) * pow(2 * y1, -1, P_MOD) % P_MOD  # tangent
    else:
        s = (y2 - y1) * pow(x2 - x1, -1, P_MOD) % P_MOD              # chord
    x3 = (s * s - x1 - x2) % P_MOD
    return x3, (s * (x1 - x3) - y1) % P_MOD


def scalar_mult(k: int, point):
    """Double-and-add: O(log k) instead of O(k) additions."""
    result, addend = None, point
    while k:
        if k & 1:
            result = point_add(result, addend)
            addend = point_add(addend, addend)
        k >>= 1
    return result


G = (3, 6)                                   # a point on the toy curve
print("3G =", scalar_mult(3, G))
print("7G =", scalar_mult(7, G))


# --- ECDH with X25519: the preferred modern primitive -------------------
alice = x25519.X25519PrivateKey.generate()
bob = x25519.X25519PrivateKey.generate()
shared = alice.exchange(bob.public_key())          # 32 bytes
assert shared == bob.exchange(alice.public_key())

key = HKDF(algorithm=hashes.SHA256(), length=32,
           salt=None, info=b"x25519 demo").derive(shared)

# X25519's safety property: every 32-byte string is a valid public key,
# so there is no invalid-point attack surface to get wrong.
attacker_point = x25519.X25519PublicKey.from_public_bytes(os.urandom(32))
_ = alice.exchange(attacker_point)                 # safe, no exception path


# --- NIST curves: same job, more care required -------------------------
nist_priv = ec.generate_private_key(ec.SECP256R1())
peer = ec.generate_private_key(ec.SECP256R1()).public_key()
nist_shared = nist_priv.exchange(ec.ECDH(), peer)
# `from_encoded_point` validates that the point lies ON the curve;
# skipping that check is the invalid-curve attack.
pt = nist_priv.public_key().public_bytes(
    serialization.Encoding.X962,
    serialization.PublicFormat.UncompressedPoint,
)
ec.EllipticCurvePublicKey.from_encoded_point(ec.SECP256R1(), pt)


# --- Size comparison, the practical argument ---------------------------
from cryptography.hazmat.primitives.asymmetric import rsa

rsa3072 = rsa.generate_private_key(public_exponent=65537, key_size=3072)
for name, k in (("RSA-3072", rsa3072), ("P-256", nist_priv),
                ("Ed25519", ed25519.Ed25519PrivateKey.generate())):
    pem = k.public_key().public_bytes(
        serialization.Encoding.DER,
        serialization.PublicFormat.SubjectPublicKeyInfo)
    print(f"{name:>9} public key: {len(pem):>4} bytes")
# RSA-3072 ~ 398 bytes, P-256 ~ 91 bytes, Ed25519 ~ 44 bytes.
# Equivalent security; the certificate and handshake shrink accordingly.

Key Takeaways

• ECC provides equivalent security to RSA at roughly one-twelfth the key size, because ECDLP resists sub-exponential attacks that weaken finite fields.
• The private key is a scalar; the public key is that scalar times the base point. Scalar multiplication is the one-way function.
• ECDH mirrors Diffie-Hellman exactly, so all the authentication and ephemerality requirements carry over unchanged.
• Curve choice is a security decision: P-256 is ubiquitous, Curve25519 and Ed25519 are designed to resist implementation mistakes.
• X25519's "every 32-byte string is a valid key" property removes the invalid-point attack surface entirely.
• NIST curves require explicit point validation; omitting it enables invalid-curve attacks that recover the private key.
• Smaller keys mean smaller certificates and faster handshakes, which is why ECC is the default for new systems and mandatory in practice on constrained devices.

🧪 Practice

1. Using the toy curve code, compute kG for k from 1 to 10 and verify that each result satisfies y^2 = x^3 + 2x + 3 mod 97.
2. Measure and tabulate the DER-encoded public key sizes for RSA-2048, RSA-3072, P-256, and Ed25519, then compute the bytes saved per TLS handshake assuming a three-certificate chain.
3. Explain why X25519 needs no point validation while P-256 does, and describe what an invalid-curve attack achieves against an implementation that skips the check.
4. Interview-style: "Would you choose P-256 or X25519 for a new internal service, and why?" Hint: weigh ecosystem and compliance support (FIPS, hardware tokens, older TLS stacks) against implementation safety and performance — and note that the right answer may differ for a greenfield internal service versus a public-facing certificate.

Digital Signatures: RSA, DSA, ECDSA, EdDSA

Theory

Encryption answers "can anyone else read this?" Signatures answer a different and often more important question: "did this really come from who it claims, and has it been altered?" Signatures underpin software updates, TLS certificates, code signing, JWTs, and blockchain transactions.

A signature scheme provides three properties:

• Authenticity — the message came from the holder of the private key.
• Integrity — the message has not been modified since signing.
• Non-repudiation — the signer cannot plausibly deny signing, because only they hold the key. This is what distinguishes a signature from a MAC: a MAC uses a shared key, so either party could have produced it, and it therefore proves nothing to a third party.

Mechanically, every scheme hashes the message first and signs the hash. This is essential for three reasons: signature operations work on fixed-size inputs bounded by the key size, hashing a gigabyte file to 32 bytes makes signing cheap, and the hash binds the entire message. It also means the signature is only as strong as the hash — SHA-1 collisions enable signature forgery, which is why SHA-1 signatures were removed from certificates.

The four schemes in practice:

RSA signatures reverse the key roles: sign with the private key, verify with the public. Use PSS padding for new code, which is randomised and has a security proof. PKCS#1 v1.5 signatures remain common for compatibility and are not catastrophically broken, but implementation bugs in v1.5 verification (accepting trailing garbage, ignoring the hash OID) have caused real forgeries. RSA signatures are large (256 bytes at RSA-2048) and verification is fast, which suits certificates.

DSA uses the discrete logarithm problem and produces small signatures, but it has a brutal requirement: each signature needs a fresh random nonce k, and if k repeats or is predictable, the private key falls out of simple algebra. DSA is deprecated; FIPS 186-5 (2023) withdrew it for new signatures.

ECDSA is DSA over elliptic curves — small keys, small signatures, widely deployed in TLS, Bitcoin, and SSH. It inherits the nonce requirement, and this has caused spectacular real-world failures: the Sony PlayStation 3 code-signing key was recovered in 2010 because Sony used a constant k; Android Bitcoin wallets were drained in 2013 due to a broken SecureRandom. The defence is RFC 6979 deterministic ECDSA, which derives k from the private key and message hash via HMAC, eliminating the randomness dependency entirely.

EdDSA (Ed25519) is the modern default. It is deterministic by design — k is derived from the private key and message, so nonce reuse is structurally impossible — it is fast, it produces compact 64-byte signatures with 32-byte keys, and its reference implementations are naturally constant-time. It also avoids ECDSA's malleability. Choose Ed25519 for anything new unless a compliance regime or ecosystem forces otherwise.

Examples

SIGN AND VERIFY

  SIGNING                             VERIFICATION
  message ──► [ hash ] ──► h          message ──► [ hash ] ──► h'
                          │                                    │
            private key ──┤                      public key ───┤
                          ▼                                    ▼
                     signature ───────────────────────► valid / INVALID

  The signature covers the HASH, so it is only as strong as the hash.

SIGNATURE vs MAC

                   │ Key          │ Third party can verify │ Non-repudiation
  Signature (Ed25519)│ key pair   │ yes, with public key   │ yes
  MAC (HMAC)         │ shared     │ no                     │ NO -- either
                     │            │                        │ party could
                     │            │                        │ have made it

ECDSA NONCE REUSE => PRIVATE KEY RECOVERY

  s1 = k^-1 (h1 + r*d) mod n
  s2 = k^-1 (h2 + r*d) mod n       same k => same r
  ───────────────────────────
  k = (h1 - h2) / (s1 - s2) mod n          recover the nonce
  d = (s1*k - h1) / r     mod n            recover the PRIVATE KEY

  Real victims: Sony PS3 (constant k), Android wallets (broken RNG).
  Fixes: RFC 6979 deterministic ECDSA, or use Ed25519.

from cryptography.exceptions import InvalidSignature
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec, ed25519, padding, rsa

message = b"firmware-v4.2.1.bin sha256:9f86d081..."

# --- Ed25519: the modern default. Deterministic, compact, misuse-resistant.
ed_priv = ed25519.Ed25519PrivateKey.generate()
sig = ed_priv.sign(message)                  # no hash algorithm to choose,
print(len(sig))                              # no padding, no nonce: 64 bytes
ed_priv.public_key().verify(sig, message)    # raises InvalidSignature if bad

# Deterministic by construction -- signing twice gives identical output,
# which is why nonce reuse cannot happen.
assert ed_priv.sign(message) == sig


# --- ECDSA: widely deployed, inherits the nonce requirement ------------
ec_priv = ec.generate_private_key(ec.SECP256R1())
ec_sig = ec_priv.sign(message, ec.ECDSA(hashes.SHA256()))
print(len(ec_sig))                           # ~70-72 bytes, DER-encoded
# Randomised: two signatures over the same message differ.
assert ec_priv.sign(message, ec.ECDSA(hashes.SHA256())) != ec_sig


# --- RSA-PSS: large signatures, fast verification, suits certificates --
rsa_priv = rsa.generate_private_key(public_exponent=65537, key_size=2048)
pss = padding.PSS(mgf=padding.MGF1(hashes.SHA256()),
                  salt_length=padding.PSS.MAX_LENGTH)
rsa_sig = rsa_priv.sign(message, pss, hashes.SHA256())
print(len(rsa_sig))                          # 256 bytes


# --- Tampering is detected regardless of scheme -----------------------
for name, verify in (
    ("Ed25519", lambda m: ed_priv.public_key().verify(sig, m)),
    ("ECDSA", lambda m: ec_priv.public_key().verify(
        ec_sig, m, ec.ECDSA(hashes.SHA256()))),
    ("RSA-PSS", lambda m: rsa_priv.public_key().verify(
        rsa_sig, m, pss, hashes.SHA256())),
):
    try:
        verify(message.replace(b"4.2.1", b"4.2.0"))   # one version bumped
        print(f"{name}: ACCEPTED -- this would be a vulnerability")
    except InvalidSignature:
        print(f"{name}: rejected the modified message")


# --- The ECDSA nonce-reuse break, shown as algebra --------------------
def recover_ecdsa_key(r, s1, s2, h1, h2, n):
    """Two signatures sharing a nonce (identical r) leak the private key.
    This is pure algebra: no cryptanalysis and no brute force required."""
    k = (h1 - h2) * pow(s1 - s2, -1, n) % n       # recover the nonce
    return (s1 * k - h1) * pow(r, -1, n) % n      # recover the private key

Scheme	Key size	Signature size	Deterministic	Status
RSA-PSS	2048-4096 bits	256-512 bytes	No (salted)	Recommended for RSA
RSA PKCS#1 v1.5	2048+ bits	256+ bytes	Yes	Legacy; verification bugs are common
DSA	2048 bits	~56 bytes	No	Withdrawn (FIPS 186-5)
ECDSA (P-256)	256 bits	~72 bytes	No (unless RFC 6979)	Widely deployed; nonce-fragile
Ed25519	256 bits	64 bytes	Yes, by design	Preferred for new systems

Key Takeaways

• Signatures provide authenticity, integrity, and non-repudiation; MACs provide the first two but cannot prove anything to a third party.
• Every scheme signs a hash of the message, so the signature's strength is capped by the hash's collision resistance.
• RSA signatures should use PSS; PKCS#1 v1.5 verification bugs have produced real forgeries.
• DSA and ECDSA require a unique, unpredictable nonce per signature; reuse leaks the private key through simple algebra.
• The Sony PS3 and Android wallet compromises were both ECDSA nonce failures, not algorithm weaknesses.
• RFC 6979 deterministic ECDSA removes the randomness dependency; Ed25519 removes it structurally.
• Prefer Ed25519 for new systems: compact, fast, deterministic, and naturally constant-time.

🧪 Practice

1. Sign the same message twice with Ed25519 and twice with ECDSA. Explain why one pair is identical and the other is not, and which property each behaviour reflects.
2. Implement recover_ecdsa_key against two signatures you generate with a deliberately fixed nonce (use a small toy curve), and confirm you recover the private key.
3. Verify a real signature: download a package and its detached signature, then verify it with gpg --verify or openssl dgst -verify. Describe what the verification does and does not prove.
4. Interview-style: "When is a MAC sufficient and when do you need a signature?" Hint: ask who needs to be convinced — if only the two key-sharing parties, a MAC is cheaper; if a third party or a court must be convinced, the shared key destroys the argument.

Hybrid Cryptosystems

Theory

Symmetric cryptography is fast but cannot solve key distribution. Asymmetric cryptography solves key distribution but is slow and size-limited. A hybrid cryptosystem uses each for what it is good at: asymmetric cryptography to establish or wrap a symmetric key, and symmetric cryptography for all the actual data. Essentially every real system — TLS, SSH, PGP, Signal, age, S/MIME, encrypted messaging, encrypted backups — is a hybrid cryptosystem.

The performance argument is decisive. AES-GCM with hardware acceleration runs at several gigabytes per second. RSA-2048 performs a few thousand operations per second and can encrypt at most 190 bytes per operation. Encrypting a 1 GB file directly with RSA is not merely slow; it is impossible without chunking it into millions of blocks, each requiring a separate operation, which would also be insecure and produce a vastly larger ciphertext.

Two patterns exist, and the distinction matters:

Key transport (KEM-style). The sender generates a random symmetric key, encrypts the data with it, and encrypts the symmetric key under the recipient's public key. The recipient decrypts the key, then the data. This is how PGP and S/MIME encrypt files, and it suits store-and-forward messaging where the recipient is offline. It provides no forward secrecy: the wrapped key sits in the ciphertext forever, so compromising the long-term private key later decrypts everything ever sent.

Key agreement (ECIES / ECDH-style). The sender generates an ephemeral key pair, performs ECDH against the recipient's static public key, derives a symmetric key via a KDF, encrypts the data, and transmits the ephemeral public key alongside. The recipient repeats the ECDH with their private key. This is more compact and is the basis of TLS and modern tools like age. With ephemeral keys on both sides it also provides forward secrecy.

A critical design rule applies to both: multi-recipient encryption wraps one data key many times. Encrypt the file once under a random data key, then wrap that data key separately for each recipient's public key. This is how PGP encrypts to multiple people and how cloud KMS envelope encryption works, and it means adding a recipient does not require re-encrypting the data.

Three mistakes recur in hand-rolled hybrid schemes:

1. Using the raw DH output as a key. It must go through a KDF, with context in the info parameter to bind the key to its protocol and direction.
2. Forgetting authentication. Encrypting with the recipient's public key proves nothing about the sender; anyone can do it. Sender authenticity requires a signature or an authenticated exchange.
3. Not authenticating the wrapped key. The symmetric layer must be AEAD, and the wrapped key and any metadata should be covered by the AAD so an attacker cannot swap components between messages.

Examples

HYBRID ENCRYPTION: each primitive doing what it is good at

  ┌─────────────────── ASYMMETRIC (once, slow, small) ───────────────────┐
  │  recipient's public key  ──►  wrap/derive a 32-byte data key         │
  └──────────────────────────────────────────────────────────────────────┘
                                   │
                              data key (32 B)
                                   │
  ┌─────────────────── SYMMETRIC (bulk, fast, unlimited) ───────────────┐
  │  AES-256-GCM / ChaCha20-Poly1305  ──►  the entire 1 GB payload      │
  └──────────────────────────────────────────────────────────────────────┘

PATTERN A -- KEY TRANSPORT (PGP, S/MIME)
  wire format: [ RSA-OAEP(data key) ][ nonce ][ AES-GCM(data) ][ tag ]
  no forward secrecy: the wrapped key is in the ciphertext forever

PATTERN B -- KEY AGREEMENT (ECIES, TLS, age)
  wire format: [ ephemeral public key ][ nonce ][ AEAD(data) ][ tag ]
  smaller, and forward-secret when both sides are ephemeral

MULTI-RECIPIENT: wrap the data key once per recipient
  ┌──────────────────────────────────────────────────────┐
  │ wrap(pk_alice, DK) │ wrap(pk_bob, DK) │ wrap(pk_c,DK)│
  ├──────────────────────────────────────────────────────┤
  │        AEAD(DK, the payload)  -- encrypted ONCE      │
  └──────────────────────────────────────────────────────┘
  Adding a recipient = one more small wrap, no re-encryption.

PERFORMANCE
  AES-GCM (AES-NI) : ~3 GB/s          RSA-2048 decrypt: ~1500 ops/s
  Encrypting 1 GB  : ~0.3 s           ... and 190 bytes per op

import os

from cryptography.hazmat.primitives import hashes, serialization
from cryptography.hazmat.primitives.asymmetric import padding, rsa, x25519
from cryptography.hazmat.primitives.ciphers.aead import AESGCM
from cryptography.hazmat.primitives.kdf.hkdf import HKDF

OAEP = padding.OAEP(mgf=padding.MGF1(hashes.SHA256()),
                    algorithm=hashes.SHA256(), label=None)


# --- PATTERN A: key transport, multi-recipient (the PGP model) ---------
def seal_for_many(payload: bytes, recipients: dict) -> dict:
    """Encrypt the payload ONCE; wrap the data key per recipient."""
    data_key = AESGCM.generate_key(bit_length=256)
    nonce = os.urandom(12)
    # AAD binds the recipient list to the ciphertext so components
    # cannot be swapped between messages.
    aad = b"|".join(sorted(recipients)).encode()
    body = AESGCM(data_key).encrypt(nonce, payload, aad)
    return {
        "wrapped": {name: pk.encrypt(data_key, OAEP)
                    for name, pk in recipients.items()},
        "nonce": nonce,
        "body": body,
        "aad": aad,
    }


def unseal(env: dict, name: str, private_key) -> bytes:
    data_key = private_key.decrypt(env["wrapped"][name], OAEP)
    return AESGCM(data_key).decrypt(env["nonce"], env["body"], env["aad"])


alice = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob = rsa.generate_private_key(public_exponent=65537, key_size=2048)

payload = os.urandom(5_000_000)        # 5 MB: RSA alone could never do this
env = seal_for_many(payload, {"alice": alice.public_key(),
                              "bob": bob.public_key()})
assert unseal(env, "alice", alice) == unseal(env, "bob", bob) == payload
print(f"payload {len(payload):,} B, wrapped key {len(env['wrapped']['alice'])} B")


# --- PATTERN B: key agreement (ECIES), compact and forward-secret ------
def ecies_seal(payload: bytes, recipient_pub) -> tuple[bytes, bytes, bytes]:
    """An ephemeral key pair per message. The ephemeral private key is
    discarded immediately, so this message cannot be decrypted later even
    if the SENDER is fully compromised."""
    eph = x25519.X25519PrivateKey.generate()
    shared = eph.exchange(recipient_pub)
    eph_pub = eph.public_key().public_bytes(
        serialization.Encoding.Raw, serialization.PublicFormat.Raw)

    key = HKDF(
        algorithm=hashes.SHA256(), length=32, salt=None,
        # Binding the ephemeral key into `info` prevents an attacker from
        # substituting a different ephemeral public key.
        info=b"ecies-v1|" + eph_pub,
    ).derive(shared)

    nonce = os.urandom(12)
    # The ephemeral public key is authenticated as AAD.
    return eph_pub, nonce, AESGCM(key).encrypt(nonce, payload, eph_pub)


def ecies_open(eph_pub: bytes, nonce: bytes, ct: bytes, recipient_priv):
    shared = recipient_priv.exchange(
        x25519.X25519PublicKey.from_public_bytes(eph_pub))
    key = HKDF(algorithm=hashes.SHA256(), length=32, salt=None,
               info=b"ecies-v1|" + eph_pub).derive(shared)
    return AESGCM(key).decrypt(nonce, ct, eph_pub)


recipient = x25519.X25519PrivateKey.generate()
parts = ecies_seal(b"compact and forward-secret", recipient.public_key())
print(ecies_open(*parts, recipient))
# Overhead: 32 bytes ephemeral key vs 256 bytes for an RSA-2048 wrap.

Aspect	Key transport (RSA-OAEP wrap)	Key agreement (ECIES / ECDHE)
Overhead per message	256+ bytes (RSA-2048)	32 bytes (X25519)
Forward secrecy	No	Yes (with ephemeral keys)
Recipient must be online	No	No (static recipient key)
Used by	PGP, S/MIME, JWE RSA-OAEP	TLS 1.3, age, Signal, JWE ECDH-ES
Multi-recipient	Wrap per recipient	Derive per recipient

Key Takeaways

• Every practical system is hybrid: asymmetric cryptography establishes a symmetric key, and the symmetric cipher handles all the data.
• The motivation is hard necessity, not just speed: RSA-2048 can encrypt only 190 bytes per operation.
• Key transport wraps a random data key under a static public key and provides no forward secrecy.
• Key agreement derives the key from an ephemeral exchange, is far more compact, and gives forward secrecy.
• Multi-recipient encryption encrypts the payload once and wraps the data key per recipient, so adding a recipient is cheap.
• Always run the exchange output through a KDF with protocol-binding context, never use it directly as a key.
• Encrypting to a public key proves nothing about the sender; sender authenticity requires a signature or an authenticated exchange, and the symmetric layer must be AEAD with metadata in the AAD.

🧪 Practice

1. Measure the throughput of encrypting 100 MB with AES-256-GCM, then measure how many RSA-2048 OAEP operations per second your machine performs. Compute how long RSA-only encryption of 100 MB would take.
2. Extend seal_for_many to support revoking a recipient. Explain whether the payload must be re-encrypted and what that implies about already-distributed ciphertext.
3. Modify ecies_seal to omit the ephemeral public key from both info and the AAD, then describe what an attacker who can modify messages in transit gains.
4. Interview-style: "Design encrypted file sharing where any of five named people can decrypt, and one can later be removed." Hint: separate the data key from the recipient wraps, then be explicit that removal cannot un-distribute an existing ciphertext — it only affects future encryptions, which means you also need re-encryption and key rotation in the design.

Post-Quantum Cryptography Overview

Theory

A sufficiently large quantum computer would break all currently deployed public-key cryptography. This is not speculation about a new attack; it is a known consequence of Shor's algorithm (1994), which factors integers and computes discrete logarithms in polynomial time. RSA, finite-field Diffie-Hellman, ECDH, ECDSA, and EdDSA all fall. Symmetric cryptography and hashing are affected far less.

The asymmetry between the two halves of the field is the key insight:

Primitive	Quantum impact	Response
RSA, DH, ECDH, ECDSA, EdDSA	Broken by Shor's algorithm	Replace with post-quantum algorithms
AES-128	128 bits to ~64 bits (Grover)	Move to AES-256
AES-256	256 bits to ~128 bits (Grover)	Sufficient
SHA-256	Collision resistance reduced modestly	Sufficient; SHA-384 for margin

Grover's algorithm gives only a square-root speedup, so doubling a symmetric key size restores the original security level. Shor's algorithm, by contrast, is an exponential improvement, and no key size makes RSA or ECC safe.

The urgent consideration is "harvest now, decrypt later." An adversary can record encrypted traffic today and decrypt it once a quantum computer exists. For data with a long confidentiality lifetime — medical records, state secrets, identity documents, long-lived credentials — the threat is effectively present tense, even though no capable quantum computer exists yet. This is why migration began before the hardware arrived. Signatures are less exposed in this respect, since forging a signature after the fact is usually less valuable than decrypting past traffic, but long-lived roots of trust (code-signing roots, CA roots, firmware verification keys) do need forward planning.

NIST ran an eight-year standardization process and published the first standards in August 2024:

• ML-KEM (FIPS 203), formerly CRYSTALS-Kyber — a lattice-based key encapsulation mechanism, the replacement for ECDH key exchange.
• ML-DSA (FIPS 204), formerly CRYSTALS-Dilithium — a lattice-based signature scheme, the general-purpose replacement for ECDSA and Ed25519.
• SLH-DSA (FIPS 205), formerly SPHINCS+ — a hash-based signature scheme. Larger and slower, but its security rests only on hash functions, making it a conservative hedge if lattice assumptions fail.
• HQC was selected in 2025 as a backup KEM based on different (code-based) mathematics, for diversity.

The practical costs are real: ML-KEM-768 public keys are about 1,184 bytes versus 32 for X25519, and ML-DSA signatures run about 3,300 bytes versus 64 for Ed25519. This inflates handshakes and certificates measurably.

Current deployment practice is hybrid: combine a classical and a post-quantum algorithm so the result is secure if either holds. TLS now widely supports X25519MLKEM768, which concatenates both shared secrets into the KDF. Chrome and Firefox enable it by default, and Cloudflare and AWS support it server-side; a large share of TLS traffic is already post-quantum protected in the key-exchange step. Hybrid is the right choice because the post-quantum algorithms are young — the SIKE scheme was broken in 2022 by a classical attack after reaching the final round, which is exactly the risk hybrid mitigates.

For practitioners today the actionable steps are: inventory where public-key cryptography is used and what each key's confidentiality lifetime is; prefer AES-256 and SHA-384 for long-lived data; ensure crypto-agility so algorithms can be swapped without redesign; and enable hybrid key exchange where your stack supports it.

Examples

WHAT QUANTUM BREAKS

  SHOR'S ALGORITHM (polynomial time) -- catastrophic
    factoring      ──► RSA broken
    discrete log   ──► DH, ECDH broken
                   ──► DSA, ECDSA, EdDSA broken
    No key size helps.

  GROVER'S ALGORITHM (square-root speedup) -- manageable
    2**128 search  ──► 2**64    AES-128 weakened
    2**256 search  ──► 2**128   AES-256 still fine
    Doubling the key size restores the original level.

HARVEST NOW, DECRYPT LATER

  2026 ──── adversary records TLS traffic ────────────┐
                                                      │ store
  20XX ──── quantum computer available ───────────────┤
                                                      ▼
            Shor's algorithm ──► session keys ──► plaintext

  Data whose secrecy must outlive the quantum milestone is at risk TODAY.

HYBRID KEY EXCHANGE (what browsers ship now)

   X25519 shared secret ──┐
                          ├──► HKDF ──► session key
   ML-KEM-768 secret  ────┘
   Secure if EITHER component holds. Hedges both quantum attack
   and the youth of the PQ algorithm (cf. SIKE, broken in 2022).

SIZE COSTS
  primitive        │ public key │ signature/ciphertext
  X25519           │     32 B   │      32 B
  ML-KEM-768       │  1,184 B   │   1,088 B
  Ed25519          │     32 B   │      64 B
  ML-DSA-65        │  1,952 B   │   3,309 B
  SLH-DSA-128s     │     32 B   │   7,856 B

# NIST standards, August 2024. Library support is still maturing, so the
# exact import path varies; this is the shape of the API you will meet.
#
#   pip install pqcrypto        # or liboqs-python, or kyber-py

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import x25519
from cryptography.hazmat.primitives.kdf.hkdf import HKDF


def classical_exchange() -> tuple[bytes, bytes]:
    """X25519: 32-byte keys, broken by a future quantum computer."""
    a = x25519.X25519PrivateKey.generate()
    b = x25519.X25519PrivateKey.generate()
    return a.exchange(b.public_key()), b.exchange(a.public_key())


def hybrid_session_key(classical_secret: bytes, pq_secret: bytes) -> bytes:
    """The deployed pattern: feed BOTH secrets into one KDF.

    An attacker must break both X25519 AND ML-KEM to recover the key, so
    the construction survives either a quantum breakthrough or the
    discovery of a classical flaw in the young PQ algorithm."""
    return HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=None,
        info=b"hybrid X25519MLKEM768 v1",
    ).derive(classical_secret + pq_secret)   # concatenation, order fixed


# A KEM has a different shape from Diffie-Hellman: encapsulate/decapsulate
# rather than a symmetric exchange.
#
#   from pqcrypto.kem.ml_kem_768 import generate_keypair, encrypt, decrypt
#
#   public_key, secret_key = generate_keypair()        # 1184 B / 2400 B
#   ciphertext, shared = encrypt(public_key)           # 1088 B ciphertext
#   assert decrypt(secret_key, ciphertext) == shared

pq_shared = b"\x00" * 32                    # stand-in for the ML-KEM secret
classical, _ = classical_exchange()
print(hybrid_session_key(classical, pq_shared).hex()[:32])


# --- Crypto-agility: the design property that makes migration possible ---
SUITES = {
    "x25519":          {"kex": "X25519", "pq": None, "bytes": 32},
    "x25519mlkem768":  {"kex": "X25519", "pq": "ML-KEM-768", "bytes": 1216},
}


def negotiate(client_supported: list[str]) -> str:
    """Prefer hybrid when both sides support it, fall back cleanly.
    Hard-coding one algorithm is the real post-quantum risk: systems that
    cannot change algorithms cannot be migrated when they must be."""
    for suite in ("x25519mlkem768", "x25519"):
        if suite in client_supported:
            return suite
    raise ValueError("no mutually supported suite")


print(negotiate(["x25519", "x25519mlkem768"]))     # x25519mlkem768


# --- Inventory question: what is each key's confidentiality lifetime? ---
for data, years in (("session cookie", 0.01), ("payment token", 1),
                    ("medical record", 50), ("state secret", 75)):
    risk = "AT RISK -- migrate now" if years > 10 else "lower urgency"
    print(f"{data:<16} {years:>5} yr  {risk}")

Key Takeaways

• Shor's algorithm breaks RSA, DH, ECDH, ECDSA, and EdDSA in polynomial time; no key size rescues them.
• Grover's algorithm only halves effective symmetric key length, so AES-256 and SHA-384 remain adequate.
• "Harvest now, decrypt later" makes the threat present tense for any data whose confidentiality must outlive the quantum milestone.
• NIST standardized ML-KEM (FIPS 203), ML-DSA (FIPS 204), and SLH-DSA (FIPS 205) in August 2024, with HQC added in 2025 for mathematical diversity.
• Post-quantum keys and signatures are substantially larger, which measurably inflates handshakes and certificate chains.
• Hybrid constructions such as X25519MLKEM768 are secure if either component holds, hedging against both quantum attack and immaturity in the new algorithms — SIKE's 2022 classical break is the cautionary example.
• The most valuable thing to build today is crypto-agility: a system that cannot swap algorithms cannot be migrated when it must be.

🧪 Practice

1. Inventory the public-key cryptography in a system you know: list each use, the algorithm, and how long the protected data must stay confidential. Rank the entries by migration urgency.
2. Visit a TLS test site (for example https://pq.cloudflareresearch.com) in your browser and determine whether your connection negotiated a hybrid post-quantum key exchange. Then find the corresponding setting in your browser's configuration.
3. Compute the handshake size increase for a certificate chain of three ML-DSA-65 signatures and keys versus the same chain with Ed25519. Express it as bytes and as a percentage of a typical 5 KB handshake.
4. Interview-style: "Management asks whether to rip out RSA and ECDSA this quarter. What do you advise?" Hint: separate confidentiality (harvest-now-decrypt-later, urgent for long-lived data) from authentication (less urgent, forgery must happen in real time), and make the case for hybrid deployment and crypto-agility over a disruptive rip-and-replace.

<a id="34-hashing-and-integrity"></a>

3.4 Hashing and Integrity

Hash functions are the most-used cryptographic primitive and the most frequently misused. This section separates the three jobs that all get called "hashing" — integrity checking, message authentication, and password storage — because each demands a different function with opposite performance requirements.

Properties of Cryptographic Hash Functions

Theory

A cryptographic hash function maps input of any length to a fixed-length output (a digest) deterministically. SHA-256 maps a single byte or a terabyte file to exactly 32 bytes. The digest acts as a compact, unforgeable fingerprint of the data.

The useful mental model is a fingerprint: tiny compared to the person, effectively unique, trivially comparable, and useless for reconstructing the person. The analogy breaks down in one important way — a hash is deterministic, so identical inputs always produce identical digests, which is both the feature that makes comparison work and the weakness that makes unsalted password hashes crackable.

Three security properties define a cryptographic hash, in increasing strength:

1. Preimage resistance (one-wayness). Given h, it is infeasible to find any m with hash(m) = h. Cost for an n-bit hash: 2^n. This is what stops someone reversing a digest.
2. Second-preimage resistance. Given a specific m1, it is infeasible to find a different m2 with the same digest. Cost: 2^n. This is what stops substituting a different file for a specific known file.
3. Collision resistance. It is infeasible to find any pair m1 != m2 with the same digest. Cost: only 2^(n/2) because of the birthday paradox — the attacker gets to choose both messages, so they search for any match among many pairs rather than targeting one value.

The birthday bound is why output length matters so much. SHA-256's 256-bit output gives 256-bit preimage resistance but only 128-bit collision resistance. The same counting argument explains why 23 people in a room give a 50 percent chance of a shared birthday: you are comparing 253 pairs, not 23 individuals.

Two further properties are required in practice:

• The avalanche effect. Flipping one input bit should change about half the output bits, with no detectable pattern. Without it, digests of similar inputs would be similar, leaking information and enabling targeted search.
• Efficiency — but note this cuts both ways. Fast hashing is exactly what you want for verifying a 10 GB download and exactly what you must not have for storing passwords, where the attacker's guessing rate is the thing you are trying to limit.

The critical limitation to internalize: a bare hash provides integrity against accidental corruption, not against an attacker. Anyone who can modify the file can recompute and replace the digest. Real integrity against an adversary requires a key: a MAC (shared key) or a signature (key pair). A checksum published on the same server as the download protects against bit rot and truncated transfers, not against a compromise of that server.

Examples

FIXED OUTPUT, ANY INPUT

  ""              ──► SHA-256 ──► e3b0c44298fc1c14...  (32 bytes)
  "a"             ──► SHA-256 ──► ca978112ca1bbdca...  (32 bytes)
  10 GB ISO file  ──► SHA-256 ──► 7f83b1657ff1fc53...  (32 bytes)

THE THREE PROPERTIES

  PREIMAGE          given  h  ──find──►  any m with hash(m)=h     2**n
                    "reverse the digest"

  SECOND PREIMAGE   given m1  ──find──►  m2 != m1, same digest    2**n
                    "substitute for THIS specific file"

  COLLISION         given nothing ──find──► ANY m1 != m2 colliding 2**(n/2)
                    "forge a pair you control"       <- BIRTHDAY BOUND

WHY COLLISIONS ARE CHEAPER (birthday paradox)
  targeting ONE value : check 2**n candidates
  finding ANY pair    : 2**(n/2) candidates gives 2**n PAIRS to compare

  SHA-256: 256-bit preimage resistance, 128-bit COLLISION resistance

AVALANCHE EFFECT
  "hello"  ──► 2cf24dba5fb0a30e26e83b2ac5b9e29e...
  "hellp"  ──► 7a6cfb4cbb1f1a52c0b43b1a0b0d2d7f...
               ^ one input bit changed, ~50% of output bits differ

BARE HASH IS NOT ADVERSARIAL INTEGRITY
  attacker modifies file ──► recomputes digest ──► replaces published digest
  Needs a KEY to stop:  MAC (shared key)  or  SIGNATURE (key pair)

import hashlib
import hmac
import os

# --- Determinism and fixed output size --------------------------------
for data in (b"", b"a", b"a" * 1_000_000):
    d = hashlib.sha256(data).hexdigest()
    print(f"{len(data):>9} bytes -> {d[:16]}... ({len(d) // 2} bytes)")


# --- Avalanche effect, measured --------------------------------------
def hamming_distance(a: bytes, b: bytes) -> int:
    return sum(bin(x ^ y).count("1") for x, y in zip(a, b))


h1 = hashlib.sha256(b"hello").digest()
h2 = hashlib.sha256(b"hellp").digest()          # one bit differs in input
print(f"output bits changed: {hamming_distance(h1, h2)} / 256")   # ~128


# --- The birthday bound, demonstrated on a truncated hash ------------
def find_collision(bits: int) -> tuple[bytes, bytes, int]:
    """Truncate SHA-256 to `bits` and search for any colliding pair.
    Expected work is ~2**(bits/2), not 2**bits -- run it and see."""
    seen, attempts = {}, 0
    while True:
        candidate = os.urandom(16)
        attempts += 1
        digest = hashlib.sha256(candidate).digest()
        truncated = int.from_bytes(digest, "big") >> (256 - bits)
        if truncated in seen and seen[truncated] != candidate:
            return seen[truncated], candidate, attempts
        seen[truncated] = candidate


a, b, n = find_collision(32)
print(f"32-bit collision in {n:,} attempts (expect ~2**16 = 65,536)")
assert hashlib.sha256(a).digest()[:4] == hashlib.sha256(b).digest()[:4]


# --- Bare hash vs keyed MAC: the adversarial difference --------------
file_data = b"transfer 100 USD to account 999"

# Integrity against ACCIDENT only: an attacker recomputes both.
checksum = hashlib.sha256(file_data).hexdigest()

# Integrity against an ATTACKER: without the key, no valid tag exists.
mac_key = os.urandom(32)
tag = hmac.new(mac_key, file_data, hashlib.sha256).digest()

tampered = b"transfer 900 USD to account 999"
print("recomputed checksum matches tampered file:",
      hashlib.sha256(tampered).hexdigest() ==
      hashlib.sha256(tampered).hexdigest())            # True -- useless
print("MAC verifies for tampered file:",
      hmac.compare_digest(tag, hmac.new(mac_key, tampered,
                                        hashlib.sha256).digest()))  # False

Property	Attacker's goal	Cost (n-bit hash)	Broken for MD5/SHA-1?
Preimage resistance	Reverse a digest	2^n	No (MD5 preimage still ~2^123)
Second-preimage	Match a given message	2^n	No
Collision resistance	Find any colliding pair	2^(n/2)	Yes — MD5 seconds, SHA-1 feasible

Key Takeaways

• A cryptographic hash is deterministic, fixed-output, and one-way, acting as a compact fingerprint of arbitrary data.
• The three properties are preimage, second-preimage, and collision resistance, in increasing strength and decreasing attack cost.
• Collision resistance is only half the output length because of the birthday bound: SHA-256 gives 128-bit collision resistance.
• The avalanche effect means a one-bit input change flips about half the output bits, with no exploitable pattern.
• Hash speed is a feature for file verification and a serious liability for password storage.
• A bare hash detects accidents, not attackers: anyone who can change the data can change the digest, so adversarial integrity requires a key (MAC or signature).

🧪 Practice

1. Run find_collision for 16, 24, and 32 bits, averaging over several runs, and plot attempts against bit length. Confirm the growth matches 2^(bits/2).
2. Measure the avalanche effect properly: hash 1,000 random inputs and their single-bit-flipped variants, and report the mean and standard deviation of the number of changed output bits.
3. Explain why a Linux distribution publishes both a SHA-256 checksum file and a detached GPG signature of that checksum file. State precisely what each one defends against.
4. Interview-style: "SHA-256 has 256-bit output. How much security does it actually provide?" Hint: the answer depends on which property matters for the use case — distinguish the preimage figure from the collision figure, and name a scenario where only the smaller one is relevant.

MD5 and SHA-1 Collision Attacks

Theory

MD5 and SHA-1 are the clearest case study in cryptographic deprecation: both were universal, both were known to be theoretically weak years before practical attacks, and both took far too long to remove. Understanding their breaks teaches what a collision actually lets an attacker do, which is more subtle than "the hash is broken."

MD5 (1992, 128-bit output) was the default hash for a decade. Weaknesses appeared in 1996, Wang and Yu published a practical collision attack in 2004, and today a collision can be produced in seconds on a laptop. The devastating real-world consequence was Flame (2012), state-sponsored malware that forged a Microsoft code-signing certificate by exploiting an MD5-based CA signature, letting it appear as a legitimate Windows Update.

SHA-1 (1995, 160-bit output) replaced it. Theoretical attacks appeared in 2005, NIST deprecated it in 2011, and in 2017 Google and CWI executed SHAttered, producing two different PDF files with the same SHA-1 digest at a cost of about 6,500 CPU-years (roughly 110,000 dollars of cloud compute at the time). In 2020 the SHA-1 is a Shambles attack demonstrated a chosen-prefix collision for about 45,000 dollars, which is the dangerous variant: the attacker controls meaningful content on both sides rather than merely finding two random colliding blobs. Browsers stopped trusting SHA-1 certificates in 2017, and Git has since adopted collision detection.

The important nuance is what a collision does and does not enable:

• A collision lets an attacker create two documents of their own with the same digest, get one signed or approved, and then substitute the other. This breaks code signing, certificates, document notarization, and any "approved artifact" workflow.
• A collision does not let an attacker match the digest of an existing file they did not create — that would require second-preimage resistance, which is not broken for MD5 or SHA-1. So an attacker cannot forge a malicious file matching a published checksum of a file they did not author.

This distinction is why "MD5 is fine for checksums" is a half-truth. Against accidental corruption it works. Against an attacker who authored the original file, or who can substitute their own artifact into a signing pipeline, it fails completely. The safe policy is simply to use SHA-256, since there is no performance reason not to.

Both hashes also share a structural flaw worth knowing: the Merkle-Damgard construction processes the message in blocks, carrying state forward, and outputs that state directly. This enables length-extension attacks: given hash(secret || message) and the length of the secret, an attacker can compute hash(secret || message || padding || extra) without knowing the secret. This breaks naive "hash the secret with the data" authentication schemes — Flickr's API was compromised this way in 2009. MD5, SHA-1, and SHA-2 are all affected; SHA-3 and BLAKE2 are not, and HMAC's nested construction defeats it by design.

Examples

COLLISION ATTACK COST OVER TIME

  MD5     1992 published
          1996 structural weakness found
          2004 practical collisions (Wang & Yu)
          2008 rogue CA certificate demonstrated
          2012 FLAME forges a Microsoft code-signing certificate
          now  collisions in SECONDS on a laptop

  SHA-1   1995 published
          2005 theoretical attack (2**69 < 2**80 brute force)
          2011 NIST deprecates
          2017 SHAttered: real collision, ~6500 CPU-years / ~$110k
          2020 Shambles: CHOSEN-PREFIX collision, ~$45k
          now  within reach of well-funded attackers

WHAT A COLLISION ENABLES -- and what it does not

  BROKEN (collision resistance)         STILL SAFE (second preimage)
  ─────────────────────────────         ────────────────────────────
  attacker writes doc A and doc B       attacker is GIVEN your file
  same digest, different content        must find a different file
  gets A signed, ships B                with YOUR file's digest
  => code signing, certificates,        => matching a published
     notarisation all broken               checksum you did not author
                                            is NOT feasible

MERKLE-DAMGARD LENGTH EXTENSION (MD5, SHA-1, SHA-2)

  hash(secret || msg) outputs the INTERNAL STATE directly
     │
     └──► attacker resumes from that state without knowing `secret`
          and computes hash(secret || msg || padding || attacker_data)

  Vulnerable:  tag = sha256(secret + message)        <- NEVER do this
  Safe:        tag = hmac_sha256(secret, message)
  Immune by construction: SHA-3 (sponge), BLAKE2

import hashlib
import hmac

# --- The SHAttered PDFs: real colliding files, verifiable yourself -----
# Download from https://shattered.io/ then:
#   sha1sum shattered-1.pdf shattered-2.pdf   -> IDENTICAL digests
#   sha256sum shattered-1.pdf shattered-2.pdf -> different digests
# The files render as visibly different documents.

# --- Which algorithms to use ------------------------------------------
BROKEN = {"md5", "sha1"}
ACCEPTABLE = {"sha256", "sha384", "sha512", "sha3_256", "blake2b"}


def safe_digest(data: bytes, algorithm: str = "sha256") -> str:
    if algorithm in BROKEN:
        raise ValueError(f"{algorithm} has practical collision attacks")
    return hashlib.new(algorithm, data).hexdigest()


# --- LENGTH EXTENSION: why naive keyed hashing is not a MAC -----------
SECRET = b"server-side-secret-key"


def broken_tag(message: bytes) -> str:
    """VULNERABLE: the digest leaks the internal state, so an attacker who
    knows len(SECRET) can append data and produce a valid tag."""
    return hashlib.sha256(SECRET + message).hexdigest()


def correct_tag(message: bytes) -> str:
    """HMAC's nested construction (inner and outer hash with derived keys)
    means the output is not a resumable internal state."""
    return hmac.new(SECRET, message, hashlib.sha256).hexdigest()


# The attack, conceptually: given broken_tag(b"user=guest"), an attacker
# computes a valid tag for b"user=guest" + padding + b"&admin=true"
# using a length-extension tool (e.g. hashpumpy), never learning SECRET.
original = b"user=guest&role=viewer"
print("vulnerable tag:", broken_tag(original)[:16], "...")
print("correct tag:   ", correct_tag(original)[:16], "...")


# --- Verifying with constant-time comparison --------------------------
def verify(message: bytes, provided: str) -> bool:
    expected = correct_tag(message)
    # `==` on strings leaks the match prefix through timing.
    return hmac.compare_digest(expected, provided)


print(verify(original, correct_tag(original)))            # True
print(verify(original, correct_tag(b"user=admin")))       # False


# --- Where MD5 and SHA-1 legitimately survive -------------------------
# Non-security uses only: hash table keys, cache busting, deduplication of
# non-adversarial data, and legacy protocol compatibility. Even here,
# BLAKE3 or xxHash are faster, so there is rarely a reason to choose MD5.
print(hashlib.md5(b"cache-key", usedforsecurity=False).hexdigest()[:16])

Hash	Output	Collision cost	Status	Acceptable use
MD5	128 bits	Seconds	Broken	Non-security only (cache keys)
SHA-1	160 bits	~$45k (chosen-prefix)	Broken	Legacy compatibility only
SHA-256	256 bits	2^128	Secure	General purpose
SHA-512	512 bits	2^256	Secure	Faster on 64-bit CPUs
SHA-3-256	256 bits	2^128	Secure	Length-extension immune
BLAKE2/BLAKE3	Variable	2^(n/2)	Secure	Fast, length-extension immune

Key Takeaways

• MD5 collisions take seconds and SHA-1 chosen-prefix collisions cost roughly 45,000 dollars; both are broken for any security purpose.
• A collision lets an attacker create two colliding documents of their own, breaking code signing, certificates, and approval workflows — Flame forged a Microsoft certificate this way.
• A collision does not let an attacker match an existing file's digest; that requires second-preimage resistance, which remains unbroken.
• Both hashes were known to be weak years before practical attacks, and deprecation still lagged badly — treat theoretical weakening as the signal to migrate.
• MD5, SHA-1, and SHA-2 are all vulnerable to length extension because of the Merkle-Damgard construction, which breaks hash(secret || message) as an authentication scheme.
• Use HMAC rather than keyed hashing, and SHA-3 or BLAKE2 if length-extension immunity is needed in the primitive itself.
• SHA-256 is the default; there is no performance argument for retaining MD5 or SHA-1 in new code.

🧪 Practice

1. Download the two SHAttered PDFs, confirm their SHA-1 digests match and their SHA-256 digests do not, and open both to see they differ visually.
2. Install a length-extension tool and forge a valid broken_tag for user=guest&role=viewer&role=admin, given only the original tag and the secret length. Then verify the same attack fails against correct_tag.
3. Audit a codebase for md5 and sha1 usage, classify each occurrence as security-relevant or not, and write the remediation for the security-relevant ones.
4. Interview-style: "A colleague says MD5 is still fine for verifying file downloads because nobody can reverse it. What is right and wrong in that claim?" Hint: they are correct about preimage resistance and wrong about the relevant threat — distinguish who authored the file, and consider the case where the attacker supplies both the file and the checksum.

SHA-2 and SHA-3 Families

Theory

After SHA-1's weakening, two standard families emerged. Understanding why both exist — and why SHA-3 is not simply "better" — prevents a common misconception.

SHA-2 (2001) is a family sharing one design: SHA-224, SHA-256, SHA-384, SHA-512, and the truncated variants SHA-512/224 and SHA-512/256. It uses the same Merkle-Damgard construction as SHA-1 but with a strengthened compression function, more rounds, and larger state. It has resisted two decades of cryptanalysis with no meaningful attack on the full function, and it is the workhorse of modern cryptography: TLS, Bitcoin, code signing, and HMAC all use it.

A performance detail that surprises people: SHA-512 is often faster than SHA-256 on 64-bit CPUs, because it operates on 64-bit words. Where output size permits, SHA-512/256 (SHA-512 truncated to 256 bits) gives SHA-256's output length with SHA-512's speed, plus length-extension resistance from the truncation.

SHA-3 (2015, originally Keccak) was standardized not because SHA-2 was broken but as insurance. NIST ran an open competition precisely so that a structurally different alternative would be ready if SHA-2 ever fell. SHA-3 uses a completely different design — a sponge construction — so an attack on SHA-2's Merkle-Damgard structure would not transfer.

The sponge works in two phases. In the absorbing phase, message blocks are XORed into part of a large internal state (1,600 bits for SHA-3) and the state is permuted. In the squeezing phase, output is read out of the state, permuting between reads. The state is divided into a rate (the part touched by input and output) and a capacity (never directly exposed), and the capacity determines the security level. Because the full state is never output, sponges are immune to length extension — a structural advantage over SHA-2.

The sponge also enables extendable-output functions (XOFs): SHAKE128 and SHAKE256 produce output of any requested length. This is genuinely useful for mask generation, key derivation, and post-quantum schemes, and has no SHA-2 equivalent.

The practical guidance:

• SHA-256 remains the default. It is ubiquitous, hardware-accelerated on modern CPUs (SHA-NI on x86, ARMv8 crypto extensions), and secure.
• SHA-3 is chosen for structural diversity, length-extension immunity, or XOF needs. It is typically slower than SHA-2 in software because it lacks equivalent hardware support in most deployments.
• BLAKE2 and BLAKE3 deserve mention: BLAKE2 was a SHA-3 finalist and is faster than SHA-2 in software with length-extension immunity and built-in keying; BLAKE3 is faster still and parallelizable via a Merkle tree, making it excellent for large files. They are not NIST standards, which matters for compliance but not for security.

Examples

MERKLE-DAMGARD (SHA-1, SHA-2) -- state is the output

  IV ──►[ f ]──►[ f ]──►[ f ]──► DIGEST
         ▲       ▲       ▲
        M1      M2      M3

  The final internal state IS the digest  =>  resumable
                                          =>  length extension possible

SPONGE (SHA-3) -- capacity is never exposed

      ABSORB                        SQUEEZE
  M1    M2    M3
   │     │     │
   ▼     ▼     ▼
 ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
 │ r │ │ r │ │ r │ │ r │─┬─► output block 1
 ├───┤ ├───┤ ├───┤ ├───┤ │ ┌───┐
 │ c │ │ c │ │ c │ │ c │ └─│ r │──► output block 2  (XOF: repeat as needed)
 └───┘ └───┘ └───┘ └───┘   ├───┤
   └─ permute ─┴─ permute ─┘ │ c │
                            └───┘
  r = rate (touched by I/O)   c = capacity (NEVER output)
  state = 1600 bits;  security = c/2
  Capacity hidden => NO length extension, and output can be ANY length.

FAMILY OVERVIEW
  SHA-2:  SHA-224  SHA-256  SHA-384  SHA-512  SHA-512/224  SHA-512/256
  SHA-3:  SHA3-224 SHA3-256 SHA3-384 SHA3-512 + SHAKE128, SHAKE256 (XOF)

import hashlib
import time

data = b"x" * 10_000_000            # 10 MB

# --- SHA-2 family ----------------------------------------------------
for name in ("sha224", "sha256", "sha384", "sha512"):
    print(f"{name:>10}: {hashlib.new(name, b'test').hexdigest()[:16]}...")

# SHA-512/256: SHA-256's output length at SHA-512's speed, plus the
# truncation makes it length-extension resistant.
print("sha512_256:", hashlib.new("sha512_256", b"test").hexdigest()[:16])


# --- SHA-3 family and XOFs -------------------------------------------
print("sha3_256  :", hashlib.sha3_256(b"test").hexdigest()[:16])

# SHAKE: ANY output length from one function. No SHA-2 equivalent.
shake = hashlib.shake_256(b"seed material")
print("shake 16B :", shake.hexdigest(16))
print("shake 64B :", shake.hexdigest(64))     # same function, longer output


# --- Speed: why SHA-512 can beat SHA-256 on 64-bit CPUs -------------
def bench(name: str) -> float:
    t0 = time.perf_counter()
    hashlib.new(name, data)
    return (time.perf_counter() - t0) * 1000


for name in ("sha256", "sha512", "sha512_256", "sha3_256", "blake2b"):
    print(f"{name:>12}: {bench(name):>7.1f} ms")
# Typical ordering without SHA-NI: blake2b < sha512 ~ sha512_256
#                                  < sha256 < sha3_256


# --- Length extension: SHA-2 vulnerable, SHA-3 immune ---------------
# Both of these leak nothing about the secret directly, but only the
# SHA-3 version resists an attacker appending data to the message.
secret = b"key"
sha2_state_exposed = hashlib.sha256(secret + b"msg").hexdigest()   # extendable
sha3_capacity_hidden = hashlib.sha3_256(secret + b"msg").hexdigest()  # not

# Still use HMAC rather than relying on this, for domain separation
# and because HMAC is what every peer implementation expects.


# --- BLAKE2: keyed hashing without the HMAC wrapper ------------------
keyed = hashlib.blake2b(b"message", key=b"secret-key", digest_size=32)
print("blake2b keyed:", keyed.hexdigest()[:16])
# BLAKE2's built-in keying is a secure MAC by design -- no nesting needed.

Family	Construction	Length extension	XOF	Hardware accel	Typical use
SHA-2 (256/512)	Merkle-Damgard	Vulnerable	No	Yes (SHA-NI, ARMv8)	Default everywhere
SHA-512/256	Merkle-Damgard + truncation	Resistant	No	Partial	256-bit output, 64-bit speed
SHA-3	Sponge (Keccak)	Immune	SHAKE128/256	Rare	Structural diversity, XOF
BLAKE2	HAIFA / ChaCha-like	Immune	No	No (fast in software)	Fast keyed hashing
BLAKE3	Merkle tree	Immune	Yes	No (parallelizable)	Large files, high throughput

Key Takeaways

• SHA-2 is secure and remains the default; SHA-3 was standardized as structural insurance, not because SHA-2 failed.
• SHA-2 uses Merkle-Damgard and is length-extension vulnerable; SHA-3's sponge never exposes its capacity and is immune.
• The sponge construction enables XOFs (SHAKE128/256) that produce arbitrary-length output, which SHA-2 cannot do.
• SHA-512 is often faster than SHA-256 on 64-bit CPUs, and SHA-512/256 combines that speed with a 256-bit, length-extension-resistant output.
• SHA-3 is usually slower in software because hardware acceleration for SHA-2 is widespread and for SHA-3 is not.
• BLAKE2 and BLAKE3 are faster than SHA-2 in software with built-in keying and length-extension immunity, at the cost of not being NIST standards.
• Choose SHA-256 by default, SHA-3 or BLAKE2 when you need length-extension immunity or an XOF, and let compliance requirements settle ties.

🧪 Practice

1. Benchmark SHA-256, SHA-512, SHA3-256, and BLAKE2b on 100 MB. Check whether your CPU reports SHA-NI support and explain how that changes the ranking.
2. Use SHAKE256 to derive 16, 32, and 64 bytes from the same seed, and explain why the shorter outputs are not simply prefixes of the longer one (verify whether they are).
3. Explain why SHA-512/256 resists length extension while SHA-512 does not, in terms of what the final output reveals about the internal state.
4. Interview-style: "Should we migrate from SHA-256 to SHA-3?" Hint: establish whether there is a concrete driver — length-extension exposure, an XOF requirement, a compliance mandate, or algorithm diversity policy — because without one the migration cost buys nothing.

Message Authentication Codes (HMAC)

Theory

A hash gives integrity against accidents. A MAC gives integrity and authenticity against an attacker, because producing a valid tag requires a secret key. The MAC is what you reach for whenever two parties share a key and need to know that a message arrived unmodified from the other party.

The naive approach — tag = hash(key || message) — is broken by the length-extension attack described earlier: the digest exposes the hash's internal state, so an attacker can append data and compute a valid tag without the key. The variant hash(message || key) is also weak, because a collision in the message part produces identical tags regardless of the key.

HMAC (RFC 2104) solves this with a nested construction:

HMAC(K, m) = H( (K XOR opad) || H( (K XOR ipad) || m ) )

The inner hash processes the message with one key-derived prefix; the outer hash processes that result with a different key-derived prefix. Because the output of the inner hash is fed into a fresh hash invocation, the final digest is not a resumable internal state, which kills length extension. HMAC has a security proof reducing its strength to properties of the underlying compression function, and — importantly — HMAC-SHA1 and even HMAC-MD5 remain unbroken as MACs, because HMAC's security does not depend on collision resistance. (Use HMAC-SHA256 anyway; there is no reason not to.)

Two non-negotiable implementation requirements:

1. Constant-time comparison. Comparing tags with == returns as soon as bytes differ, leaking the length of the matching prefix through timing. An attacker forges a tag byte by byte, needing only 256 attempts per byte. Always use hmac.compare_digest or the platform equivalent.
2. Cover everything that matters. A MAC authenticates exactly the bytes fed into it. If the IV, the message type, the recipient, or the expiry is outside the MAC, an attacker can change it. The classic failure is MACing the payload but not the algorithm field — the JWT alg: none family of vulnerabilities.

The crucial conceptual distinction is MAC versus signature. Both provide integrity and authenticity. A MAC uses a shared key, so either party could have produced any tag, and it therefore offers no non-repudiation — it cannot convince a third party of anything. A signature uses a key pair, so only the private key holder could have produced it, and a third party with the public key can verify. MACs are far faster and have smaller tags, so use them when both parties share a key and no third party needs convincing.

Related constructions worth knowing: CMAC (AES-based, for environments with AES hardware but no hash), Poly1305 (a one-time MAC used inside ChaCha20-Poly1305 and AES-GCM-style AEADs), and KMAC (SHA-3-based). And when you need both confidentiality and authenticity, do not compose a cipher and a MAC by hand — use AEAD.

Examples

HMAC CONSTRUCTION

  K ──► pad/hash to block size ──► K'
                                    │
          ┌─────────────────────────┴──────────────────────┐
          │                                               │
    K' XOR ipad (0x36...)                        K' XOR opad (0x5c...)
          │                                               │
          ▼                                               ▼
   ┌─────────────┐                               ┌─────────────┐
   │ H(ipad||msg)│ ────────── inner digest ─────►│ H(opad||.)  │──► TAG
   └─────────────┘                               └─────────────┘

  The inner digest enters a FRESH hash => the output is not a resumable
  state => length extension is impossible.

MAC vs SIGNATURE

                       │ MAC (HMAC)          │ Signature (Ed25519)
  key                  │ shared secret       │ private/public pair
  who can create       │ both parties        │ only the key holder
  who can verify       │ both parties        │ anyone with the public key
  non-repudiation      │ NO                  │ YES
  tag size             │ 32 bytes            │ 64 bytes
  speed                │ very fast           │ ~1000x slower
  use when             │ two parties, shared │ third party must be
                       │ key, no dispute     │ convinced

TIMING ATTACK ON NAIVE COMPARISON

  expected = a3 9f 2c 71 ...
  attacker = 00 ...        -> returns after 1 byte   (fast)
  attacker = a3 00 ...     -> returns after 2 bytes  (slower!)
                              ^ the delta reveals the byte was correct

  256 guesses per byte x 32 bytes = 8192 requests to forge a tag.
  FIX: hmac.compare_digest -- runtime independent of content.

import hashlib
import hmac
import os
import time

KEY = os.urandom(32)


# --- Correct MAC generation and verification -------------------------
def sign(message: bytes) -> bytes:
    return hmac.new(KEY, message, hashlib.sha256).digest()


def verify(message: bytes, tag: bytes) -> bool:
    expected = sign(message)
    # MUST be constant-time. `expected == tag` is a vulnerability.
    return hmac.compare_digest(expected, tag)


msg = b"amount=100&to=alice"
tag = sign(msg)
print(verify(msg, tag))                              # True
print(verify(b"amount=900&to=alice", tag))           # False


# --- MAC EVERYTHING THAT MATTERS -------------------------------------
def bad_token(user: str, role: str, expiry: int) -> dict:
    """VULNERABLE: `role` is outside the MAC, so the client can change it."""
    return {"user": user, "role": role, "exp": expiry,
            "tag": sign(f"{user}|{expiry}".encode()).hex()}


def good_token(user: str, role: str, expiry: int) -> dict:
    """Every field that affects a decision is inside the MAC. The length
    prefixes prevent ambiguity: ("a|b", "c") and ("a", "b|c") must not
    produce the same MAC input."""
    payload = f"{len(user)}:{user}|{len(role)}:{role}|{expiry}"
    return {"user": user, "role": role, "exp": expiry,
            "tag": sign(payload.encode()).hex()}


t = bad_token("alice", "viewer", 1800000000)
t["role"] = "admin"                   # the tag still verifies -- privilege escalation
print("bad_token tag still valid:",
      verify(f"{t['user']}|{t['exp']}".encode(), bytes.fromhex(t["tag"])))


# --- The timing leak, demonstrated -----------------------------------
def insecure_verify(message: bytes, tag: bytes) -> bool:
    expected = sign(message)
    for a, b in zip(expected, tag):
        if a != b:
            return False              # early exit == measurable timing signal
    return len(expected) == len(tag)


def timed(fn, message, tag, trials=2000) -> float:
    t0 = time.perf_counter_ns()
    for _ in range(trials):
        fn(message, tag)
    return (time.perf_counter_ns() - t0) / trials


wrong_first = bytes([tag[0] ^ 0xFF]) + tag[1:]        # fails at byte 0
wrong_last = tag[:-1] + bytes([tag[-1] ^ 0xFF])       # fails at byte 31
print(f"insecure, fail at byte 0 : {timed(insecure_verify, msg, wrong_first):.0f} ns")
print(f"insecure, fail at byte 31: {timed(insecure_verify, msg, wrong_last):.0f} ns")
print(f"secure,   fail at byte 0 : {timed(verify, msg, wrong_first):.0f} ns")
print(f"secure,   fail at byte 31: {timed(verify, msg, wrong_last):.0f} ns")
# The insecure pair diverges; the secure pair does not.


# --- Why HMAC and not hash(key + message) ---------------------------
naive = hashlib.sha256(KEY + msg).hexdigest()   # length-extension vulnerable
proper = sign(msg).hex()                        # safe

Construction	Based on	Tag size	Notes
HMAC-SHA256	Hash	32 bytes	Default choice, universally supported
HMAC-SHA512	Hash	64 bytes	Faster on 64-bit CPUs
CMAC-AES	Block cipher	16 bytes	For AES-hardware-only environments
Poly1305	Polynomial in GF(2^130-5)	16 bytes	One-time key; used inside AEADs
KMAC	SHA-3	Variable	Length-extension immune primitive
BLAKE2 keyed	Hash with native keying	Variable	No nesting needed

Key Takeaways

• A MAC provides integrity and authenticity against an active attacker because forging a tag requires the shared key.
• hash(key || message) is not a MAC: length extension lets an attacker append data and produce a valid tag.
• HMAC's nested construction defeats length extension and has a security proof that does not rely on collision resistance.
• Tag comparison must be constant-time; == leaks the matching prefix and allows byte-by-byte forgery in a few thousand requests.
• A MAC must cover every field that influences a decision — role, expiry, algorithm, IV — or those fields are attacker-controlled.
• Use unambiguous encoding (length prefixes) when concatenating fields into MAC input, to prevent field-boundary confusion.
• MACs give no non-repudiation because the key is shared; use a signature when a third party must be convinced.

🧪 Practice

1. Run the timing comparison above with enough trials to see a clear separation, then explain how an attacker turns that signal into a forged tag and how many requests it takes.
2. Exploit bad_token to escalate from viewer to admin, then confirm the same change fails against good_token.
3. Construct two different (user, role) pairs that produce identical MAC input under a naive f"{user}|{role}" encoding, and show why length prefixes prevent it.
4. Interview-style: "An API signs requests with HMAC-SHA256 but omits the HTTP method and path from the signed string. What can an attacker do?" Hint: think about replaying a valid signature against a different endpoint or verb, and what the signed string must canonically include to bind the tag to one specific request.

Authenticated Encryption (AEAD)

Theory

Encryption alone protects confidentiality and nothing else. Every unauthenticated mode is malleable: an attacker who cannot read the plaintext can still modify it in predictable ways. In CTR or OFB mode, flipping a ciphertext bit flips exactly the corresponding plaintext bit. In CBC, modifying one ciphertext block makes targeted changes to the next plaintext block. These are not theoretical — they have been used to change amounts in encrypted transactions and to flip authorization flags in encrypted cookies.

Authenticated encryption with associated data (AEAD) solves this by providing confidentiality, integrity, and authenticity in a single primitive with a single key. The interface is deliberately hard to misuse:

• encrypt(key, nonce, plaintext, aad) -> ciphertext || tag
• decrypt(key, nonce, ciphertext || tag, aad) -> plaintext or an error

The associated data (AAD) is authenticated but not encrypted. This is for metadata that must travel in the clear but must not be tampered with: packet headers needed for routing, a record's database ID, a message version number, a key identifier. Binding this context into the tag prevents an attacker from taking a valid ciphertext and replaying it in a different context — a different user's record, a different protocol version, a different endpoint.

The most important property is the all-or-nothing decryption contract: the tag is verified before any plaintext is released. A failed verification returns an error and no plaintext whatsoever. This is what eliminates the padding-oracle attack class — there is no intermediate state for an attacker to probe. Correspondingly, the cardinal implementation rule is never use plaintext from a failed decryption, not even for logging or error messages.

For the historical alternative of composing a cipher and a MAC manually, the orderings are not equivalent:

Order	Security	Used by
Encrypt-then-MAC	Secure; MAC verified before decryption	IPsec, modern designs
MAC-then-encrypt	Weak; must decrypt before verifying (Lucky13)	TLS 1.0-1.2 CBC
Encrypt-and-MAC	Weak; MAC over plaintext can leak	SSH (legacy)

Even encrypt-then-MAC, done correctly, requires separate keys for encryption and authentication, a MAC that covers the IV and all metadata, and constant-time verification. AEAD packages all of this correctly, so hand-composition should be treated as a finding.

The standard choices:

• AES-GCM — the default where AES hardware exists. Fast, parallelizable, widely supported. Sharp edge: nonce reuse leaks the GHASH authentication key and permits arbitrary forgery.
• ChaCha20-Poly1305 — the default without AES hardware. Constant-time by construction.
• AES-GCM-SIV / AES-SIV — nonce-misuse resistant. Reusing a nonce only reveals that two plaintexts were equal; it does not break authenticity. Use these when nonce uniqueness cannot be guaranteed.
• AES-CCM — used in 802.11 and constrained devices; slower, sequential.
• XChaCha20-Poly1305 — 192-bit nonce, making random nonces safe; the practical default for file and message encryption in libsodium-style libraries.

Examples

WHY ENCRYPTION ALONE IS NOT ENOUGH

  CTR / stream mode -- bit flips pass straight through
    plaintext   "transfer 0100 USD"
    attacker XORs the ciphertext byte at offset 10 with (0x31 ^ 0x39)
    plaintext   "transfer 0900 USD"      <- no error, no detection

  CBC -- modifying C[i] makes targeted changes to P[i+1]
    C[i] garbles P[i] completely but lets the attacker XOR
    arbitrary bits into P[i+1].

AEAD INTERFACE

           key   nonce   plaintext   AAD (authenticated, not encrypted)
            │      │         │        │
            ▼      ▼         ▼        ▼
         ┌──────────────────────────────────┐
         │          AEAD encrypt            │
         └──────────────────┬───────────────┘
                            ▼
              ciphertext ‖ tag (16 bytes)

  DECRYPT:  verify tag FIRST  ──► fail ──► ERROR, zero plaintext released
                              ──► pass ──► plaintext

  No intermediate state to probe => no padding oracle.

COMPOSITION ORDERS (if you must hand-roll)
  encrypt-then-MAC   MAC(IV || ciphertext), verify BEFORE decrypting  SAFE
  MAC-then-encrypt   must decrypt+unpad to verify                     Lucky13
  encrypt-and-MAC    MAC over plaintext can leak information          WEAK

import os

from cryptography.exceptions import InvalidTag
from cryptography.hazmat.primitives.ciphers.aead import (
    AESGCM, AESGCMSIV, ChaCha20Poly1305)

key = AESGCM.generate_key(bit_length=256)
aead = AESGCM(key)

# --- AAD binds context the attacker must not be able to change -------
record_id = b"user=1042;table=accounts;v=2"     # travels in clear
nonce = os.urandom(12)
ct = aead.encrypt(nonce, b"balance=100", record_id)

# Correct decryption requires the SAME AAD.
print(aead.decrypt(nonce, ct, record_id))       # b'balance=100'

# Replaying this ciphertext against a DIFFERENT record fails, because the
# AAD is part of the authenticated input. Without AAD, the attacker could
# move user 1042's encrypted balance onto their own record.
try:
    aead.decrypt(nonce, ct, b"user=9999;table=accounts;v=2")
except InvalidTag:
    print("cross-record replay rejected")


# --- Tamper detection: any single bit flip is caught -----------------
for position in (0, len(ct) // 2, len(ct) - 1):
    bad = bytearray(ct)
    bad[position] ^= 0x01
    try:
        aead.decrypt(nonce, bytes(bad), record_id)
        print(f"byte {position}: ACCEPTED -- would be a vulnerability")
    except InvalidTag:
        print(f"byte {position}: rejected")


# --- THE CARDINAL RULE: never use plaintext from a failed decrypt ----
def safe_open(blob: bytes, aad: bytes) -> bytes:
    """On failure: no plaintext, no partial data, no detail in the error.
    Leaking WHY it failed can reconstruct an oracle."""
    n, body = blob[:12], blob[12:]
    try:
        return aead.decrypt(n, body, aad)
    except InvalidTag:
        raise ValueError("decryption failed") from None   # generic, uniform


# --- Choosing the right AEAD -----------------------------------------
# 1. AES hardware available, nonce uniqueness guaranteed:
gcm = AESGCM(key)

# 2. No AES hardware (mobile, embedded), or constant-time required:
chacha = ChaCha20Poly1305(ChaCha20Poly1305.generate_key())

# 3. Nonce uniqueness CANNOT be guaranteed (stateless, forks, snapshots):
siv = AESGCMSIV(AESGCMSIV.generate_key(bit_length=256))
n = os.urandom(12)
a = siv.encrypt(n, b"balance=100", None)
b = siv.encrypt(n, b"balance=900", None)
# Nonce reuse here leaks only that the plaintexts differ. Under plain GCM
# the same mistake would leak the GHASH key and allow arbitrary forgery.
print("SIV survives nonce reuse:", siv.decrypt(n, a, None))


# --- A complete, self-describing sealed format ----------------------
def seal(plaintext: bytes, aad: bytes) -> bytes:
    """nonce || ciphertext || tag. The nonce is public; prepending it
    keeps the blob self-contained and avoids out-of-band state."""
    n = os.urandom(12)
    return n + aead.encrypt(n, plaintext, aad)


blob = seal(b"secret payload", record_id)
print(safe_open(blob, record_id))

AEAD	Nonce	Misuse resistant	Hardware accelerated	Best for
AES-128/256-GCM	96 bits	No	Yes (AES-NI, PCLMUL)	Default with AES hardware
ChaCha20-Poly1305	96 bits	No	No (fast anyway)	Mobile, embedded, constant-time
XChaCha20-Poly1305	192 bits	Effectively (random-safe)	No	Files, messages, libsodium
AES-GCM-SIV	96 bits	Yes	Yes	Unreliable nonce state
AES-SIV	Optional	Yes (deterministic)	Partial	Key wrapping, deduplication
AES-CCM	96 bits	No	Partial	802.11, constrained devices

Key Takeaways

• Unauthenticated encryption is malleable: CTR allows exact bit flips and CBC allows targeted changes to the following block.
• AEAD provides confidentiality, integrity, and authenticity in one primitive with one key, and is the correct default.
• The AAD authenticates cleartext metadata, which prevents replaying a valid ciphertext in a different context such as another user's record.
• Decryption is all-or-nothing: the tag is verified before any plaintext is released, which eliminates padding oracles.
• Never use, log, or hint at plaintext from a failed decryption, and keep failure messages uniform.
• Hand-composing cipher and MAC is error-prone; only encrypt-then-MAC is sound, and it still needs separate keys and full metadata coverage.
• Choose AES-GCM with AES hardware, ChaCha20-Poly1305 without it, and a SIV mode whenever nonce uniqueness cannot be guaranteed.

🧪 Practice

1. Encrypt a record with AES-GCM using its row ID as AAD, then attempt to decrypt it with a different row ID. Explain what attack this prevents in a database-column-encryption design.
2. Take an AES-CTR implementation that encrypts amount=0100, flip the right ciphertext bits to make it decrypt as amount=0900, then repeat against AES-GCM and show the failure.
3. Compare AES-GCM and AES-GCM-SIV under deliberate nonce reuse: encrypt two different plaintexts with the same nonce under each, and describe exactly what leaks in both cases.
4. Interview-style: "A design encrypts with AES-CBC and stores a SHA-256 hash of the plaintext alongside for integrity. What is wrong?" Hint: ask what prevents the attacker from replacing both the ciphertext and the hash, then consider whether the hash itself leaks information about the plaintext and what ordering would have been sound.

Password Hashing: bcrypt, scrypt, Argon2

Theory

Password storage is the one place in cryptography where slowness is the goal. This inverts every other instinct in this chapter, and failing to understand why is the single most common cause of mass credential compromise after a database breach.

The reasoning starts from an assumption: the password database will eventually leak. Given that, the only question is how long the stolen hashes resist offline cracking. An attacker with the file is unconstrained by rate limits, lockouts, or network latency; they run billions of guesses per second on GPUs against your hashes. The defence is to make each individual guess expensive.

General-purpose hashes are catastrophically wrong here. A modern GPU computes roughly 10 billion SHA-256 hashes per second. Against an unsalted SHA-256 database, every password in a typical leak that appears in a wordlist falls in minutes. The hash is not weak; it is fast, and fast is the vulnerability.

A password hashing function therefore adds deliberate cost. Three generations exist:

PBKDF2 (2000) iterates HMAC a configurable number of times. It is the weakest acceptable option because it is CPU-bound only and uses very little memory, so GPUs and ASICs parallelize it almost perfectly — a GPU gets a 100-to-1,000-fold advantage over the defender's server. It remains in use for FIPS compliance. OWASP currently recommends 600,000 iterations with HMAC-SHA256.

bcrypt (1999) is based on a modified Blowfish key schedule and is deliberately memory-access-heavy, requiring about 4 KB of rapidly-accessed state. That small working set still frustrates GPUs, which have limited fast memory per core. Its cost factor is logarithmic: factor 12 means 2^12 iterations. Its notable limitation is a 72-byte input truncation — longer passwords are silently cut, and some implementations have had null-byte handling bugs. Pre-hashing with SHA-256 before bcrypt is the standard workaround, but note that base64-encoding the pre-hash is necessary to avoid null bytes.

scrypt (2009) was the first explicitly memory-hard function: it requires a large, tunable amount of memory, so an attacker must spend silicon area on RAM rather than compute units. This dramatically reduces the ASIC and GPU advantage, because memory is expensive and does not parallelize cheaply.

Argon2 (2015) won the Password Hashing Competition and is the current recommendation. It is memory-hard with three independent parameters — memory, time (iterations), and parallelism — and comes in three variants: Argon2d (data-dependent access, maximum GPU resistance, but side-channel-vulnerable), Argon2i (data-independent, side-channel resistant), and Argon2id (a hybrid, and the one you should use).

Current OWASP guidance: Argon2id with at least 19 MiB of memory, 2 iterations, and parallelism 1; or bcrypt with cost factor 10 or more; or scrypt with N=2^17, r=8, p=1; falling back to PBKDF2-HMAC-SHA256 at 600,000 iterations only where compliance demands it.

The right way to tune: pick a target verification time (typically 250 to 500 milliseconds on your production hardware), then raise parameters until you hit it, bearing in mind that login throughput and denial-of-service resistance set the ceiling.

Examples

THE ECONOMICS OF OFFLINE CRACKING

  algorithm              │ guesses/sec (one high-end GPU)
  SHA-256                │ ~10,000,000,000      <- NEVER for passwords
  PBKDF2 600k iters      │ ~10,000
  bcrypt cost 12         │ ~1,000
  scrypt N=2^17          │ ~100
  Argon2id 19MiB,t=2     │ ~100

  Cracking a 10-million-entry leak of common passwords:
    SHA-256        : minutes
    bcrypt cost 12 : years of GPU time
  Same passwords. The only difference is the cost per guess.

WHY MEMORY-HARDNESS BEATS ITERATION COUNT

  CPU-bound (PBKDF2)          MEMORY-HARD (Argon2, scrypt)
  ┌──┬──┬──┬──┬──┬──┬──┐      ┌──────────────────────────┐
  │C │C │C │C │C │C │C │      │  19 MiB RAM per guess    │
  └──┴──┴──┴──┴──┴──┴──┘      └──────────────────────────┘
  GPU: 10,000 cores, all       GPU: 10,000 cores but only
  running PBKDF2 in parallel   ~8 GB RAM => ~400 parallel
  => huge attacker advantage   guesses => advantage collapses

STORED HASH FORMAT (self-describing: parameters travel with the hash)

  $argon2id$v=19$m=19456,t=2,p=1$<base64 salt>$<base64 hash>
   └──┬───┘ └─┬─┘ └──────┬──────┘ └────┬─────┘ └─────┬────┘
   algorithm version  parameters      salt        digest

  This is what allows transparent upgrades: read the parameters from
  the stored hash, verify, and re-hash with stronger ones on success.

# pip install argon2-cffi bcrypt
import hashlib
import secrets
import time

import bcrypt
from argon2 import PasswordHasher
from argon2.exceptions import VerifyMismatchError, VerificationError

# --- NEVER DO THIS ---------------------------------------------------
def catastrophic(password: str) -> str:
    """~10 billion guesses/sec on a GPU, and identical passwords produce
    identical hashes so one cracked hash reveals every reuse."""
    return hashlib.sha256(password.encode()).hexdigest()


# --- RECOMMENDED: Argon2id ------------------------------------------
ph = PasswordHasher(
    memory_cost=19456,   # 19 MiB -- the memory-hardness parameter
    time_cost=2,         # iterations over that memory
    parallelism=1,       # lanes
)

stored = ph.hash("correct horse battery staple")
print(stored)            # $argon2id$v=19$m=19456,t=2,p=1$...$...
# The salt is generated automatically and embedded in the output.


def check(stored_hash: str, candidate: str) -> tuple[bool, str | None]:
    """Verify, and transparently upgrade the hash when parameters change.
    This is how you migrate a user base without forcing a password reset."""
    try:
        ph.verify(stored_hash, candidate)
    except (VerifyMismatchError, VerificationError):
        return False, None
    if ph.check_needs_rehash(stored_hash):
        return True, ph.hash(candidate)      # caller persists the new hash
    return True, None


print(check(stored, "correct horse battery staple")[0])   # True
print(check(stored, "wrong password")[0])                  # False


# --- bcrypt: still fine, with one sharp edge ------------------------
pw = b"a" * 100                              # longer than 72 bytes
h = bcrypt.hashpw(pw, bcrypt.gensalt(rounds=12))
# bcrypt TRUNCATES at 72 bytes, so these two different passwords match:
print(bcrypt.checkpw(b"a" * 100, h))         # True
print(bcrypt.checkpw(b"a" * 72, h))          # True -- the truncation

# Standard workaround: pre-hash, then base64 so no null bytes appear.
import base64


def bcrypt_prehash(password: str) -> bytes:
    digest = hashlib.sha256(password.encode()).digest()
    return base64.b64encode(digest)          # 44 bytes, null-free


h2 = bcrypt.hashpw(bcrypt_prehash("a" * 100), bcrypt.gensalt(rounds=12))
print(bcrypt.checkpw(bcrypt_prehash("a" * 100), h2))   # True
print(bcrypt.checkpw(bcrypt_prehash("a" * 72), h2))    # False -- fixed


# --- Tune to a target verification time on YOUR hardware ------------
def measure(hasher: PasswordHasher, trials: int = 5) -> float:
    t0 = time.perf_counter()
    for _ in range(trials):
        hasher.hash("benchmark-password")
    return (time.perf_counter() - t0) / trials * 1000


for mib in (19, 47, 64, 128):
    h_test = PasswordHasher(memory_cost=mib * 1024, time_cost=2, parallelism=1)
    print(f"{mib:>4} MiB -> {measure(h_test):>7.1f} ms")
# Target 250-500 ms, bounded by your peak login rate and DoS tolerance.

Function	Hard in	Parameters	2026 guidance
SHA-256 / MD5	Nothing	—	Never for passwords
PBKDF2-HMAC-SHA256	CPU	600,000 iterations	Only for FIPS compliance
bcrypt	Small memory	cost >= 10	Acceptable; 72-byte limit
scrypt	Memory	N=2^17, r=8, p=1	Good
Argon2id	Memory + CPU	m=19 MiB, t=2, p=1	Recommended

Key Takeaways

• Password hashing must be deliberately slow, because the threat model assumes the database leaks and the attacker cracks offline without rate limits.
• General-purpose hashes are the vulnerability: a GPU does about 10 billion SHA-256 operations per second.
• Memory-hardness beats iteration count, because it denies attackers the cheap parallelism that GPUs and ASICs provide.
• Argon2id is the current recommendation (19 MiB, 2 iterations, parallelism 1); bcrypt at cost 10 or more and scrypt remain acceptable; PBKDF2 only for compliance.
• bcrypt silently truncates input at 72 bytes, so pre-hash and base64-encode long passwords.
• Store parameters with the hash in the standard self-describing format, and use that to re-hash transparently on successful login when parameters strengthen.
• Tune to 250 to 500 milliseconds on production hardware, bounded by login throughput and denial-of-service considerations.

🧪 Practice

1. Benchmark SHA-256, PBKDF2 at 600,000 iterations, bcrypt cost 12, and Argon2id at 19 MiB on your machine. Compute how long each would take to test a 14-million-entry wordlist.
2. Implement the transparent-rehash-on-login pattern: store a hash with weak parameters, then verify with stronger ones configured and confirm the hash is upgraded.
3. Demonstrate the bcrypt 72-byte truncation, then show that the base64 pre-hash workaround fixes it. Explain why plain hex or raw bytes would be a worse choice.
4. Interview-style: "Our login endpoint is slow because Argon2 takes 400 ms. Should we reduce the parameters?" Hint: separate the user-perceived cost of a single login from the attacker's aggregate cost across billions of guesses, and consider whether the real fix is asynchronous handling, rate limiting, or horizontal capacity rather than weakening the hash.

Salting, Peppering, and Key Stretching

Theory

A slow hash raises the cost per guess. Salting attacks a different axis: it destroys the attacker's ability to amortize work across multiple targets.

Without a salt, hashing is deterministic, so identical passwords produce identical hashes. Three consequences follow immediately, all bad. The attacker can see which users share a password, simply by looking for repeated hashes. They can precompute a table of hash(password) once and then look up every user in the database instantly. And cracking one hash cracks that password for every user who chose it.

A salt is a unique random value per password, concatenated with the password before hashing and stored in plaintext alongside the hash. The salt need not be secret — its job is purely to make every hash unique. Now identical passwords produce different hashes, precomputed tables are worthless (the attacker would need a separate table per salt), and the attacker must attack each user's hash independently. Requirements: at least 16 bytes, from a CSPRNG, unique per password — not per user, per application, or per deployment. Modern password-hashing libraries generate and embed the salt automatically, so hand-rolling salt logic is itself a warning sign.

A pepper is a different mechanism that is often confused with a salt. It is a single secret value, shared across all passwords, stored outside the database — in an HSM, a secrets manager, or application configuration. The point is defence in depth against the specific scenario of a database-only breach: an attacker with SQL injection access who dumps the users table has the salts (they are in the table) but not the pepper, so they cannot crack anything. The right implementation is to apply the pepper as an HMAC key before the password hash, or to encrypt the final hash with a key from the HSM, rather than concatenating a secret string. The trade-off is operational: rotating a pepper requires re-processing every stored hash, and losing it invalidates every password in the system.

Key stretching is the general term for the iteration and memory cost that the previous topic covered — deriving an expensive-to-compute value from a low-entropy input. The same machinery serves a second purpose: key derivation, turning a password into an encryption key, which is what full-disk encryption, password managers, and encrypted archives do. Here the function must be slow for the same reason, but note a distinction in tools: use HKDF when the input is already high-entropy (a Diffie-Hellman output, a random master key), and use Argon2id, scrypt, or PBKDF2 when the input is a human password. HKDF is fast by design and would be a serious mistake for a password.

Putting the layers together, a complete defence has four independent parts: a unique salt (removes amortization), a slow memory-hard function (raises per-guess cost), an optional pepper (survives database-only breaches), and rate limiting with monitoring on the login endpoint (constrains online guessing, which salting and stretching do nothing about).

Examples

WITHOUT SALT: one table breaks everyone

  alice  "password123"  ──► ef92b778ba...
  bob    "password123"  ──► ef92b778ba...   <- identical: reuse is visible
  carol  "password123"  ──► ef92b778ba...

  Attacker precomputes ONE table:
    ef92b778ba... -> "password123"
  Then every matching user is cracked instantly, for all databases ever.

WITH SALT: each hash must be attacked alone

  alice  salt=7f3a..  ──► $argon2id$...$7f3a..$9c1e..
  bob    salt=b821..  ──► $argon2id$...$b821..$44ad..
  carol  salt=0d5c..  ──► $argon2id$...$0d5c..$e07b..

  Same password, three different hashes. Precomputation is worthless;
  reuse is invisible; cracking alice reveals nothing about bob.

PEPPER: survives a DATABASE-ONLY breach

  ┌──────────── DATABASE (stolen via SQLi) ────────────┐
  │  username │ salt (plaintext) │ hash               │
  └────────────────────────────────────────────────────┘
                        │
                   NOT ENOUGH
                        │
  ┌──────── HSM / secrets manager (NOT stolen) ────────┐
  │  PEPPER = 32 random bytes, shared by all rows      │
  └────────────────────────────────────────────────────┘

  hash = argon2id( salt, hmac_sha256(PEPPER, password) )
  Without the pepper, the stolen rows cannot be cracked at all.
  Cost: rotating the pepper requires re-processing every hash.

THE FOUR INDEPENDENT LAYERS
  1. unique salt      -> no precomputation, no amortisation
  2. slow memory-hard -> high cost per guess
  3. pepper           -> DB-only breach yields nothing
  4. rate limiting    -> constrains ONLINE guessing (the other three do not)

import hashlib
import hmac
import os
import secrets

from argon2 import PasswordHasher
from argon2.exceptions import VerifyMismatchError
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives.kdf.scrypt import Scrypt

# --- WRONG: unsalted. Identical passwords collide. -------------------
def unsalted(password: str) -> str:
    return hashlib.sha256(password.encode()).hexdigest()


print(unsalted("password123") == unsalted("password123"))   # True -- the leak


# --- Salting done by hand, to show the mechanism ---------------------
def manual_salt(password: str) -> tuple[bytes, bytes]:
    salt = secrets.token_bytes(16)      # >= 16 bytes, CSPRNG, per password
    digest = hashlib.pbkdf2_hmac("sha256", password.encode(), salt, 600_000)
    return salt, digest                 # the salt is stored in PLAINTEXT


s1, d1 = manual_salt("password123")
s2, d2 = manual_salt("password123")
print(d1 == d2)                         # False -- same password, different hash


# --- In practice the library handles salting for you ----------------
ph = PasswordHasher(memory_cost=19456, time_cost=2, parallelism=1)
print(ph.hash("password123") != ph.hash("password123"))   # True

# --- PEPPER: applied as an HMAC key, not concatenated ---------------
PEPPER = os.environ.get("PASSWORD_PEPPER", "").encode() or os.urandom(32)
# In production this comes from an HSM or secrets manager, NEVER the DB.


def store(password: str) -> str:
    """HMAC with the pepper first, then the memory-hard hash. An attacker
    with only the database cannot compute the HMAC input."""
    peppered = hmac.new(PEPPER, password.encode(), hashlib.sha256).digest()
    return ph.hash(peppered)


def authenticate(stored_hash: str, password: str) -> bool:
    peppered = hmac.new(PEPPER, password.encode(), hashlib.sha256).digest()
    try:
        ph.verify(stored_hash, peppered)
        return True
    except VerifyMismatchError:
        return False


record = store("correct horse battery staple")
print(authenticate(record, "correct horse battery staple"))   # True
print(authenticate(record, "wrong"))                           # False


# --- KEY DERIVATION: choose the KDF by the ENTROPY of the input -----
# From a PASSWORD (low entropy): must be slow and memory-hard.
def key_from_password(password: str, salt: bytes) -> bytes:
    return Scrypt(salt=salt, length=32, n=2 ** 17, r=8, p=1).derive(
        password.encode())


# From a HIGH-ENTROPY secret (a DH output, a random master key):
# HKDF is correct here and is FAST by design -- using it on a password
# would be a serious vulnerability.
def key_from_shared_secret(secret: bytes, context: bytes) -> bytes:
    return HKDF(algorithm=hashes.SHA256(), length=32,
                salt=os.urandom(16), info=context).derive(secret)


disk_key = key_from_password("user passphrase", os.urandom(16))
session_key = key_from_shared_secret(os.urandom(32), b"app/v1 session")

Mechanism	Secret?	Scope	Stored where	Defends against
Salt	No	Per password	Beside the hash	Precomputation, rainbow tables, reuse visibility
Pepper	Yes	All passwords	HSM / secrets manager	Database-only breach
Key stretching	No	Per hash	In the parameters	Fast offline guessing
Rate limiting	No	Per account / IP	Application layer	Online guessing, credential stuffing

Key Takeaways

• A salt is a unique, non-secret, per-password random value that makes every hash distinct, defeating precomputation and hiding password reuse.
• Salts must be at least 16 bytes from a CSPRNG and unique per password, not per application or deployment.
• A pepper is a single secret stored outside the database, and it specifically defends the database-only-breach scenario.
• Apply the pepper as an HMAC key before the password hash rather than concatenating it, and accept that rotation requires re-processing every hash.
• Key stretching serves both password storage and password-based key derivation; both need slowness.
• Choose the KDF by input entropy: HKDF for high-entropy secrets, Argon2id or scrypt for human passwords. Using HKDF on a password is a serious error.
• The four layers — salt, slow hash, pepper, rate limiting — are independent, and only rate limiting addresses online guessing.

🧪 Practice

1. Hash the same password 1,000 times with Argon2id and confirm every output differs. Then extract the salts from the encoded strings and verify they are unique.
2. Implement pepper rotation: write a migration that re-processes stored hashes from an old pepper to a new one. Explain at which point in the login flow the migration can actually happen and why.
3. Build a small unsalted SHA-256 "database" of 10 users where three share a password, then show how an attacker identifies the shared password and cracks all three with one table lookup.
4. Interview-style: "If the salt is stored in plaintext right next to the hash, what is the point of it?" Hint: the salt was never meant to be secret — reframe the question around what the attacker can no longer reuse across targets, and compare the work to crack 10 million hashes with and without unique salts.

Rainbow Tables and Their Mitigation

Theory

A rainbow table is a precomputation attack: do the expensive work once, store a compressed result, and then crack any hash in that space almost instantly. Understanding the technique explains precisely why salting works, and why the attack is largely historical today — displaced by something arguably worse.

The naive version is a simple lookup table: compute hash(p) for every candidate password and store the pairs. This gives instant lookups but enormous storage; all 8-character alphanumeric passwords at 32 bytes per hash would be well into the petabytes.

A rainbow table is the clever time-memory trade-off (Oechslin, 2003). Instead of storing every pair, store only the endpoints of long chains. A chain alternates hashing with a reduction function that maps a hash back to a candidate password: p1 -> h1 -> p2 -> h2 -> ... -> pn. Only p1 and pn are stored. To crack a hash, apply reduction and hashing repeatedly until you hit a stored endpoint, then regenerate that chain from its start to find the preimage. (The "rainbow" part is that a different reduction function is used at each step, which greatly reduces the chain merges that plagued earlier designs.) The result is a table thousands of times smaller than the full lookup table, at the cost of some computation per lookup.

The historically devastating application was Windows LM hashes: no salt, passwords uppercased, split into two 7-character halves hashed independently. Rainbow tables covering the entire LM space fit on a DVD and cracked any Windows password in seconds. Unsalted MD5 and SHA-1 tables for common password spaces remain freely downloadable.

Salting defeats rainbow tables completely, and the reason is simple arithmetic. A table is built for one specific hash function. Adding a 16-byte salt means the attacker needs a separate table for each of 2^128 possible salts. The precomputation can no longer be amortized across even two users, which is the entire basis of the attack.

The crucial modern point: rainbow tables are largely obsolete, but not because defenders improved. They were displaced by GPU brute force. A modern GPU computes tens of billions of fast hashes per second, which makes generating candidates on the fly cheaper than storing and looking up precomputed chains. Against a fast unsalted hash, a GPU cracks faster than a rainbow table loads from disk. So "we use salts, so we are safe from rainbow tables" is true and almost irrelevant — the live threat is high-speed offline guessing, which is defeated by a slow hash, not by salting.

The complete mitigation stack, in order of importance against the modern threat:

1. A slow, memory-hard hash (Argon2id, bcrypt, scrypt) — defeats GPU brute force, which is the actual threat.
2. A unique per-password salt — defeats precomputation and amortization. Automatic in modern libraries.
3. A pepper — defeats database-only breaches.
4. Password policy and breach-list screening — raises candidate entropy. Check new passwords against the Have I Been Pwned corpus (via the k-anonymity range API, so the password never leaves your system) rather than enforcing arbitrary composition rules, which demonstrably push users toward predictable patterns.
5. Multi-factor authentication — makes a cracked password insufficient on its own, and is the single highest-value control in this list.

Examples

LOOKUP TABLE vs RAINBOW TABLE

  LOOKUP TABLE: store every pair
    "password" -> 5f4dcc3b5a...
    "123456"   -> e10adc3949...
    ... petabytes for 8-char alphanumeric

  RAINBOW CHAIN: store only the endpoints
    p1 ─hash─► h1 ─R1─► p2 ─hash─► h2 ─R2─► p3 ... ─► p1000
    ▲                                                   ▲
    └── STORED                                   STORED ┘
    998 intermediate values are recomputed on demand.

    Cracking h:  R(h) ─hash─► ... until an endpoint matches,
                 then regenerate that chain from its start.

    Thousands of times smaller, at the cost of per-lookup compute.

WHY SALT KILLS IT

  no salt:  ONE table covers every user in every database, forever
  16-byte salt: the attacker needs 2**128 tables -- one per salt value
                precomputation cannot be amortised across even two users

WHAT ACTUALLY REPLACED RAINBOW TABLES

  2003: rainbow tables -- storage was cheaper than compute
  2026: GPU brute force -- compute is cheaper than storage
        ~10**10 SHA-256/sec means generating candidates on the fly
        beats loading precomputed chains from disk

  => The modern defence is a SLOW hash, not merely a salt.

MITIGATION STACK (ordered by effect against the CURRENT threat)
  1. Argon2id / bcrypt / scrypt     <- defeats GPU brute force
  2. unique per-password salt       <- defeats precomputation
  3. pepper outside the DB          <- defeats DB-only breach
  4. breach-list screening          <- raises candidate entropy
  5. MFA                            <- a cracked password is not enough

import hashlib
import secrets

# --- A toy rainbow table, to see the mechanism ----------------------
CHARSET = "abcdefghijklmnopqrstuvwxyz"
CHAIN_LENGTH = 100


def reduce_hash(digest: bytes, step: int, length: int = 4) -> str:
    """Map a hash back to a candidate password. A DIFFERENT reduction per
    step is what makes the table 'rainbow' and limits chain merges."""
    n = int.from_bytes(digest, "big") + step
    return "".join(CHARSET[(n >> (5 * i)) % len(CHARSET)] for i in range(length))


def build_table(num_chains: int = 2000) -> dict[str, str]:
    """Store ONLY (endpoint -> start). Intermediates are recomputed."""
    table = {}
    for _ in range(num_chains):
        start = "".join(secrets.choice(CHARSET) for _ in range(4))
        current = start
        for step in range(CHAIN_LENGTH):
            h = hashlib.md5(current.encode()).digest()
            current = reduce_hash(h, step)
        table[current] = start
    return table


def crack(target: bytes, table: dict[str, str]) -> str | None:
    """Walk forward from the target until an endpoint matches, then
    regenerate that chain from its start to find the preimage."""
    for start_step in range(CHAIN_LENGTH - 1, -1, -1):
        current = reduce_hash(target, start_step)
        for step in range(start_step + 1, CHAIN_LENGTH):
            current = reduce_hash(hashlib.md5(current.encode()).digest(), step)
        if current in table:
            candidate = table[current]          # regenerate the chain
            for step in range(CHAIN_LENGTH):
                if hashlib.md5(candidate.encode()).digest() == target:
                    return candidate
                candidate = reduce_hash(
                    hashlib.md5(candidate.encode()).digest(), step)
    return None


table = build_table()
print(f"table holds {len(table)} chains, covering up to "
      f"{len(table) * CHAIN_LENGTH:,} candidates")
print("cracked:", crack(hashlib.md5(b"hash").digest(), table))


# --- Salting makes the whole table useless -------------------------
salt = secrets.token_bytes(16)
salted = hashlib.md5(salt + b"hash").digest()
print("salted hash cracked by the same table:",
      crack(salted, table))            # None -- the table does not apply


# --- Breach-list screening with k-anonymity ------------------------
def pwned_prefix(password: str) -> tuple[str, str]:
    """Send only the first 5 SHA-1 characters to the HIBP range API; the
    password and its full hash never leave your system. The response
    contains ~500 suffixes, and you match locally."""
    digest = hashlib.sha1(password.encode()).hexdigest().upper()
    return digest[:5], digest[5:]
    # GET https://api.pwnedpasswords.com/range/{prefix}
    # then search the response for {suffix}


print(pwned_prefix("password123"))     # ('CBFDA', 'C1F347...')

Era	Dominant attack	Economics	Defence
1990s	Dictionary lookup	Storage cheap	Salting
2003-2010	Rainbow tables	Storage cheaper than compute	Salting
2010-now	GPU / ASIC brute force	Compute cheaper than storage	Slow memory-hard hash
Always	Credential stuffing	Reuse across sites	MFA, breach screening

Key Takeaways

• A rainbow table is a time-memory trade-off storing only chain endpoints, making precomputation feasible where a full lookup table would not be.
• A per-password salt defeats rainbow tables entirely, because a table is specific to one hash function and the attacker would need one per salt value.
• Rainbow tables are largely obsolete because GPU brute force is cheaper than storing and loading chains, not because defences improved.
• The modern threat is high-speed offline guessing, and the control that addresses it is a slow memory-hard hash, not salting.
• Windows LM hashes were the canonical victim: unsalted, uppercased, and split into independently hashed halves.
• Screen passwords against breach corpora using the k-anonymity range API rather than enforcing composition rules that push users toward predictable patterns.
• MFA is the highest-value control, because it makes a successfully cracked password insufficient on its own.

🧪 Practice

1. Run the toy rainbow table, measure its hit rate against 100 random 4-character passwords, then increase the chain count and length and describe the trade-off you observe.
2. Confirm that salting defeats the table, then explain in one paragraph why a salted fast hash is still inadequate against a modern attacker.
3. Implement the HIBP k-anonymity check end to end and test it with a known-breached password. Explain precisely what the API learns about the password you checked.
4. Interview-style: "Our passwords are salted SHA-256. Are we protected against rainbow tables?" Hint: answer the literal question honestly, then redirect to the threat that actually applies — estimate how long a GPU needs against salted SHA-256 versus Argon2id for the same wordlist.

<a id="35-public-key-infrastructure"></a>

3.5 Public Key Infrastructure

A public key is only a number; by itself it says nothing about who holds the matching private key. Public key infrastructure is the set of formats, authorities, and processes that bind keys to identities so that strangers can authenticate each other, and this section covers certificates, trust chains, revocation, and the operational reality of managing keys over their lifetime.

Digital Certificates and X.509 Format

Theory

Diffie-Hellman and RSA let you establish a secure channel with someone, but not with a specific someone. An active attacker can substitute their own public key and you would never know. The missing piece is a trusted statement of the form "this public key belongs to example.com", signed by a party you already trust. That statement is a certificate.

The analogy is a passport. A passport is a document binding your photograph and name together, signed (physically sealed) by a government. A border official who does not know you can verify the seal, trust the government, and thereby trust the binding. They do not need to have met you. Equally, a passport is useless if you do not trust the issuing government, and it expires so that the binding must be periodically re-confirmed.

X.509 is the standard certificate format, defined by ITU-T and profiled for the internet by RFC 5280. A certificate is a structured document containing:

• Subject — the identity being asserted (for TLS, the domain names).
• Subject Public Key Info — the public key and its algorithm.
• Issuer — the distinguished name of the authority making the assertion.
• Validity — notBefore and notAfter timestamps.
• Serial Number — unique per issuer; used in revocation lists.
• Extensions — the operationally important part (see below).
• Signature — the issuer's signature over all of the above.

The extensions carry most of the meaning in modern certificates:

• Subject Alternative Name (SAN) — the actual list of domain names. The legacy Common Name field is ignored by all modern browsers; a certificate without a matching SAN entry fails validation regardless of its CN.
• Basic Constraints — whether this certificate may act as a CA (CA:TRUE) and the maximum chain depth. A missing or unchecked constraint is catastrophic: before 2002, some implementations let any leaf certificate sign others, allowing anyone with a valid certificate to impersonate any site.
• Key Usage / Extended Key Usage — what the key may be used for (digitalSignature, keyEncipherment, serverAuth, clientAuth, codeSigning).
• Authority Information Access (AIA) — where to fetch the issuer certificate and the OCSP responder URL.
• CRL Distribution Points — where to fetch the revocation list.
• Signed Certificate Timestamps (SCTs) — proofs of submission to Certificate Transparency logs.

Encoding is a frequent source of confusion. The structure is defined in ASN.1 and serialized with DER (a canonical binary form). PEM is DER wrapped in base64 with -----BEGIN CERTIFICATE----- headers, which is what you usually see in files. The file extensions are unreliable: .crt, .cer, and .pem may each hold either form, .der is binary, .p12/.pfx is a PKCS#12 bundle containing a certificate and its private key (so treat those as secrets), and .key is typically a private key.

A note on the key fact that trips people up: a certificate is public data. It contains no secrets. Publishing it is harmless and in fact mandatory — every TLS server sends its certificate to every client that connects. The private key is the secret, and it is never in the certificate.

Examples

X.509 CERTIFICATE STRUCTURE

  ┌─────────────────────────────────────────────────────────┐
  │ TBSCertificate ("to be signed" -- everything below)     │
  │   Version:              v3                              │
  │   Serial Number:        0x04f8e1...                     │
  │   Signature Algorithm:  ecdsa-with-SHA256               │
  │   Issuer:               CN=R11, O=Let's Encrypt, C=US   │
  │   Validity:             2026-08-01 .. 2026-10-30        │
  │   Subject:              CN=example.com                  │
  │   Subject Public Key:   id-ecPublicKey, P-256, 04:a3..  │
  │   Extensions:                                           │
  │     Subject Alternative Name: example.com,              │
  │                               www.example.com     <-- authoritative
  │     Basic Constraints:        CA:FALSE             <-- cannot sign
  │     Key Usage:                digitalSignature     (critical)
  │     Extended Key Usage:       serverAuth, clientAuth
  │     Authority Info Access:    OCSP, CA Issuers URLs
  │     SCT List:                 3 log proofs             │
  ├─────────────────────────────────────────────────────────┤
  │ Signature Algorithm: ecdsa-with-SHA256                  │
  │ Signature Value:     30:45:02:21:00:b7...               │
  │   (the ISSUER's signature over TBSCertificate)          │
  └─────────────────────────────────────────────────────────┘

ENCODINGS
  ASN.1  ── the abstract structure definition
    │
    DER  ── canonical binary serialisation      (.der, .cer)
    │
    PEM  ── base64(DER) + header/footer lines   (.pem, .crt, .cer)

  -----BEGIN CERTIFICATE-----
  MIIDdzCCAl+gAwIBAgIEAgAAuTANBgkqhkiG9w0BAQUFADBaMQswCQYDVQQG...
  -----END CERTIFICATE-----

  PKCS#12 (.p12/.pfx) = certificate + PRIVATE KEY in one file => SECRET

WHAT IS PUBLIC AND WHAT IS NOT
  certificate  ── public, sent to every client     no secrets inside
  private key  ── secret, never leaves the server  never in the cert

from cryptography import x509
from cryptography.hazmat.primitives import hashes, serialization
from cryptography.x509.oid import ExtensionOID, NameOID

# --- Inspect a real certificate ---------------------------------------
#   openssl s_client -connect example.com:443 -servername example.com \
#     </dev/null 2>/dev/null | openssl x509 -out example.pem
#   openssl x509 -in example.pem -text -noout

with open("example.pem", "rb") as fh:
    cert = x509.load_pem_x509_certificate(fh.read())

print("subject   :", cert.subject.rfc4514_string())
print("issuer    :", cert.issuer.rfc4514_string())
print("serial    :", hex(cert.serial_number))
print("valid     :", cert.not_valid_before_utc, "->", cert.not_valid_after_utc)
print("sig alg   :", cert.signature_algorithm_oid._name)
print("public key:", type(cert.public_key()).__name__)

# The SAN extension is what browsers check. The CN is IGNORED.
san = cert.extensions.get_extension_for_oid(
    ExtensionOID.SUBJECT_ALTERNATIVE_NAME)
print("SAN       :", san.value.get_values_for_type(x509.DNSName))

try:
    cn = cert.subject.get_attributes_for_oid(NameOID.COMMON_NAME)[0].value
    print(f"CN        : {cn}  (legacy, not used for name matching)")
except IndexError:
    print("CN        : absent -- entirely normal for modern certificates")

# Basic Constraints: whether this certificate may sign others.
bc = cert.extensions.get_extension_for_oid(ExtensionOID.BASIC_CONSTRAINTS)
print(f"is a CA   : {bc.value.ca}  (critical={bc.critical})")
# A leaf with CA:TRUE, or a client that ignores this field, lets any
# certificate holder impersonate any site.

# The fingerprint: used for pinning and for identifying a certificate.
print("sha256 fp :", cert.fingerprint(hashes.SHA256()).hex())


# --- Format conversion -------------------------------------------------
der_bytes = cert.public_bytes(serialization.Encoding.DER)
pem_bytes = cert.public_bytes(serialization.Encoding.PEM)
print(f"DER {len(der_bytes)} bytes, PEM {len(pem_bytes)} bytes (base64 overhead)")

# Equivalent OpenSSL commands:
#   openssl x509 -in cert.pem -outform DER -out cert.der
#   openssl x509 -in cert.der -inform DER -out cert.pem
#   openssl pkcs12 -in bundle.p12 -nokeys -out cert.pem      # extract cert
#   openssl pkcs12 -in bundle.p12 -nocerts -out key.pem      # extract KEY

Field / extension	Purpose	Failure if wrong
Subject Alternative Name	The authoritative domain list	Name mismatch; connection refused
Common Name	Legacy identity field	Ignored by modern clients
Basic Constraints	May this certificate sign others?	Universal impersonation if unchecked
Key Usage / EKU	Permitted key operations	Certificate misuse across purposes
Validity	Lifetime bounds	Expiry outages (very common)
Serial Number	Unique per issuer	Revocation cannot reference it
AIA / CRL DP	Where to check revocation	Revocation checking impossible
SCT List	Certificate Transparency proof	Browser rejection

Key Takeaways

• A certificate is a signed assertion binding a public key to an identity, which is what makes authentication of strangers possible.
• X.509 (RFC 5280) defines the format; the extensions carry most of the operational meaning.
• Subject Alternative Name is authoritative for domain matching, and Common Name is ignored by modern clients.
• Basic Constraints determines whether a certificate may sign others; unchecked, it permits universal impersonation.
• ASN.1 defines the structure, DER is the binary encoding, and PEM is base64-wrapped DER; file extensions are unreliable indicators.
• PKCS#12 (.p12, .pfx) bundles contain the private key and must be handled as secrets.
• A certificate contains no secrets and is meant to be published; only the private key is confidential.

🧪 Practice

1. Fetch and fully decode the certificate for a site you use, listing its SAN entries, validity window, signature algorithm, and whether it carries SCTs.
2. Convert a certificate between PEM and DER with OpenSSL in both directions and verify the SHA-256 fingerprint is unchanged. Explain why the fingerprint is computed over DER.
3. Find a certificate whose SAN list does not include the Common Name value, and explain what a browser does with each field.
4. Interview-style: "A developer emails you a .pfx file so you can 'install the certificate'. What is your reaction?" Hint: consider what a PKCS#12 bundle normally contains beyond the certificate, and whether the thing they needed to send was secret at all.

Certificate Authorities and Trust Chains

Theory

A certificate is only as meaningful as your trust in whoever signed it. Certificate authorities (CAs) are organizations whose public keys are pre-installed in operating systems and browsers as trust anchors, forming the root of all certificate validation.

Trust is delegated through a chain. A root CA certificate is self-signed and lives in the client's trust store. Roots are kept offline in hardware security modules and used rarely, because compromise of a root is unrecoverable — it would require every client in the world to update. Roots therefore sign intermediate CA certificates, which are kept online and do the day-to-day work of signing leaf (end-entity) certificates. If an intermediate is compromised, it can be revoked without touching the root.

Validation walks the chain from leaf to root and checks, at every link:

1. Signature — each certificate's signature verifies against its issuer's public key.
2. Name chaining — each certificate's Issuer field matches the Subject of the next certificate up.
3. Validity period — every certificate in the chain is currently within its window.
4. Basic Constraints — every non-leaf has CA:TRUE and the path length is within limits.
5. Key Usage / EKU — the leaf permits the intended use (serverAuth), and CAs permit certificate signing.
6. Revocation — none of the certificates has been revoked.
7. Hostname match — the leaf's SAN covers the name the client actually requested.
8. Trust anchor — the chain terminates at a root in the local trust store.

All of these must pass. The vulnerability pattern that has recurred for twenty years is omitting step 7: code that verifies the chain cryptographically but never checks the hostname will happily accept a valid certificate for attacker.com when connecting to bank.com. Entire classes of mobile app vulnerabilities come from exactly this, and it is usually caused by someone "fixing" a certificate error by disabling verification.

A server must send the leaf and all intermediates; omitting an intermediate is one of the most common TLS misconfigurations, producing errors on some clients and not others depending on whether they happen to have cached the intermediate.

The structural weakness of this system is that it is only as strong as the weakest CA. A browser trusts well over a hundred root CAs, and any of them can issue a certificate for any domain. History bears this out: DigiNotar (2011) was compromised and issued fraudulent *.google.com certificates used to intercept Iranian users' traffic; the CA was removed from all trust stores and went bankrupt. TrustWave (2012) admitted selling a subordinate CA certificate for traffic inspection. Symantec (2017) was distrusted by Google after repeated misissuance. These incidents drove the creation of Certificate Transparency and CAA records.

Two complementary controls limit the damage:

• CAA DNS records let a domain owner specify which CAs may issue for their domain, and CAs are required to honor them. This narrows the attack surface from "any of 100+ CAs" to the ones you authorize.
• Certificate Transparency makes misissuance detectable, which is the subject of a later topic.

Examples

THE TRUST CHAIN

  ┌─────────────────────────────────────────────────────────────┐
  │  ROOT CA   CN=ISRG Root X1        self-signed               │
  │  - private key OFFLINE in an HSM                            │
  │  - pre-installed in OS/browser trust stores                 │
  │  - compromise is UNRECOVERABLE                              │
  └───────────────────────────┬─────────────────────────────────┘
                              │ signs
  ┌───────────────────────────▼─────────────────────────────────┐
  │  INTERMEDIATE CA   CN=R11                                   │
  │  - private key ONLINE, does the daily signing               │
  │  - revocable without touching the root                      │
  │  - MUST be sent by the server alongside the leaf            │
  └───────────────────────────┬─────────────────────────────────┘
                              │ signs
  ┌───────────────────────────▼─────────────────────────────────┐
  │  LEAF   CN=example.com,  SAN: example.com, www.example.com  │
  │  - CA:FALSE, EKU: serverAuth                                │
  │  - private key on the web server                            │
  └─────────────────────────────────────────────────────────────┘

VALIDATION -- every step must pass

  leaf.signature       verifies with intermediate.publicKey     [ok]
  leaf.issuer       ==  intermediate.subject                    [ok]
  intermediate.sig     verifies with root.publicKey             [ok]
  intermediate.issuer ==  root.subject                          [ok]
  root                 present in local trust store             [ok]
  all validity windows currently valid                          [ok]
  intermediate BasicConstraints CA:TRUE, path length ok         [ok]
  leaf EKU includes serverAuth                                  [ok]
  nothing in the chain revoked                                  [ok]
  HOSTNAME requested matches leaf SAN           <-- MOST OFTEN OMITTED

THE WEAKEST-LINK PROBLEM
  100+ trusted roots x ANY of them can issue for ANY domain

  DigiNotar 2011 ──► fraudulent *.google.com ──► MITM of Iranian users
                     CA removed from all trust stores, bankrupt
  Symantec 2017  ──► repeated misissuance ──► distrusted by Google

  Mitigations: CAA records (restrict WHO may issue)
               Certificate Transparency (DETECT misissuance)

import socket
import ssl
from datetime import datetime, timezone

from cryptography import x509
from cryptography.hazmat.primitives.asymmetric import padding, ec
from cryptography.x509.oid import ExtensionOID

# --- Correct TLS verification: the defaults do the right thing --------
ctx = ssl.create_default_context()
# These are already the defaults. Setting them to anything else is the
# vulnerability, not the fix.
assert ctx.verify_mode == ssl.CERT_REQUIRED
assert ctx.check_hostname is True

with socket.create_connection(("example.com", 443)) as sock:
    # `server_hostname` drives BOTH SNI and the hostname check.
    with ctx.wrap_socket(sock, server_hostname="example.com") as tls:
        print("protocol:", tls.version(), "cipher:", tls.cipher()[0])


# --- THE CLASSIC VULNERABILITY ---------------------------------------
def never_do_this() -> ssl.SSLContext:
    """Disabling verification accepts ANY certificate from ANY party,
    including a self-signed one generated by an attacker on the path.
    This turns TLS into obfuscation. It appears in real code whenever
    someone 'fixes' a certificate error by silencing it."""
    bad = ssl.create_default_context()
    bad.check_hostname = False
    bad.verify_mode = ssl.CERT_NONE
    return bad


# Subtler and just as broken: verifying the chain but NOT the hostname.
def also_broken() -> ssl.SSLContext:
    ctx = ssl.create_default_context()
    ctx.check_hostname = False        # chain still verified...
    return ctx                        # ...so a valid cert for attacker.com
                                      # is accepted when connecting to bank.com


# --- Walking a chain manually, to see what validation checks ---------
def verify_link(child: x509.Certificate, parent: x509.Certificate) -> bool:
    """One link of the chain: signature plus name chaining."""
    if child.issuer != parent.subject:
        return False                              # name chaining failed
    pub = parent.public_key()
    try:
        if isinstance(pub, ec.EllipticCurvePublicKey):
            pub.verify(child.signature, child.tbs_certificate_bytes,
                       ec.ECDSA(child.signature_hash_algorithm))
        else:
            pub.verify(child.signature, child.tbs_certificate_bytes,
                       padding.PKCS1v15(), child.signature_hash_algorithm)
        return True
    except Exception:
        return False


def check_ca_constraints(cert: x509.Certificate) -> bool:
    """A non-leaf MUST assert CA:TRUE. Skipping this check historically
    allowed any leaf certificate holder to sign for any domain."""
    try:
        bc = cert.extensions.get_extension_for_oid(
            ExtensionOID.BASIC_CONSTRAINTS).value
        return bc.ca
    except x509.ExtensionNotFound:
        return False


def check_validity(cert: x509.Certificate) -> bool:
    now = datetime.now(timezone.utc)
    return cert.not_valid_before_utc <= now <= cert.not_valid_after_utc


# --- Diagnosing a missing intermediate -------------------------------
#   openssl s_client -connect example.com:443 -showcerts
# Count the certificates returned. A server sending only the leaf will
# fail on clients that have not cached the intermediate -- which is why
# "it works in my browser but not in curl" is such a common report.
#
#   Check CAA records to see which CAs are authorised for a domain:
#     dig CAA example.com +short
#     example.com. CAA 0 issue "letsencrypt.org"

Key Takeaways

• Trust is anchored in root CA certificates pre-installed in OS and browser trust stores, and delegated downward through intermediates.
• Roots are kept offline because their compromise is unrecoverable; intermediates do the daily signing and can be revoked.
• Validation checks signature, name chaining, validity, Basic Constraints, key usage, revocation, hostname match, and anchoring — all of them.
• The hostname check is the step most often omitted, and omitting it accepts a valid certificate for the wrong domain.
• Servers must send the full chain minus the root; a missing intermediate causes failures on some clients and not others.
• The system is only as strong as its weakest CA: any trusted root can issue for any domain, as DigiNotar and Symantec demonstrated.
• CAA records restrict which CAs may issue for your domain, and Certificate Transparency makes misissuance detectable.

🧪 Practice

1. Use openssl s_client -showcerts against three sites and record how many certificates each sends. Identify any that omit an intermediate.
2. Write a script that walks a fetched chain and verifies each signature and name link manually, reporting which check fails if you deliberately reorder the certificates.
3. Query the CAA records for several large domains with dig CAA. Explain what a CA is required to do when it sees a record that does not include it.
4. Interview-style: "Why is a CA compromise more serious than a single server's key compromise?" Hint: compare the blast radius — one domain's traffic versus the ability to impersonate any domain — and consider why removing a root from trust stores is so disruptive that it is a last resort.

Certificate Signing Requests and Issuance

Theory

Getting a certificate requires proving two things to a CA: that you control the private key matching the public key you are submitting, and that you control the domain you are claiming. The certificate signing request (CSR) handles the first; domain validation handles the second.

A CSR (PKCS#10) contains the public key, the requested subject name and SANs, and a signature made with the corresponding private key. That self-signature is a proof of possession: it demonstrates the requester holds the private key without ever transmitting it. The CA verifies the self-signature, performs its own validation of the identity claim, then discards most of the CSR's requested fields and issues a certificate with the values its policy dictates.

The private key never leaves the server, which is the single most important property of the process. A CA that offers to generate your key pair for you is asking you to accept that they hold a copy of your private key.

Validation levels determine what the CA actually checks:

Level	What is verified	Issuance time	Browser display
DV (Domain Validation)	Control of the domain only	Seconds to minutes	Padlock
OV (Organization Validation)	Domain plus organizational existence	Days	Padlock; details in cert
EV (Extended Validation)	Extensive legal verification	Days to weeks	Padlock (green bar removed in 2019)

The practical point is that DV, OV, and EV provide identical cryptographic security. They differ only in the identity assertion. Browsers removed the EV visual indicator because research showed users did not notice or understand it, and because EV certificates were obtained for misleading entity names. For most purposes DV via an automated issuer is correct.

Domain validation methods, in rough order of preference:

• DNS-01 — place a specific TXT record under _acme-challenge.example.com. The only method that supports wildcard certificates, and it works without exposing anything publicly.
• HTTP-01 — serve a specific token at http://example.com/.well-known/acme-challenge/<token>. Simple, but requires port 80 and does not support wildcards.
• TLS-ALPN-01 — respond on port 443 with a special ALPN protocol. Useful when port 80 is unavailable.
• Email validation — a link sent to admin@example.com or a WHOIS contact. Legacy and weaker.

ACME (RFC 8555) automates all of this, and Let's Encrypt made it free and universal. The workflow is: create an account key, request an order for the names, satisfy a challenge per name, submit the CSR, and download the certificate. Clients such as certbot, acme.sh, lego, and caddy handle the whole loop including renewal.

Automation is not a convenience, it is a requirement. Certificate lifetimes have fallen steadily — Let's Encrypt issues for 90 days, the CA/Browser Forum has agreed to reduce maximum TLS certificate lifetimes to 47 days by 2029, and Let's Encrypt now offers 6-day certificates. Manual renewal at these intervals is not viable, and expired-certificate outages remain one of the most common self-inflicted production incidents. The correct posture is automated renewal at roughly one-third of the lifetime remaining, with monitoring that alerts on expiry independently of the renewal mechanism.

Examples

THE ISSUANCE FLOW

  1. GENERATE KEY PAIR          (private key NEVER leaves the server)
         │
  2. CREATE CSR                 public key + requested names,
         │                      SELF-SIGNED with the private key
         │                      => proof of possession
         ▼
  3. SUBMIT TO CA ──────────────────────────────────┐
                                                    │
  4. CA VALIDATES DOMAIN CONTROL                    │
       DNS-01       : TXT record at                 │
                      _acme-challenge.example.com   │
       HTTP-01      : token at /.well-known/        │
                      acme-challenge/<token>        │
       TLS-ALPN-01  : special ALPN on port 443      │
                                                    │
  5. CA SIGNS ◄─────────────────────────────────────┘
         │     (ignores most requested fields; applies its own policy)
         ▼
  6. CERTIFICATE + CHAIN returned, installed, and RENEWED AUTOMATICALLY

WHAT THE CSR PROVES

  CSR ──► [ public key ][ requested subject + SANs ][ self-signature ]
                                                     │
          verified with the public key in the CSR ───┘
          => the requester holds the matching PRIVATE key
          => the private key was never transmitted

CERTIFICATE LIFETIMES ARE COLLAPSING
  2015: 39 months        2020: 13 months       2026: 200 days (max)
  2027: 100 days         2029: 47 days         Let's Encrypt: 90 or 6 days

  => Manual renewal is no longer operationally possible.
     Renew at ~1/3 of remaining lifetime; monitor expiry SEPARATELY
     from the renewal mechanism, so a silent renewal failure is caught.

from cryptography import x509
from cryptography.hazmat.primitives import hashes, serialization
from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.x509.oid import NameOID

# --- Step 1: generate the key pair. It stays here, forever. -----------
key = ec.generate_private_key(ec.SECP256R1())

with open("server.key", "wb") as fh:
    fh.write(key.private_bytes(
        encoding=serialization.Encoding.PEM,
        format=serialization.PrivateFormat.PKCS8,
        # Encrypt at rest, or rely on filesystem permissions (0600) plus
        # disk encryption. NoEncryption on a shared host is a finding.
        encryption_algorithm=serialization.NoEncryption(),
    ))

# --- Step 2: build the CSR -------------------------------------------
csr = (
    x509.CertificateSigningRequestBuilder()
    .subject_name(x509.Name([
        # The CN is largely vestigial; the SAN list is what matters.
        x509.NameAttribute(NameOID.COMMON_NAME, "example.com"),
        x509.NameAttribute(NameOID.ORGANIZATION_NAME, "Example Ltd"),
        x509.NameAttribute(NameOID.COUNTRY_NAME, "GB"),
    ]))
    .add_extension(
        x509.SubjectAlternativeName([
            x509.DNSName("example.com"),
            x509.DNSName("www.example.com"),
            x509.DNSName("api.example.com"),
        ]),
        critical=False,
    )
    # Signing the CSR with `key` is the proof of possession.
    .sign(key, hashes.SHA256())
)

with open("server.csr", "wb") as fh:
    fh.write(csr.public_bytes(serialization.Encoding.PEM))

# Verify the self-signature, which is exactly what the CA checks first.
print("CSR signature valid:", csr.is_signature_valid)
print("requested SANs:", csr.extensions.get_extension_for_class(
    x509.SubjectAlternativeName).value.get_values_for_type(x509.DNSName))


# --- Equivalent OpenSSL, for reference -------------------------------
# Generate key and CSR in one step, with SANs (required by modern CAs):
#   openssl req -new -newkey ec -pkeyopt ec_paramgen_curve:P-256 \
#     -nodes -keyout server.key -out server.csr \
#     -subj "/CN=example.com/O=Example Ltd/C=GB" \
#     -addext "subjectAltName=DNS:example.com,DNS:www.example.com"
#
# Inspect a CSR before sending it:
#   openssl req -in server.csr -text -noout -verify


# --- In practice: let ACME do all of it ------------------------------
# certbot certonly --dns-cloudflare -d example.com -d '*.example.com'
# certbot renew --deploy-hook "systemctl reload nginx"
#
# Monitor expiry INDEPENDENTLY of the renewal mechanism:
#   echo | openssl s_client -connect example.com:443 2>/dev/null \
#     | openssl x509 -noout -checkend 1209600    # fails if < 14 days left

Method	Wildcard support	Requirements	Notes
DNS-01	Yes	DNS API access	Preferred; works for internal hosts
HTTP-01	No	Port 80 reachable	Simplest for public web servers
TLS-ALPN-01	No	Port 443 reachable	When port 80 is unavailable
Email	No	Mailbox at the domain	Legacy, weaker assurance

Key Takeaways

• A CSR carries the public key and requested names, self-signed with the private key as proof of possession; the private key is never transmitted.
• The CA validates domain control independently and applies its own policy, discarding most requested fields.
• DV, OV, and EV are cryptographically identical and differ only in identity assurance; the EV browser indicator was removed in 2019.
• DNS-01 is the most flexible validation method and the only one supporting wildcards; HTTP-01 is the simplest for public web servers.
• ACME (RFC 8555) automates issuance and renewal, and automation is mandatory given shrinking lifetimes.
• Certificate lifetimes are dropping toward 47 days by 2029, with 6-day options already available.
• Renew at roughly one-third of remaining lifetime and monitor expiry separately from the renewal mechanism, so a silent renewal failure is still caught.

🧪 Practice

1. Generate an EC key and a CSR with three SAN entries, then verify the CSR's self-signature and decode it with openssl req -text -noout.
2. Obtain a real certificate for a domain you control using certbot with DNS-01 validation, then inspect the issued certificate and compare its fields to what you requested.
3. Write a monitoring check that reports the days remaining on a certificate and exits non-zero below a threshold. Explain why this must not depend on the renewal tool's own status.
4. Interview-style: "Why should a CA never generate your private key for you?" Hint: think about what proof of possession is for, who could then impersonate you, and whether you could ever prove the CA had not retained a copy.

Revocation: CRL and OCSP

Theory

Certificates carry an expiry date, but things go wrong before expiry: a private key leaks, a server is compromised, a domain changes hands, a certificate is misissued. Revocation is the mechanism for declaring a certificate invalid before its notAfter date. It is also, candidly, the part of PKI that works least well.

Certificate Revocation Lists (CRLs) are the original design: the CA publishes a signed list of revoked serial numbers at a URL in the certificate's CRL Distribution Points extension. Clients download it and check. The problems are structural — CRLs for a large CA grow to megabytes, they are cached so revocation takes effect only after the cache expires (typically hours to days), and downloading a multi-megabyte list before completing a handshake is unacceptable for a browser.

OCSP (Online Certificate Status Protocol) replaced the bulk download with a per-certificate query: the client asks the CA's responder "is serial X still valid?" and gets a small signed answer. This fixed the size problem and introduced three worse ones:

1. Privacy. Every OCSP query tells the CA which site the user is visiting, when. This is a browsing-history feed to a third party.
2. Latency. An extra network round trip to a third-party server, on the critical path of every new connection.
3. Soft-fail. If the responder is unreachable, clients proceed anyway. They must, because hard-failing would mean a CA outage takes down a large part of the web. But soft-fail makes revocation checking useless against an active attacker, who simply blocks the OCSP request — the very attacker revocation was meant to stop.

OCSP stapling addresses privacy and latency: the server periodically fetches a signed OCSP response for its own certificate and includes it in the TLS handshake. The client gets fresh revocation status with no extra round trip and no third-party contact. The Must-Staple extension in a certificate instructs clients to hard-fail if no stapled response is present, which closes the soft-fail hole for that certificate at the cost of an outage if stapling breaks.

The industry's actual answer has been to route around the problem:

• Short-lived certificates. If a certificate expires in 6 to 47 days, expiry does most of revocation's job. This is the main reason lifetimes are shrinking, and it is why Let's Encrypt stopped supporting OCSP entirely in 2025, switching to CRLs for the cases that need them.
• Browser-pushed lists. Chrome's CRLSets and Firefox's CRLite compress revocation data (CRLite uses a cascade of Bloom filters to compress all WebPKI revocations into a few hundred kilobytes) and ship it through the browser's own update channel. No per-connection network dependency, no privacy leak, and hard-fail becomes feasible.
• Certificate Transparency for detection, so that misissuance is caught rather than merely revocable.

The practical guidance for operators: enable OCSP stapling where your CA still supports it, keep certificate lifetimes short, and treat key compromise as requiring both revocation and key rotation — a revoked certificate whose key is still in use elsewhere is not contained.

Examples

CRL -- download the whole list

  client ──► GET http://crl.ca.example/root.crl ──► CA
         ◄── signed list of revoked serials (can be MEGABYTES) ──
  Cached for hours or days => revocation is slow to take effect.

OCSP -- ask about one certificate

  client ──► "is serial 0x04f8e1 valid?" ──► CA's OCSP responder
         ◄── signed: good | revoked | unknown ──
  Small and fresh, BUT:
    - the CA learns every site the user visits    (privacy)
    - an extra round trip per connection          (latency)
    - unreachable responder => client proceeds    (SOFT-FAIL)

THE SOFT-FAIL PROBLEM -- revocation vs the attacker it was built for

  attacker holds a stolen key for a REVOKED certificate
      │
      ├─► presents the revoked certificate
      └─► BLOCKS the client's OCSP request (they are already on the path)
            │
            ▼
      client cannot reach the responder ──► SOFT-FAIL ──► proceeds
      Revocation checking provided zero protection.

OCSP STAPLING -- the server does the fetching

  server ──► OCSP responder (periodically, every few hours)
         ◄── signed response, cached locally
  client ──► TLS handshake
         ◄── certificate + STAPLED OCSP response
  No extra round trip, no privacy leak, fresh status.
  Must-Staple extension => client HARD-FAILS without a staple.

WHAT THE INDUSTRY ACTUALLY DID
  short-lived certs (6-47 days)  -> expiry does revocation's job
  CRLSets (Chrome)               -> pushed via browser updates
  CRLite (Firefox)               -> Bloom filter cascade, ~hundreds of KB
  Certificate Transparency       -> detect misissuance, don't just revoke
  Let's Encrypt dropped OCSP in 2025 in favour of CRLs

import socket
import ssl
import subprocess

# --- Check whether a server staples an OCSP response -----------------
#   openssl s_client -connect example.com:443 -status </dev/null 2>/dev/null \
#     | grep -A 20 "OCSP response"
#
# Expected output when stapling works:
#   OCSP Response Status: successful (0x0)
#   Cert Status: good
#   This Update: ...   Next Update: ...
#
# "OCSP response: no response sent" means stapling is not configured.


def check_stapling(host: str, port: int = 443) -> bool:
    """Returns True if the server stapled an OCSP response."""
    out = subprocess.run(
        ["openssl", "s_client", "-connect", f"{host}:{port}",
         "-servername", host, "-status"],
        input=b"", capture_output=True, timeout=15,
    ).stdout.decode(errors="replace")
    return "Cert Status: good" in out


print("example.com staples OCSP:", check_stapling("example.com"))


# --- Manual OCSP query, to see the protocol -------------------------
#   openssl ocsp -issuer chain.pem -cert leaf.pem \
#     -url http://r11.o.lencr.org -text
#
# And fetching a CRL:
#   openssl crl -in crl.der -inform DER -text -noout | head -40


# --- Python's view of stapling and verification ---------------------
ctx = ssl.create_default_context()
with socket.create_connection(("example.com", 443)) as sock:
    with ctx.wrap_socket(sock, server_hostname="example.com") as tls:
        # Python exposes the DER certificate; stapled OCSP handling is
        # performed inside OpenSSL during the handshake rather than here.
        der = tls.getpeercert(binary_form=True)
        print(f"certificate received: {len(der)} bytes")


# --- Server configuration: enable stapling ---------------------------
NGINX = """
ssl_stapling on;
ssl_stapling_verify on;
# The full chain including the issuer, needed to verify the OCSP response:
ssl_trusted_certificate /etc/letsencrypt/live/example.com/chain.pem;
resolver 1.1.1.1 8.8.8.8 valid=300s;
resolver_timeout 5s;
"""

APACHE = """
SSLUseStapling On
SSLStaplingCache "shmcb:/var/run/ocsp(128000)"
SSLStaplingReturnResponderErrors Off
"""

# --- Key compromise response: revoke AND rotate ---------------------
# Revocation alone is insufficient, because soft-fail means many clients
# will still accept the revoked certificate.
#
#   certbot revoke --cert-path /etc/letsencrypt/live/example.com/cert.pem \
#     --reason keycompromise
#   certbot certonly --force-renewal -d example.com   # NEW key pair
#
# Then audit everywhere the old key may have been copied: backups,
# configuration management, container images, developer laptops.

Mechanism	Size	Freshness	Privacy	Fails how	Status
CRL	MB	Hours to days	Good	Soft	Returning to favour
OCSP	Bytes	Minutes	Poor	Soft (useless vs attacker)	Being retired
OCSP stapling	Bytes	Hours	Good	Soft	Recommended where supported
Must-Staple	Bytes	Hours	Good	Hard	Rare; outage risk
CRLSet / CRLite	KB, pushed	Days	Good	Hard	Browser default
Short lifetimes	Zero	N/A	Good	N/A	The real answer

Key Takeaways

• Revocation declares a certificate invalid before expiry, and it is the weakest part of PKI in practice.
• CRLs are large and stale; OCSP is small and fresh but leaks browsing history and adds latency.
• Soft-fail makes revocation checking useless against an on-path attacker, who simply blocks the query — yet hard-fail risks outages from CA downtime.
• OCSP stapling moves the fetch to the server, removing the privacy leak and the extra round trip; Must-Staple enables hard-fail at the cost of outage risk.
• The industry's real solution is short certificate lifetimes, which is why maximum lifetimes are falling to 47 days and Let's Encrypt retired OCSP in 2025.
• Browser-pushed revocation data (Chrome CRLSets, Firefox CRLite) avoids per-connection network dependencies entirely.
• Key compromise requires both revocation and key rotation, plus an audit of everywhere the old key was copied.

🧪 Practice

1. Test five sites for OCSP stapling with openssl s_client -status and record which staple. For one that does not, look up the server software and find the configuration directive it is missing.
2. Download a CRL from a major CA, decode it, and count the revoked entries and file size. Estimate the bandwidth cost if every client downloaded it per connection.
3. Explain why hard-fail revocation checking is not the default in browsers, then describe the two mechanisms that make hard-fail practical.
4. Interview-style: "A server's private key was exposed in a public Git repository. Walk me through your response." Hint: revocation is necessary but not sufficient — cover issuing a new key pair rather than reusing the old one, the reason code you would pick, auditing everywhere the key propagated, and why you cannot rely on clients honouring the revocation.

Certificate Pinning and Transparency Logs

Theory

Standard PKI validation accepts a certificate from any trusted CA. That is convenient and it is the system's structural weakness: a single compromised or coerced CA among the hundred-plus in a trust store can impersonate any site. Two complementary mechanisms address this — pinning prevents, transparency detects.

Certificate pinning narrows what a client will accept for a specific host. Instead of "any certificate from any trusted CA," the client requires "a certificate matching this specific key or issuer." Pinning granularity matters:

• Certificate pinning — pin the leaf's fingerprint. Breaks on every renewal, which with 47-day lifetimes is untenable.
• Public key pinning — pin the hash of the Subject Public Key Info. Survives renewal as long as the key is reused. This is the correct granularity.
• CA pinning — pin the intermediate or root. Most flexible, least protective.

Pinning's danger is bricking. If the pinned key is lost or must be rotated urgently, clients reject every certificate you can obtain, and you cannot fix it without shipping an update. HTTP Public Key Pinning (HPKP), the web standard for this, was deprecated and removed from browsers precisely because sites pinned themselves into outages — including deliberate "RansomPKP" attacks where an intruder pinned keys they controlled. The lessons that survive: always pin at least one backup key that is generated and stored offline, and keep pin lifetimes short.

Pinning remains appropriate and widely used in mobile apps and embedded devices, where you control both endpoints and can ship updates. Android's Network Security Configuration and iOS App Transport Security both support it declaratively. It is also how certificate-based device authentication works in closed systems. Note that pinning is a frequent target in mobile pentesting, since bypassing it is usually a prerequisite for inspecting app traffic.

Certificate Transparency (CT) takes the opposite approach: rather than restricting issuance, make all issuance publicly auditable. CAs submit every certificate they issue to multiple append-only, cryptographically verifiable logs built on Merkle trees. The log returns a Signed Certificate Timestamp (SCT), which the CA embeds in the certificate. Since 2018, Chrome requires valid SCTs for all publicly trusted certificates, and Safari followed; a certificate without them is rejected. CT is therefore effectively mandatory.

The Merkle tree structure is what makes the log trustworthy: anyone can verify that a certificate is included (an inclusion proof is logarithmic in log size) and that the log has only ever appended (a consistency proof), so a log operator cannot retroactively remove or alter an entry without detection.

The practical consequence for defenders is monitoring. Services like crt.sh and Cert Spotter, or your own log-monitoring code, let you watch for certificates issued for your domains. If a CA misissues a certificate for your domain, you find out within minutes. This is how several real misissuance incidents were discovered. It is also an under-used control: setting up CT monitoring for your domains takes minutes and provides detection that no other mechanism offers.

A side effect worth knowing in both directions: CT logs are public reconnaissance data. Every internal hostname you request a public certificate for becomes world-readable. dev-staging.internal.example.com in a CT log is a gift to an attacker. Use wildcard certificates or an internal CA for non-public names.

Examples

PINNING: narrow what the client will accept

  STANDARD VALIDATION          PINNED VALIDATION
  any of 100+ trusted CAs      ONLY this specific public key
         │                              │
  a single compromised CA      a compromised CA cannot help the
  can impersonate the site     attacker -- the key does not match

  GRANULARITY
    leaf certificate  -> breaks on every renewal          AVOID
    public key (SPKI) -> survives renewal if key reused   CORRECT
    intermediate/root -> flexible, least protective        OK for CA pinning

  THE BRICKING RISK
    pinned key lost / must rotate urgently
      => every obtainable certificate is rejected
      => only an app update fixes it
    HPKP was REMOVED from browsers for exactly this reason.
    MITIGATION: always pin a BACKUP key generated and stored offline.

CERTIFICATE TRANSPARENCY: make issuance auditable

  CA issues cert ──► submits to CT logs ──► receives SCTs
                                             │
                     SCTs embedded in the certificate
                                             │
  client ──► checks for valid SCTs ──► Chrome REQUIRES them since 2018

  MERKLE TREE LOG (append-only, verifiable)

                      root hash (signed by the log)
                     /                    \
              h(0,1)                        h(2,3)
             /      \                      /      \
         h(c0)      h(c1)              h(c2)      h(c3)
           │          │                  │          │
         cert0      cert1              cert2      cert3

    inclusion proof : O(log n) hashes prove cert2 is in the log
    consistency proof: proves the log only ever APPENDED
    => the operator cannot remove or alter an entry undetected

  DEFENDER'S USE: monitor the logs for your own domains
    a misissued certificate for example.com appears publicly
    within minutes of issuance.

  ATTACKER'S USE: CT logs are public reconnaissance
    dev-staging.internal.example.com  <-- now world-readable
    => use wildcards or an internal CA for non-public names

import base64
import hashlib
import json
import socket
import ssl
import urllib.request

from cryptography import x509
from cryptography.hazmat.primitives import hashes, serialization

# --- Compute an SPKI pin (the correct granularity) -------------------
def spki_pin(cert_der: bytes) -> str:
    """Base64 SHA-256 of the SubjectPublicKeyInfo. Survives certificate
    renewal as long as the key pair is reused -- which is exactly what
    makes it safer to pin than the leaf fingerprint."""
    cert = x509.load_der_x509_certificate(cert_der)
    spki = cert.public_key().public_bytes(
        encoding=serialization.Encoding.DER,
        format=serialization.PublicFormat.SubjectPublicKeyInfo,
    )
    return base64.b64encode(hashlib.sha256(spki).digest()).decode()


ctx = ssl.create_default_context()
with socket.create_connection(("example.com", 443)) as sock:
    with ctx.wrap_socket(sock, server_hostname="example.com") as tls:
        der = tls.getpeercert(binary_form=True)

print("pin-sha256:", spki_pin(der))
# Equivalent with OpenSSL:
#   openssl x509 -in cert.pem -pubkey -noout \
#     | openssl pkey -pubin -outform DER \
#     | openssl dgst -sha256 -binary | base64


# --- Enforcing a pin in client code ---------------------------------
PINS = {
    "example.com": {
        "primary-key-pin-base64",
        "BACKUP-key-pin-base64",     # generated offline; NEVER skip this
    },
}


def verify_pinned(host: str, port: int = 443) -> bool:
    """Connect with normal validation, THEN additionally require a pin
    match. Pinning supplements chain validation, never replaces it."""
    ctx = ssl.create_default_context()      # chain + hostname still checked
    with socket.create_connection((host, port)) as sock:
        with ctx.wrap_socket(sock, server_hostname=host) as tls:
            return spki_pin(tls.getpeercert(binary_form=True)) in PINS[host]


# --- Read the embedded SCTs from a certificate ----------------------
cert = x509.load_der_x509_certificate(der)
try:
    scts = cert.extensions.get_extension_for_class(
        x509.PrecertificateSignedCertificateTimestamps).value
    for sct in scts:
        print(f"SCT: log={sct.log_id.hex()[:16]}... at {sct.timestamp}")
except x509.ExtensionNotFound:
    print("no SCTs -- Chrome and Safari would reject this certificate")


# --- Monitor CT logs for your own domains ---------------------------
def ct_search(domain: str) -> list[dict]:
    """Query crt.sh for every logged certificate covering a domain.
    Run this on a schedule and alert on issuers you did not authorise."""
    url = f"https://crt.sh/?q=%25.{domain}&output=json"
    with urllib.request.urlopen(url, timeout=30) as resp:
        return json.load(resp)


EXPECTED_ISSUERS = {"Let's Encrypt", "R10", "R11", "E5", "E6"}


def detect_misissuance(domain: str) -> list[dict]:
    """Any certificate from an unexpected issuer is worth investigating
    immediately -- this is the detection CT uniquely provides."""
    return [
        entry for entry in ct_search(domain)
        if not any(known in entry.get("issuer_name", "")
                   for known in EXPECTED_ISSUERS)
    ]


# --- Mobile pinning configuration, declaratively --------------------
ANDROID_NSC = """
<network-security-config>
  <domain-config>
    <domain includeSubdomains="true">api.example.com</domain>
    <pin-set expiration="2027-01-01">
      <pin digest="SHA-256">primary-key-pin-base64</pin>
      <pin digest="SHA-256">BACKUP-key-pin-base64</pin>
    </pin-set>
  </domain-config>
</network-security-config>
"""
# Note `expiration`: after that date the pin set is ignored rather than
# bricking the app. Short pin lifetimes are a deliberate safety valve.

Mechanism	Prevents or detects	Risk	Where to use
Leaf certificate pinning	Prevents	Breaks on every renewal	Avoid
SPKI (public key) pinning	Prevents	Bricking if key is lost	Mobile apps, embedded, internal clients
CA pinning	Prevents	Weaker protection	When CA choice is stable
HPKP	Prevents	Caused outages	Removed from browsers
Certificate Transparency	Detects	Leaks internal hostnames	Mandatory; monitor your domains
CAA records	Prevents	Minimal	Always set them

Key Takeaways

• Standard validation accepts a certificate from any trusted CA, which is the structural weakness that pinning and CT address.
• Pin the SubjectPublicKeyInfo hash, not the leaf certificate, so pins survive renewal.
• Pinning's real danger is bricking; always pin an offline-generated backup key and set a pin expiration.
• HPKP was removed from browsers because sites pinned themselves into outages; pinning now belongs in mobile apps and embedded devices where you control updates.
• Certificate Transparency makes issuance publicly auditable via append-only Merkle tree logs, and Chrome has required SCTs since 2018.
• Merkle inclusion and consistency proofs mean a log operator cannot remove or alter entries undetected.
• Monitor CT logs for your own domains — it is cheap detection for misissuance that nothing else provides.
• CT logs are public reconnaissance: never request a public certificate for an internal hostname you want kept quiet.

🧪 Practice

1. Compute the SPKI pin for three sites using both the Python function and the OpenSSL pipeline, and confirm they agree.
2. Search crt.sh for a domain you own or a large public domain, and list every distinct issuer and every subdomain that appears. Note any hostname you would consider sensitive.
3. Set up CT monitoring for a domain and verify it fires by requesting a new certificate. Define what your alert rule should treat as suspicious.
4. Interview-style: "A mobile team wants to pin certificates. What do you tell them?" Hint: endorse the goal but drive the conversation to granularity, backup pins, pin expiration, and the rollout question — what happens to installed app versions when the key must be rotated urgently.

Self-Signed Certificates and Internal CAs

Theory

A self-signed certificate is one where the subject and issuer are the same: it vouches for itself. Cryptographically it is identical to any other certificate — the same key sizes, the same TLS session strength. What it lacks is any third-party assertion of identity, so no client trusts it by default.

The consequence is important and widely misunderstood. A self-signed certificate does provide encryption against a passive eavesdropper. It does not provide authentication, which means it is defeated by an active machine-in-the-middle: the attacker presents their own self-signed certificate, and since the client has no basis for distinguishing yours from theirs, there is nothing to detect. Worse, the normal operational response — telling users to click through the browser warning, or setting verify=False in code — trains everyone to accept any certificate, which disables the protection permanently and everywhere in that codebase.

Self-signed certificates are legitimate in narrow cases: local development, automated tests, and situations where the certificate is pinned out-of-band so the client knows exactly which certificate to expect.

For anything larger, the correct tool is an internal CA (private PKI). You generate your own root, distribute that root certificate to your internal clients' trust stores via configuration management or MDM, and then issue certificates to internal services from it. Clients validate normally, with no warnings and no disabled verification, and you retain full control over naming — including internal hostnames that no public CA would ever issue for, and which you would not want appearing in Certificate Transparency logs.

Building an internal CA properly means treating the root the way public CAs do:

• Keep the root offline. Ideally on an air-gapped machine or in an HSM. It should sign only intermediates.
• Issue from an intermediate. This lets you revoke and replace the signing capability without redistributing the root to every client.
• Constrain the root's authority with name constraints. A root in your trust store can otherwise sign a valid certificate for google.com. The nameConstraints extension limits it to your own domains, which contains the damage if the internal CA is compromised.
• Set appropriate lifetimes. Long for the root (10 years), moderate for intermediates, short for leaves, with automated issuance.
• Automate. Tools such as step-ca, HashiCorp Vault PKI, cfssl, and cloud private CA services provide ACME endpoints, so internal services renew exactly the way public ones do. For local development, mkcert sets up a local CA and installs it in system trust stores in one command.

A modern alternative worth knowing: a service mesh (Istio, Linkerd) or SPIFFE/SPIRE issues short-lived workload certificates automatically and handles rotation and identity entirely, which for Kubernetes-based infrastructure is usually a better fit than managing an internal CA by hand.

Examples

SELF-SIGNED vs INTERNAL CA vs PUBLIC CA

  SELF-SIGNED            issuer == subject
    ┌──────────┐         encryption: YES
    │ CN=dev   │◄──┐     authentication: NO
    │ issuer=  │   │     client reaction: warning / must disable checks
    │ CN=dev   │───┘     use for: local dev, tests, pinned clients only
    └──────────┘

  INTERNAL CA            you are the trust anchor
    ┌──────────────┐     root distributed via MDM / config management
    │ Internal Root│     clients validate NORMALLY -- no warnings
    └──────┬───────┘     you can issue for internal.example.local
           │ signs       names never appear in CT logs
    ┌──────▼───────┐
    │ Internal Int.│     keep the ROOT offline; issue from here
    └──────┬───────┘
           │ signs
    ┌──────▼─────────────────┐
    │ db.internal.example    │
    └────────────────────────┘

  PUBLIC CA              pre-trusted everywhere, public names only

NAME CONSTRAINTS -- essential for an internal root

  Without:  your internal root can sign a VALID certificate for
            google.com, and every client that trusts your root
            will accept it. A compromise of your CA is a compromise
            of every site your employees visit.

  With:     nameConstraints: permitted: .example.internal, .corp.example.com
            the root is cryptographically incapable of issuing
            outside those namespaces.

THE ANTI-PATTERN THAT CAUSES BREACHES
  self-signed cert in staging
    => "just set verify=False to make it work"
    => that line ships to production
    => TLS is now obfuscation, not security, for ALL hosts
  The fix is an internal CA, not disabled verification.

import datetime

from cryptography import x509
from cryptography.hazmat.primitives import hashes, serialization
from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.x509.oid import NameOID

NOW = datetime.datetime.now(datetime.timezone.utc)


# --- 1. The internal ROOT: long-lived, offline, name-constrained -------
root_key = ec.generate_private_key(ec.SECP384R1())
root_name = x509.Name([
    x509.NameAttribute(NameOID.COMMON_NAME, "Example Internal Root CA"),
    x509.NameAttribute(NameOID.ORGANIZATION_NAME, "Example Ltd"),
])

root_cert = (
    x509.CertificateBuilder()
    .subject_name(root_name)
    .issuer_name(root_name)                      # self-signed: same name
    .public_key(root_key.public_key())
    .serial_number(x509.random_serial_number())
    .not_valid_before(NOW)
    .not_valid_after(NOW + datetime.timedelta(days=3650))
    .add_extension(x509.BasicConstraints(ca=True, path_length=1),
                   critical=True)
    .add_extension(
        x509.KeyUsage(digital_signature=False, content_commitment=False,
                      key_encipherment=False, data_encipherment=False,
                      key_agreement=False, key_cert_sign=True,
                      crl_sign=True, encipher_only=False,
                      decipher_only=False),
        critical=True,
    )
    # CRITICAL: without this the root can sign a valid cert for ANY domain.
    .add_extension(
        x509.NameConstraints(
            permitted_subtrees=[x509.DNSName(".example.internal"),
                                x509.DNSName(".corp.example.com")],
            excluded_subtrees=None,
        ),
        critical=True,
    )
    .sign(root_key, hashes.SHA384())
)


# --- 2. An INTERMEDIATE does the day-to-day signing -------------------
int_key = ec.generate_private_key(ec.SECP256R1())
int_cert = (
    x509.CertificateBuilder()
    .subject_name(x509.Name([x509.NameAttribute(
        NameOID.COMMON_NAME, "Example Internal Issuing CA")]))
    .issuer_name(root_cert.subject)
    .public_key(int_key.public_key())
    .serial_number(x509.random_serial_number())
    .not_valid_before(NOW)
    .not_valid_after(NOW + datetime.timedelta(days=1825))
    .add_extension(x509.BasicConstraints(ca=True, path_length=0),
                   critical=True)
    .sign(root_key, hashes.SHA384())             # signed by the ROOT
)


# --- 3. A LEAF for an internal service, short-lived ------------------
leaf_key = ec.generate_private_key(ec.SECP256R1())
leaf_cert = (
    x509.CertificateBuilder()
    .subject_name(x509.Name([x509.NameAttribute(
        NameOID.COMMON_NAME, "db.example.internal")]))
    .issuer_name(int_cert.subject)
    .public_key(leaf_key.public_key())
    .serial_number(x509.random_serial_number())
    .not_valid_before(NOW)
    .not_valid_after(NOW + datetime.timedelta(days=90))
    .add_extension(
        x509.SubjectAlternativeName([
            x509.DNSName("db.example.internal"),
            x509.DNSName("db-replica.example.internal"),
        ]),
        critical=False,
    )
    .add_extension(x509.BasicConstraints(ca=False, path_length=None),
                   critical=True)
    .add_extension(
        x509.ExtendedKeyUsage([
            x509.ObjectIdentifier("1.3.6.1.5.5.7.3.1"),   # serverAuth
            x509.ObjectIdentifier("1.3.6.1.5.5.7.3.2"),   # clientAuth
        ]),
        critical=False,
    )
    .sign(int_key, hashes.SHA256())              # signed by the INTERMEDIATE
)

for name, cert in (("root", root_cert), ("intermediate", int_cert),
                   ("leaf", leaf_cert)):
    print(f"{name:>13}: {cert.subject.rfc4514_string()}")


# --- 4. Distribute the ROOT to clients; verify normally -------------
with open("internal-root.pem", "wb") as fh:
    fh.write(root_cert.public_bytes(serialization.Encoding.PEM))

# Clients then verify against your root WITHOUT disabling anything:
#
#   import ssl
#   ctx = ssl.create_default_context(cafile="internal-root.pem")
#   # check_hostname stays True, verify_mode stays CERT_REQUIRED
#
#   requests.get("https://db.example.internal", verify="internal-root.pem")
#   export REQUESTS_CA_BUNDLE=/etc/ssl/certs/internal-root.pem
#
# System-wide installation:
#   Debian: cp internal-root.pem /usr/local/share/ca-certificates/x.crt
#           && update-ca-certificates
#   RHEL:   cp internal-root.pem /etc/pki/ca-trust/source/anchors/
#           && update-ca-trust
#
# Better still, use tooling that does all of the above plus ACME:
#   mkcert          -- local development, one command
#   step-ca         -- internal ACME server
#   Vault PKI       -- dynamic short-lived certificates
#   SPIFFE/SPIRE    -- workload identity for Kubernetes

Option	Client trust	Authentication	Best for
Self-signed	Manual per certificate	None unless pinned	Local dev, tests
Internal CA	Install root once	Full	Internal services, device fleets
Public CA (DV)	Automatic	Full	Anything internet-facing
Service mesh / SPIFFE	Automatic in-mesh	Full, with rotation	Kubernetes workloads

Key Takeaways

• A self-signed certificate is cryptographically normal but carries no third-party identity assertion, so it gives encryption without authentication.
• Encryption without authentication is defeated by an active machine-in-the-middle, and the usual workaround of disabling verification makes things permanently worse.
• Disabling certificate verification to accommodate a self-signed certificate is the anti-pattern that turns TLS into obfuscation across an entire codebase.
• An internal CA is the correct solution beyond local development: distribute your root once and let clients validate normally.
• Keep the internal root offline, issue from an intermediate, and set name constraints so the root cannot sign for domains you do not own.
• Automate internal issuance with step-ca, Vault PKI, cfssl, or a cloud private CA, using ACME so renewal works like the public web.
• Internal CAs also keep internal hostnames out of Certificate Transparency logs, which public certificates would publish.

🧪 Practice

1. Build the three-tier internal CA from the code above, then verify the leaf against the root using openssl verify -CAfile root.pem -untrusted intermediate.pem leaf.pem.
2. Install your internal root into your OS trust store, serve the leaf with a local HTTPS server, and confirm curl succeeds with no flags. Then remove the root and observe the failure.
3. Attempt to issue a certificate for google.com from your name-constrained root and show that validation rejects it. Explain which extension caused the rejection.
4. Interview-style: "A team disabled TLS verification because their internal service uses a self-signed certificate. What is the risk and the fix?" Hint: establish that the disabled check applies to every host the client talks to, not just the internal one, then propose the internal-CA path and explain why name constraints matter for the root you are about to install everywhere.

Key Lifecycle Management and Escrow

Theory

Cryptographic algorithms rarely fail. Key management fails constantly, and it is where nearly all real-world cryptographic incidents originate. A key has a lifecycle, and each stage has its own failure mode.

The stages:

1. Generation — from a properly seeded CSPRNG, at the required strength, ideally inside an HSM so the key never exists in general-purpose memory. Failure mode: weak entropy at early boot, which produced tens of thousands of internet hosts sharing RSA keys.
2. Distribution — getting the key where it is needed without exposing it. Failure mode: keys in environment variables visible to every process, in CI logs, in Slack messages, in Git history.
3. Storage — encrypted at rest under a separate key, with access controlled and audited. Failure mode: hardcoded keys in source code, which is the most common secret-scanning finding in existence.
4. Use — in memory for as short a time as possible, zeroized after use where the language permits, never logged. Failure mode: keys in crash dumps, heap dumps, and debug logs.
5. Rotation — replacing a key on a schedule, with a transition period during which both the old and new keys are accepted for verification but only the new one is used for creation. Failure mode: no rotation capability designed in, so rotation requires downtime and therefore never happens.
6. Archival — retaining old keys for as long as data encrypted under them must be readable. Failure mode: destroying a key that still protects needed backups, which is unrecoverable data loss.
7. Destruction — secure, verified deletion including every backup copy. Failure mode: a "destroyed" key still present in a snapshot.

Crypto-shredding is a useful consequence of this model: if each tenant's or user's data is encrypted under a distinct key, deleting that key makes their data permanently unrecoverable everywhere it exists, including in backups. This is often the only practical way to honour a data deletion request against immutable backups.

Key hierarchy is the standard design pattern, and it solves rotation economically:

• A root or master key lives in an HSM or cloud KMS and never leaves it.
• Key-encryption keys (KEKs) are encrypted under the master key.
• Data-encryption keys (DEKs) are generated per object or per tenant, used for the actual encryption, and stored encrypted under a KEK alongside the ciphertext.

This is envelope encryption, and the operational benefit is that rotating a KEK requires re-encrypting only the small DEKs, not the terabytes of data. Every cloud KMS implements this pattern.

Key escrow is the deliberate retention of a copy of a key by a third party. It is legitimate and sometimes required: disk-encryption recovery keys held by enterprise IT so an employee's laptop is recoverable, encrypted-backup keys held so the business survives a key holder leaving. It is also a genuine security trade-off, because the escrow becomes a high-value target and a single point of compromise. The honest framing is that escrow is appropriate for data-at-rest keys where availability matters and inappropriate for signing keys (it destroys non-repudiation) and for session keys (it destroys forward secrecy). Government-mandated escrow — the Clipper chip in the 1990s, recurring "lawful access" proposals since — has been consistently opposed by cryptographers on the grounds that a mandated backdoor cannot be restricted to authorized users. Where escrow is needed, split knowledge (Shamir secret sharing with an M-of-N threshold) means no single custodian can act alone.

Examples

THE KEY LIFECYCLE AND ITS FAILURE MODES

  GENERATE ──► DISTRIBUTE ──► STORE ──► USE ──► ROTATE ──► ARCHIVE ──► DESTROY
     │             │            │        │        │          │           │
  weak         keys in       hardcoded  logged  no rotation  key      copy left
  entropy      CI logs,      in source  in      designed    destroyed  in a
  at boot      Slack, Git    code       crash   in          too early  snapshot
                                        dumps              => data loss

KEY HIERARCHY (envelope encryption)

  ┌─────────────────────────────────────────────────────────┐
  │  MASTER KEY  -- in an HSM / cloud KMS, NEVER exported   │
  └──────────────────────────┬──────────────────────────────┘
                             │ encrypts
  ┌──────────────────────────▼──────────────────────────────┐
  │  KEK (key-encryption key)  -- stored encrypted          │
  └──────────────────────────┬──────────────────────────────┘
                             │ encrypts
  ┌──────────────────────────▼──────────────────────────────┐
  │  DEK (data-encryption key) -- one per object or tenant  │
  │  stored encrypted NEXT TO the ciphertext it protects    │
  └──────────────────────────┬──────────────────────────────┘
                             │ encrypts
                      the actual data (terabytes)

  Rotating the KEK re-encrypts only the small DEKs, not the data.
  Deleting a tenant's DEK = CRYPTO-SHREDDING: their data becomes
  permanently unrecoverable, including in immutable backups.

ROTATION WITH A TRANSITION WINDOW

  t0 ── key v1 active ──────────────────────────────────┐
  t1 ── key v2 created; v2 SIGNS/ENCRYPTS, v1 still     │
        VERIFIES/DECRYPTS                               │ overlap
  t2 ── all data re-encrypted or expired                │
  t3 ── v1 archived, then destroyed ────────────────────┘

  Key IDs in the ciphertext are what make this possible:
    [ key_id ][ nonce ][ ciphertext ][ tag ]

ESCROW: appropriate and inappropriate uses

  APPROPRIATE                      INAPPROPRIATE
  disk-encryption recovery keys     signing keys (kills non-repudiation)
  encrypted backup keys             session keys (kills forward secrecy)
  => availability matters           => the whole point is that only
                                       one party can act

  SPLIT KNOWLEDGE: Shamir 3-of-5 so no single custodian can act alone
    share1  share2  share3  share4  share5
      └───────┴───────┘                      any 3 reconstruct
                                             any 2 learn NOTHING

import os

from cryptography.hazmat.primitives.ciphers.aead import AESGCM

# --- ENVELOPE ENCRYPTION: the standard pattern ----------------------
class KeyManager:
    """A simplified KMS. In production the master key lives in an HSM or
    cloud KMS and is never present in application memory at all."""

    def __init__(self) -> None:
        self._master_versions = {1: AESGCM.generate_key(bit_length=256)}
        self._current = 1

    def rotate_master(self) -> int:
        """Old versions are RETAINED so existing DEKs stay decryptable.
        Only new wraps use the new version."""
        self._current += 1
        self._master_versions[self._current] = AESGCM.generate_key(
            bit_length=256)
        return self._current

    def wrap(self, dek: bytes) -> bytes:
        """Returns version || nonce || wrapped DEK, so the ciphertext is
        self-describing and rotation does not break old data."""
        key = self._master_versions[self._current]
        nonce = os.urandom(12)
        version = self._current.to_bytes(2, "big")
        # The version is AAD, so it cannot be swapped to force an old key.
        return version + nonce + AESGCM(key).encrypt(nonce, dek, version)

    def unwrap(self, blob: bytes) -> bytes:
        version_bytes, nonce, body = blob[:2], blob[2:14], blob[14:]
        key = self._master_versions[int.from_bytes(version_bytes, "big")]
        return AESGCM(key).decrypt(nonce, body, version_bytes)


kms = KeyManager()


def encrypt_object(plaintext: bytes, context: bytes) -> dict:
    """A fresh DEK per object. The wrapped DEK travels WITH the ciphertext,
    so there is no central table of data keys to lose or leak."""
    dek = AESGCM.generate_key(bit_length=256)
    nonce = os.urandom(12)
    record = {
        "wrapped_dek": kms.wrap(dek),
        "nonce": nonce,
        "ciphertext": AESGCM(dek).encrypt(nonce, plaintext, context),
        "context": context,
    }
    del dek                      # minimise the window in memory
    return record


def decrypt_object(record: dict) -> bytes:
    dek = kms.unwrap(record["wrapped_dek"])
    return AESGCM(dek).decrypt(record["nonce"], record["ciphertext"],
                               record["context"])


rec = encrypt_object(b"customer PII", b"tenant=acme;table=users")
print(decrypt_object(rec))

# Rotating the master re-wraps only the small DEKs. Existing objects stay
# readable because their version tag selects the right master key.
new_version = kms.rotate_master()
rec2 = encrypt_object(b"newer record", b"tenant=acme;table=users")
print(decrypt_object(rec), decrypt_object(rec2))   # both still work


# --- CRYPTO-SHREDDING: per-tenant keys make deletion verifiable -----
class TenantKeys:
    def __init__(self) -> None:
        self._wrapped: dict[str, bytes] = {}

    def key_for(self, tenant: str) -> bytes:
        if tenant not in self._wrapped:
            self._wrapped[tenant] = kms.wrap(
                AESGCM.generate_key(bit_length=256))
        return kms.unwrap(self._wrapped[tenant])

    def shred(self, tenant: str) -> None:
        """Deleting the key renders that tenant's data permanently
        unrecoverable EVERYWHERE, including in immutable backups. Often
        the only practical way to honour a deletion request."""
        self._wrapped.pop(tenant, None)


# --- SPLIT KNOWLEDGE for escrow: Shamir 3-of-5 ----------------------
# pip install pyshamir
#
#   from pyshamir import split, combine
#   shares = split(master_key, parts=5, threshold=3)
#   # Distribute to five custodians in separate locations.
#   # Any 3 reconstruct the key; any 2 learn nothing about it.
#   recovered = combine(shares[:3])
#
# This is how HSM master keys and cryptocurrency cold storage are
# genuinely administered: no single person can act alone.


# --- Secret scanning: catch the most common failure before it ships --
# gitleaks detect --source . --verbose
# trufflehog git file://. --only-verified
# git secrets --scan-history
#
# And rotate anything that was ever committed -- git history is forever,
# and removing the commit does not un-leak the key.

Stage	Control	Common failure
Generation	CSPRNG, HSM, correct strength	Weak entropy at early boot
Distribution	Secrets manager, short-lived tokens	Keys in CI logs, Slack, Git
Storage	Encrypted at rest, access-audited	Hardcoded in source
Use	Minimal memory lifetime, no logging	Keys in crash and heap dumps
Rotation	Key IDs in ciphertext, overlap window	No rotation designed in
Archival	Retain while data must be readable	Destroyed too early; data loss
Destruction	Verified deletion of all copies	Copy left in a snapshot

Key Takeaways

• Algorithms almost never fail; key management fails constantly, and each lifecycle stage has a distinct failure mode.
• Envelope encryption with a master key, KEKs, and per-object DEKs is the standard design and makes rotation cheap.
• Embed a key identifier in the ciphertext so rotation can proceed with an overlap window instead of downtime.
• Rotation requires a transition period where the old key still verifies and decrypts but only the new key signs and encrypts.
• Archival and destruction are in tension: destroying a key that still protects needed backups is unrecoverable data loss.
• Per-tenant keys enable crypto-shredding, which is often the only practical way to honour deletion against immutable backups.
• Escrow is appropriate for data-at-rest keys where availability matters, and inappropriate for signing keys and session keys.
• Use split knowledge (Shamir M-of-N) so no single custodian can act alone, and run secret scanning to catch the most common failure of all.

🧪 Practice

1. Implement envelope encryption with a key ID in the ciphertext, rotate the master key, and confirm that objects encrypted under both versions remain decryptable.
2. Design a rotation plan for an HMAC key used to sign API tokens with a 30-day validity. State exactly when the old key may be destroyed and why.
3. Run a secret scanner over a repository's full history and triage any findings. For each one, write the remediation including rotation, not just removal.
4. Interview-style: "How would you honour a GDPR deletion request for data that exists in immutable backups?" Hint: you cannot modify the backups — think about what you can delete that makes the data unreadable, and what the encryption architecture must look like beforehand for that option to exist.

Hardware Security Modules and TPMs

Theory

Every software key-protection scheme shares one weakness: at some point the key exists in memory, where it can be read by a sufficiently privileged attacker, dumped in a crash, swapped to disk, or extracted by a vulnerability like Heartbleed. Hardware security modules remove that weakness by ensuring the key never exists outside dedicated hardware.

The operating principle is non-extractability: the key is generated inside the device and cannot be exported, by anyone, including administrators. You do not retrieve the key to use it. You send the device data and an instruction, and it returns the result of the cryptographic operation. The key never crosses the boundary.

This changes the consequence of a server compromise fundamentally. An attacker with root on a server holding a software key copies the key and can then use it forever, anywhere, undetectably. An attacker with root on a server using an HSM can request operations while they retain access, which is bad but bounded, logged, rate-limitable, and ends when the access ends.

The main device categories:

Device	Form	Typical use	Scale
HSM	Network appliance or PCIe card	CA roots, payment processing, code signing	Thousands of ops/sec
TPM	Chip soldered to a motherboard	Platform integrity, disk encryption, device identity	One per machine
Secure Enclave / TrustZone	Co-processor in a phone or laptop SoC	Biometrics, device keys, payment tokens	One per device
Smart card / YubiKey	Removable token	User authentication, SSH, code signing	One per user
Cloud HSM / KMS	Managed service	Envelope encryption, general key management	Elastic

TPMs deserve separate explanation because their main job is different. A TPM provides key storage, but its distinctive capability is measured boot: as the machine boots, each stage hashes the next and extends that measurement into a Platform Configuration Register (PCR). PCRs can only be extended, never set, so the final values are a tamper-evident fingerprint of exactly what software booted. Two things follow:

• Sealing. A key can be sealed to specific PCR values, so it is only released if the machine booted the expected software. This is how BitLocker unlocks a disk without a password and still resists an attacker who boots a different OS to read it.
• Remote attestation. The TPM signs its PCR values with a device-unique key, so a remote server can verify what the client actually booted before granting access.

FIPS 140-2/140-3 certification levels describe physical protection: Level 2 adds tamper-evidence, Level 3 adds tamper-response (the device zeroizes its keys when opened), and Level 4 adds protection against environmental attacks. Many regulated contexts mandate Level 3.

The practical trade-offs are real. HSMs are expensive, slower per operation than software (an HSM might do thousands of RSA signatures per second where software does tens of thousands), add operational complexity, and create a hard availability dependency — if the HSM is unreachable, you cannot sign or decrypt anything. They also require careful backup planning, since a non-extractable key cannot be backed up conventionally; the standard answer is a cloned HSM or an M-of-N split backup under the device's own wrapping key.

The sensible posture for most organizations is to use a cloud KMS for general key management, since it provides HSM-backed keys without the appliance operations, and reserve dedicated HSMs for the cases that genuinely require them: CA roots, code-signing keys, payment HSMs where the card schemes mandate it, and any key whose compromise would be unrecoverable.

Examples

SOFTWARE KEY vs HSM KEY -- what a root compromise means

  SOFTWARE KEY                        HSM KEY
  ┌──────────────────────┐            ┌──────────────────────┐
  │ key in process memory│            │ app sends DATA       │
  │ key on disk          │            │ HSM returns RESULT   │
  │ key in crash dumps   │            │ key NEVER leaves     │
  │ key in swap          │            │ the hardware         │
  └──────────────────────┘            └──────────────────────┘
  attacker with root:                 attacker with root:
    COPIES the key                      can request operations
    uses it forever, anywhere,          ONLY while access lasts;
    undetectably                        logged, rate-limitable,
                                        ends with the access

TPM MEASURED BOOT -- PCRs are extend-only

  UEFI firmware ──hash──► extend PCR0
       │
  bootloader ────hash──► extend PCR4
       │
  kernel ────────hash──► extend PCR9
       │
  final PCR values = a fingerprint of EXACTLY what booted

  PCR extend:  PCR_new = hash(PCR_old || measurement)
               cannot be set directly, cannot be rewound
               => tamper-evident by construction

  SEALING: release the disk key only if PCRs match the expected values
    boot the expected OS   ──► PCRs match ──► key released ──► disk unlocks
    attacker boots a live USB ──► PCRs differ ──► key NEVER released

  REMOTE ATTESTATION: the TPM signs its PCRs so a server can verify
  what the client booted before granting network access.

FIPS 140-3 LEVELS
  L1  software, approved algorithms
  L2  tamper-EVIDENCE (you can see it was opened)
  L3  tamper-RESPONSE (opening ZEROIZES the keys)   <- commonly mandated
  L4  environmental attack resistance (voltage, temperature)

# --- PKCS#11: the standard HSM/token API ----------------------------
# pip install python-pkcs11
import pkcs11
from pkcs11 import KeyType, Mechanism, ObjectClass

lib = pkcs11.lib("/usr/lib/softhsm/libsofthsm2.so")   # SoftHSM for testing
token = lib.get_token(token_label="my-token")

with token.open(user_pin="1234") as session:
    # Generate the key INSIDE the device. `store=True` makes it persistent;
    # the private key object has no exportable value at all.
    public, private = session.generate_keypair(
        KeyType.RSA, 2048, store=True, label="signing-key")

    # Sign by sending data to the device. The key does not come back.
    signature = private.sign(b"firmware-v4.2.1", mechanism=Mechanism.SHA256_RSA_PKCS)
    print(f"signature: {len(signature)} bytes, key never left the HSM")

    # Attempting to read the private key's value fails by design.
    try:
        _ = private[pkcs11.Attribute.PRIVATE_EXPONENT]
    except pkcs11.AttributeSensitive:
        print("private exponent is SENSITIVE -- non-extractable, as intended")


# --- TPM 2.0 via tpm2-tools -----------------------------------------
TPM_COMMANDS = r"""
# Read the PCRs: a fingerprint of exactly what booted
tpm2_pcrread sha256:0,1,2,3,4,5,6,7

# Create a primary key in the TPM's owner hierarchy
tpm2_createprimary -C o -g sha256 -G rsa -c primary.ctx

# Create a signing key under it; the private portion stays in the TPM
tpm2_create -C primary.ctx -G rsa -u key.pub -r key.priv
tpm2_load -C primary.ctx -u key.pub -r key.priv -c key.ctx
tpm2_sign -c key.ctx -g sha256 -o sig.bin message.txt

# SEAL a secret to the current boot state: it is released only if the
# PCRs match, so booting different software makes it unrecoverable.
tpm2_createpolicy --policy-pcr -l sha256:0,2,4,7 -L policy.dat
tpm2_create -C primary.ctx -L policy.dat -i secret.txt \
            -u seal.pub -r seal.priv

# Inspect what BitLocker/LUKS binds to:
#   systemd-cryptenrol --tpm2-device=auto --tpm2-pcrs=0+2+4+7 /dev/sda2
"""


# --- Cloud KMS: HSM-backed keys without appliance operations --------
CLOUD_EXAMPLES = r"""
# AWS KMS -- the key material never leaves the service
aws kms create-key --key-usage SIGN_VERIFY --key-spec RSA_2048 \
    --origin AWS_CLOUDHSM
aws kms sign --key-id alias/signing --message fileb://doc.bin \
    --signing-algorithm RSASSA_PSS_SHA_256

# Envelope encryption: KMS wraps the DEK, your app encrypts the data
aws kms generate-data-key --key-id alias/app --key-spec AES_256
# -> returns {Plaintext: <use then discard>, CiphertextBlob: <store this>}

# GCP
gcloud kms keys create signing --keyring=prod --purpose=asymmetric-signing \
    --default-algorithm=rsa-sign-pss-2048-sha256 --protection-level=hsm

# Azure
az keyvault key create --vault-name prod --name signing --kty RSA-HSM
"""

# --- Choosing the right tool ----------------------------------------
GUIDANCE = {
    "CA root key": "dedicated HSM, FIPS 140-3 Level 3, offline",
    "code signing": "HSM or hardware token; mandated by most ecosystems",
    "payment processing": "payment HSM; required by PCI and card schemes",
    "general app keys": "cloud KMS -- HSM-backed without the operations",
    "disk encryption": "TPM with PCR sealing",
    "device identity": "TPM or Secure Enclave",
    "SSH and user auth": "YubiKey or smart card",
    "development and test": "SoftHSM -- same PKCS#11 API, no hardware",
}
for use, tool in GUIDANCE.items():
    print(f"{use:>22}: {tool}")

Key Takeaways

• An HSM's defining property is non-extractability: keys are generated inside and cannot be exported, so operations are requested rather than keys retrieved.
• This bounds a server compromise — the attacker can use the key only while they hold access, and every use is logged and rate-limitable.
• TPMs add measured boot: extend-only PCRs fingerprint exactly what software booted, enabling sealing and remote attestation.
• Sealing releases a key only when the PCRs match, which is how full-disk encryption resists an attacker booting different software.
• FIPS 140-3 Level 3 adds tamper response (keys are zeroized on physical intrusion) and is commonly mandated in regulated contexts.
• The real costs are expense, per-operation latency, operational complexity, and a hard availability dependency.
• Non-extractable keys cannot be backed up conventionally; plan for cloned devices or M-of-N split backups from the start.
• Use a cloud KMS for general key management and reserve dedicated HSMs for CA roots, code signing, payment, and other unrecoverable-compromise cases.

🧪 Practice

1. Install SoftHSM, generate a key pair through PKCS#11, sign data with it, and confirm that reading the private exponent fails. Explain what production detail SoftHSM does not reproduce.
2. Read your machine's PCR values with tpm2_pcrread, record them, then change a boot setting and read them again. Explain what the difference means for a sealed key.
3. Compare signing throughput between a software RSA-2048 key and a cloud KMS key, and describe how the latency difference would shape the architecture of a high-volume signing service.
4. Interview-style: "Our code-signing key is in a file on a build server. Convince management to fund an HSM." Hint: frame it around what an attacker who compromises the build server can do with a copied key versus a non-extractable one — specifically, how long the forgery capability lasts and whether you would even be able to tell it had been used.

---

<a id="4-program-analysis"></a>