RSA Padding and Why Textbook RSA Fails

The RSA operation itself is a permutation of the integers modulo $n$: encryption is $c = m^e \bmod n$ and decryption is $m = c^d \bmod n$. Applied directly to a message, that permutation is a catastrophically bad encryption scheme, and the reasons are arithmetic rather than implementation sloppiness. The padding schemes in PKCS #1 exist to make the permutation usable, and each one closes a specific failure.

The multiplicative structure is an attack surface

Because exponentiation is a homomorphism, $E(m_1) \cdot E(m_2) \equiv E(m_1 m_2) \pmod n$. An attacker who has a ciphertext $c = m^e$ can multiply it by $s^e$ for a chosen $s$ and obtain $(ms)^e$. The result decrypts to a message the attacker chose to be a multiple of the original. If the recipient’s protocol reveals anything about the decrypted plaintext — a parse error, a rejection reason, an acknowledgement — the attacker learns whether $ms$ fell into a valid range, and from that recovers $m$ by a blinding and unblinding procedure.

This is the shape of Bleichenbacher’s 1998 attack on PKCS #1 v1.5 encryption. The padding format begins with a fixed byte 0x00 0x02 and requires a specific number of nonzero padding bytes. A recipient that returns a distinguishable error for “padding invalid” versus “padding valid but content malformed” leaks one bit per query about whether the padded plaintext is in range. Multiplying the ciphertext by successive values of $s$ shifts the plaintext, and each response narrows the interval containing $m$. The attack needs on the order of a million queries against a 1024-bit key — feasible over a network — and recovers the plaintext outright. Variants of the same idea have resurfaced repeatedly against TLS, JSON Web Encryption, and other protocols that used RSA encryption without a uniform error path.

The lesson generalises: any oracle that distinguishes decryption outcomes is fatal when the ciphertext is malleable.

Determinism loses semantic security

Textbook RSA is a deterministic function. Encrypting the same message twice produces the same ciphertext, so an observer can tell whether two ciphertexts carry the same plaintext without decrypting either. That violates the standard notion of security for encryption, indistinguishability under chosen plaintext attack, and no amount of key size fixes it.

The fix is randomised padding: before exponentiation, the message is combined with fresh random bytes in a way that is invertible given the private key. Two encryptions of the same message then differ with overwhelming probability, and the randomness is discarded at decryption.

OAEP: a two-round Feistel on the padded block

Optimal Asymmetric Encryption Padding, from Bellare and Rogaway, builds the padded block from the message, a seed, and a hash function. For a modulus of $k$ bytes and a hash of $h$ bytes, the encoded block has the layout 0x00 || maskedSeed || maskedDB, where DB is a label hash, a string of zero bytes, a 0x01 separator, and the message.

DB        = lHash || PS (zeros) || 0x01 || M
dbMask    = MGF1(seed, k - hLen - 1)
maskedDB  = DB XOR dbMask
seedMask  = MGF1(maskedDB, hLen)
maskedSeed = seed XOR seedMask

EM = 0x00 || maskedSeed || maskedDB

MGF1 is a mask generation function built from the hash: concatenate the seed with a four-byte counter, hash, and repeat until enough bytes are produced. The construction is a two-round Feistel network, which is what gives it the property that inverting the encoding without the seed requires inverting the hash. Note that the second mask is derived from the masked database, not from the unmasked one; deriving both masks from the seed alone would leave the two halves independent and break the Feistel structure.

Decryption reverses the masks, checks that the leading byte is zero, recomputes the label hash, and verifies that the padding string consists of zeros followed by exactly one 0x01. The critical implementation requirement is that all of these checks happen and that the failure is reported identically regardless of which one failed. A decoder that returns “label mismatch” for one input and “separator not found” for another reintroduces the oracle that OAEP was designed to remove. Constant-time comparison and a single error path are part of the scheme, not optimizations of it.

