View source for Chosen-plaintext attack

{{short description|Attack model for cryptanalysis with presumed access to ciphertexts for chosen plaintexts}}
{{Refimprove|date=November 2015}}
A '''chosen-plaintext attack''' ('''CPA''') is an [[attack model]] for [[cryptanalysis]] which presumes that the attacker can obtain the [[ciphertext]]s for arbitrary [[plaintext]]s.<ref name="RASE">Ross Anderson, ''Security Engineering: A Guide to Building Dependable Distributed Systems''. The first edition (2001): http://www.cl.cam.ac.uk/~rja14/book.html</ref> The goal of the attack is to gain information that reduces the security of the [[encryption]] scheme.<ref>{{Cite journal|last1=Barrera|first1=John Fredy|last2=Vargas|first2=Carlos|last3=Tebaldi|first3=Myrian|last4=Torroba|first4=Roberto|date=2010-10-15|title=Chosen-plaintext attack on a joint transform correlator encrypting system|url=https://www.sciencedirect.com/science/article/pii/S0030401810006036|journal=Optics Communications|language=en|volume=283|issue=20|pages=3917–3921|doi=10.1016/j.optcom.2010.06.009|bibcode=2010OptCo.283.3917B|issn=0030-4018}}</ref>

Modern ciphers aim to provide semantic security, also known as ''ciphertext indistinguishability under chosen-plaintext attack'', and they are therefore, by design, generally immune to chosen-plaintext attacks if correctly implemented.

==Introduction==
In a chosen-plaintext attack the [[Adversary (cryptography)|adversary]] can (possibly [[Adaptive algorithm|adaptively]]) ask for the ciphertexts of arbitrary plaintext messages. This is formalized by allowing the adversary to interact with an encryption [[Oracle machine|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 that an attacker could 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|In practice]]). Chosen-plaintext attacks become extremely important in the context of [[public key cryptography]] where the encryption key is public and so attackers can encrypt any plaintext 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. This is often the meaning intended by "chosen-plaintext attack" when this 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|date=February 2019}}:
# The attacker may choose ''n'' plaintexts. (This parameter ''n'' is specified as part of the [[attack model]], it may or may not be bounded.)
# The attacker then sends these ''n'' plaintexts to the encryption oracle.
# The encryption oracle will then encrypt the attacker's plaintexts and send them back to the attacker.
# The attacker receives ''n'' ciphertexts back from the oracle, in such a way that the attacker knows which ciphertext corresponds to each plaintext.
# 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, 
# The adversary outputs two plaintexts {{var|m}}<sub>0</sub> and {{var|m}}<sub>1</sub>.
# A bit {{var|b}} is chosen uniformly at random <math>b\leftarrow\{0,1\}</math>.
# The adversary receives the encryption of {{var|m}}<sub>b</sub>, and attempts to "guess" which plaintext it received, and outputs a bit {{var|b'}}.

A cipher has '''indistinguishable encryptions under a chosen-plaintext attack''' if after running the above experiment the adversary can't guess correctly ({{var|b}}={{var|b'}}) with probability non-[[Negligible function|negligibly]] better than 1/2.<ref name="modern" />

==Examples==

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

===Caesar cipher===
The following attack on the [[Caesar cipher]] allows full recovery of the secret key:
# Suppose the adversary sends the message: {{code|Attack at dawn}},
# and the oracle returns {{code|Nggnpx ng qnja}}.
# The adversary can then work through to recover the key in the same way as a Caesar cipher. The adversary could deduce the substitutions {{nowrap|{{code|A}} → {{code|N}}}}, {{nowrap|{{code|T}} → {{code|G}}}} and so on. This would lead the adversary to determine that 13 was the key used in the Caesar cipher.

With more intricate or complex encryption methodologies the decryption method becomes more resource-intensive, however, the core concept is still relatively the same.

===One-time pads===

The following attack on a [[one-time pad]] allows full recovery of the secret key. Suppose the message length and key length are equal to {{var|n}}.
# The adversary sends a string consisting of {{var|n}} zeroes to the oracle.
# The oracle returns the [[Bitwise operation|bitwise]] [[Exclusive or|exclusive-or]] of the key with the string of zeroes.
# The string returned by the oracle ''is'' the secret key. 

