Bleichenbacher Attack
Description
The popular RSA asymmetric encryption has a deterministic nature. Therefore PKCS 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. Following is a picture of a valid PKCS 1.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 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 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.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.
Requirements
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 Envryption: 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 eroors 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
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 key exchange is fully dropped regarding the encryption.