Hubbry Logo
Chosen-ciphertext attackChosen-ciphertext attackMain
Open search
Chosen-ciphertext attack
Community hub
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.
Chosen-ciphertext attack
Chosen-ciphertext attack
Chosen-ciphertext attack
View on Wikipedia
from Wikipedia

A chosen-ciphertext attack (CCA) is an attack model for cryptanalysis where the cryptanalyst can gather information by obtaining the decryptions of chosen ciphertexts. From these pieces of information the adversary can attempt to recover the secret key used for decryption.

For formal definitions of security against chosen-ciphertext attacks, see for example: Michael Luby[1] and Mihir Bellare et al.[2]

Introduction

[edit]

A number of otherwise secure schemes can be defeated under chosen-ciphertext attack. For example, the El Gamal cryptosystem is semantically secure under chosen-plaintext attack, but this semantic security can be trivially defeated under a chosen-ciphertext attack. Early versions of RSA padding used in the SSL protocol were vulnerable to a sophisticated adaptive chosen-ciphertext attack which revealed SSL session keys. Chosen-ciphertext attacks have implications for some self-synchronizing stream ciphers as well. Designers of tamper-resistant cryptographic smart cards must be particularly cognizant of these attacks, as these devices may be completely under the control of an adversary, who can issue a large number of chosen-ciphertexts in an attempt to recover the hidden secret key.

It was not clear at all whether public key cryptosystems could withstand the chosen ciphertext attack until the initial breakthrough work of Moni Naor and Moti Yung in 1990, which suggested a mode of dual encryption with integrity proof (now known as the "Naor-Yung" encryption paradigm).[3] This work made understanding of the notion of security against chosen ciphertext attack much clearer than before and open the research direction of constructing systems with various protections against variants of the attack.

When a cryptosystem is vulnerable to chosen-ciphertext attack, implementers must be careful to avoid situations in which an adversary might be able to decrypt chosen-ciphertexts (i.e., avoid providing a decryption oracle). This can be more difficult than it appears, as even partially chosen ciphertexts can permit subtle attacks. Additionally, other issues exist and some cryptosystems (such as RSA) use the same mechanism to sign messages and to decrypt them. This permits attacks when hashing is not used on the message to be signed. A better approach is to use a cryptosystem which is provably secure under chosen-ciphertext attack, including (among others) RSA-OAEP secure under the random oracle heuristics, Cramer-Shoup which was the first public key practical system to be secure. For symmetric encryption schemes it is known that authenticated encryption which is a primitive based on symmetric encryption gives security against chosen ciphertext attacks, as was first shown by Jonathan Katz and Moti Yung.[4]

Varieties

[edit]

Chosen-ciphertext attacks, like other attacks, may be adaptive or non-adaptive. In an adaptive chosen-ciphertext attack, the attacker can use the results from prior decryptions to inform their choices of which ciphertexts to have decrypted. In a non-adaptive attack, the attacker chooses the ciphertexts to have decrypted without seeing any of the resulting plaintexts. After seeing the plaintexts, the attacker can no longer obtain the decryption of additional ciphertexts.

Lunchtime attacks

[edit]

A specially noted variant of the chosen-ciphertext attack is the "lunchtime", "midnight", or "indifferent" attack, in which an attacker may make adaptive chosen-ciphertext queries but only up until a certain point, after which the attacker must demonstrate some improved ability to attack the system.[5] The term "lunchtime attack" refers to the idea that a user's computer, with the ability to decrypt, is available to an attacker while the user is out to lunch. This form of the attack was the first one commonly discussed: obviously, if the attacker has the ability to make adaptive chosen ciphertext queries, no encrypted message would be safe, at least until that ability is taken away. This attack is sometimes called the "non-adaptive chosen ciphertext attack";[6] here, "non-adaptive" refers to the fact that the attacker cannot adapt their queries in response to the challenge, which is given after the ability to make chosen ciphertext queries has expired.

Adaptive chosen-ciphertext attack

[edit]
Main article: Adaptive chosen-ciphertext attack

