An adaptive chosen-ciphertext attack (CCA2) is an advanced form of chosen-ciphertext attack where an attacker adaptively submits multiple ciphertexts for decryption before attempting to distinguish a target ciphertext, without querying the challenge ciphertext itself. This attack extends the non-adaptive or indifferent CCA1 attack by allowing adaptive queries after the target is revealed. Introduced by Charles Rackoff and Dan Simon, the definition builds on earlier work by Moni Naor and Moti Yung. In public-key cryptography, CCA2 attacks exploit ciphertext malleability, enabling attackers to infer information about the encrypted message or the decryption key.
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 used by thousands of web servers at the time.1
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.2 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, this vulnerability was still exploitable in many servers in 2018, under the new name "Return Of Bleichenbacher's Oracle Threat" (ROBOT).3
Preventing attacks
In order to prevent adaptive-chosen-ciphertext attacks, it is necessary to use an encryption or encoding scheme that limits ciphertext malleability and a proof of security of the system. After the theoretical and foundation level development of CCA secure systems, a number of systems have been proposed in the Random Oracle model: the most common standard for RSA encryption is Optimal Asymmetric Encryption Padding (OAEP). Unlike improvised schemes such as the padding used in the early versions of PKCS#1, OAEP has been proven secure in the random oracle model,4 OAEP was incorporated into PKCS#1 as of version 2.0 published in 1998 as the now-recommended encoding scheme, with the older scheme still supported but not recommended for new applications.5 However, the golden standard for security is to show the system secure without relying on the Random Oracle idealization.6
Mathematical model
In complexity-theoretic cryptography, security against adaptive chosen-ciphertext attacks is commonly modeled using ciphertext indistinguishability (IND-CCA2).
References
Bleichenbacher, Daniel (August 23–27, 1998). Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1 (PDF). CRYPTO '98. Santa Barbara, California: Springer Berlin Heidelberg. pp. 1–12. doi:10.1007/BFb0055716. ISBN 978-3-540-64892-5. 978-3-540-64892-5 ↩
Pornin, Thomas (2014). "Can you explain Bleichenbacher's CCA attack on PKCS#1 v1.5?". Cryptography Stack Exchange. https://crypto.stackexchange.com/a/12706 ↩
Hanno Böck; Juraj Somorovsky; Craig Young. "ROBOT attack". Retrieved February 27, 2018. https://robotattack.org ↩
Fujisaki, Eiichiro; Okamoto, Tatsuaki; Pointcheval, David; Stern, Jacques (2004). "RSA-OAEP Is Secure under the RSA Assumption" (PDF). Journal of Cryptology. 17 (2): 81–104. CiteSeerX 10.1.1.11.7519. doi:10.1007/s00145-002-0204-y. S2CID 218582909. Retrieved 2009-01-12. https://www.di.ens.fr/~pointche/Documents/Papers/2004_joc.pdf ↩
Kaliski, B.; Staddon, J. (October 1998). PKCS #1: RSA Cryptography Specifications Version 2.0. IETF. doi:10.17487/RFC2437. RFC 2437. Retrieved February 20, 2019. https://datatracker.ietf.org/doc/html/rfc2437 ↩
Katz, Jonathan; Lindell, Yehuda (2015). Introduction to Modern Cryptography (2 ed.). Boca Raton: Chapman & Hall/CRC. pp. 174–175, 179–181. ISBN 978-1-4665-7027-6. 978-1-4665-7027-6 ↩