14
$\begingroup$

In CPA, it is said that the adversaries get ciphertext for the choice of plaintext of adversaries through an encryption oracle. Is this a realistic assumption in real-world, in which the adversaries get ciphertext for the choice of their plaintexts? If so, please provide me with some example scenarios illustrating how adversaries obtain ciphertexts for their plaintexts?

$\endgroup$
  • 1
    $\begingroup$ +1 Surely there must some example more recent than WW2? Something that involves a modern-ish block cipher and isn't entirely hypothetical? $\endgroup$ – Mike Ounsworth Aug 29 '18 at 15:13
  • 6
    $\begingroup$ I had the opportunity once. My boss wanted me to find out some information that was on the company e-mail server before the mail got delivered the next morning. I found the directory where mail was cached (encrypted), sent a chosen-text message, and looked at the new file in the cache. It was easy to determine the minimal encryption they used. $\endgroup$ – Lee Daniel Crocker Aug 29 '18 at 21:01
22
$\begingroup$

Bruce Schneier foresaw your skepticism and directly answered this question in "Applied Cryptography":

Known-plaintext attacks and chosen-plaintext attacks are more common than you might think. It is not unheard-of for a cryptanalyst to get a plaintext message that has been encrypted or to bribe someone to encrypt a chosen message. You may not even have to bribe someone; if you give a message to an ambassador, you will probably find that it gets encrypted and sent back to his country for consideration. Many messages have standard beginnings and endings that might be known to the cryptanalyst. Encrypted source code is especially vulnerable because of the regular appearance of keywords: #define, struct, else, return. Encrypted executable code has the same kinds of problems: functions, loop structures, and so on. Known-plaintext attacks (and even chosen-plaintext attacks) were successfully used against both the Germans and the Japanese during World War II. David Kahn's books [794, 795, 796] have historical examples of these kinds of attacks.

Here are the referenced books:

  1. D. Kahn, The Codebreakers: The Story of Secret Writing, New York: Macmillan Publishing Co., 1967.
  2. D. Kahn, Kahn on Codes, New York: Macmillan Publishing Co., 1983.
  3. D. Kahn, Seizing the Enigma, Boston: Houghton Mifflin Co., 1991.
$\endgroup$
  • 4
    $\begingroup$ "Known plaintext" and "Chosen Plaintext" are different. Most of that quote is about "Known plaintext"; the ambassador and bribery is the only chosen plaintext, right? $\endgroup$ – Yakk - Adam Nevraumont Aug 30 '18 at 13:57
  • $\begingroup$ "Encrypted executable code has the same kinds of problems: functions, loop structures, and so on" - including the ginormous .exe file header that contains a DOS program to display an error message... $\endgroup$ – John Dvorak Aug 30 '18 at 15:34
  • $\begingroup$ @Yakk-AdamNevraumont: Nope, Nathalie Sergueiew got the Germans to encrypt arbitrary, lengthy plaintexts with Enigma. More generally, see also the practice of gardening. $\endgroup$ – Kevin Aug 31 '18 at 5:24
  • $\begingroup$ (And for that matter, GARBO did it too.) $\endgroup$ – Kevin Aug 31 '18 at 5:32
17
$\begingroup$

It's not necessary that you encounter a situation like this in the real world to motivate the definition. There are some weaker adversaries that you would like to rule out in your security model, and CPA-security usually would encompass them all.

Think for example of an encryption scheme which is intended to be used to encrypt one bit, like "yes" or "no". In such scenario it is not so unreasonable to assume that an adversary can force some of the parties to encrypt messages of its choice! Specially if this response depends on some external behavior, potentially controlled (or partially controlled) by the adversary.