A (full) adaptive chosen-ciphertext attack is an attack in which ciphertexts may be chosen adaptively before and after a challenge ciphertext is given to the attacker, with only the stipulation that the challenge ciphertext may not itself be queried. This is a stronger attack notion than the lunchtime attack, and is commonly referred to as a CCA2 attack, as compared to a CCA1 (lunchtime) attack.[6] Few practical attacks are of this form. Rather, this model is important for its use in proofs of security against chosen-ciphertext attacks. A proof that attacks in this model are impossible implies that any realistic chosen-ciphertext attack cannot be performed.

A practical adaptive chosen-ciphertext attack is the Bleichenbacher attack against PKCS#1.[7]

Numerous cryptosystems are proven secure against adaptive chosen-ciphertext attacks, some proving this security property based only on algebraic assumptions, some additionally requiring an idealized random oracle assumption. For example, the Cramer-Shoup system[5] is secure based on number theoretic assumptions and no idealization, and after a number of subtle investigations it was also established that the practical scheme RSA-OAEP is secure under the RSA assumption in the idealized random oracle model.[8]

See also

[edit]

References

[edit]

Further reading

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Chosen-ciphertext attack

View on Grokipedia
from Grokipedia
A chosen-ciphertext attack (CCA) is a cryptanalytic technique in which an adversary selects arbitrary ciphertexts and obtains their corresponding decryptions, typically via access to a decryption , to infer information about secret keys or other plaintexts. This attack model assumes the adversary operates in a scenario where they can interact adaptively with the decryption process, making it more powerful than a (CPA) by simulating real-world active adversaries who can tamper with or probe encrypted communications. In formal terms, CCA security for an encryption scheme is defined through an indistinguishability game where the adversary, given access to a decryption for all ciphertexts except a challenge one, must distinguish between encryptions of two chosen messages with only negligible advantage over random guessing. The CCA model emerged as a critical standard for evaluating public-key encryption schemes in the 1990s, highlighting vulnerabilities in systems like the one-time pad or basic block cipher modes (e.g., CTR or CBC without authentication), which fail under decryption oracle access due to malleability or predictable responses. A notable real-world example is Bleichenbacher's 1998 attack on RSA with PKCS#1 v1.5 padding, where an attacker exploits error messages from a server during decryption attempts on chosen ciphertexts to iteratively narrow down the plaintext, potentially recovering the entire message after millions of queries. Such attacks underscore the need for CCA-secure constructions, often achieved by combining CPA-secure encryption with message authentication codes (MACs) or using padding schemes like OAEP (Optimal Asymmetric Encryption Padding). CCA security remains essential for modern cryptographic protocols, such as those in TLS/SSL, where unauthenticated ciphertexts could otherwise leak sensitive data through side-channel observations during decryption. While basic schemes like textbook RSA are inherently vulnerable, provably secure alternatives ensure robustness against adaptive adversaries, influencing standards from bodies like NIST.

Fundamentals

Overview of cryptographic attacks

Cryptographic attacks are categorized into passive and active types based on the adversary's level of interaction with the system. Passive attacks, such as ciphertext-only or known-plaintext attacks, involve an eavesdropper who observes communications without modifying or influencing the process, aiming to extract information solely from intercepted data. In contrast, active attacks require the adversary to interact directly with the , potentially altering messages or exploiting system components to gain unauthorized access or recover secrets; chosen-ciphertext attacks (CCA) exemplify this category by involving queries to decryption mechanisms. A foundational in active attack models is the (CPA), where the adversary gains access to an oracle that encrypts arbitrarily selected plaintexts under the target's key, allowing analysis of the resulting ciphertexts to uncover patterns or weaknesses in the scheme. This model formalizes scenarios where an attacker can influence the process, such as by submitting chosen messages to a compromised device, and serves as a baseline for evaluating , ensuring that even with such access, the adversary cannot distinguish encryptions of different messages. The evolution of these attack models began with basic eavesdropping assumptions in early cryptography, rooted in Shannon's perfect secrecy paradigm from the 1940s, but shifted toward interactive oracles in the 1980s and 1990s as public-key systems emerged. Seminal works, including Goldwasser and Micali's 1982 introduction of probabilistic encryption and semantic security, formalized CPA-like models to address limitations of deterministic schemes vulnerable to chosen inputs. By the 1990s, definitions incorporated stronger adversaries with oracle access, reflecting real-world threats like malleable ciphertexts in protocols. CCA builds directly on the CPA framework by augmenting the adversary's capabilities with access to a decryption , enabling queries on chosen ciphertexts (excluding the challenge) and thus simulating more realistic active tampering, which elevates the threat level beyond mere observation. This progression underscores the need for cryptosystems resilient to interactive decryption queries, as passive or CPA-secure schemes often fail under such conditions.

