Hubbry Logo
Adaptive chosen-ciphertext attackAdaptive chosen-ciphertext attackMain
Open search
Adaptive chosen-ciphertext attack
Community hub
Adaptive chosen-ciphertext attack
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Adaptive chosen-ciphertext attack
Adaptive chosen-ciphertext attack
Adaptive chosen-ciphertext attack
View on Wikipedia
from Wikipedia

An adaptive chosen-ciphertext attack (abbreviated as CCA2) is an interactive form of chosen-ciphertext attack in which an attacker first sends a number of ciphertexts to be decrypted chosen adaptively, and then uses the results to distinguish a target ciphertext without consulting the oracle on the challenge ciphertext. In an adaptive attack, the attacker is further allowed adaptive queries to be asked after the target is revealed (but the target query is disallowed). It is extending the indifferent (non-adaptive) chosen-ciphertext attack (CCA1) where the second stage of adaptive queries is not allowed. 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 this attack is to gradually reveal 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 — that is, a ciphertext can be modified in specific ways that will have a predictable effect on the decryption of that message.

Practical attacks

[edit]

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

[edit]

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

[edit]

In complexity-theoretic cryptography, security against adaptive chosen-ciphertext attacks is commonly modeled using ciphertext indistinguishability (IND-CCA2).

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Adaptive chosen-ciphertext attack

View on Grokipedia
from Grokipedia
An adaptive chosen-ciphertext attack (CCA2) is an interactive adversarial model in public-key cryptography that assesses the security of encryption schemes by allowing an attacker access to a decryption oracle for any chosen ciphertext, with queries permitted both before and after the attacker receives a challenge ciphertext encoding one of two target messages; the sole restriction is that the challenge ciphertext itself cannot be submitted to the oracle. In this setup, the attacker's queries can adaptively depend on prior responses and the challenge, simulating a powerful eavesdropper who can exploit decryption capabilities to attempt breaking the scheme's confidentiality. Security under CCA2 is typically defined via IND-CCA2, where the scheme is secure if no probabilistic polynomial-time adversary can distinguish the challenge encryption of one message from the other with advantage greater than negligible. The foundations of chosen-ciphertext attacks trace back to the late and early , amid growing recognition that basic public-key schemes like RSA were vulnerable to active attacks beyond mere . In 1990, Moni Naor and Moti Yung introduced the first construction of a public-key cryptosystem provably secure against chosen-ciphertext attacks (CCA), albeit in a non-adaptive ("lunchtime") setting, by combining any secure with non-interactive zero-knowledge proofs to prevent malleability. This was extended to the adaptive case in 1991 by Charles Rackoff and Daniel R. Simon, who leveraged non-interactive zero-knowledge proofs of knowledge to achieve security against adversaries making post-challenge decryption queries, marking the birth of the CCA2 model. Subsequent formalization in by Mihir Bellare, Anand Desai, David Pointcheval, and Phillip Rogaway clarified the relationships among various security notions, establishing IND-CCA2 as the strongest standard for privacy in public-key and proving its equivalence to other robust definitions like non-malleability under CCA2. Today, IND-CCA2 is the benchmark for in standards like those from NIST for , essential for protocols including TLS, SSH, and where adversaries might control network elements or compromise partial systems. Constructions achieving IND-CCA2, such as OAEP and various hybrid schemes, rely on assumptions like the hardness of factoring or discrete logarithms, often in the model.

Introduction

Definition and overview

