Chosen-ciphertext attack

A chosen-ciphertext attack (CCA) is an attack model for cryptanalysis in which the cryptanalyst gathers information, at least in part, by choosing a ciphertext and obtaining its decryption under an unknown key.

When a cryptosystem is susceptible to chosen-ciphertext attack, implementers must be careful to avoid situations in which an attackers might be able to decrypt chosen ciphertexts (i.e., avoid providing a decryption scheme). 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.

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" or "midnight" 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.[1] 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";[2] 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.

Many chosen-ciphertext attacks of practical importance are lunchtime attacks, including, for instance, when Daniel Bleichenbacher of Bell Laboratories demonstrated a practical attack against systems using the PKCS#1; invented and published by RSA Security.[3]

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 ONE condition 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.[2] 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 practical chosen-ciphertext attack cannot be performed.

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

Related pages

References

  1. 1.0 1.1 Ronald Cramer and Victor Shoup, "A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack[dead link]", in Advances in Cryptology – CRYPTO '98 proceedings, Santa Barbara, California, 1998, pp. 13–25. (article)
  2. 2.0 2.1 Mihir Bellare, Anand Desai, David Pointcheval, and Philip Rogaway, Relations among Notions of Security for Public-Key Encryption Schemes[dead link], in Advances in Cryptology – CRYPTO '98, Santa Barbara, California, pp. 549–570.
  3. D. Bleichenbacher. Chosen Ciphertext Attacks against Protocols Based on RSA Encryption Standard PKCS #1 Archived 2000-08-15 at the Wayback Machine. In Advances in Cryptology – CRYPTO'98, LNCS vol. 1462, pages: 1–12, 1998
  4. 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, 1995. full version (pdf)