A bleichenbacher attack recovers the plaintext behind an RSA ciphertext without ever holding the private key, using a server that quietly reveals whether a decrypted message had valid PKCS#1 v1.5 padding. The attacker never factors the modulus. They send thousands of slightly altered ciphertexts, read one yes or no answer each time, and let that answer narrow the hidden message down to a single value. Daniel Bleichenbacher published this in 1998, and the same oracle keeps returning in modern TLS stacks. This post walks the padding, the oracle, the math, and the fix.
What a bleichenbacher attack actually is
A bleichenbacher attack is an adaptive chosen ciphertext attack on RSA with PKCS#1 v1.5 encryption padding. RSA is not broken here. The modulus is never factored and the private exponent never leaks. The target is a small piece of behavior wrapped around the cipher: the step that checks whether the recovered bytes are formatted correctly and reacts differently when they are not. That difference is the oracle, and one fact about RSA turns it into a decryption machine.
RSA encryption is c = m^e mod N and decryption is m = c^d mod N. The property the attack rides on is that RSA is multiplicative. If you multiply a ciphertext by another number raised to the public exponent, the decrypted plaintext is multiplied by that same number:
(c * s^e)^d = m * s mod N
So an attacker who does not know m can still produce a ciphertext whose plaintext is m times any chosen value s. They steer the hidden plaintext by multiplication, then ask the oracle what the result looked like.
The padding that becomes a leak
PKCS#1 v1.5 encryption wraps the real message in a fixed structure the width of the modulus. For a key whose modulus is k bytes, an encryption block looks like this before it is raised to the public exponent:
00 02 [ at least 8 random nonzero bytes ] 00 [ message ]
The first two bytes are always 00 02. A message that starts with those two bytes after decryption is called conforming. The receiver checks for them, strips the random padding up to the 00 separator, and keeps the rest. If the first two bytes are wrong, the receiver knows the block was malformed and reacts, often with an error, sometimes with a timing difference, sometimes with a dropped connection. Any observable difference between conforming and not conforming is the oracle.
In TLS that used RSA key exchange, the client encrypts a premaster secret with the server’s RSA public key and sends it over. The server decrypts it with PKCS#1 v1.5 and proceeds. A server that behaves differently when the padding is wrong hands the attacker exactly the signal the attack needs, once per request, as often as they care to ask.
Turning one bit into the whole plaintext
Here is the idea without the full bookkeeping. Define B = 2^(8*(k-2)), which is the place value of that second byte. A conforming message, one that begins with 00 02, always sits in a known range:
2B <= m < 3B
The attacker picks a multiplier s, builds c' = c * s^e mod N, and submits it. When the oracle says conforming, they have learned that m * s mod N also sits between 2B and 3B. That single inequality rules out a slice of possible values for m. The attacker keeps choosing new values of s, each conforming answer adds another constraint, and the set of possible plaintexts shrinks. Bleichenbacher’s method chooses those multipliers so the remaining interval roughly halves each round, and it closes in on the one true m.
The key never leaked and the modulus was never factored. The server simply answered, a million times, one question it believed was harmless: did this decrypt to something that starts with the right two bytes?
The original attack needed on the order of a million queries, which is why people still call it the million message attack. Later refinements cut the count sharply by picking smarter multipliers, but the shape is unchanged: adaptive queries, one bit of padding feedback each, a hidden plaintext squeezed to a point. For an invented billing service, call it Acme Invoicing, that decrypts an RSA protected token and returns a clean error on bad padding, a patient loop recovers the token contents. This is the same structural flaw as a padding oracle attack on CBC, moved to the asymmetric side: a formatting check on attacker controlled bytes whose result is allowed to escape.
The modern resurrection in TLS
This is not a closed chapter from 1998. In 2016 and 2017 researchers found that many live TLS servers still carried a bleichenbacher attack oracle in their RSA key exchange. One line of work abused the ancient SSLv2 protocol as a decryption oracle against recorded modern traffic that shared an RSA key. Another, named the Return Of Bleichenbacher’s Oracle Threat, showed that a long list of mainstream implementations leaked the conforming signal through small differences in how they handled malformed key exchange records, such as different alert messages on padding failure versus other failures. The lesson repeated each time: an oracle does not need an explicit error string. A status code, an alert type, or a timing gap is the same bit by another name.
The fix: remove the padding, make responses uniform
The clean fix is to stop using RSA PKCS#1 v1.5 for key transport at all. Modern TLS prefers forward secret key exchange with ephemeral Diffie Hellman, and TLS 1.3 removed RSA key transport from the protocol entirely, which deletes the oracle’s target outright. If you are encrypting data with RSA directly, use RSA OAEP, a padding scheme designed so that malformed ciphertext cannot be distinguished in a way that helps an attacker.
Where legacy RSA key exchange cannot be removed yet, the defense is to make the response identical whether padding is valid or not. The standard countermeasure generates a random premaster secret before looking at the padding, and on any padding failure continues the handshake with that random value. The handshake then fails later at MAC verification in exactly the same way a wrong key would, so the attacker sees one uniform failure and gets no bit back. This decision must not branch on the padding result in any way the attacker can measure, timing included.
- Drop RSA PKCS#1 v1.5 key exchange in favor of ephemeral Diffie Hellman, and adopt TLS 1.3.
- Use RSA OAEP, never v1.5, for any new RSA encryption.
- If v1.5 decryption must stay, respond uniformly, generating a random secret on failure and branching on nothing the attacker can measure.
- Treat every error, alert, status code, and timing difference as attacker visible.
For the wider family this belongs to, see our hub on cryptographic oracle attacks, and for how a close cousin abuses loose verification rather than decryption, read about rsa signature forgery. If you are new to how these classes are grouped, start with vulnerability basics.
The assumption that breaks
Strip away the modular arithmetic and one assumption holds the whole thing up. The server assumes that telling a client whether a message was formatted correctly gives nothing away. It feels harmless, the way a clear error for a malformed request feels like good manners. But that single bit, asked enough times against ciphertext the attacker multiplies at will, is a full decryption oracle. You find this by asking, of every response a system gives, what it tells someone asking ten thousand times on purpose. That is what an autonomous researcher built to test assumptions does: reason about how an app uses a primitive and whether a secret dependent response leaks. Read more on our about page.
Frequently asked questions
What is a Bleichenbacher attack in simple terms?
It is a way to recover the plaintext behind an RSA ciphertext without the private key. The attacker sends many altered ciphertexts and watches whether the server says each one decrypted to a message with valid PKCS#1 v1.5 padding. Each yes or no answer narrows the hidden message, and after enough queries the plaintext is fully recovered. The key is never factored; only the padding check leaks.
Why does multiplying the ciphertext help the attacker?
RSA is multiplicative. If you multiply a ciphertext by a chosen value raised to the public exponent, the decrypted plaintext is multiplied by that same value, shown by (c * s^e)^d = m * s mod N. The attacker cannot read the plaintext, but they can steer it by choosing the multiplier, then ask the padding oracle what the steered result looked like.
Is the Bleichenbacher attack still relevant in modern TLS?
Yes. In 2016 and 2017 researchers found that many live TLS servers still carried the same oracle in their RSA key exchange, leaking the padding signal through small differences in alerts or timing. TLS 1.3 removed RSA key transport entirely, which is the cleanest defense. The MITRE entry CWE-208, observable timing discrepancy covers one way the signal escapes.
How do you prevent a Bleichenbacher attack?
Stop using RSA PKCS#1 v1.5 for key transport and move to ephemeral Diffie Hellman and TLS 1.3, which deletes the target. For direct RSA encryption use RSA OAEP instead of v1.5. If v1.5 decryption must stay, make the response uniform by generating a random secret on padding failure and continuing, so the attacker sees one identical failure no matter what and gets no bit back.
Put an autonomous researcher on your own systems
UnboundCompute is an autonomous security researcher that reasons about how an application fits together and proves the access control and injection bugs it finds. We are opening a small number of founding design partner seats: private early access pointed at a staging target you choose, and a say in what it looks for. If your team ships software worth pressure testing, apply to the design partner program.