An adaptive chosen-ciphertext attack, often denoted as CCA2, models a where an adversary has access to a and can submit chosen of its choice for decryption, receiving the corresponding plaintexts, with the exception of a specific target challenge ciphertext; crucially, the adversary can adapt its subsequent queries based on the responses obtained from previous decryptions. This interactive access allows the attacker to refine its strategy progressively, simulating realistic threats in cryptographic systems where partial decryption capabilities might be available. The model was first formalized by Rackoff and Simon in their work on non-interactive zero-knowledge proofs, which strengthened prior notions by permitting post-challenge decryption queries to address limitations like "lunchtime attacks." In comparison to a (CPA), where the adversary is limited to an encryption oracle for generating ciphertexts from selected plaintexts without any decryption access, the adaptive CCA represents a significantly stronger adversarial capability. CPA security focuses on preventing information leakage from encryptions alone, whereas CCA incorporates decryption oracles to model environments like network protocols or services where an attacker might intercept and query modified messages, such as in compromised decryption endpoints. This distinction underscores CCA's relevance to practical deployments, as evidenced in analyses of public-key encryption schemes. The key threat in an adaptive CCA arises from the potential to exploit inherent weaknesses in schemes, such as malleability—where modifications to a predictably alter the underlying —or vulnerabilities in mechanisms that leak information through responses. For instance, in a hypothetical malleable scheme like unpadded RSA, an attacker could observe a target encrypting an unknown mm, then query the with a modified version obtained by multiplying the by a chosen factor rer^e (where ee is the public exponent and rr is known), receiving a m′=m⋅rm' = m \cdot r; by comparing m′m' to expected values or repeating with varied rr, the attacker could infer bits of the original mm. Security against adaptive CCA is formally captured by the indistinguishability under adaptive chosen-ciphertext attack (IND-CCA2) definition, which requires that no efficient adversary can distinguish encryptions of two chosen plaintexts even with oracle access.

Historical context

The concept of adaptive chosen-ciphertext attacks emerged in the late and early , coinciding with the rapid development of following the introduction of systems like RSA in 1978. Early work focused on strengthening against active adversaries who could query decryption oracles, building on notions of introduced by Goldwasser and Micali in 1982. A pivotal contribution came from Moni Naor and Moti Yung in 1990, who demonstrated a paradigm for constructing public-key cryptosystems provably secure against chosen-ciphertext attacks (CCS-PKC) using probabilistic and non-interactive zero-knowledge proofs, highlighting the implications for achieving in the presence of such threats. Key milestones in formalizing adaptive chosen-ciphertext security occurred in the early 1990s, building on Rackoff and Simon's 1991 introduction of the model, with Mihir Bellare and Phillip Rogaway's 1994 work on optimal asymmetric encryption, which analyzed and applied strong security notions including indistinguishability under adaptive chosen-ciphertext attack (IND-CCA2) to propose practical constructions like optimal asymmetric encryption padding (OAEP) secure against adaptive chosen-ciphertext attacks, addressing vulnerabilities in practical schemes like RSA. This formalization emphasized the need for encryption to withstand decryption queries even after seeing a target ciphertext, distinguishing it from weaker models. The practical urgency of these notions was underscored in 1998 by Daniel Bleichenbacher's adaptive chosen-ciphertext attack on RSA with PKCS#1 v1.5 padding, which exploited implementation flaws in SSL servers to decrypt messages using as few as a million oracle queries, exposing real-world risks in deployed systems. Following these developments, the post-2000 era saw increased emphasis on chosen-ciphertext security in cryptographic standards, particularly for protocols like TLS, where Bleichenbacher's attack prompted countermeasures such as strict padding validation and countermeasures against timing oracles in RFC 2246 (TLS 1.0, 1999) and subsequent versions. By the 2020s, as threats loomed, adaptive CCA resistance became integral to designs; for instance, the CRYSTALS-Kyber key encapsulation mechanism, selected by NIST, achieves IND-CCA2 security via the Fujisaki-Okamoto transform applied to its IND-CPA-secure base. This culminated in NIST's standardization of ML-KEM (based on ) in FIPS 203, which mandates IND-CCA2 security to ensure robustness against chosen-ciphertext attacks in quantum-resistant settings, alongside FIPS 204 for signatures.

Attack Models

Non-adaptive chosen-ciphertext attack