While the one-time pad is used as an example of an [[information-theoretically secure]] cryptosystem, this security only holds under security definitions weaker than CPA security. This is because under the formal definition of CPA security the encryption oracle has no state. This vulnerability may not be applicable to all practical implementations – the one-time pad can still be made secure if key reuse is avoided (hence the name "one-time" pad).

==In practice==

In [[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, confirming the Navy's hypothesis and allowing them to position their force to win the [[Battle of Midway|battle]].<ref name="modern">{{cite book|last1=Katz|first1=Jonathan|last2=Lindell|first2=Yehuda|title=Introduction to Modern Cryptography: Principles and Protocols|date=2007|publisher=Chapman and Hall/CRC|location=Boca Raton|isbn=978-1584885511|author-link=Jonathan Katz (computer scientist)|oclc=893721520}}</ref><ref name="Navy Midway">{{cite web |url=http://www.navy.mil/midway/how.html |title=How Cryptology enabled the United States to turn the tide in the Pacific War. |last1=Weadon |first1=Patrick D. |website=www.navy.mil |publisher=US Navy |access-date=2015-02-19 |archive-url=https://web.archive.org/web/20150131043802/http://www.navy.mil/midway/how.html |archive-date=2015-01-31 |url-status=dead }}</ref>

Also during [[World War II]], Allied codebreakers at [[Bletchley Park]] would sometimes ask the [[Royal Air Force]] to lay mines at a position that didn't have any 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, giving the allies enough information about the message to break the German naval Enigma. This process of ''planting'' a known-plaintext was called ''[[Gardening (cryptanalysis)|gardening]]''.<ref>{{Citation  | last = Morris | first = Christopher | year = 1993 | contribution = Navy Ultra's Poor Relations | editor-last = Hinsley | editor-first = F.H. | editor-link = Harry Hinsley | editor2-last = Stripp | editor2-first = Alan | title = Codebreakers: The inside story of Bletchley Park | location = Oxford | publisher = Oxford University Press | isbn = 978-0-19-280132-6 | page=235}}</ref> Allied codebreakers also helped craft messages sent by double agent [[Juan Pujol García]], whose encrypted radio reports were received in Madrid, manually decrypted, and then re-encrypted with an [[Enigma machine]] for transmission to Berlin.<ref name=BBC_News_Magazine>{{cite news|last=Kelly|first=Jon|title=The piece of paper that fooled Hitler|url=https://www.bbc.co.uk/news/magazine-12266109|publisher=BBC|access-date=1 January 2012|quote=The Nazis believed Pujol, whom they code named Alaric Arabel, was one of their prize assets|date=27 January 2011}}</ref>  This helped the codebreakers decrypt the code used on the second leg, having supplied the original [[Plaintext|text]].<ref name=MarkSeaman73>[[#Seaman|Seaman (2004)]]. "The first code which Garbo was given by the Germans for his wireless communications turned out to be the identical code which was currently in use in the German circuits"</ref>

In modern day, chosen-plaintext attacks (CPAs) are often used to break [[Symmetric-key_algorithm|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, allowing faster gathering of data relevant to cryptanalysis. Therefore, any cipher that prevents chosen-plaintext attacks is also secure against [[known-plaintext attack|known-plaintext]] and [[ciphertext-only]] attacks.

However, a chosen-plaintext attack is less powerful than a [[chosen-ciphertext attack]], where the attacker can obtain the plaintexts of arbitrary ciphertexts. A CCA-attacker can sometimes break a CPA-secure system.<ref name="modern" /> For example, the  [[ElGamal encryption|El Gamal cipher]] is secure against chosen plaintext attacks, but vulnerable to chosen ciphertext attacks because it is [[Malleability (cryptography)|unconditionally malleable]].

== See also ==

* [[GMR (cryptography)]]

==References==
{{Reflist}}
{{Spoken Wikipedia|date=2023-12-28|Chosen-plaintext_attack.ogg}}
{{Attack models in cryptanalysis|state=expanded}}

{{DEFAULTSORT:Chosen-Plaintext Attack}}
[[Category:Chosen-plaintext attacks| ]]