To be more concrete, think of a situation in which one observator will report to his headquarters whether or not enemy troops are moving (yes or no). Clearly, by intercepting the secure channel and by moving the troops adequately, a CPA attack can be mounted (if I'm not wrong something like this did happen during the second world war... does someone have a reference?).

The attack here works because the distribution of the inputs can be altered by the adversary. There are some other scenarios in which such correlation makes sense, and CPA security is there to provide security guarantees without knowing the internals of such correlation: By allowing the adversary to choose the messages at its own will, any possible attack by biasing the input distribution is ruled out.

In general, the goal of CPA security is to avoid the security of the scheme to be affected by a possibly malicious input distribution. We want security to rely on the distribution of the keys, not on the distribution of the inputs. Therefore, even if the inputs are somehow correlated to adversarial behavior, in a CPA-secure scheme nothing can be learned about a plaintext from a ciphertext.

$\endgroup$
  • $\begingroup$ Thanks for the example. What is the role of an encryption oracle in CPA?. In the given example, CPA was succeed based on the contextual scenario and guess. Guesses may or may not work all the time. How about the possibility of inflicting CPA on the encryptor system without any prior contextual situation and guess? Is this possible or not? Please clarify me in this regard. $\endgroup$ – Siva Kumar Aug 29 '18 at 16:18
  • $\begingroup$ From a definitional point of view, the role of the oracle is to sort of "model" this bias in the distribution that the adversary can cause (the strongest bias is one where the adversary chooses the messages itself, right?). Regarding your last two questions, that's more like an application-dependent remark. There may be some applications for which a full CPA is not really a concern, and others in which it is. For example, what if you are encrypting only random values? As long as you generate them honestly there is not really a bias that can be added. Other applications may behave differently $\endgroup$ – Daniel Aug 29 '18 at 17:44
  • 3
    $\begingroup$ @SivaKumar: Yes, the abstract CPA model most likely overestimates the degree to which an attacker can influence the plaintext distribution in a given concrete system. This is a feature, not a bug -- it means that we don't have to worry about whether it underestimates our real enemy's capabilities in that direction. A whole class of potential weaknesses in our security analysis is made impossible. And the overestimation doesn't cost us anything, because ciphers and modes that are reasonably believed to be resistant against full CPA are available off-the-shelf anyway. $\endgroup$ – Henning Makholm Aug 29 '18 at 22:56
  • $\begingroup$ Chosen-plaintext encryption is fairly easy to demonstrate with any HTTP server that supports file uploads. Just upload the file that you want to be encrypted, and the server will give it back to you over HTTPS! $\endgroup$ – Riking Aug 31 '18 at 3:27
17
$\begingroup$

Practical chosen-plaintext attacks have been discovered against modern cryptosystems like TLS/SSL. One noteworthy type of vulnerability can occur when a cryptosystem includes a compression step before encryption (which TLS used to do). This led to several well-known exploits such as CRIME and BREACH.

In CRIME, the adversary attacks a visitor of a HTTPS-secured website by inducing the victim's web browser to include text of the attacker's choice in requests made to the target website. By observing the length of an encrypted request, the attacker can then deduce whether other parts of the request matched the chosen plaintext: in case of a match the compression causes the request length to be slightly smaller than it would be otherwise. This allows the attacker to gain information about secrets included in the request, e.g. the victim's session token which may be sent as a cookie.

Juliano Rizzo, one of the researchers who found CRIME, describes it as follows:

[...] “Basically, the attacker is running [a] script in Evil.com. He forces the browser to open requests to Bank.com by, for example, adding tags with src pointing to Bank.com,” Rizzo said. “Each of those requests contains data from mixed sources.” In these requests, attacker data and data produced by the browser is compressed and mixed together. Those requests can include the path, which the attacker controls, the browser’s headers, which are public, and the cookie, which should be secret.

“The problem is that compression combines all those sources together,” Rizzo added. “The attacker can sniff the packets and get the size of the requests that are sent. By changing the path, he could attempt to minimize the request size, i.e., when the file name matches the cookie.” [...]

A detailed description can be found in this question on security.SE.

In response to CRIME, the compression feature was deprecated in newer versions of TLS. However, attacks can still occur if the application protocol on top of TLS performs compression (e.g. HTTP gzip compression; SPDY; etc.). BREACH is an example of such a CRIME variant.

BEAST, an earlier attack by the same researchers, was another chosen-plaintext attack against TLS. It did not rely on an abuse of compression, but exploited a vulnerability in how CBC mode was implemented in block ciphers of TLS 1.0 and earlier.

$\endgroup$
11
$\begingroup$

There are some interesting examples in section 3.4.2 of Katz-Lindell book. Here is just one of them:

During World War II, the British placed mines at certain locations and (intentionally) managed to let the Germans discover them. They knew that the Germans would encrypt the locations and send back to the headquarters. These encrypted messages were used by cryptanalysts at Bletchley Park to break the Enigma machine.

$\endgroup$
8
$\begingroup$

The lead up to the Battle of Midway also involved a chosen plaintext attack. The Americans had mostly broken the Japanese code JN-25b, and knew the Japanese were attacking "AF". They guessed that "AF" was Midway, but to be sure they had Midway send a cleartext message that their fresh water system was broken, and soon picked up a Japanese message "AF was short on water".

$\endgroup$
2
$\begingroup$

Another scenario: a disk encryption system where the attacker can let the system store chosen files in a known location (like a Downloads folder), and can observe the cipher text later.

$\endgroup$
0
$\begingroup$

Another WW2 example. German U-boats always started their encrypted transmissions with a weather report in a standard format which was revealed when the British captured a copy of the weather codebook. If the British knew what the weather was like at the time and place of the transmission, then they knew what the plaintext must be. (The U-boats also disengaged one rotor of their four-rotor Enigma machines for the weather report, which was even more stupid but is not relevant here.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.