Role of decryption oracles

In chosen-ciphertext attacks, the decryption serves as a critical interactive component, modeled as a that allows an adversary to submit arbitrary for decryption under the target's secret key. Upon receiving a valid as input, the outputs the corresponding ; for invalid inputs, it typically returns an indicator of failure, such as an or rejection signal, without revealing additional details about the decryption process. This access enables the adversary to explore the encryption scheme's behavior across a wide range of inputs, but the excludes queries on the specific challenge to prevent trivial recovery of the target message. The mechanics of the decryption highlight vulnerabilities arising from malleability, where an adversary can construct modified versions of observed —such as by altering bits or —and submit them to the to obtain partial information about the underlying . For instance, if the scheme permits predictable changes to the ciphertext that correspond to changes in the (e.g., in a basic XOR-based using a pseudorandom function), querying the on a modified ciphertext c′=c⊕δc' = c \oplus \delta might yield m′=m⊕δm' = m \oplus \delta, allowing the adversary to infer bits of the original mm by reversing the modification. Such interactions expose risks in schemes lacking integrity protection, as the effectively provides feedback on the scheme's deterministic or probabilistic responses to tampering. Unlike the encryption oracle in chosen-plaintext attacks (CPA), which only permits the adversary to obtain encryptions of chosen plaintexts and limits threats to passive observation, the decryption oracle in CCA grants active access to the decryption functionality, dramatically escalating the by enabling manipulation and verification of ciphertexts. This distinction underscores why CCA represents a stronger adversarial model: decryption queries allow testing of scheme weaknesses like malleability or inconsistencies that CPA cannot capture, potentially revealing key material or message contents indirectly.

Core Concepts

Formal definition of CCA

A chosen-ciphertext attack (CCA) is formally defined in the context of public-key schemes as a security game between a probabilistic polynomial-time (PPT) adversary A\mathcal{A} and a challenger, where A\mathcal{A} aims to distinguish between encryptions of two messages it selects while interacting with encryption and decryption oracles. The game proceeds in phases: first, the challenger generates a public key pkpk and a corresponding secret key sksk using the key generation algorithm Gen(1λ)\mathsf{Gen}(1^\lambda), where λ\lambda is the security parameter, and provides pkpk to A\mathcal{A}. In the pre-challenge phase, A\mathcal{A} may query the oracle OEnc\mathcal{O}_\mathsf{Enc}, which on input a message mm returns Enc(pk,m)\mathsf{Enc}(pk, m), and the decryption oracle ODec\mathcal{O}_\mathsf{Dec}, which on input a cc returns Dec(sk,c)\mathsf{Dec}(sk, c) (or ⊥\perp if invalid). A\mathcal{A} can make polynomially many such queries. Then, in the challenge phase, A\mathcal{A} submits two equal-length messages m0m_0 and m1m_1, and the challenger selects a random bit b∈{0,1}b \in \{0,1\}, computes the challenge ciphertext c∗=Enc(pk,mb;r)c^* = \mathsf{Enc}(pk, m_b; r) for random coins rr, and sends c∗c^* to A\mathcal{A}. Following the challenge, A\mathcal{A} resumes querying the oracles, but is restricted from submitting c∗c^* to ODec\mathcal{O}_\mathsf{Dec}. Finally, A\mathcal{A} outputs a guess b′b' for bb. The adversary A\mathcal{A} wins the game if b′=bb' = b. The scheme is CCA-secure if for every PPT adversary A\mathcal{A}, the winning probability satisfies Pr⁡[A wins]=12+ϵ(λ),\Pr[\mathcal{A} \text{ wins}] = \frac{1}{2} + \epsilon(\lambda), where ϵ(λ)\epsilon(\lambda) is a in the security parameter λ\lambda. This advantage ϵ\epsilon measures A\mathcal{A}'s ability to distinguish m0m_0 from m1m_1 beyond random guessing, derived from the experiment's structure: the pre- and post-challenge queries model access to a decryption , while the challenge tests indistinguishability under this access, with the restriction on c∗c^* preventing trivial wins. This definition assumes a PPT adversary and may be analyzed in the model for certain constructions, though the core game holds in the .

