An Ok/Err Result Is a Bleichenbacher Oracle

A function returns Ok on valid padding and Err on invalid padding. That is a padding oracle. Bleichenbacher published the attack in 1998. It still works, and it does not care how fast your code runs.

The timing variant, Marvin, leaks tens of nanoseconds under microseconds of jitter. Kario demonstrated it remotely over a network, but pulling the signal out takes statistics over many samples. The behavioral version needs none of that. Böck, Somorovsky, and Young’s ROBOT (disclosed 2017, USENIX Security 2018) re-found Bleichenbacher’s oracle across at least seven vendors (and several open-source projects) by reading their responses, not their clocks. Its authors were candid about how little that took:

So… ROBOT doesn’t add a whole lot, right? That’s correct. The surprising fact is that our research was very straightforward. We used minor variations of the original attack and were successful. This issue was hiding in plain sight. […] neither the vendors of the affected products nor security researchers have investigated this before, although it’s a very classic and well-known attack.

the ROBOT FAQ

This blog post uses even less: the textbook 1998 attack, unmodified, against a current crate.

The oracle is one bit

PKCS#1 v1.5 decryption recovers an integer and checks its structure: leading bytes 00 02, then ≥8 nonzero padding bytes, a 00 separator, then the message. The attacker chooses the ciphertexts and reads whether it conformed.

RSA is multiplicatively homomorphic: multiply a ciphertext c by sᵉ mod n and the underlying plaintext is multiplied by s. So the attacker submits c · sᵉ for a chosen s and asks the oracle: is m · s still a conforming block? Each “yes” pins m into a narrower band. Most of the work is the sequential hunt for each conforming s; once a single interval survives, each new conforming s roughly halves that interval until it collapses to a single value: the plaintext.

Demonstrated against a current implementation

A ~300-line standalone proof of concept. Its only cryptographic dependency is the published rsa = "=0.10.0-rc.18" crate; the rest is attacker-side bignum and SHA-256. It mounts the attack with nothing but this:

// The whole oracle. One bit. No timing.
fn query(&mut self, s: &BigUint) -> bool {
    let c = (&self.c0 * s.modpow(&self.e, &self.n)) % &self.n;
    let ct = uint_to_be_padded(&c, self.k);
    self.key.decrypt(Pkcs1v15Encrypt, &ct).is_ok()   // Ok => conforming, Err => not
}

Results over 100 distinct deterministic RSA-4096 keys (untuned 1998 attack: every key recovered and forged):

The forgery uses the identical machinery, since signing is RSA “decryption” of a message representative: the same oracle that recovers a plaintext also forges a signature over an attacker-chosen message. The attacker never recovers the private key in either case. A bigger modulus only makes each query slower.

The implementation’s own source comment warns of exactly this: an attacker who observes the padding-check outcome “can decrypt and forge signatures as if they had the private key.”

The cure: stop using RSA encryption

ROBOT, published in 2018, under a heading that is just “Disable RSA encryption!”:

We believe RSA encryption modes are so risky that the only safe course of action is to disable them.

They scope it:

By disabling RSA encryption we mean all ciphers that start with TLS_RSA. It does not include the ciphers that use RSA signatures and include DHE or ECDHE in their name.

Alicja Kario’s Marvin attack showed Bleichenbacher’s timing channel is still common in current libraries, and she authors the CFRG’s RSA-guidance draft. The draft is normative:

Current protocol deployments MUST NOT use encryption with RSAES-PKCS-v1_5 padding.

Support for RSAES-PKCS-v1_5 SHOULD be disabled in default configuration of any implementation of RSA cryptosystem.

On the Marvin page:

Stop using RSA PKCS#1 v1.5 encryption!

We have had 25 years of people trying to patch this fundamentally broken padding mode.

Her advice to library authors is to “deprecate and disable support for PKCS#1 v1.5 padding for encryption.” If you truly cannot drop RSA encryption, use RSA-OAEP, but only with a constant-time decode, because OAEP has its own oracle (Manger).

When you cannot drop v1.5 yet, implicit rejection is the stopgap. Return a fixed-length value for every ciphertext, valid or not, derived from the private key and the ciphertext: the CFRG §7.2 “Implicit rejection” construction, which says to “use the private key and the provided ciphertext to derive a static, but unknown to the attacker, random value.” No Ok/Err to read.

decrypt(ct)                   -> Ok(variable-length msg) | Err    // a one-bit oracle
decrypt_session_key(ct, len)  -> always len bytes, valid or not   // nothing to observe

Implicit rejection is easy to get wrong. The fixed-length value has to be produced in constant time, and you have to measure that it is. Skip the measurement and the same bit can leak through timing instead. That’s a Marvin-style timing channel.

This was one library. Many that roll their own v1.5 still hand the bit over. The companion survey of 27 RSA libraries maps the rest.