Chosen ciphertext attacks↑

Chosen ciphertext attacks compromise encryption by manipulating ciphertexts and observing how systems respond to decryption attempts. Although initially considered a theoretical concern, these attacks have been used to breach real-world systems, including SSL/TLS and major web frameworks.

An example of this type of attack is the padding oracle attack, which exploits how systems respond to padding errors during decryption. These attacks have been used to break PKCS#1v1.5 RSA encryption—in this case the attack is often referred to as Bleichenbacher’s attack—and CBC-mode encryption in older SSL/TLS versions.

To prevent chosen ciphertext attacks, use cryptographic schemes with IND-CCA¹ security. This means using OAEP² padding for RSA instead of PKCS#1v1.5, and adopting authenticated encryption modes like GCM instead of CBC. Minimizing information leakage, such as through padding error messages, is also important when implementing secure systems. IND-CCA security is the standard for modern encryption solutions, and any deviations require careful consideration.

General introduction↑

Chosen ciphertext attacks are a broad class of cryptography attacks that aim to break the confidentiality provided by encryption schemes. These attacks involve an attacker manipulating a target ciphertext and querying decryptions of the resulting malformed ciphertexts such that the responses help the attacker obtain useful information about the target plaintext—in the worst case, even allowing the attacker to recover the entire plaintext.

Although the notion of chosen ciphertext attacks are, strictly speaking, an abstract attack model used by cryptographers to formally analyze cryptographic schemes, they’re also relevant in practice. They were used to compromise TLS implementations, XML frameworks, Android KeyStore, and more.

A key ingredient of chosen ciphertext attacks is a decryption oracle that is queried by the attacker on their manipulated ciphertexts. The real-world attacks mentioned earlier became possible because attackers could construct approximations of these oracles in practice by using methods such as malware exploits and padding oracles. The latter method is common in practical chosen ciphertext attacks and will be discussed in the next section.

Chosen ciphertext attacks in practice: padding oracle attacks↑

Padding oracle attacks are a form of chosen-ciphertext attack that exploits how padding errors are handled during decryption. They serve as building blocks for many cryptographic attacks, including the BEAST attack on TLS, attacks on web frameworks, and attacks on PKCS#11 cryptographic hardware.

At a high level, messages are padded with redundant data before encryption for various reasons, such as to ensure the message has the correct length for the underlying encryption function (as in block cipher modes such as CBC), or randomizing the message to prevent certain attacks (as in RSA encryption). During decryption, an additional check is typically performed on the decrypted plaintext to determine whether its padding is valid before the message is returned.

In some cases, certain systems, such as servers, exhibit different behavior when they receive messages with valid padding compared to messages with invalid padding. For example, a protocol may return an error message if it receives a ciphertext with invalid padding, while proceeding with the rest of the protocol if the padding is valid. Attackers exploit these oracles that reveal padding validity—hence the name, padding oracles—to compromise the security of the system.

It’s important to note that padding oracles, strictly speaking, are weaker than decryption oracles—as discussed in the context of chosen ciphertext attacks above—since they do not return the entire decryption of an attacker’s query, but only indicate whether the decrypted query contains valid padding. However, as we’ll see in the following examples, padding oracles can be sufficient to completely break security in real-world scenarios.

Attacks on PKCS#1v1.5 RSA encryption↑

This class of attacks against RSA encryption with PKCS#1v1.5 padding was first proposed by Daniel Bleichenbacher in 1998, and many attack variants and improvements have since been reported. TLS versions up to 1.2 include RSA PKCS#1v1.5 as a key-establishment method, and are therefore vulnerable to these attacks without additional countermeasures.

Specifically, PKCS#1v1.5 RSA encryption is used to encrypt a premaster secret. This serves as an input to derive the final session key and is then transmitted from the client to the server.

Bleichenbacher-style attacks require access to a padding oracle, which allows an attacker to determine whether a particular ciphertext is accepted as a valid PKCS#1v1.5-padded plaintext after being decrypted. An attacker can then manipulate a target ciphertext in different ways and query this padding oracle to see if it’s accepted or not. From this pattern of acceptance and rejection, the attacker can recover the entire plaintext.

Returning to the TLS example above, an attacker can iteratively decrypt the premaster secret, which is used to derive the session key if the server’s decryption behavior reveals padding errors.

Such attacks are generally efficient. For example, for an implementation that strictly follows PKCS#1v1.5 padding rules, the attack typically requires around 15,000 queries to the padding oracle.

Attacks on CBC-mode encryption↑

This category of padding oracle attacks against the CBC mode of operation was first proposed by Serge Vaudenay in 2002, and subsequent variants have since led to real-world security vulnerabilities, including the Lucky Thirteen attack against CBC in TLS (up to version 1.2) and the POODLE attack, which exploited CBC weaknesses in SSL v3.0.

CBC-mode encrypts data in chunks of b bits, where b is typically 128—the block size of AES, the most widely used block cipher. Messages, however, do not necessarily have a length that is a multiple of b bits. Thus, padding schemes are employed to extend the message to the required length. One such padding scheme is PKCS#7.

The attack exploits:

the absence of guarantees for the integrity of ciphertexts.
the fact that PKCS#7 padding can be valid or invalid.

Put simply, ensuring ciphertext integrity prevents an attacker from manipulating ciphertexts in a way that produces meaningful responses. The lack of these guarantees is the root vulnerability, while the presence of a padding oracle—which reveals whether padding is valid or invalid—is the means by which this vulnerability can be efficiently exploited.

The attack relies on querying such a padding oracle. Specifically, the attacker proceeds by flipping bits in the ciphertext and observing whether this produces a valid or invalid padding. The attacker can then infer the plaintext from the pattern of valid or invalid padding responses.

The attack is efficient. The required number of padding oracle queries is linear in the number of bits in the target message. Extracting each byte of plaintext typically requires around b oracle queries.

Security recommendations↑

Use cryptographic schemes that are proven to offer security against chosen-ciphertext attacks, that is, use schemes which achieve IND-CCA security.

For example, Bleichenbacher-style attacks can be mitigated against RSA encryption by switching from PKCS#1 v1.5 padding to OAEP (PKCS#1 v2.0) padding. This has been shown to offer IND-CCA security in an idealised model known as the random oracle model. PKCS#1v1.5 encryption should also not be made available to attackers anywhere in the API. Starting in TLS 1.3, PKCS#1 v1.5 encryption has been removed.

Similarly, use authenticated encryption modes such as GCM or CCM to prevent CBC-mode attacks. For more information on block cipher modes, refer to Block and Stream Ciphers.

Sources↑

Indistinguishability under Chosen-Ciphertext Attack ↩
Optimal Asymmetric Encryption Padding ↩