2
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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?

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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... $\endgroup$
    – Carmageddon
    May 26, 2014 at 21:43
  • $\begingroup$ I fixed the original question, note the 128 bolded .. 128 cipher blocks.. I am still unsure how to approach this question entirely. $\endgroup$
    – Carmageddon
    May 26, 2014 at 21:45
  • $\begingroup$ @Carmageddon: hint: how big are the plaintext/ciphertext blocks? $\endgroup$
    – poncho
    May 26, 2014 at 21:52
  • $\begingroup$ 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... $\endgroup$
    – Carmageddon
    May 26, 2014 at 22:43
  • $\begingroup$ @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? $\endgroup$
    – poncho
    May 27, 2014 at 4:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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