RSA Padding Oracles: From a Validity Bit to Lost Secrecy

Most cryptographic attacks that make headlines break something. The padding oracle breaks nothing. It needs no factoring, no weakness in the key, no flaw in the mathematics of RSA. It needs only a receiver that, after decrypting an attacker-supplied ciphertext, behaves slightly differently depending on whether the result looked well formed. That difference, a distinct error message, a different alert, a slower response, a dropped connection, is one bit of information about a secret number. Daniel Bleichenbacher showed in 1998 that an attacker who can ask that one-bit question enough times, about cleverly chosen variants of a captured ciphertext, can recover the hidden plaintext completely. Twenty years later, researchers presenting the ROBOT study found the same leak alive in widely deployed systems. This article explains why a single validity bit is enough, why the leak is so hard to remove from implementations, and why the most reliable defences remove the question rather than try to hide its answer. It also argues that AI agent platforms create a fresh version of the problem: systems in which an automated, tireless client can be steered into asking the question on an attacker's behalf.

A one-bit question about a secret

RSA encrypts by raising a message representative to a public exponent on the clock of a public modulus. Because the bare operation is deterministic and malleable, real systems first wrap the message in padding. The encryption padding in PKCS #1 version 1.5, specified today in RFC 8017, lays out the block as a zero byte, a byte with value two, at least eight nonzero random bytes, a zero byte as a separator, and then the message. A receiver who decrypts must check this structure before using the message.

That check is where the oracle lives. An oracle, in cryptographic terms, is any mechanism that answers a question the asker could not otherwise answer. Here the question is whether a particular ciphertext decrypts to a block that begins with the bytes zero and two and, depending on the implementation, satisfies the remaining structural rules. The answer reveals something about the hidden number: a block that begins with zero and two lies in a known, narrow band of all possible values on the modulus clock, roughly the band between two and three times a fixed power of two set by the key length.

One such answer on its own reveals very little. The power of the attack comes from asking the question about many related ciphertexts, each chosen so that the answer constrains the original secret a little further. The next section explains how an attacker can manufacture those related questions without knowing the private key.

Malleability turns one ciphertext into many questions

Textbook RSA has a multiplicative property: multiplying a ciphertext by the encryption of a chosen number produces a valid ciphertext whose plaintext is the original plaintext multiplied by that number, on the same clock. An attacker who has captured a target ciphertext can therefore create unlimited variants, each corresponding to the unknown plaintext scaled by a factor of the attacker's choosing, using only the public key.

Each variant is submitted to the receiver. If the receiver signals that the variant decrypted to correctly formatted padding, the attacker learns that the scaled plaintext, for that particular multiplier, fell inside the narrow band that begins with the bytes zero and two. Because the attacker knows the multiplier, that fact translates into a constraint on the original plaintext itself: it must lie in one of a small set of intervals.

The attack is adaptive. Successful multipliers guide the choice of the next ones, so that later queries are spent where they narrow the remaining intervals fastest. This is a chosen-ciphertext attack in the precise sense: the adversary chooses inputs to the decryption operation and learns from the responses, which is exactly the capability that chosen-ciphertext security definitions try to neutralise. The countermeasures listed here are the ones that remove the attacker's ability to learn from those responses.

How answers narrow the secret

Conceptually, the attacker maintains a description of every plaintext still consistent with all answers so far, a set of intervals on the modulus clock. Initially this set is the single narrow band of conforming blocks, since the target itself was a valid encryption. Each accepted query intersects the set with the band implied by that query's multiplier, and the remaining intervals shrink. Once a single interval remains, the attacker can choose multipliers that roughly halve it with each further success, and the process ends when the interval contains exactly one integer, which is the padded plaintext.

The number of queries depends heavily on how strict the receiver's check is. A receiver that accepts any block beginning with zero and two answers yes more often, so the attacker learns faster; a receiver that also checks the separator position, the minimum padding length and the expected message length answers yes less often, so each success is rarer but carries more information. Bleichenbacher's original analysis described the attack as requiring on the order of a million queries against typical implementations, which is why it is often called the million-message attack. Later work refined the strategy and showed that the required number varies widely with oracle strictness; this article treats those figures as orders of magnitude rather than constants.

The defensive reading of this is uncomfortable. Making the check stricter does not remove the oracle; it changes its rate. Only making the answers indistinguishable, or removing the decryption operation from the attacker's reach, closes it.

