Body of question

Note: this is THEORETICAL exercise. I understand OTP and CBC does not get along.

I have to find a CPA on CBC enc-mode using OTP as the encryption algorithm, s.t a new key is generated only for every new message, but not for every block.

Second question is whether this method is not safe at all, or, it could be safe for odd block number, or perhaps for even block number?

What I've tried myself

I can see myself that in even block number case, the key is cancelled out at last (thanks to CBC), so what I get is $IV \oplus P_1 \oplus...\oplus P_n$, but can't think of a way to distinguish two messages with the IND-test for CPA.

Basically I can calculate the blocks of each $m_1,m_2$ that I use for the test, but the randomized IV will prevent me from knowing what message is the ciphered text retrieved from the test...

And what about the odd case?

Any ideas?


1 Answer 1


Scheme is not IND-CPA for any message longer than one block. I'll include a image of CBC mode below for reference (Source: Wikipedia).

enter image description here

Suppose instead of block cipher encryption we have plaintext xor-ed with the key as you propose. You'll note that for message block 1, $M_1$, the ciphertext block $C_1 = M_1 \oplus IV \oplus Key$. Similarly $C_2 = M_2 \oplus C_1 \oplus Key$ Substituting for $C_1$ we get $C_2 = M_2 \oplus M_1 \oplus IV \oplus Key \oplus Key$ which reduces to $C_2 = M_1 \oplus M_2 \oplus IV$. Knowing this we can build a distinguisher $D$.

Suppose we send two messages $M0$ and $M1$ to the encryption oracle and get back $C$. $D$ will take $C$ and check if either $C_2 = M0_1 \oplus M0_2 \oplus IV$ or $C_2 = M1_1 \oplus M1_2 \oplus IV$ (note that the $IV$ is not secret), returning whichever plaintext corresponds to $C$. Clearly this distinguisher has non-negligible advantage, and thus the scheme is not IND-CPA for messages longer than one block.

  • $\begingroup$ Thanks. Didn't know the distinguisher had access to the IV, that's why I've failed. (I know it's not encrypted, but thought the test should be done without assuming that we are sniffing the communication or something...). $\endgroup$
    – Jjang
    May 1, 2016 at 16:11
  • $\begingroup$ By the way, for odd number of blocks the key isn't cancelled out... not just for 1 block. Am I right? $\endgroup$
    – Jjang
    May 1, 2016 at 16:16
  • $\begingroup$ is it CPA-secure when the blocks number is odd? $\endgroup$
    – Jjang
    Jun 27, 2016 at 17:49

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.