HOME

TheInfoList



OR:

A chosen-ciphertext attack (CCA) is an
attack model In cryptanalysis, attack models or attack types are a classification of cryptographic attacks specifying the kind of access a Cryptanalysis, cryptanalyst has to a system under attack when attempting to "break" an Encryption, encrypted message (also ...
for
cryptanalysis Cryptanalysis (from the Greek ''kryptós'', "hidden", and ''analýein'', "to analyze") refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic sec ...
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 hidden secret key used for decryption. For formal definitions of security against chosen-ciphertext attacks, see for example:
Michael Luby Michael George Luby is a mathematician and computer scientist, CEO of BitRipple, Senior Research Scientist at the International Computer Science Institute (ICSI), former VP Technology at Qualcomm, co-founder and former Chief Technology Officer ...
and
Mihir Bellare Mihir Bellare is a cryptographer and professor at the University of California San Diego. He has published several seminal papers in the field of cryptography (notably in the area of provable security), many of which were co-written with Phillip R ...
et al.


Introduction

A number of otherwise secure schemes can be defeated under chosen-ciphertext attack. For example, the
El Gamal In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1985. ElGamal encryption is used in the ...
cryptosystem is
semantically secure In cryptography, a semantically secure cryptosystem is one where only negligible information about the plaintext can be feasibly extracted from the ciphertext. Specifically, any probabilistic, polynomial-time algorithm (PPTA) that is given the cip ...
under
chosen-plaintext attack A chosen-plaintext attack (CPA) is an attack model for cryptanalysis which presumes that the attacker can obtain the ciphertexts for arbitrary plaintexts.Ross Anderson, ''Security Engineering: A Guide to Building Dependable Distributed Systems''. ...
, 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 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 tar ...
which revealed SSL session keys. Chosen-ciphertext attacks have implications for some self-synchronizing
stream cipher stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream ...
s as well. Designers of tamper-resistant cryptographic
smart card A smart card, chip card, or integrated circuit card (ICC or IC card) is a physical electronic authentication device, used to control access to a resource. It is typically a plastic credit card-sized card with an embedded integrated circuit (IC) c ...
s 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 can withstand the chosen ciphertext attack until the initial breakthrough work of
Moni Naor Moni Naor ( he, מוני נאור) is an Israeli Israeli may refer to: * Something of, from, or related to the State of Israel * Israelis, citizens or permanent residents of the State of Israel * Modern Hebrew, a language * ''Israeli'' (news ...
and
Moti Yung Mordechai M. "Moti" Yung is a cryptographer and computer scientist known for his work on cryptovirology and kleptography. Career Yung earned his PhD from Columbia University in 1988 under the supervision of Zvi Galil. In the past, he worked at the ...
in 1990, which suggested a mode of dual encryption with
integrity Integrity is the practice of being honest and showing a consistent and uncompromising adherence to strong moral and ethical principles and values. In ethics, integrity is regarded as the honesty and truthfulness or accuracy of one's actions. Inte ...
proof (now known as the "Naor-Yung" encryption paradigm). 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 Hash, hashes, hash mark, or hashing may refer to: Substances * Hash (food), a coarse mixture of ingredients * Hash, a nickname for hashish, a cannabis product Hash mark *Hash mark (sports), a marking on hockey rinks and gridiron football field ...
is not used on the message to be signed. A better approach is to use a cryptosystem which is
provably secure Provable security refers to any type or level of computer security that can be proved. It is used in different ways by different fields. Usually, this refers to mathematical proofs, which are common in cryptography. In such a proof, the capabiliti ...
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 Authenticated Encryption (AE) and Authenticated Encryption with Associated Data (AEAD) are forms of encryption which simultaneously assure the confidentiality and authenticity of data. Programming interface A typical application programming in ...
which is a primitive based on
symmetric encryption Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both the encryption of plaintext and the decryption of ciphertext. The keys may be identical, or there may be a simple transformation to go between th ...
gives security against chosen ciphertext attacks, as was first shown by
Jonathan Katz Jonathan Paul Katz (born December 1, 1946) is an American actor and comedian best known for his starring role in the animated sitcom ''Dr. Katz, Professional Therapist'' as Dr. Katz. He also is known for voicing Erik Robbins in the UPN/Adult Swi ...
and
Moti Yung Mordechai M. "Moti" Yung is a cryptographer and computer scientist known for his work on cryptovirology and kleptography. Career Yung earned his PhD from Columbia University in 1988 under the supervision of Zvi Galil. In the past, he worked at the ...
.


Varieties

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

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.
Ronald Cramer Ronald John Fitzgerald Cramer (born 3 February 1968 in Haarlem) is a professor at the Centrum Wiskunde & Informatica (CWI) in Amsterdam and the University of Leiden. He obtained his PhD from the University of Amsterdam in 1997. Prior to returning to ...
and
Victor Shoup Victor Shoup is a computer scientist and mathematician. He obtained a PhD in computer science from the University of Wisconsin–Madison in 1989, and he did his undergraduate work at the University of Wisconsin-Eau Claire. He is a professor at t ...
,
A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack
, in Advances in Cryptology --
CRYPTO Crypto commonly refers to: * Cryptocurrency, a type of digital currency secured by cryptography and decentralization * Cryptography, the practice and study of hiding information Crypto or Krypto may also refer to: Cryptography * Cryptanalysis, ...
'98 proceedings,
Santa Barbara, California Santa Barbara ( es, Santa Bárbara, meaning "Saint Barbara") is a coastal city in Santa Barbara County, California, of which it is also the county seat. Situated on a south-facing section of coastline, the longest such section on the West Coas ...
, 1998, pp. 13-25. (
article Article often refers to: * Article (grammar), a grammatical element used to indicate definiteness or indefiniteness * Article (publishing), a piece of nonfictional prose that is an independent part of a publication Article may also refer to: G ...
)
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";
Mihir Bellare Mihir Bellare is a cryptographer and professor at the University of California San Diego. He has published several seminal papers in the field of cryptography (notably in the area of provable security), many of which were co-written with Phillip R ...
,
Anand Desai Anand may refer to: People * Anand (name), a surname and given name (including a list of people with the name) * Anand (actor), Indian actor * Anand (Maoist), Indian communist * Anand (writer) (born 1936), Indian Malayalam writer Places * Anan ...
,
David Pointcheval David Pointcheval is a French cryptographer. He is currently a Senior Researcher at CNRS. He is head of the Computer Science Department and Cryptography Laboratory at the École normale supérieure. He is mainly known for his contributions in the a ...
, and
Phillip Rogaway Phillip Rogaway is a professor of computer science at the University of California, Davis. He graduated from Beverly Hills High School, and later earned a BA in computer science from UC Berkeley and completed his PhD in cryptography at MIT, in ...

Relations among Notions of Security for Public-Key Encryption Schemes
in Advances in Cryptology -- CRYPTO '98, Santa Barbara, California, pp. 549-570.
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

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. 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. 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 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. M. Bellare, P. Rogaway ''Optimal Asymmetric Encryption -- How to encrypt with RSA'' extended abstract in Advances in Cryptology - Eurocrypt '94 Proceedings, Lecture Notes in Computer Science Vol. 950, A. De Santis ed,
Springer-Verlag Springer Science+Business Media, commonly known as Springer, is a German multinational publishing company of books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing. Originally founded in 1842 in ...
, 1995.
full version (pdf)


See also


Dancing on the Lip of the Volcano: Chosen Ciphertext Attacks on Apple iMessage (Usenix 2016)


References

{{DEFAULTSORT:Chosen-Ciphertext Attack Cryptographic attacks