What counts as an answer

Implementers often believe they have closed the oracle once error messages are unified. The historical record shows how many other channels can carry the same bit. Böck, Somorovsky and Young's 2018 ROBOT study scanned widely used Transport Layer Security (TLS) deployments and found vulnerable implementations from a number of vendors, with the bit leaking through channels that included different alert messages, a connection being closed or reset rather than continued, and a server waiting for a timeout in one case but not the other. The leak had survived nineteen years of awareness because each of these behaviours looked like a harmless implementation detail.

Timing deserves particular mention. A receiver that returns the same message for every failure but takes measurably longer to reach it on one path still answers the question, as Kocher's 1996 work on timing attacks first showed for private-key operations in general. Timing oracles are noisier, so they cost more queries, but noise can be averaged away given enough samples, and an attacker positioned close to the target on a network can measure surprisingly small differences.

The practical conclusion is that the oracle is a property of the entire receiving system, including the protocol state machine, the network stack, logging and error-handling code, not of a single function. Reviewing the decryption routine alone is not enough.

Why OAEP helps, and where it does not

Optimal Asymmetric Encryption Padding (OAEP), recommended by RFC 8017 for new applications, replaces the simple byte layout with two rounds of masking driven by a random seed and a hash-based mask generation function. Its design gives a security proof against chosen-ciphertext attacks in the random oracle model: informally, an attacker who submits modified ciphertexts learns nothing useful from a receiver that answers only accept or reject, because tampered inputs almost never decode to a valid structure.

The proof's scope is the key point. It assumes the receiver's only output is the decryption result or a single failure indication. In 2001 James Manger showed that an OAEP implementation which reveals whether the first byte of the decrypted block was zero, before completing the remaining checks, again provides an oracle, and one that can recover plaintexts with far fewer queries than Bleichenbacher's attack on version 1.5. RFC 8017 consequently warns that implementations must not let an attacker distinguish the different error conditions.

OAEP is therefore a substantial improvement, not a cure. It reduces how often malformed inputs can be confused with valid ones and gives a precise target for implementation correctness. Uniform, constant-time failure behaviour is still required.

Defences that remove the question

Three families of defence exist, in increasing order of reliability. The first is to hide the answer: return identical errors with identical timing on every failure path. This is necessary but fragile, because every new code path, logging change or protocol behaviour can reintroduce a distinction, as the ROBOT findings illustrate.

The second is implicit rejection. Instead of signalling a failure at all, the receiver substitutes an unpredictable value for the decrypted message and continues as if decryption had succeeded. TLS version 1.2, in RFC 5246, prescribes this for RSA key transport: on any padding error the server generates a random premaster secret and proceeds, so the handshake fails later, at a point that does not depend on the padding. Done correctly, the attacker's question receives no distinguishable answer.

The third and most reliable is to remove the operation. TLS version 1.3, RFC 8446, dropped RSA key transport entirely, so a server never decrypts attacker-supplied RSA ciphertexts during a handshake. Where key transport is needed elsewhere, OAEP with a hardened implementation, or a key-encapsulation design that avoids decrypting arbitrary inputs, achieves the same effect. In this article's assessment, any system that can be redesigned to stop decrypting attacker-chosen RSA ciphertexts should be, because the other defences require every future change to preserve a subtle invariant.

A new exposure: AI agent platforms

Padding oracles were historically a server problem reached over a network protocol. AI agent platforms create a different topology, which this article treats as an emerging exposure rather than a documented incident class. Agents are frequently given tools that unwrap keys, decrypt tokens or open protected payloads: a key-management tool, a JSON Web Encryption (JWE) token handler, a document decryption service. JSON Web Algorithms, RFC 7518, still defines the RSA1_5 key-management algorithm alongside RSA-OAEP, and marks RSA1_5 as not recommended for exactly these reasons.

Two properties of agents matter. First, an agent is an automated client that will repeat an operation many times and relay results faithfully, which removes the human-scale friction that once made a million queries impractical. Second, an agent whose instructions can be influenced by untrusted content, through prompt injection in a document, a web page or a tool result, can be steered into submitting attacker-chosen inputs to an internal tool and reporting whether each one succeeded. The attacker never touches the decryption service directly; the agent crosses the trust boundary on the attacker's behalf.

