Reverse-Bleichenbacher: Bleichenbacher Attacks are Practical Again

What it is

Reverse-Bleichenbacher is a variant of the Bleichenbacher RSA PKCS#1 v1.5 padding-oracle attack, to be presented at NDSS 2027. It targets TLS RSA key exchange. It is meant to make the attack fit inside a live man-in-the-middle connection timeout.

How it works

Classical Bleichenbacher narrows the plaintext interval from the top down. It spends many queries on padding bytes that carry no secret before it reaches the PreMasterSecret in the low-order 46 bytes. Reverse-Bleichenbacher recovers the least significant bytes first and stops as soon as the secret is found. Improved trimmers and a coverage-optimized search reduce the work further.

Numbers against a standards-conforming PKCS#1 v1.5 oracle with 2048-bit keys:

• Median oracle queries fall from 11,428 to 1,801.
• Overall success rate is 84.8%, so about 15% of runs fail.
• At the observed 2.6 ms median RTT to vulnerable hosts, with 2 round trips per query, 68.3% of runs finish within a 30s timeout. None of the prior algorithms did.
• At 20 ms RTT, parallelizing independent queries cuts median end-to-end runtime from 59.3s to 8.3s, at the cost of extra queries.

Preconditions / Affected

• The attacker must be an active network attacker.
• The server (or client) must still permit RSA key exchange and expose a PKCS#1 v1.5 padding oracle.
• Latency to the target matters. The page's feasibility figures assume low RTT to a single server, and higher RTT needs batching.
• 640 domains in the Tranco Top 1M were found vulnerable, many behind Alibaba Cloud load balancers.
• The authors demonstrated MITM injection of malicious updates on real software distribution channels, leading to remote code execution on the victim device. The page names no specific products.

What to do

The page excerpt gives no patches or commands. The preconditions point to the following actions, which are my inference rather than the page's text:

• Check whether your TLS endpoints and load balancers still accept RSA key exchange.
• Check whether update clients accept it as well.
• If they do, you are in the affected population.

Caveats

• Only the abstract was available, so the oracle behavior of specific implementations and the vendor disclosure status are not covered here.
• The headline 68.3% within-30s result is for single-server, low-latency conditions.