Chosen-plaintext attack

This article needs more citations. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Chosen-plaintext attack" – news · newspapers · books · scholar · JSTOR (November 2015) (Learn how and when to remove this message)

A chosen-plaintext attack (CPA) is an attack model for cryptanalysis which presumes that the attacker can obtain the ciphertexts for arbitrary plaintexts. The goal of the attack is to gain information that reduces the security of the encryption scheme.

Immunity to a chosen-plaintext attack is called ciphertext indistinguishability under chosen-plaintext attack (IND-CPA). With an IND-CPA property, the cryptographic scheme is resistant to an attacker that has access to the encryption oracle (e.g., the encryption device) itself. This property is equivalent to the semantic security under CPA (inability of the adversary to gain even partial information about the plaintext from observing the ciphertext). A similar (but stronger) property of indistinguishability under a chosen-ciphertext attack (IND-CCA) reflects the resistance to adversary having access to a decryptor.'

A deterministic block cipher scheme (like electronic codebook) does not possess the IND-CPA, as it will encrypt the plaintext with repeating blocks into ciphertext that will be easily recognizable because its blocks are repeated as well.

Introduction

In a chosen-plaintext attack the adversary can (possibly adaptively) ask for the ciphertexts of arbitrary plaintext messages. That is formalized by allowing the adversary to interact with an encryption oracle, viewed as a black box. The attacker’s goal is to reveal all or a part of the secret encryption key.

It may seem infeasible in practice for an attacker to obtain ciphertexts for given plaintexts. However, modern cryptography is implemented in software or hardware and is used for a diverse range of applications; for many cases, a chosen-plaintext attack is often very feasible (see also In practice). Chosen-plaintext attacks become extremely important in the context of public key cryptography in which the encryption key is public and so attackers can encrypt any plaintext that they choose.

Different forms

There are two forms of chosen-plaintext attacks:

• Batch chosen-plaintext attack, where the adversary chooses all of the plaintexts before seeing any of the corresponding ciphertexts. That is often the meaning intended by "chosen-plaintext attack" when it is not qualified.
• Adaptive chosen-plaintext attack (CPA2), where the adversary can request the ciphertexts of additional plaintexts after seeing the ciphertexts for some plaintexts.

General method of an attack

A general batch chosen-plaintext attack is carried out as follows ^{[failed verification]}:

1. The attacker may choose n plaintexts. (This parameter n is specified as part of the attack model, it may or may not be bounded.)
2. The attacker then sends these n plaintexts to the encryption oracle.
3. The encryption oracle will then encrypt the attacker's plaintexts and send them back to the attacker.
4. The attacker receives n ciphertexts back from the oracle, in such a way that the attacker knows which ciphertext corresponds to each plaintext.
5. Based on the plaintext–ciphertext pairs, the attacker can attempt to extract the key used by the oracle to encode the plaintexts. Since the attacker in this type of attack is free to craft the plaintext to match his needs, the attack complexity may be reduced.

Consider the following extension of the above situation. After the last step,

1. The adversary outputs two plaintexts m₀ and m₁.
2. A bit b is chosen uniformly at random ${\displaystyle b\leftarrow \{0,1\}}$.
3. The adversary receives the encryption of m_b, and attempts to "guess" which plaintext it received, and outputs a bit b'.

A cipher has indistinguishable encryptions under a chosen-plaintext attack if after running the above experiment, the adversary cannot guess correctly (b=b') with probability non-negligibly better than 1/2.

Examples

The following examples demonstrate how some ciphers that meet other security definitions may be broken with a chosen-plaintext attack:

In practice

During World War II, US Navy cryptanalysts discovered that Japan was planning to attack a location referred to as "AF". They believed that "AF" might be Midway Island because other locations in the Hawaiian Islands had codewords that began with "A". To prove their hypothesis that "AF" corresponded to "Midway Island," they asked the US forces at Midway to send a plaintext message about low supplies. The Japanese intercepted the message and immediately reported to their superiors that "AF" was low on water. That confirmed the Navy's hypothesis and allowed it to position its force to win the Battle of Midway.

Also during World War II, Allied codebreakers at Bletchley Park would sometimes ask the Royal Air Force to lay mines at a position that had no abbreviations or alternatives in the German naval system's grid reference. The hope was that the Germans, seeing the mines, would use an Enigma machine to encrypt a warning message about the mines and an "all clear" message after they were removed, which would give the Allies enough information about the message to break Germany's naval Enigma. The process of planting a known-plaintext was called gardening. Allied codebreakers also helped craft messages sent by the double agent Juan Pujol García, whose encrypted radio reports were received in Madrid, manually decrypted, and re-encrypted with an Enigma machine for transmission to Berlin. That helped the codebreakers decrypt the code used on the second leg since they had supplied the original original text.

Today, chosen-plaintext attacks (CPAs) are often used to break symmetric ciphers. To be considered CPA-secure, the symmetric cipher must not be vulnerable to chosen-plaintext attacks. Thus, it is important for symmetric cipher implementors to understand how an attacker would attempt to break their cipher and make relevant improvements.

For some chosen-plaintext attacks, only a small part of the plaintext may need to be chosen by the attacker; such attacks are known as plaintext injection attacks.

Relation to other attacks

A chosen-plaintext attack is more powerful than known-plaintext attack because the attacker can directly target specific terms or patterns without having to wait for these to appear naturally. That allows faster gathering of data relevant to cryptanalysis. Therefore, any cipher that prevents chosen-plaintext attacks is also secure against known-plaintext and ciphertext-only attacks.

However, a chosen-plaintext attack is less powerful than a chosen-ciphertext attack in which the attacker can obtain the plaintexts of arbitrary ciphertexts. A CCA-attacker can sometimes break a CPA-secure system. For example, the El Gamal cipher is secure against chosen plaintext attacks, but vulnerable to chosen ciphertext attacks because it is unconditionally malleable.

The IND-CPA property is easier to prove than the IND-CCA and so few schemes were suggested to convert public key encryption algorithms possessing IND-CPA into IND-CCA ones, with the most important one being the Fujisaki-Ocamoto transformation (1999).

See also

• GMR (cryptography)

References

Sources

• Bagherzandi, A.; Azimian, K.; Mohajeri, J.; Salmasizadeh, M. (2005). "Relations between semantic security and indistinguishability against cpa, non-adaptive cca and adaptive cca in comparison based framework". arXiv:cs/0508110.
• Goldwasser, S.; Micali, S. (1984). "Probabilistic encryption" (PDF). Journal of Computer and System Sciences. 28 (2): 270–299. doi:10.1016/0022-0000(84)90070-9.
• Hofheinz, Dennis; Hövelmanns, Kathrin; Kiltz, Eike (2 November 2021). "A Modular Analysis of the Fujisaki-Okamoto Transformation". arXiv:1712.03108 [cs.CR].
• Katz, J.; Lindell, Y. (2007). Introduction to Modern Cryptography (PDF). CRC Press. ISBN 978-1584885511.

Listen to this article (11 minutes)

This audio file is based on a version from this article dated 28 December 2023 (2023-12-28), and does not reflect subsequent edits.

(Audio help · More spoken articles)