OAEP is proven secure against chosen-ciphertext attack in the random oracle model, assuming the underlying permutation is hard to invert. That proof is the reason it displaced the earlier v1.5 padding for encryption. The proof’s assumptions matter: it treats the hash as an ideal random function, and real hashes are not that. The gap has not produced a practical break of OAEP with a sound hash, but it means the guarantee is conditional.

PSS: randomised signatures

Signature schemes have a different requirement. A signature must be verifiable by anyone with the public key, so it cannot depend on a secret random value at verification time. The earlier v1.5 signature padding was deterministic and, while not broken, has no tight security proof in the standard model.

PSS, proposed by the same two researchers, salts the message hash and applies a mask so that the signature is randomised but the verifier can recover the salt from the signature. The construction mirrors OAEP’s mask structure:

mHash   = Hash(M)
salt    = random sLen bytes
M'      = 0x00 * 8 || mHash || salt
H       = Hash(M')
PS      = 0x00 * (emLen - sLen - hLen - 2)
DB      = PS || 0x01 || salt
dbMask  = MGF1(H, emLen - hLen - 1)
maskedDB = DB XOR dbMask
EM      = maskedDB || H || 0xbc

The final byte 0xbc is a fixed trailer that makes the encoding self-identifying. Verification recomputes the mask from the transmitted $H$, recovers the salt, rebuilds $M’$, and checks that the hash matches. The salt can be recovered because the mask is derived from $H$, which is part of the signature. PSS has a tight security proof in the random oracle model, and with a full-length salt it is the recommended signature padding in current standards.

The salt length is a compatibility variable. RFC 8017 defines a saltLength parameter, and verification can either require a specific length or recover whatever length the signature encodes. Implementations that hardcode 20 bytes — the hash output length for SHA-1 — reject valid signatures made with a longer salt. The safe choice at verification is to accept the length the encoding implies and check the structure, rather than to enforce a value the signer may not have used.

Where the failures actually appear

The padding schemes are sound; the breaks come from the seams around them.

Mixed error paths. A protocol that reports decryption failure at one layer and content-format failure at another gives the attacker the oracle. The correct design is to decrypt, and if anything fails, return a single generic failure after a delay that does not depend on the failure type. Bleichenbacher’s attack and its many descendants all exploit a distinguishable outcome.

Partial plaintext leakage. Even with OAEP, an application that echoes the decrypted bytes or their length on failure leaks information. The padding protects the block; it does not protect a protocol that inspects the block.

Re-encoding in signatures. A signature scheme that hashes a message and then encodes it with a permissive parser allows a forgery: the attacker constructs a different message whose encoding collides with a valid one. The defence is to hash the exact bytes and to parse the encoding strictly, rejecting anything that is not in the canonical form the signer would produce. This class of bug appeared in implementations that accepted multiple ASN.1 encodings of the same value.

Key type confusion. If a protocol accepts both RSA and elliptic curve keys and does not bind the key type into what is signed, a signature under one algorithm can be reinterpreted as a value under another. The fix is to include the algorithm identifier in the signed structure, as modern signature formats do.

Choosing between the two paddings

Encryption and signing are separate uses with separate paddings, and mixing them is a mistake. OAEP is for encryption: it is randomised, it hides the message, and it is verified only by the holder of the private key. PSS is for signatures: it is randomised at signing but publicly verifiable, and its security goal is unforgeability rather than confidentiality. Using a signature padding to encrypt, or an encryption padding to sign, produces something that is neither proven nor obviously broken — the worst position to be in.

For new designs, the broader trend is to avoid RSA encryption entirely and use it only for signatures, with key establishment handled by Diffie-Hellman or a hybrid scheme. The reasons are in Hybrid Encryption and the Cost of Encrypting Long Messages: RSA can only encrypt a block smaller than the modulus, so any real message needs a symmetric layer anyway, and once that layer exists the RSA step can be replaced by a key transport or a KEM without changing the message handling. The arithmetic that makes the private operation expensive is in Modular Exponentiation and the Cost of One Key Operation.