In the non-adaptive chosen-ciphertext attack model, also denoted as CCA1 or the "lunchtime" attack, an adversary obtains access to a and can submit chosen adaptively prior to receiving the target challenge , refining queries based on previous oracle responses, but without the capability for post-challenge queries or adaptation based on the challenge itself. This setup models a scenario of limited, temporary oracle access, where the attacker exploits the decryption mechanism interactively during a brief window like a lunch break when the key owner is unavailable—a term introduced by Naor and Yung to illustrate real-world constraints on attack feasibility. Security in this model ensures that even with such pre-challenge decryption queries, the adversary cannot distinguish between encryptions of two target messages, providing a baseline protection against pre-challenge probes but lacking robustness against more dynamic threats. Compared to stronger models, CCA1 is inherently weaker because it prohibits post-challenge query , preventing the capture of scenarios where attackers iteratively exploit partial information to escalate their assault. Early public-key constructions, including the original Naor-Yung based on probabilistic and non-interactive zero-knowledge proofs, achieved provable CCA1 under standard assumptions but failed against adaptive variants, influencing legacy analyses where full adaptivity was not yet prioritized. Nevertheless, CCA1 falls short in addressing persistent threats in contemporary systems, such as protocols, where adversaries can feasibly conduct repeated, evolving decryption queries across multiple interactions.

Adaptive chosen-ciphertext attack

An adaptive chosen-ciphertext attack (CCA2) models a powerful adversarial in where the attacker interacts dynamically with a decryption to compromise the of an encrypted message. In this model, the adversary aims to distinguish between encryptions of two target messages or recover the of a challenge through iterative queries. Unlike weaker models, CCA2 captures the full of a persistent attacker who can refine their strategy based on responses, making it a standard benchmark for secure schemes. The attack proceeds in phases, allowing the adversary adaptive access to the decryption oracle before and after receiving a challenge ciphertext. Initially, the adversary obtains the public key and may query the oracle with chosen ciphertexts c1,c2,…c_1, c_2, \dots to receive their corresponding plaintexts, gathering information about the system's behavior. The adversary then selects two equal-length messages m0m_0 and m1m_1, and a challenger encrypts one of them (chosen randomly) as the target ciphertext c∗c^*, providing it to the adversary. Subsequently, the adversary continues querying the oracle with new ciphertexts ci≠c∗c_i \neq c^*, using the returned plaintexts to inform further choices, ultimately attempting to guess which message was encrypted in c∗c^* or decrypt it directly. This process can be formalized in pseudocode as follows:

Adversary A on CCA2(pk): 1. For i = 1 to q1: // Pre-challenge phase Choose c_i m_i ← Dec(sk, c_i) // [Oracle](/page/Oracle) returns [plaintext](/page/Plaintext) Use m_i to adapt next choices 2. Choose m0, m1 of equal length b ← {0,1} randomly c* ← Enc(pk, m_b) // Challenge 3. For i = q1+1 to q_total: // Post-challenge phase Choose c_i ≠ c* m_i ← Dec(sk, c_i) Use m_i and prior info to adapt 4. Output guess b' for b

Adversary A on CCA2(pk): 1. For i = 1 to q1: // Pre-challenge phase Choose c_i m_i ← Dec(sk, c_i) // [Oracle](/page/Oracle) returns [plaintext](/page/Plaintext) Use m_i to adapt next choices 2. Choose m0, m1 of equal length b ← {0,1} randomly c* ← Enc(pk, m_b) // Challenge 3. For i = q1+1 to q_total: // Post-challenge phase Choose c_i ≠ c* m_i ← Dec(sk, c_i) Use m_i and prior info to adapt 4. Output guess b' for b

