Adaptive chosen-ciphertext attack

Charles Rackoff and Dan Simon defined CCA2 and suggested a system building on the non-adaptive CCA1 definition and system of Moni Naor and Moti Yung, which was the first treatment of chosen ciphertext attack immunity of public key systems.

In certain practical settings, the goal of the attack is gradually revealing information about an encrypted message or about the decryption key itself. For public-key systems, adaptive-chosen-ciphertexts are generally applicable only when they have the property of ciphertext malleability, when a ciphertext can be modified in specific ways that will have a predictable effect on the decryption of that message.

Practical attacks

Adaptive-chosen-ciphertext attacks were perhaps considered to be a theoretical concern but not to have been be manifested in practice until 1998, when Daniel Bleichenbacher (then of Bell Laboratories) demonstrated a practical attack against systems using RSA encryption in concert with the PKCS#1 v1.5 encoding function, including a version of the Secure Sockets Layer (SSL) protocol that was used by thousands of web servers at the time.

The Bleichenbacher attacks, also known as the million message attack, took advantage of flaws within the PKCS #1 v1.5 padding function to gradually reveal the content of an RSA encrypted message. Under this padding function, padded plaintexts have a fixed format that it should follow. If the decryption device (e.g. SSL-equipped web server) somehow reveals whether the padding is valid, it also serves as an "oracle" that reveals information on the secret key. Finding the whole key requires sending several million test ciphertexts to the target. In practical terms, this means that an SSL session key can be exposed in a reasonable amount of time, perhaps a day or less.

With slight variations, the vulnerability was still exploitable in many servers in 2018, under the new name "Return Of Bleichenbacher's Oracle Threat" (ROBOT), and again in 2023, as the Marvin Attack.