Chosen-plaintext attack

From Wikipedia, the free encyclopedia
  (Redirected from Chosen plaintext attack)
Jump to: navigation, search

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

Introduction[edit]

In a chosen-plaintext attack the adversary can adaptively ask for the ciphertexts of arbitrary plaintext messages. This 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 part of the secret encryption key.

The circumstances by which an attacker may obtain ciphertexts for given plaintexts are rare. 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. 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[edit]

There are two forms of chosen-plaintext attacks:

  • Batch chosen-plaintext attack, where the cryptanalyst chooses all of the plaintexts before seeing any of the corresponding ciphertexts. This is often the meaning of an unqualified use of "chosen-plaintext attack".
  • Adaptive chosen-plaintext attack (CPA2), where the cryptanalyst can request the ciphertexts of additional plaintexts after seeing the ciphertexts for some plaintexts.

General Method of an Attack[edit]

A general chosen-plaintext attack is carried out as follows:

  1. The attacker may choose some number of plaintext's, x. The number of plaintexts is arbitrary and up to the attacker.
  2. The attacker then sends x plaintext's to the encryption oracle.
  3. The encryption oracle will then encrypt the attackers plaintext's and send them back to the attacker.
  4. The attacker receives x number of ciphertext's back from the oracle, each one able to be paired with its plaintext (s.t. the attacker knows that the plaintext z has the ciphertext of y).
  5. Based on the pairs of plaintext's and ciphertext's, the adversary can attempt to extract the key used to encode the plaintext's by the oracle. Since the attacker in this type of attack can craft his own plaintext to tailor to his needs, the break attempt is fairly straight forward. An example would be for the attacker to craft plaintext's with one containing 'a', one 'aa', one 'aaa' and so on. This would then allow the attacker to extrapolate information about how the oracle is encrypting the data being passed to it by comparing the plaintexts of a's to the ciphertexts of a's. For an easy and manageable example it is sufficient to use a Caesar Cipher. An example is as follows:
So, suppose the attacker goes and sends the message:
Attack at dawn

And the oracle returns
Nggnpx ng qnja

The attacker can then work through to recover the key in the same way you would decrypt a Caesar Cipher. The attacker could see A->N , T->G and so on. This would lead the attacker to figure out that 13 was the secret Caesar Cipher key used. Obviously with more intricate encryption the decryption method becomes  more resource intensive, but the core concept is still relatively the same.

In the modern world, a cipher is considered secure against a chosen plaintext attack if, allowed to choose two arbitrary plaintexts (p_0, p_1), an adversary who has been told to pick the ciphertext for p_0 cannot do so with probability greater than 0.5 (50%) which is known as Ciphertext Indistinguishability.

In practice[edit]

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.[2][3]

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.[4] 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.[5] This helped the codebreakers decrypt the code used on the second leg, having supplied the original text.[6]

In modern day chosen plaintext attacks are often used to break symmetric cyphers. These symmetric cyphers, to be considered secure, must be secure against these Chosen Plaintext Attacks. Thus, it is important for symmetric cypher implementors to understand how an attacker would attempt to break their cypher 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[edit]

A chosen-plaintext attack is more powerful than known-plaintext attack, because the attacker can obtain many pairs of plaintexts and ciphertexts, instead of only one pair, and therefore has more data for 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, where the attacker can obtain the plaintexts of arbitrary ciphertexts. A CCA-attacker can sometimes break a CPA-secure system.[2] For example, the El Gamal cipher is secure against chosen plaintext attacks, but vulnerable to chosen ciphertext attacks because it is unconditionally malleable.

See also[edit]

References[edit]

  1. ^ Ross Anderson, Security Engineering: A Guide to Building Dependable Distributed Systems. The first edition (2001): http://www.cl.cam.ac.uk/~rja14/book.html
  2. ^ a b Katz, Jonathan; Lindell, Yehuda (2007). Introduction to Modern Cryptography: Principles and Protocols. Chapman and Hall/CRC. 
  3. ^ Weadon, Patrick D. "How Cryptology enabled the United States to turn the tide in the Pacific War.". www.navy.mil. US Navy. Retrieved 2015-02-19. 
  4. ^ Morris, Christopher (1993), "Navy Ultra's Poor Relations", in Hinsley, F.H.; Stripp, Alan, Codebreakers: The inside story of Bletchley Park, Oxford: Oxford University Press, p. 235, ISBN 978-0-19-280132-6 
  5. ^ Kelly, Jon (27 January 2011). "The piece of paper that fooled Hitler". BBC. Retrieved 1 January 2012. The Nazis believed Pujol, whom they code named Alaric Arabel, was one of their prize assets 
  6. ^ 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"