Bleichenbacher Attack

From Embedded Lab Vienna for IoT & Security
Jump to navigation Jump to search


The popular RSA asymmetric encryption has a deterministic nature. Therefore PKCS #1 v1.5(a padding standard used for RSA transmission, defined in RFC 8017) was added to RSA which uses padding to remove this deterministic property and add two functionalities. This are the signature and the encryption of packets and each of those are indicated at the second MSB (Most Significant Bit). Following is a picture of a valid PKCS #1 v1.5 packet (bytes are displayed as hex):


In this picture you see a 0 Byte as MSB followed by a "2" to indicate encryption. Following is the variable length random padding with at least 8 Byte, delimited by another 0 Byte. After this delimiter you find the data you want to send or like to receive. At the sender side this packet is now encrypted with RSA and on the receiver side the data is extracted after RSA decryption. This encryption and most important decryption is only successful if the validity of such a PKCS#1 v1.5 packet is given. Therefore decrypted data is checked upon the validity.

Daniel Bleichenbacher published a method in 1998 called the "Bleichenbacher Attack" to use this validity check to decrypt a previous captured packet. An attacker therefore captures a packet sent from client to server and multiplies it with a number. This number can be chosen randomly and due to the fact, that the public key of the server previously used by the client is also available to the attacker, he or she is able to compute a new packet and send it to the target system. This system acts as an oracle and answers most likely with an error due to the invalid PKCS#1 v1.5 packet because of an unknown structure. For example there is no 0 as MSB after modifying this packet. After receiving the first answer, the attacker computes a new packet with another number and sends it again to the oracle. This procedure is now constantly repeated until no error message is answered. The attacker now knows that his comuted packet produced a decrypted packet between:

020000000... << 030000000...

By further continuing this procedure the attacker learns more intervals and can eventually derive the originally encrypted message. Because of the amount of messages that have to be sent, this attack also is called the "Million Message Attack". In case of SSL encryption the RSA key exchange is using PKCS#1 v1.5 to transmit the so called pre_master_secret. If an attacker can capture and decrypt this packet, he or she can read the entire transmitted data between this client and the server within this specific ssl session.


There are a couple things which are needed for an effective Bleichenbacher Attack. Basically this attack works with RSA PKCS 1.5 and the initial captured packet itself must be PKCS conform. But there is one main important requirement: a Bleichenbacher Oracle. Such an oracle is a target system which answers repeated questions concerning the validity of an PKCS packet. To create such an oracle there are basically three ways:

  • Plain Encryption: if implementation is without signature, the target system will only check the validity of the PKCS packet and sending an error message if the packet is invalid
  • Detailed Error Messages: if encryption and signature is applied, but the target system generates specific errors regarding the validity of an pkcs packet
  • Timing Attack: if encryption and signature is applied in a proper way, you can still check the time between responses to generate a side channel regarding the validity of the packet

Return of Bleichenbacher's Oracle Threat

The ROBOT attack, standing as an acronym for "Return Of Bleichenbacher's Oracle Threat," is a cryptographic vulnerability that surfaced nearly two decades after the original Bleichenbacher Attack. This modern exploit, brought to light by security researchers Hanno Böck, Juraj Somorovsky, and Craig Young leverages a refined technique that bears similarities to its predecessor but incorporates subtle variations to target HTTPS hosts.

Attack Mechanism

Unlike the original Bleichenbacher Attack, which manipulated client messages post the ClientHello and ServerHello exchanges, the ROBOT attack takes advantage of a unique approach. Specifically, the attack permits the ClientKeyExchange message to proceed without interruption. However, the subsequent absence or manipulation of the Finished message, along with other message alterations, induces varied responses from the server. These manipulated server responses enable adversaries to exploit the system further, even after mitigative measures have been instituted in response to the Bleichenbacher vulnerabilities.

Targets and Impact

The ramifications of the ROBOT attack were profound, targeting a slew of prominent HTTPS hosts. Notably, one of its most high-profile victims was Facebook. Initially, the researchers executed a Bleichenbacher-style attack against Facebook's systems. After Facebook fortified its defenses in response, the researchers pivoted and deployed the nuanced ROBOT technique. This adaptation allowed them to compromise Facebook's cryptographic signatures and similarly breach other web servers.

Affected Products

There are many implementations that are vulnerable. The product list includes:

  • F5
  • Citrix
  • Cisco
  • Java / JSSE
  • IBM GSKit
  • Bouncy Castle
  • SSL 1.0 - 1.3
  • TLS 1.0 - 1.2

Implementations in TLS 1.1 and 1.2 may not be practicably vulnerable if implemented with the attack in mind. Due to the complexity of an correct implementation, this easily can be done wrong and there's still a side channel to generate an oracle. With TLS 1.3 RSA PKCS#1 v1.5 key exchange is fully dropped regarding the encryption.


Several defenses have been developed to protect against the Bleichenbacher Attack. One approach is to eliminate the error message that signals invalid ciphertexts, making it more difficult for an attacker to obtain information about the private key. This approach is known as the "Bleichenbacher Oracle Attack" defense. Another approach is to use a more secure implementation of RSA decryption that does not use the CRT. This approach is known as the "Full RSA" defense. In addition, cryptographic experts have developed several countermeasures to protect against the Bleichenbacher Attack. For example, the Transport Layer Security (TLS) protocol has been updated to include protections against the attack. The TLS 1.3 protocol, released in 2018, includes several protections against the attack, including eliminating the error message that signals invalid ciphertexts and adding additional padding to ciphertexts. NIST (National Institute of Standards and Technology ) claims that Government systems must support TLS 1.3 by January 1st, 2024. [1]