Adversary capabilities

In the chosen-ciphertext attack (CCA) model, the adversary is modeled as a probabilistic polynomial-time (PPT) algorithm that interacts with and decryption oracles to attempt to compromise the of a public-key scheme. This adversary possesses the public key but has no access to the corresponding private key, ensuring that it cannot perform unrestricted decryptions on its own. The PPT constraint limits the adversary's computational resources to those feasible within polynomial time relative to the security parameter, reflecting realistic attacker capabilities in cryptographic analysis. The primary capabilities of the CCA adversary include making polynomially many queries to an oracle, allowing it to obtain ciphertexts for arbitrarily chosen plaintexts, and querying a oracle with chosen ciphertexts to receive their corresponding plaintexts. However, a key constraint prohibits the adversary from submitting the challenge ciphertext—the encryption of one of two target plaintexts chosen by the challenger—to the oracle, preventing direct recovery of the . These oracle interactions enable the adversary to probe the system's behavior extensively, but the exclusion of the challenge query maintains the integrity of the security experiment. Strategically, the adversary aims to exploit these oracle accesses to recover the of the challenge ciphertext, break by distinguishing between encryptions of two related messages, or, in broader applications such as hybrid schemes, digital signatures by leveraging malleability in the ciphertexts. This setup captures scenarios where the adversary seeks to undermine or through adaptive interactions, without direct key compromise. In real-world terms, the CCA adversary models an attacker who gains temporary or indirect access to a decryption device or service—such as by exploiting a protocol —but remains blind to the specific target message, relying on manipulated inputs to infer sensitive information.

Variants

Non-adaptive CCA (lunchtime attack)

A non-adaptive chosen-ciphertext attack, also known as a lunchtime attack or CCA1, permits an adversary to submit a batch of chosen ciphertexts to a decryption prior to receiving a challenge ciphertext, but prohibits any further queries afterward. In this model, the adversary's decryption queries are completed in a single phase, simulating a limited access window to the , after which the challenge—typically an encryption of one of two target plaintexts under the public key—is issued, and the adversary must distinguish the challenge without additional interactions. The term "lunchtime attack" was introduced by Mihir Bellare and Phillip Rogaway in their paper on security notions for public-key encryption, evoking the scenario of an attacker exploiting a brief, temporary opportunity to access decryption capabilities, such as during an unattended period. This nomenclature highlights the non-adaptive constraint, where the attacker's preparations must be finalized before the challenge, contrasting with more flexible threat models. A classic example of a non-adaptive CCA exploits the structure of Rabin's cryptosystem, where encryption computes the quadratic residue c=m2mod  nc = m^2 \mod n for modulus n=pqn = pq and plaintext mm. An adversary selects a random xx, computes c=x2mod  nc = x^2 \mod n, and queries the decryption oracle to obtain a square root yy of cc modulo nn. With probability 1/2, y≢±xmod  ny \not\equiv \pm x \mod n, allowing the computation of gcd⁡(y−x,n)\gcd(y - x, n) to reveal a non-trivial factor of nn, thus recovering the private keys pp and qq and enabling decryption of any ciphertext, including the subsequent challenge. This variant is inherently weaker than adaptive chosen-ciphertext attacks, as the absence of post-challenge queries limits the adversary's ability to refine strategies based on the target ciphertext. Consequently, numerous encryption schemes achieve security against non-adaptive CCA—such as basic ElGamal with certain modifications—but remain vulnerable to stronger adaptive threats, underscoring the need for robust defenses in practical deployments.

