How does a chosen ciphertext attack work, with a simple example?

Can someone please explain - using a simple example - how a chosen ciphertext attack works?

-

migrated from math.stackexchange.comNov 19 '11 at 0:33

This question came from our site for people studying math at any level and professionals in related fields.

Hello, welcome to crypto.se. I've sent you a message in chat too, but just in case, if you register your account with us, you'll be able to pick up your response notifications and reputation here too. – user46 Nov 19 '11 at 0:42

In a chosen-ciphertext attack, the attacker is assumed to have a way to trick someone who knows the secret key into decrypting arbitrary message blocks and tell him the result. The attacker can choose some arbitrary nonsense as an "encrypted message" and ask to see the (usually) different nonsense it decrypts to, and he can do this a number of times.

Having this capability obviously already allows the attacker to read an intercepted message, since he can just ask to have it decrypted. But in this attack his goal is more ambitious than that: he wants to deduce what the secret key is, such that he can encrypt messages himself, and also keep decrypting after his access to having things decrypted for him vanishes.

The attack is successful if if an attacker has a significant chance of being able to deduce the key after having "relatively few" blocks decrypted and without doing so much work himself that he could just as well have brute-forced it.

The term "chosen-ciphertext attack" does not in itself say anything about how the attacker chooses the nonsense blocks he asks to have decrypted, or what kind of computations he does in order to recover the key from the responses.

As a concrete example, suppose General A is sending messages to General B using a Vigenère cipher with an unknown key. The enemy is somehow able to intercept a message and replace it with some completely random letters of his own choosing, say NLLCJOVFXXHMLY. General B decrypts this and gets AKRUWNBXKWNEYX which is nonsense. Bemused, and not thinking this nonsense is worth keeping secret, he picks up a non-secure phone and calls General A: "What the hell do you mean with AKRUWNBXKWNEYX? Did they change the key without telling me?" But the enemy is eavesdropping on the line and now knows that NLLCJOVFXXHMLY decrypts to AKRUWNBXKWNEYX. He can then subtract the two sets of nonsense to get MATHMATHMATHMA, and now he knows the key.

(In this example, getting a single message decrypted was enough for the attacker to learn the key. In general one also considers attacks where the attacker needs to query for multiple messages, perhaps using the response to one somehow to construct the next one).

-
I'm a bit confused because I read a definition where the adversary is not allowed to query the oracle on the "challenge ciphertext"! But you re saying that he is?? – mixkat Nov 19 '11 at 0:16
In that variant, the attacker is not interested in the key as such, but merely in decrypting an intercepted message (= the "challenge ciphertext") without letting the victim know that message. Then he's allowed to ask the oracle about anything but the challenge, and if the responses to that will allow him to decrypt the challenge, he wins. One way to do this would be to derive the key, but it is conceivable that there are shortcuts that doesn't result in full knowledge about the key. – Henning Makholm Nov 19 '11 at 0:23
Also...Does the attack rely on the fact that General B will call from a non-secure phone and ask for the key? In other words can the key still be obtained (and the message deciphered) if the two parties dont ever use a non-secure line? – mixkat Nov 19 '11 at 0:25
The important fact is that the attacker somehow learns what his test message decrypts to. It doesn't need to be anything as "obviously risky" as calling on an unsecured line -- in a more modern setting, we could be thinking of a protocol where an encrypted message contains a nonce that the recipient will later echo back without encryption, or of a setting where the encrypted message contains data that the recipient is supposed to publish on behalf of the sender. – Henning Makholm Nov 19 '11 at 0:38
Yeah but it definitely requires some sort of "unprotected" communication though right? – mixkat Nov 19 '11 at 1:03

Another variant (besides the ones explained by Henning) which I also would call chosen-ciphertext attack, is one where the attacker doesn't get the whole plaintext corresponding to its chosen ciphertext, but only a result like "valid" or "not valid", i.e. he has a validation oracle, with some useful definition of "valid". The goal is to decrypt some message captured before.

One example where this is used is the recently discovered weakness in XML encryption, when used for Web services.

For security proofs we usually have some attack model which exactly specifies what the attacker can do, and what its goal is. One example is IND-CCA/IND-CCA2, where the attacker can use an encryption oracle and a decryption oracle, then submits two plaintexts (none of which may have been encrypted before), gets the ciphertext to one of them back and tries to guess which one it was. In the adaptive variant IND-CCA2, the attacker is also allowed to use more decryption oracle calls (other than the challenge ciphertext) after getting the challenge, in non-adaptive case only more encryptions are allowed.

(In general, we want our algorithms/protocols to be secure also in the case of chosen-ciphertext attacks.)

-
Are you not confusing it with CPA?? I thought that in a CCA attack the adversary submits 2 ciphertexts and gets the decryption of one of them! Also what exactly is the IND property? I know that it stands for indistinguishability but cant see how it relates! Does it have to do with the fact that the adversary sends 2 msgs and tries to tell them apart or...? – mixkat Nov 19 '11 at 14:40
In a chosen-plaintext-attack, the attacker gets to chose plaintexts and sees their encryption. In a chosen-ciphertext attack, the attacker can only chose ciphertexts, and may see their decryption (when one has a decryption oracle), or only a bit less (for the validation oracle). – Paŭlo Ebermann Nov 19 '11 at 15:00
Ok! And how does the attacker then actually get the plaintext if he is not allowed to query the oracle on the ciphertext that was "sniffed"? – mixkat Nov 19 '11 at 15:06
I got this description from Wikipedia. But as all understand, all the IND-properties (indistinguishable) are like "attacker chooses two plaintexts and gets to see the ciphertext of one of them, then has to guess which one". (This actually correlates to a quite common scenario, where it is already narrowed down that Bob did send either "Yes" or "No".) They just differ about what means the attacker has to do this, like a ciphertext-only-attack, a chosen-plaintext attack, a chosen-ciphertext attack. – Paŭlo Ebermann Nov 19 '11 at 15:06
Yeah that what I get too! I just cant see how it works in the chosen-ciphertext-attack scenario! I mean..the way I see it is that it really comes down to guessing in the end! – mixkat Nov 19 '11 at 15:11