A padding oracle in RSA1_5, and what constant-time rejection means

In 1998 Daniel Bleichenbacher showed that a server willing to say « this padding is wrong » leaks enough to decrypt a message without holding the key. GHSA-5739-39v2-5754 is the same idea, in a JWE decryption path.

The oracle

RSACrypt::decryptWithRSA15(), used by the RSA1_5 key-encryption algorithm, checked the PKCS#1 v1.5 padding and reported failure when it was malformed.

That single bit of information, valid or not, is the oracle. An attacker submits adaptively crafted ciphertexts and, from the pattern of answers, recovers the content encryption key. No private key required, only patience and a server that answers honestly.

The counter-intuitive fix

The remedy is called implicit rejection, and it consists in not rejecting anything visibly.

When the padding is malformed, the implementation does not raise an error. It returns a random value of the expected length, deterministically derived from the key and the ciphertext. Decryption then continues and fails later, on the authentication tag, exactly as it would for any other wrong key.

The attacker sees one behaviour in both cases. The oracle is gone, not because the check disappeared but because its outcome stopped being observable.

Constant time is part of it

Returning the same answer is not enough if it arrives at a different moment. A comparison that stops at the first wrong byte tells the attacker how many bytes were right, through timing alone. The corrected path compares in constant time, so the duration reveals nothing either.

What you should do

Update, of course: 3.4.10, 4.0.7 or 4.1.7.

But the better move is to stop registering RSA1_5 at all. Its padding has been a source of oracles for a quarter of a century, and every implementation carries the burden of getting the mitigation right. RSA-OAEP-256 or ECDH-ES do the same job without the history.