Adaptive CCA

In adaptive chosen-ciphertext attacks (CCA), also known as IND-CCA2, the adversary is permitted to query a decryption in two distinct phases: first, before receiving the challenge , and second, after observing the challenge, with the restriction that the challenge itself cannot be submitted for decryption. This model allows the attacker to interact dynamically with the decryption mechanism, simulating more realistic scenarios where an adversary can adapt strategies based on partial information gained during the attack. The primary advantage for the attacker lies in the ability to iteratively refine their approach, particularly through post-challenge queries that enable probing of ciphertexts closely related to the challenge without directly decrypting it, thereby narrowing down possible plaintexts or keys over multiple rounds. In contrast to non-adaptive CCA, this phased querying overcomes limitations of static pre-challenge interactions by incorporating feedback loops that amplify the attack's effectiveness in exploiting implementation flaws. A prominent example is Bleichenbacher's 1998 attack on RSA encryption with v1.5 , where the adversary exploits an adaptive —revealing whether a has valid —to iteratively decrypt the target message through thousands of carefully crafted queries, often requiring as few as 20,000 calls in practice. This attack highlighted the vulnerability of common schemes to adaptive exploitation, leading to widespread implementation fixes in protocols like SSL/TLS. Subsequent variants of Bleichenbacher-style attacks have continued to expose vulnerabilities in real-world systems. The attack, disclosed in 2018, exploited padding oracles in RSA across multiple TLS implementations and protocols, enabling cross-protocol attacks to recover session keys with as few as hundreds of thousands of queries. More recently, the Marvin attack, described in 2023, introduced a timing-based variant that bypasses some constant-time mitigations, allowing attackers to mount Bleichenbacher-like oracles through side-channel observations on decryption timing, affecting libraries like NSS. These developments underscore the ongoing challenges in achieving full practical security against adaptive CCA, even with theoretical provability. Following real-world demonstrations of such vulnerabilities in the late , the adaptive CCA model became the standard benchmark for secure public-key encryption schemes in modern , influencing the design of provably secure systems like Cramer-Shoup from onward. This shift emphasized the need for robustness against dynamic adversaries, solidifying IND-CCA2 as the gold standard for evaluating encryption security post-.

Security Models

IND-CCA1 security

IND-CCA1 security, also known as indistinguishability under non-adaptive , is a security model for public-key encryption schemes that captures resistance to adversaries who can query a only before receiving a challenge ciphertext. In this model, the adversary's ability to distinguish between encryptions of two chosen plaintexts is limited, with its advantage defined as negligible in the security parameter after pre-challenge queries only. The IND-CCA1 security game proceeds in the following phases: first, the challenger runs the key generation algorithm to produce a public key pkpk and secret key sksk, providing pkpk to the probabilistic polynomial-time (PPT) adversary A\mathcal{A}. Next, in the pre-challenge phase, A\mathcal{A} adaptively queries a decryption oracle Decsk(⋅)\mathsf{Dec}_{sk}(\cdot) on ciphertexts of its choice, receiving the corresponding plaintexts, but cannot query the challenge ciphertext once issued. The adversary then selects two equal-length plaintexts m0m_0 and m1m_1, and the challenger picks a random bit b∈{0,1}b \in \{0,1\}, computes the challenge ciphertext c∗=Encpk(mb)c^* = \mathsf{Enc}_{pk}(m_b), and sends c∗c^* to A\mathcal{A}. Finally, without access to any further oracle queries, A\mathcal{A} outputs a guess b′b' for bb. A public-key scheme is IND-CCA1 if, for all PPT adversaries A\mathcal{A}, the advantage in this game is . The advantage is formally defined as ∣Pr⁡[b′=b]−12∣≤negl(n),\left| \Pr[b' = b] - \frac{1}{2} \right| \leq \mathsf{negl}(n),
Add your contribution
Related Hubs
User Avatar
No comments yet.