Breaking One Time Pad with CCA

Question

I was taught that:

although OTP is CPA secure, it is not the case with CCA.

I'm trying to figure how to break OTP with CCA by showing how it fails the IND test.

Note: Saw this answer, but didn't manage to extract a proper proof.

• So according to the test, the attacker chooses two messages m1, m2 of the same length, and sends them for the tester.

• In the next stage, the tester privately creates an encryption key, randomly chooses which message to encrypt, and returns c* which is the chosen message encrypted.

• Now, the attacker is able to use his chosen-ciphertext capability and decrypt any message he wants to (maybe messages - I'm not sure about this detail), as long as his chosen message is not c*, in order to guess which message was encrypted (m1 or m2).

What I already thought of:

Maybe we could split c* apart, decrypt both parts and concatenate. Or we could also add a 0 in the end of c* and then decrypt the result.

But both methods wouldn't work since the key is in the length of the original message - so it cannot decrypt messages in other lengths.

So I add a condition of which the attacker can only decrypt messages in the same length of c* (and the original messages, obviously).

So now I thought about decrypting c* but replacing the last bit to 0.

Assume c* length is n, so the in the encrypted result, denoted as r*, I know the first n-1 bits are of m1 or m2, except for the last one, so I'd distinguish between the messages by comparing the n-1 bits with each of them (of course that'd require sending different messages for the test).

I feel like I'm missing something but can't figure out what exactly.

Does anyone have better example of breaking OTP with CCA, or can justify my answer?

P.S. Just a clarification: I assume of course that key is replaced in each encryption (but it doesn't matter here because decryption is done with the same key).

Answer 1

It's actually fairly straight-forward; the attacker knows $m_0$, $m_1$, and the challenge ciphertext $c = m_r \oplus s$, for an unknown bit $r$ and an unknown string $s$; his job is to recover $r$.

One thing he can try is selecting an arbitrary ciphertext $c'$ (which needs to be distinct from the challenge ciphertext, but can be anything else of the same length), and ask for it to be decrypted. The decryption is $m' = c' \oplus s$; he can then recover $m_r = c' \oplus m' \oplus c$; he can then compare $m_r$ to $m_0$ and $m_1$ to deduce $r$.