Mark Esler

Bleichenbacher Attacks

Description

RSA PKCS#1 1.5 is used to pad and encrypt secrets. e.g., in TLS 1.2 the first two bytes are 00 02, followed by non-zero padding, a 00 delimiter, two bytes to indicate the TLS 1.2 version (03 03), and finally followed by the premaster secret. Knowing this, Bleichenbacher proved the first practical example of adaptive chosen-ciphertext attacks (CCA2) when a server reports padding validation of RSA PKCS#1 1.5.

Bob sends a ciphertext to the server Alice. Mallory eavesdrops on Bob and misuses Alice as an oracle, by altering Bob’s ciphertext cryptographically and asking Alice to validate the modified message. Alice may tells Mallory if the decrypted modified message begins with 00 02. This “million message attack” continues until Mallory has enough information to decrypt raw messages. Performance (number of messages) depends on the oracle’s properties.

Böck et al., Hubert Kario, and others have shown that modern servers are vulnerable to these attacks.

Research History

First described by Daniel Bleichenbacher at IACR’s CRYPTO ‘98 aka BB'98: Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1

BB'06 was later described and used against python-rsa in 2016 by Filippo Valsorda.

This is an ongoing problem and research topic:

• 2007 - Analysis on Bleichenbacher’s Forgery Attack
• 2014 - Revisiting SSL/TLS Implementations: New Bleichenbacher Side Channels and Attacks
• 2018 - Return Of Bleichenbacher’s Oracle Threat (ROBOT)
  • The ROBOT Attack
  • Hypothesises Heartbleed-style Bleedinbacher
• 2019 - The 9 Lives of Bleichenbacher’s CAT: New Cache Attacks on TLS Implementations
• 2023 - Everlasting ROBOT: the Marvin Attack
  • Out of the Box Testing
  • The Marvin Attack
  • Hubert Kario’s blog Securitypitfalls
  • Pure Python and python-rsa will never be safe from this attack
  • bandit request to mark PKCS1v15 as a Bleichenbacher/Marvin vulnerability

Marvin Attacks

Following Böck et al, Hubert Kario has been raising awareness and coordinating with affected downstreams.

This awareness campaign coins Bleichenbacher Attacks as Marvin Attacks:

Where does the Marvin name comes from?

The previous comprehensive attack against RSA was called ROBOT. Given the complexity and fragility of required fixes we don’t believe that this attack will generally go away. Thus we named it after an android that lasted till the end of the universe in The Hitchhiker’s Guide to the Galaxy.