Chosen-plaintext attack

From Wikipedia, the free encyclopedia
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 messages. This is formalized by allowing the adversary to interact with an encryption oracle, viewed as a black box.

This appears, at first glance, to be an unrealistic model; as it is unlikely that an attacker could persuade a human cryptographer to encrypt large amounts of plaintexts of the attacker's choosing. 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.

In the worst case, a chosen-plaintext attack could reveal the scheme's secret key. For some chosen-plaintext attacks, only a small part of the plaintext needs to be chosen by the attacker: such attacks are known as plaintext injection attacks.

Forms of chosen-plaintext attacks[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.

Chosen-plaintext attacks in practice[edit]

A technique termed "Gardening" was used by Allied codebreakers in World War II who were solving messages encrypted on the Enigma machine. Gardening can be viewed as a plaintext injection attack.

In WWII US Navy cryptoanalysts 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]

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 cryptoanalysis. 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]

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.