# Chosen Ciphertext Attack with a theoretical decryption machine

Say we have an encryption algorithm that encrypts data blocks of 128 bits size, and makes them cipher blocks $C = E(P)$ without chaining.

Also assume there is a linearity rule for XOR: For every pair of plaintext blocks $P_1$, $P_2$ there is: $E(P_1 \oplus P_2) = E(P_1) \oplus E(P_2)$ for all patterns. Encryption is done using a specific secret key.

Now assume the attacker has a decryption machine, and can do Chosen Cipertext Attacks: He can pick a set of 128 cipher blocks say ${C_j}$, and the decryption machine gives him the matching ${P_j}$ Plaintext blocks.

I am wondering, how to prove that he can decipher ANY cipher block without knowledge of the secret key?

-

Well, one obvious way he can decrypt ANY cipher block is just give it to his Decryption machine; that machine will give him the matching plaintext block, which is precisely what he is looking for.

Now, normally when we give an attacker a decryption oracle, and give him a challenge "decrypt this specific message", we put a limitation on the oracle that it won't decrypt that specific message; let us assume that there is such a limitation (even though it was not specifically listed).

So, we know that the encryption algorithm obeys $E(P_1 \oplus P_2) = E(P_1) \oplus E(P_2)$.

First question: does this imply that $D(C_1 \oplus C_2) = D(C_1) \oplus D(C_2)$ (where $D$ is the inverse of $E$)? How would you show that?

Next question: if $D(C_1 \oplus C_2) = D(C_1) \oplus D(C_2)$, how would you select a set of ciphertexts $\{C_1, C_2, ..., C_n\}$ such that any ciphertext can be expressed as the exclusive-or of some subset of $C_i$? How can you use this observation to decrypt this arbitrary ciphertext?

Bonus question (which goes beyond what they asked): how can you extend this observation if you were given a set of random plaintexts and their encryption?

-
Thanks for the quick answer poncho :) I will try to explain better the "decryption oracle", as you called it: Attacker can choose a SET of 128 cipher blocks, for example {Cj}, and the oracle would output him the matching blocks {Pj} - does that make the question clearer? because I dont understand how your answer helps me... –  Carmageddon May 26 '14 at 21:43
I fixed the original question, note the 128 bolded .. 128 cipher blocks.. I am still unsure how to approach this question entirely. –  Carmageddon May 26 '14 at 21:45
@Carmageddon: hint: how big are the plaintext/ciphertext blocks? –  poncho May 26 '14 at 21:52
each p/c block is of identical size of 128 bits. I also now understood your first question! yes, since non-chained plain text would have identical cipher text for 2 identical plain texts... so the answer is intuitively yes. Is that proof? I am uncertain how to formalize it... Your second question I need to think some more about... –  Carmageddon May 26 '14 at 22:43
@Carmageddon: lets see if we can cut down the problem for you -- suppose that the blocks were 4 bits long, and you could ask for the decryption of 4 ciphertext blocks of your choice -- how would you proceed? –  poncho May 27 '14 at 4:58