Say we have an encryption algorithm that encrypts data blocks of 128 bits size,

Question

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 P1, P2 there is: E(P1?P2)=E(P1)?E(P2) 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 Cj, and the decryption machine gives him the matching Pj Plaintext blocks.

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

Explanation / Answer

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(P1?P2)=E(P1)?E(P2).

First question: does this imply that D(C1?C2)=D(C1)?D(C2) (where D is the inverse of E)? How would you show that?

Next question: if D(C1?C2)=D(C1)?D(C2), how would you select a set of ciphertexts {C1,C2,...,Cn} such that any ciphertext can be expressed as the exclusive-or of some subset of Ci? 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?

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects