Chosen-ciphertext attack

Encyclopedia

A

for cryptanalysis

in which the cryptanalyst gathers information, at least in part, by choosing a ciphertext

and obtaining its decryption under an unknown key. In the attack, an adversary has a chance to enter one or more known ciphertexts into the system and obtain the resulting plaintexts. From these pieces of information the adversary can attempt to recover the hidden secret key used for decryption.

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 cipher

s as well. Designers of tamper-resistant cryptographic smart card

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.

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, 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

, Cramer-Shoup and many forms of authenticated

symmetric encryption.

A practical adaptive chosen-ciphertext attack is the Bleichenbacher attack against PKCS#1

.

Cryptosystems proven secure against adaptive chosen-ciphertext attacks include the Cramer-Shoup system and RSA-OAEP.

**chosen-ciphertext attack (CCA)**is an attack modelAttack model

Attack models or attack types specify how much information a cryptanalyst has access to when cracking an encrypted message...

for cryptanalysis

Cryptanalysis

Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...

in which the cryptanalyst gathers information, at least in part, by choosing a ciphertext

Ciphertext

In cryptography, ciphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher...

and obtaining its decryption under an unknown key. In the attack, an adversary has a chance to enter one or more known ciphertexts into the system and obtain the resulting plaintexts. From these pieces of information the adversary can attempt to recover the hidden secret key used for decryption.

A number of otherwise secure schemes can be defeated under chosen-ciphertext attack. For example, the El Gamal cryptosystem is semantically secure

Semantic security

Semantic security is a widely used definition for security in an asymmetric key encryption algorithm. For a cryptosystem to be semantically secure, it must be infeasible for a computationally bounded adversary to derive significant information about a message when given only its ciphertext and...

under chosen-plaintext attack

Chosen-plaintext attack

A chosen-plaintext attack is an attack model for cryptanalysis which presumes that the attacker has the capability to choose arbitrary plaintexts to be encrypted and obtain the corresponding ciphertexts. The goal of the attack is to gain some further information which reduces the security of the...

, 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

Adaptive chosen-ciphertext attack

An adaptive chosen-ciphertext attack is an interactive form of chosen-ciphertext attack in which an attacker sends a number of ciphertexts to be decrypted, then uses the results of these decryptions to select subsequent ciphertexts...

which revealed SSL session keys. Chosen-ciphertext attacks have implications for some self-synchronizing stream cipher

Stream cipher

In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...

s as well. Designers of tamper-resistant cryptographic smart card

Smart card

A smart card, chip card, or integrated circuit card , is any pocket-sized card with embedded integrated circuits. A smart card or microprocessor cards contain volatile memory and microprocessor components. The card is made of plastic, generally polyvinyl chloride, but sometimes acrylonitrile...

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.

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, some cryptosystems (such as RSA) use the same mechanism to sign messages and to decrypt them. This permits attacks when hashing

Cryptographic hash function

A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...

is not used on the message to be signed. A better approach is to use a cryptosystem which is provably secure

Provable security

In cryptography, a system has provable security if its security requirements can be stated formally in an adversarial model, as opposed to heuristically, with clear assumptions that the adversary has access to the system as well as enough computational resources...

under chosen-ciphertext attack, including (among others) RSA-OAEP

Optimal Asymmetric Encryption Padding

In cryptography, Optimal Asymmetric Encryption Padding is a padding scheme often used together with RSA encryption. OAEP was introduced by Bellare and Rogaway....

, Cramer-Shoup and many forms of authenticated

Authenticated encryption

Authenticated Encryption is a block cipher mode of operation which simultaneously provides confidentiality, integrity and authenticity assurances on the data. It became readily apparent that securely compositing a confidentiality mode with an authentication mode could be error prone and difficult...

symmetric encryption.

## Varieties of chosen-ciphertext attacks

Chosen-ciphertext attacks, like other attacks, may be adaptive or non-adaptive. In a non-adaptive attack, the attacker chooses the ciphertext or ciphertexts to decrypt in advance, and does not use the resulting plaintexts to inform their choice for more ciphertexts. In an adaptive chosen-ciphertext attack, the attacker makes their ciphertext choices adaptively, that is, depending on the result of prior decryptions.### 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. 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"; 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

PKCS1

In cryptography, PKCS#1 is the first of a family of standards called Public-Key Cryptography Standards , published by RSA Laboratories. It provides the basic definitions of and recommendations for implementing the RSA algorithm for public-key cryptography...

.

Cryptosystems proven secure against adaptive chosen-ciphertext attacks include the Cramer-Shoup system and RSA-OAEP.