Paper 2026/2414

Reverse-Bleichenbacher: Bleichenbacher Attacks are Practical Again

Abstract

Bleichenbacher's 1998 padding oracle attack against RSA PKCS#1 v1.5 has resurfaced repeatedly over the past decades, especially in TLS. Although modern browsers prefer TLS 1.3, many servers and clients still permit RSA key exchange for backward compatibility, enabling active network attackers to decrypt recorded sessions. Still, practical man-in-the-middle attacks remain challenging. The classical attack narrows the plaintext interval from the top down, spending many queries on secret-independent padding bytes before reaching the PreMasterSecret in the low-order 46 bytes of the RSA plaintext. As a result, prior attacks required multiple vulnerable servers in parallel to avoid connection timeouts. In this paper, we present Reverse-Bleichenbacher, a novel variant of the Bleichenbacher algorithm. In contrast to all previous Bleichenbacher-style algorithms, our algorithm recovers the least significant bytes first and terminates the search as soon as the target secret is recovered. When the secret occupies only a fraction of the plaintext, as with the TLS PreMasterSecret, this significantly reduces the number of required queries. Together with improved trimmers and a coverage-optimized search, this reduces the median number of oracle queries from 11.428 to 1801 against a standards-conforming PKCS#1 v1.5 oracle with 2048-bit keys, with an overall success rate of 84.8 %. Crucially, under realistic single-server conditions (a 2.6 ms median round-trip time we observe to vulnerable hosts and 2 round trips per query) 68.3% of all runs finish within a 30s timeout, compared with none of the prior algorithms. To remain feasible at higher latency, we parallelize independent queries: at 20 ms round-trip time, batching reduces the median end-to-end runtime from 59.3s to 8.3s, at the cost of additional queries. We identify 640 vulnerable domains in the Tranco Top 1 Million, many behind Alibaba Cloud load balancers. We demonstrate end-to-end impact on real software distribution channels: a man-in-the-middle attacker can inject malicious updates and achieve remote code execution on a victim device.