up:: Classical Cryptography MOC

RSA Padding (OAEP and PSS)

RSA padding is the structured encoding applied to a message before the RSA math runs, and it is what separates a secure RSA scheme from the insecure “textbook” version that just raises a message to a power modulo a large number. Raw RSA is deterministic and algebraically malleable, which leaks information and enables forgeries, so every real deployment wraps the message in a randomized, structured padding first. Two standardized paddings do the work, defined in RFC 8017 (PKCS #1 v2.2): OAEP (Optimal Asymmetric Encryption Padding) for encryption, and PSS (Probabilistic Signature Scheme) for signatures. The same standard still carries the older PKCS#1 v1.5 padding for backward compatibility, and that legacy encryption padding is the source of the Bleichenbacher padding-oracle attack, one of the most durable vulnerability classes in applied cryptography. All of this is classical-cryptography machinery, and the quantum transition does not patch it. Shor’s algorithm breaks the RSA math itself, so OAEP, PSS, and RSA together are being replaced wholesale by post-quantum algorithms rather than re-padded.

Source: IETF, “PKCS #1: RSA Cryptography Specifications Version 2.2,” RFC 8017, November 2016, RFC 8017.

The short version:

1. Textbook RSA is insecure. Encrypting or signing a raw message with the bare RSA operation is deterministic and malleable, which leaks information and lets an attacker manipulate ciphertexts and forge signatures.
2. Padding fixes it by adding structure and randomness. A correct padding makes ciphertexts non-deterministic and gives the recipient a way to detect tampering, which closes the algebraic holes in raw RSA.
3. OAEP is the encryption padding. RSAES-OAEP randomizes and structures the plaintext before encryption so the scheme resists chosen-ciphertext attacks, per RFC 8017.
4. PSS is the signature padding. RSASSA-PSS randomizes signatures and has a security argument tied to the hash, replacing the deterministic legacy signature padding.
5. PKCS#1 v1.5 is the cautionary tale. The older encryption padding gave rise to Bleichenbacher’s padding-oracle attack in 1998, which has resurfaced repeatedly whenever systems reveal whether padding is valid.
6. Post-quantum replaces the whole thing. Because Shor’s algorithm breaks RSA’s underlying math, the fix is not a better padding but a move to ML-KEM for key establishment and ML-DSA for signatures.

Think of raw RSA as a lockbox where the same message always produces the exact same locked package, with no seal to show whether anyone tampered with it in transit. An attacker who sees two identical packages knows the contents match, and one who can nudge the package and watch the reaction can pick the lock a piece at a time. Padding is the tamper-evident wrapping and the dab of randomness that makes every package look different and any interference detectable. OAEP is that wrapping for secrecy, PSS is the version for signatures, and the old v1.5 wrapping is the one that famously let attackers pick the lock by watching how the recipient reacted to a slightly malformed package.

Why is textbook RSA insecure?

Textbook RSA, the bare mathematical operation of raising a message to the public exponent modulo the RSA modulus, is insecure because it inherits algebraic properties that a secure encryption or signature scheme must not have. The problems compound:

1. It is deterministic. The same plaintext always encrypts to the same ciphertext under a given key. An attacker who suspects the message can encrypt guesses and compare, which breaks confidentiality for any small or predictable message space, and it leaks whether two ciphertexts hide the same plaintext.
2. It is malleable. RSA is multiplicatively homomorphic: multiply a ciphertext by an encryption of some factor and you get the encryption of the product. An attacker can transform a ciphertext into a related one without knowing the plaintext, which is exactly what a chosen-ciphertext attack exploits.
3. Signatures are forgeable through the same algebra. Raw RSA signatures inherit the multiplicative structure too, so an attacker can combine existing signatures into new valid-looking ones for messages that were never signed.
4. Small values misbehave. A short message or a small public exponent can leave the modular exponentiation without wraparound, letting an attacker recover the message by an ordinary root.

None of these are flaws in the RSA trapdoor itself. They are flaws in using the trapdoor directly on a message. The whole job of padding is to destroy the determinism and the malleability by encoding the message with randomness and structure before the RSA operation touches it, so that the ciphertext or signature stops exposing the algebraic relationships raw RSA leaks.

Source: IETF, RFC 8017, §7 and §8 (encryption and signature schemes built on the primitives), RFC 8017.

What is OAEP and how does it secure RSA encryption?

OAEP, Optimal Asymmetric Encryption Padding, is the standardized encryption padding (formally RSAES-OAEP) that transforms the raw RSA trapdoor into an encryption scheme with a strong security argument against chosen-ciphertext attacks. It works by mixing the message with randomness through a two-round structure before the RSA operation, so the encoded value is randomized and any tampering is detectable at decryption. The construction, at the level that matters:

1. A random seed is introduced. OAEP draws a fresh random value for each encryption, which makes the scheme probabilistic. Encrypting the same message twice yields different ciphertexts, so the determinism problem of raw RSA is gone.
2. The message and seed are run through a mask-generation function. OAEP uses a Feistel-like pair of masking steps built on a hash-based mask-generation function, so the padded block thoroughly mixes the message, the randomness, and a label into a single structured value with no exploitable algebra left.
3. Decryption checks the structure. After the RSA operation, the recipient unmasks the block and verifies the expected structure. A block that does not decode correctly is rejected, which is what gives OAEP its resistance to the ciphertext-manipulation an attacker would attempt.

The payoff is that OAEP-padded RSA has a proof of security against adaptive chosen-ciphertext attacks under standard assumptions, which raw RSA and the older v1.5 padding lack. When RSA is used to encrypt directly (most often to wrap a symmetric key), OAEP is the padding a modern system should use. One practical caution the standard emphasizes: an implementation must not reveal, through distinct error messages or timing, whether a decryption failed because of bad padding versus another reason, because leaking that difference reopens exactly the kind of oracle that sank v1.5.

Source: IETF, RFC 8017, §7.1 (RSAES-OAEP), RFC 8017.

What is PSS and how does it secure RSA signatures?

PSS, the Probabilistic Signature Scheme (formally RSASSA-PSS), is the standardized signature padding that gives RSA signatures a randomized encoding and a tighter security argument than the deterministic legacy padding it replaces. A digital signature is not computed over a whole document; the document is hashed first, and the signature is computed over an encoding of that hash. PSS defines that encoding. Its structure:

1. The message hash is combined with a random salt. PSS draws a fresh salt for each signature and mixes it with the message hash, so the same message signed twice produces different signatures. That randomization is what the “probabilistic” in the name refers to, and it strengthens the security reduction.
2. A mask-generation function spreads the encoding. As with OAEP, a hash-based mask-generation function fills the encoded block, binding the hash, the salt, and structural padding into one value before the RSA private-key operation signs it.
3. Verification recomputes and checks. The verifier applies the RSA public operation, recovers the encoded block, re-derives the expected structure from the message hash and the recovered salt, and accepts only if everything matches.

PSS is preferred for new RSA signatures because its security is provably tied to the hardness of the RSA problem and the strength of the hash, with a cleaner reduction than the deterministic PKCS#1 v1.5 signature padding, which lacks such a proof and has known theoretical weaknesses in some settings. Where a system still uses RSA signatures, PSS is the modern choice, and it is the signature padding profiled alongside OAEP in RFC 8017.

Source: IETF, RFC 8017, §8.1 (RSASSA-PSS), RFC 8017.

What was the Bleichenbacher attack on PKCS#1 v1.5?

The Bleichenbacher attack is a padding-oracle attack against the older PKCS#1 v1.5 encryption padding, and it is the single clearest lesson in why padding design and padding-error handling matter. RFC 8017 keeps the v1.5 padding for backward compatibility but flags exactly this weakness. Daniel Bleichenbacher published the attack in 1998, and its shape:

1. The padding has a checkable structure. A PKCS#1 v1.5 encryption block begins with fixed bytes, so a recipient decrypting a ciphertext can tell whether the result “looks like” valid padding.
2. Revealing that check creates an oracle. If a server behaves differently, a distinct error, a different response, or a timing difference, depending on whether padding was valid, an attacker learns one bit about the plaintext for each ciphertext they submit.
3. Adaptive queries recover the plaintext. By submitting many carefully chosen ciphertexts, each a mathematical transformation of the target, and observing the padding-valid-or-not answers, the attacker narrows the possible plaintext until the whole message (typically a session key) is recovered, without ever knowing the private key.

RFC 8017 states the danger directly: it is possible to generate valid v1.5 ciphertexts without knowing the plaintext, and that ability can be exploited in a chosen-ciphertext attack as shown by Bleichenbacher. The attack has resurfaced for over two decades under names like ROBOT and DROWN whenever a system leaks the padding-validity distinction, which is why the standard’s guidance is to prefer OAEP and, where v1.5 must remain, to make padding failures indistinguishable from other failures. The lesson generalizes past RSA: a cryptographic implementation must never reveal why a decryption failed.

Source: IETF, RFC 8017, §7.2.2 (decryption-error handling) and the Bleichenbacher reference, RFC 8017.

How do OAEP, PSS, and PKCS#1 v1.5 compare?

The three paddings split cleanly by purpose and by security posture, and the modern guidance is straightforward once the roles are clear. The comparison:

Padding	Purpose	Randomized	Status	Notes
PKCS#1 v1.5 (encryption)	Encryption	No	Legacy, avoid	Source of the Bleichenbacher padding-oracle attack
RSAES-OAEP	Encryption	Yes	Modern default	Provable resistance to chosen-ciphertext attacks
PKCS#1 v1.5 (signature)	Signature	No	Widely deployed, dated	Deterministic, no strong security proof
RSASSA-PSS	Signature	Yes	Modern default	Randomized, tighter security reduction

Two things are worth pulling out of the table. OAEP and PSS are the encryption-and-signature pair a new RSA deployment should use, because both are randomized and both carry security arguments the v1.5 paddings lack. And the v1.5 signature padding is still enormously deployed (much of the existing certificate and protocol world signs with it) even though it is dated, whereas the v1.5 encryption padding is the actively dangerous one because of the oracle. RFC 8017 retains both v1.5 variants only for compatibility with existing applications, so their presence in the standard is a legacy accommodation, not an endorsement.

Source: IETF, RFC 8017 (retains v1.5 schemes “for compatibility with existing applications”), RFC 8017.

Why does post-quantum cryptography replace all of this rather than re-pad it?

Post-quantum migration replaces the entire RSA construction, padding included, because the quantum threat is aimed at the RSA math itself and no padding can defend against it. OAEP, PSS, and the v1.5 paddings all sit on top of the same trapdoor: the difficulty of recovering the private key from the public key, which rests on the hardness of factoring the RSA modulus. Shor’s algorithm solves factoring efficiently on a cryptographically relevant quantum computer, which recovers the private key directly. Once the private key is exposed, an attacker decrypts any OAEP ciphertext and forges any PSS signature at will, because the padding only structures the message, it never protects the key.

That is why the migration is a wholesale replacement rather than a padding upgrade:

1. Encryption moves to a new primitive, not a new padding. RSA key transport, whether OAEP-padded or not, is replaced by ML-KEM, a lattice-based key-encapsulation mechanism whose security does not rest on factoring.
2. Signatures move to a new primitive. RSA signatures, whether PSS or v1.5, are replaced by ML-DSA or the conservative hash-based SLH-DSA, again on hardness assumptions Shor’s algorithm does not touch.
3. The padding concept does not carry over unchanged. Post-quantum schemes have their own internal encodings and security constructions appropriate to their math, so the OAEP and PSS designs are specific to RSA and retire with it.

The practical read is that padding was the fix for RSA’s algebraic problems in a classical world, and it did its job well for decades. The quantum problem is a different layer entirely, the hardness assumption under the trapdoor, so the response is to change the primitive with the crypto-agility to swap cleanly, and to treat OAEP and PSS as classical-era building blocks being replaced rather than reinforced.

Source: NIST, “Module-Lattice-Based Key-Encapsulation Mechanism Standard,” FIPS 203, August 2024, FIPS 203; NIST, “Module-Lattice-Based Digital Signature Standard,” FIPS 204, August 2024, FIPS 204.

Common misconceptions

1. “Padding is just formatting, so it does not matter for security.” It is load-bearing. Without OAEP or PSS, raw RSA is deterministic and malleable, which breaks confidentiality and lets an attacker forge signatures and manipulate ciphertexts.
2. “OAEP and PSS are interchangeable.” They are not. OAEP is an encryption padding and PSS is a signature padding, with different structures and different security goals. Using one where the other belongs is a design error.
3. “PKCS#1 v1.5 is broken everywhere and unused.” The v1.5 encryption padding is the dangerous one, source of the Bleichenbacher oracle. The v1.5 signature padding is dated but still deployed across much of the certificate world, retained by RFC 8017 for compatibility.
4. “A better padding would defend RSA against quantum computers.” No padding helps. Shor’s algorithm recovers the RSA private key from the public key, after which any padded ciphertext or signature falls, so the answer is a different primitive, not a different padding.
5. “The Bleichenbacher attack was fixed in 1998.” The specific instance was, but the padding-oracle class keeps returning (ROBOT, DROWN, and others) whenever a system reveals whether padding was valid, which is why the enduring guidance is to make padding failures indistinguishable and to prefer OAEP.

Questions people ask

Why can’t I just use RSA directly on my message? Because raw RSA is deterministic and multiplicatively malleable, which leaks whether two ciphertexts match, breaks confidentiality for guessable messages, and lets an attacker forge signatures and transform ciphertexts. Padding adds the randomness and structure that close those holes.

What is the difference between OAEP and PSS? OAEP (RSAES-OAEP) is the padding for RSA encryption, and PSS (RSASSA-PSS) is the padding for RSA signatures. Both are randomized and both are defined in RFC 8017, but they secure different operations and are not interchangeable.

What is the Bleichenbacher attack? A padding-oracle attack against the legacy PKCS#1 v1.5 encryption padding, published in 1998. If a system reveals whether a decryption had valid padding, an attacker submits many crafted ciphertexts and recovers the plaintext (usually a session key) without the private key.

Is PKCS#1 v1.5 still safe to use? The v1.5 encryption padding should be avoided in favor of OAEP because of the padding oracle. The v1.5 signature padding is dated and still widely deployed, but PSS is the modern choice for new RSA signatures. RFC 8017 keeps both v1.5 variants only for backward compatibility.

Does OAEP or PSS make RSA quantum-safe? No. Both sit on top of the RSA trapdoor, which Shor’s algorithm breaks by recovering the private key. Padding structures the message and never protects the key, so RSA moves to ML-KEM and ML-DSA rather than to a new padding.

Why do post-quantum schemes replace RSA instead of adding better padding? Because the quantum problem lives in the hardness assumption under RSA rather than in the message encoding. Post-quantum algorithms rest on different math (lattices, hashes) with their own internal constructions, so OAEP and PSS are RSA-specific and retire alongside RSA.

---

Everything here is the map, given freely. When your team needs its own RSA usage found, sized, and sequenced onto a post-quantum path before the machine arrives, that’s what an alignment briefing is for.

Last verified 2026-07-12 · Maintained by Addie LaMarr, LaMarr Labs.