The defensive implications follow from the earlier sections. Internal decrypt and unwrap tools should not exist in a form that accepts arbitrary ciphertexts from agents. Where they must exist, they should use OAEP or a key-encapsulation design, implement implicit rejection, return a single opaque result to the agent, and be rate-limited per agent identity with alerts on repeated failures.

Testing your own systems, and limitations

Because the oracle is a whole-system property, the only convincing evidence of its absence is a conformance test against the deployed system, run by its owners in a test environment. The method is defensive and does not require implementing any recovery algorithm: generate several classes of deliberately malformed ciphertexts under a test key, submit each class many times, record every observable output and its timing, and confirm statistically that the classes cannot be told apart from each other or from a valid ciphertext that fails later in the protocol. Any distinguishable class is a defect, whether or not anyone has exploited it.

This article's analysis has limits. It describes mechanisms and defences conceptually and deliberately omits the step-by-step recovery procedure. Query counts are given as orders of magnitude because they depend strongly on oracle strictness and noise. The agent-platform exposure is presented as a reasoned extrapolation from the known mechanism and the documented susceptibility of agents to injected instructions, not as a measured incident. Finally, timing-based variants continue to be reported against implementations that were believed to be fixed, which is itself the strongest argument for removing RSA decryption of attacker-chosen inputs wherever possible.

SETUP  test deployment with a test-only RSA key; no production keys
CLASSES valid_but_fails_later, bad_leading_bytes, bad_separator,
        short_padding, wrong_length
FOR each class:
    repeat N times:
        input  = make_sample(class, test_public_key)   # malformed by construction
        record response_body, status, alert, connection_state, latency
COMPARE all classes pairwise:
    any difference in body, status, alert or connection_state -> DEFECT
    latency distributions differ beyond threshold          -> DEFECT
REPORT  pass only if every class is indistinguishable

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

tool: unwrap_key
  allowed_algorithms: [RSA-OAEP-256]
  denied_algorithms:  [RSA1_5, RSA-OAEP-without-uniform-errors]
  accepts_inputs_from: [server_generated_envelopes_only]
  result_to_agent: opaque_handle   # never the reason for failure
  on_failure: implicit_rejection
  rate_limit: { per_agent: 20_per_hour, alert_after_failures: 3 }
  approval_required_if: request_originates_from_untrusted_content

for cls in [valid_fails_later, bad_prefix, bad_separator, short_pad, wrong_len]:
    obs[cls] = [observe(submit(sample(cls))) for _ in range(N)]
assert all_equal(fields(obs, ['body','status','alert','conn_state']))
assert latency_indistinguishable(obs, threshold=T)
report('PASS' if no_defects else 'DEFECT: ' + list_differences(obs))

Glossary

Padding oracle

Any mechanism by which a receiver reveals whether decrypted data had valid padding.

PKCS #1 version 1.5 encryption

An RSA encryption padding that places zero and two bytes, random nonzero bytes and a separator before the message.

Malleability

The property that ciphertexts can be transformed into valid ciphertexts of related plaintexts without the key.

Chosen-ciphertext attack

An attack in which the adversary submits chosen ciphertexts for decryption and learns from the results.

Implicit rejection

Handling a decryption failure by substituting an unpredictable value and continuing, so no failure is signalled.

OAEP

Optimal Asymmetric Encryption Padding, a randomised RSA padding with a chosen-ciphertext security proof in the random oracle model.

Timing oracle

A padding oracle whose signal is a difference in processing time rather than in content.

Prompt injection

Instructions hidden in content an AI agent processes, causing it to act on behalf of whoever wrote them.

References

1. D. Bleichenbacher, Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1, CRYPTO 1998
2. H. Böck, J. Somorovsky, C. Young, Return Of Bleichenbacher's Oracle Threat (ROBOT), USENIX Security 2018
3. J. Manger, A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0, CRYPTO 2001
4. RFC 8017: PKCS #1: RSA Cryptography Specifications Version 2.2 (IETF)
5. RFC 5246: The Transport Layer Security (TLS) Protocol Version 1.2 (IETF)
6. RFC 8446: The Transport Layer Security (TLS) Protocol Version 1.3 (IETF)
7. RFC 7518: JSON Web Algorithms (JWA) (IETF)
8. P. C. Kocher, Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, CRYPTO 1996