# Bleichenbacher's 1998 Attack on RSA-PKCS#1 v1.5 **Source**: https://quantumsequrity.com/blog/bleichenbacher-attack-1998 **Category**: Threats & Attacks --- [← Back to Blog](../../blog.html) Threats & Attacks # Bleichenbacher's 1998 Attack on RSA-PKCS#1 v1.5 12 min read In 1998, a Swiss cryptographer named Daniel Bleichenbacher published a paper that demonstrated a flaw in one of the most widely deployed encryption schemes on the Internet. The paper, "Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1," presented at CRYPTO 1998, showed that an attacker who could submit RSA-encrypted messages to a server and learn whether the decrypted plaintext had valid PKCS#1 v1.5 padding could decrypt arbitrary RSA ciphertexts. The attack required roughly one million queries to recover a single plaintext. That number sounds large until you realize the scale of the systems involved. SSL servers in 1998 routinely handled millions of connections per day. An attacker who could trigger SSL handshakes against a target server could perform the attack in hours. The disclosure forced a wave of patches across the SSL ecosystem and led to the eventual deprecation of PKCS#1 v1.5 padding for new deployments in favor of OAEP. The attack itself, the implementations of it, and its 2017 revival as ROBOT are essential parts of the history of practical cryptanalysis. Understanding what Bleichenbacher did and why it worked clarifies why modern post-quantum schemes like ML-KEM are designed with implicit rejection and why protocols like TLS 1.3 have removed RSA key exchange entirely. ## What PKCS#1 v1.5 Padding Looks Like The PKCS#1 v1.5 padding format was specified by RSA Laboratories in the late 1980s and standardized as part of PKCS #1 version 1.5 in 1993. To encrypt a message m of length k bytes using a public key of length n bytes, you first format the message into a padded block of length n bytes: The first byte is 0x00. The second byte is 0x02 to indicate encryption padding. The next bytes are random non-zero padding, padded out to fill the block leaving room for an 0x00 separator and the message itself. The 0x00 separator follows the random bytes. Then the message m fills the rest of the block. The receiver decrypts using the RSA private key, then checks the padding. They verify that the first byte is 0x00, the second byte is 0x02, that there are at least eight random bytes before the 0x00 separator, and that the separator is present. If all checks pass, the receiver extracts m. If any check fails, the receiver rejects the message. The vulnerability lies in what happens when validation fails. If the receiver returns an error that distinguishes "padding invalid" from "other failure," they create a padding oracle. The attacker can use this oracle to recover plaintexts. ## How the Attack Works Bleichenbacher's attack exploits the multiplicative property of RSA. If you have a ciphertext c that decrypts to m, you can compute c' = c times s^e modulo n, where s is any integer and e is the public exponent. The new ciphertext c' decrypts to m times s modulo n. By choosing s carefully, the attacker can force m times s modulo n to fall within specific ranges that produce valid PKCS#1 v1.5 padding. The attack proceeds in stages. The attacker starts with a target ciphertext c and an oracle that returns yes or no on padding validity. They want to learn the original plaintext m. In the first stage, the attacker searches for an s value such that c times s^e modulo n decrypts to a plaintext with valid PKCS#1 v1.5 padding. This requires that the plaintext starts with 0x00 0x02. The probability that a random plaintext satisfies this is roughly 2 in 2^16, so on average the search takes about 30,000 queries to find the first valid s. Once the attacker has found a valid s, they know that m times s modulo n falls within the range [2B, 3B), where B = 2^(8*(k-2)). This range tells them something about m. Specifically, m falls within an interval that the attacker can compute. The subsequent stages narrow the interval. The attacker chooses successive s values that, conditional on previous information, are likely to produce valid padding. Each successful query halves the size of the interval containing m. After enough iterations, the interval contains exactly one possible value of m, and the attacker has recovered the plaintext. The 1998 paper estimated that recovering a 1024-bit RSA plaintext took roughly one million oracle queries. Subsequent optimizations by other researchers reduced this to several hundred thousand or even tens of thousands in optimized variants. ## What the Oracle Looked Like in Practice In the original 1998 attack, the oracle was the SSL handshake itself. The SSL 3.0 protocol used RSA-PKCS#1 v1.5 to encrypt the pre-master secret during the handshake. A server that received a malformed pre-master secret would send a different handshake error than a server that received a well-formed pre-master secret that subsequently failed verification. This binary distinction was sufficient. Patches to SSL servers attempted to make the error response uniform regardless of padding validity. The general approach was to always proceed with the handshake using a pseudo-random pre-master secret derived deterministically from the ciphertext, so the server's behavior was identical whether the padding was valid or not. Any difference in subsequent processing was hidden behind the symmetric cipher's authenticity check. This approach worked for explicit error responses but did not eliminate timing oracles. A naive implementation that performed PKCS#1 padding validation, then derived the pseudo-random fallback only on failure, took different amounts of time for valid and invalid padding. Sophisticated implementations had to perform both code paths in constant time and select the result without branching. ## The 2017 ROBOT Attack In 2017, Hanno Böck, Juraj Somorovsky, and Craig Young published the ROBOT attack: Return Of Bleichenbacher's Oracle Threat. The paper, presented at USENIX Security 2018, scanned thousands of high-traffic HTTPS websites and found that 27 of the Alexa top 100 were vulnerable to Bleichenbacher-style attacks. The vulnerable list included major financial institutions, government services, and well-known commercial websites. The vulnerabilities came from several sources. Some servers had subtle timing differences between valid and invalid padding paths. Some had explicit error code distinctions in obscure failure cases. Some had hardware accelerators that took different times for different inputs. Some servers had been patched for the original Bleichenbacher attack but had introduced new oracles in subsequent code changes. The fix was to disable RSA key exchange entirely. RSA in TLS had been deprecated for more than a decade in favor of forward-secret key exchanges like ECDHE, but many servers retained RSA support for backward compatibility. ROBOT highlighted the cost of that compatibility. The findings were assigned multiple CVEs including CVE-2017-12373 and CVE-2017-13099. The latter, also known as the "ROBOT attack" CVE, was assigned to BearSSL's specific timing variant. ## Why OAEP Replaced PKCS#1 v1.5 Optimal Asymmetric Encryption Padding, OAEP, was published by Mihir Bellare and Phillip Rogaway in 1994. PKCS #1 version 2.0, published in 1998 in response to Bleichenbacher's attack, included OAEP as the recommended padding. RSA-OAEP is provably IND-CCA2 secure under the assumption that RSA itself is hard, in the random oracle model. OAEP works fundamentally differently from PKCS#1 v1.5. Instead of constructing a padded block with explicit byte structure, OAEP uses two cryptographic hash functions to produce a randomized encoding of the message. The ciphertext does not have a recognizable byte pattern that an attacker can manipulate using the multiplicative property of RSA. The key difference for the attack is that OAEP decryption either succeeds and returns the message or fails and returns an error. There is no intermediate state where padding can be partially valid. An attacker who submits a malformed ciphertext gets back the same error regardless of how the malformation was structured. The chosen-ciphertext attack pathway is closed. OAEP is now the standard for RSA encryption in modern protocols. PKCS#1 v1.5 lives on only for legacy compatibility. New deployments are expected to use OAEP for encryption and PSS, the corresponding signature padding scheme, for signing. ## What This Means for Post-Quantum Cryptography The lessons from Bleichenbacher have shaped the design of modern public-key encryption schemes, including the post-quantum schemes selected by NIST. ML-KEM, the post-quantum key encapsulation mechanism standardized in FIPS 203, uses the Fujisaki-Okamoto transform. The transform takes an IND-CPA secure underlying scheme and adds a re-encryption check that turns the construction into IND-CCA2. When the receiver decapsulates a ciphertext, they re-encrypt the recovered shared secret and compare against the original ciphertext. If the comparison fails, the decapsulation returns a deterministic pseudo-random value derived from the ciphertext. This implicit rejection mechanism is the post-quantum analog of the constant-time, fallback-pseudorandom approach used in patched RSA-PKCS#1 v1.5 implementations. The difference is that for ML-KEM, the design is mandatory and integral to the standard, not a workaround applied after the fact. Implementations that follow the FIPS 203 specification correctly cannot have a Bleichenbacher-style oracle, because there is no observable distinction between valid and invalid ciphertexts at the protocol level. The Wycheproof test vectors maintained by Google include cases that specifically test for invalid ciphertext handling in ML-KEM implementations. The reference implementation used in QNSQY has been audited for the constant-time and implicit-rejection properties. To understand ML-KEM in detail, see [ML-KEM Explained](ml-kem-explained.md). For the broader story of why oracle behavior must be eliminated from cryptographic implementations, see [Decryption Oracles](decryption-oracle-attacks.md). ## Implementation Pitfalls That Persist Even with OAEP and AEAD as the modern standards, implementation pitfalls persist. Hardware accelerators sometimes have timing characteristics that depend on the input. A cryptographic accelerator that performs RSA operations may complete in slightly different times depending on the structure of the ciphertext. Software wrappers that expose the accelerator's results without normalizing the timing leak this information. Side-channel attacks on RSA private operations have been demonstrated through power analysis, electromagnetic emanation analysis, and acoustic analysis of the CPU's coil whine. These attacks predate Bleichenbacher and continue to evolve. Defenses include constant-time scalar multiplication, blinded exponentiation, and operation in fixed-time hardware. Mixed cryptographic schemes can introduce oracles where none should exist. A protocol that uses RSA for key transport and a separate AEAD for bulk encryption can be vulnerable if errors at the RSA layer leak distinct information from errors at the AEAD layer. Modern protocol design unifies error handling across layers. For QNSQY specifically, the file format never uses RSA. The hybrid encryption combines ML-KEM for the post-quantum component and X25519 for the classical component. Both schemes are IND-CCA2 secure and have constant-time, implicit-rejection implementations. The session key derived via HKDF feeds into AES-256-GCM, which is itself an AEAD. There is no padding oracle pathway in the QNSQY file format. ## The Long Tail of RSA-PKCS#1 v1.5 Despite OAEP being available since 1998, RSA-PKCS#1 v1.5 has continued to appear in deployed systems. Several factors contributed to this longevity. PKCS#1 v1.5 was a default in many cryptographic libraries for backward compatibility. Code written without explicit choice of padding mode often defaulted to v1.5. New code that copied existing patterns inherited the choice. Standards bodies have been slow to mandate OAEP. Even in 2025, some industry standards still permit PKCS#1 v1.5 for compatibility with legacy systems. Hardware modules from the 2000s and earlier sometimes implemented only PKCS#1 v1.5 in the hardware path, with OAEP requiring slower software routes. Protocol upgrades have been gradual. TLS 1.0 and 1.1 used RSA key exchange with PKCS#1 v1.5. TLS 1.2 deprecated it but did not remove it. TLS 1.3 finally removed RSA key exchange entirely, but TLS 1.3 deployment took years to reach saturation. The lesson is that cryptographic transitions take much longer than the academic community expects. Even when a vulnerability is well-known and a fix is standardized, the deployed base shifts slowly. ## FAQ **Is Bleichenbacher's attack still possible against modern systems?** Direct attacks against well-maintained TLS implementations are blocked by constant-time PKCS#1 v1.5 handling and the deprecation of RSA key exchange in TLS 1.3. Custom protocols, embedded systems, and legacy software can still be vulnerable. **What is the practical query count for a real attack?** The original 1998 paper estimated one million queries for 1024-bit RSA. Optimized variants in subsequent literature reduced this to tens of thousands. ROBOT in 2017 demonstrated practical attacks against real servers in hours. **Should I still use RSA at all?** For new deployments, ECDHE-based key exchange and Ed25519-based signatures have been the preferred choices for years. RSA remains useful for backward compatibility, but new protocols should not rely on it. Post-quantum migration adds another reason to avoid RSA, since RSA will not survive a cryptographically relevant quantum computer. **Does ML-KEM avoid Bleichenbacher-style attacks?** Yes, by design. The Fujisaki-Okamoto transform built into ML-KEM eliminates the distinguishability between valid and invalid ciphertexts. Implementations that follow FIPS 203 correctly do not expose oracle behavior at the protocol level. **What about RSA in non-TLS contexts?** JWT, JOSE, and various PKI signing operations still use RSA. Most modern implementations support OAEP for encryption and PSS for signing. Legacy systems may use PKCS#1 v1.5 for both, which is why audits should specifically check the padding mode in use. ## Sources 1. Bleichenbacher, D. "Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1." CRYPTO 1998. https://link.springer.com/chapter/10.1007/BFb0055716 2. Böck, H., Somorovsky, J., and Young, C. "Return Of Bleichenbacher's Oracle Threat (ROBOT)." USENIX Security 2018. https://www.usenix.org/conference/usenixsecurity18/presentation/bock 3. Bellare, M. and Rogaway, P. "Optimal Asymmetric Encryption: How to Encrypt with RSA." EUROCRYPT 1994. https://link.springer.com/chapter/10.1007/BFb0053428 4. RSA Laboratories. "PKCS #1 v2.2: RSA Cryptography Standard." 2012. https://datatracker.ietf.org/doc/html/rfc8017 5. CVE-2017-12373, CVE-2017-13099, CVE-2017-6168 (ROBOT-related). https://cve.mitre.org/ 6. NIST FIPS 203. "Module-Lattice-Based Key-Encapsulation Mechanism Standard." 2024. https://csrc.nist.gov/pubs/fips/203/final ## Related Articles - [Padding Oracle Attacks](padding-oracle-attacks.md) - [Decryption Oracles](decryption-oracle-attacks.md) - [ML-KEM Explained](ml-kem-explained.md) - [Why RSA-2048 Will Break](why-rsa-2048-will-break.md) - [Hybrid Encryption](hybrid-encryption.md) --- ### Protect Your Data Before Q-Day Arrives QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats. [Try QNSQY](../../pricing.html)