The decryption fully decrypts valid inputs except for the target c∗c^*, on which it aborts or returns an error, preventing direct revelation of the challenge while simulating a realistic "no invalid decryptions" policy in deployed systems. This assumption models active adversaries in environments like public key infrastructures (PKIs), where attackers might exploit decryption services without triggering alarms on the target itself. Compared to the non-adaptive variant (CCA1), which limits oracle access to before the challenge, CCA2's post-challenge queries better represent real-world threats involving persistent access, such as side-channel leaks or oracle exploitation in servers, where an attacker can iteratively probe over time. This enhanced interactivity underscores why CCA2 security is crucial for practical cryptosystems, as vulnerabilities allowing even limited post-challenge interactions can cascade into full breaks.

Formal Security Definitions

Indistinguishability under adaptive CCA

Indistinguishability under adaptive chosen-ciphertext attack (IND-CCA2) is a security notion for public-key encryption schemes that ensures against powerful adversaries. Specifically, a scheme is IND-CCA2 secure if no probabilistic polynomial-time (PPT) adversary can distinguish encryptions of two equal-length messages with non-negligible advantage, even when the adversary has adaptive access to a decryption for chosen ciphertexts. This notion formalizes in the presence of active attacks, where the adversary can query the decryption of arbitrary ciphertexts before and after receiving a challenge. The core mechanism of IND-CCA2 involves a left-right challenge oracle: the adversary selects two messages m0m_0 and m1m_1 of equal length, and a challenger randomly selects a bit b∈{0,1}b \in \{0,1\} to encrypt and return Enc(pk,mb)\text{Enc}(pk, m_b) as the challenge ciphertext, without revealing bb. To prevent trivial attacks, the adversary's decryption queries are restricted—it cannot directly query the decryption of the challenge ciphertext itself. IND-CCA2 implies indistinguishability under (IND-CPA), the standard notion, but is strictly stronger due to the adversary's decryption access, which simulates real-world malleability exploits. Constructions achieving only IND-CPA may fail under CCA2, as decryption oracles can leak information about plaintexts. This underscores IND-CCA2 as the gold standard for practical public-key , ensuring robustness against sophisticated attacks. In modern , IND-CCA2 security is a desirable property for standards involving long-term public keys, such as extensions to the (CMS) for post-quantum algorithms, to protect against active adversaries in protocols like secure email and document signing. Similarly, implementations, which form the basis of CMS, benefit from IND-CCA2-compliant primitives to mitigate vulnerabilities in hybrid setups.

Game-based security proofs

Game-based security proofs formalize the IND-CCA2 security notion through an interactive game between a probabilistic polynomial-time adversary A\mathcal{A} and a challenger, ensuring that no efficient adversary can distinguish between encryptions of two chosen plaintexts with non-negligible advantage. The game proceeds in phases: first, the challenger generates key pairs for a public-key encryption scheme and provides the public key to A\mathcal{A}; A\mathcal{A} then adaptively queries an encryption oracle to obtain ciphertexts of chosen plaintexts and a decryption oracle to learn plaintexts from chosen ciphertexts, excluding the eventual challenge; next, A\mathcal{A} submits two equal-length plaintexts m0,m1m_0, m_1, and the challenger selects a random bit b∈{0,1}b \in \{0,1\}, encrypts mbm_b as the challenge ciphertext c∗c^*, and returns it to A\mathcal{A}; A\mathcal{A} continues querying the decryption oracle on arbitrary ciphertexts except c∗c^*; finally, A\mathcal{A} outputs a guess b′b' for bb. The adversary wins if b′=bb' = b. The security requirement is that for any efficient A\mathcal{A}, the winning probability Pr⁡[b′=b]\Pr[b' = b] is at most 1/2+ϵ(λ)1/2 + \epsilon(\lambda), where ϵ(λ)\epsilon(\lambda) is negligible in the security parameter λ\lambda. The advantage is formally defined as AdvA,ΠIND-CCA2(λ)=∣Pr⁡[b′=b]−12∣,\text{Adv}^{\text{IND-CCA2}}_{\mathcal{A},\Pi}(\lambda) = \left| \Pr[b' = b] - \frac{1}{2} \right|,
Add your contribution
Related Hubs
User Avatar
No comments yet.