Why raw RSA is insecure
Applying the RSA formula directly to a message ("textbook RSA") has several fatal properties for real-world use: it's deterministic, so the same plaintext always produces the same ciphertext, leaking whether two messages match; it's malleable, so an attacker can manipulate a ciphertext in predictable ways that transform the underlying plaintext; and small messages encrypted with a small public exponent can sometimes be recovered directly by taking a root, with no key-breaking required.
PKCS#1 v1.5 and the Bleichenbacher attack
PKCS#1 v1.5 padding, standardized in the 1990s, prepends structured random padding before encryption to defeat determinism. In 1998, Daniel Bleichenbacher showed that a server which distinguishes "valid padding" from "invalid padding" errors leaks enough information, through repeated queries, to decrypt a ciphertext entirely — a padding oracle attack. Variants of this attack (including the 2017 ROBOT attack) were still being found against production TLS servers nearly two decades later, because the padding-check logic is easy to implement subtly wrong.
PKCS#1 v1.5 padded message layout (before encryption)
0x00
Leading zero byte
0x02
Block type — 2 means "encryption"
PS (padding string)
Random non-zero bytes, filling the block to the modulus size
0x00
Separator marking the end of padding
M (message)
The actual plaintext being encrypted
Go deeperThe oracle, step by step⌄
Bleichenbacher's attack doesn't need to see plaintext — it only needs a yes/no signal about whether a decrypted, attacker-modified ciphertext happens to have valid PKCS#1 padding. That single bit of leakage, repeated tens of thousands of times against different modified ciphertexts, is enough to mathematically narrow down the original plaintext to an exact value.
Padding oracle attack, simplified
- 1
Intercept a ciphertext
The attacker captures a legitimately encrypted ciphertext they want to decrypt.
- 2
Submit modified variants
They multiply the ciphertext by chosen values and resubmit it to the server thousands of times.
- 3
Watch the error signal
The server's response (or timing) reveals only whether the resulting padding was "valid" — nothing else.
- 4
Narrow the plaintext
Each valid/invalid answer mathematically shrinks the range of possible plaintexts, until only one remains.
OAEP and PSS: the modern replacements
OAEP (Optimal Asymmetric Encryption Padding) is the modern standard for RSA encryption, built to be provably secure against chosen-ciphertext attacks using randomized padding derived from hash functions. For signatures, the analogous modern scheme is RSA-PSS (Probabilistic Signature Scheme), which similarly replaces the deterministic padding of PKCS#1 v1.5 signatures with a randomized construction.
OAEP builds its randomization from a fresh random seed, mixed into the message through two rounds of masking with a hash-based mask generation function (MGF1) — each round's output feeds into the next, so recovering any part of the original message requires recovering the entire encoded block intact.
OAEP encoding: two rounds of masking
The seed masks DB (top); the resulting maskedDB then masks the seed right back (middle, dashed line shows the original seed feeding that second XOR) — each half depends on the other, which is what makes recovering any part of the message require recovering the entire encoded block.
The padding overhead tax: how much message space it actually costs
Padding isn't free — it eats directly into how much you can encrypt in a single RSA operation, which is one more reason RSA wraps a symmetric key rather than the data itself. PKCS#1 v1.5 encryption padding has a fixed 11-byte overhead: a leading 0x00, a 0x02 block-type byte, at least 8 bytes of random padding, and a 0x00 separator — so the maximum message length is simply the modulus size in bytes, minus 11.
Worked example: a 1024-bit RSA key has a 128-byte modulus. Maximum PKCS#1 v1.5 message length: 128 − 11 = 117 bytes. OAEP costs more: its overhead is 2×(hash output length) + 2 bytes, since the construction embeds two hash-sized values into the encoded block. With SHA-256 (32-byte output), that's 2×32 + 2 = 66 bytes of overhead.
Practice
A 2048-bit RSA key (256-byte modulus) uses OAEP with SHA-256. What's the maximum plaintext length, in bytes, that can be encrypted in a single RSA operation?
The practical takeaway
Padding is not a minor implementation detail bolted onto RSA — it's load-bearing security logic, and it's exactly the kind of code where a subtle timing or error-message difference becomes a full key-recovery attack. This is why every serious cryptography guideline says the same thing: never implement RSA padding yourself, and use a vetted, actively maintained cryptographic library.