(Non-) Perfect Secrecy of Vernam Cipher Using $E(m) = m \oplus k \oplus \operatorname{rev}(k)$

Question

Given the cipher $$E(k, m) = m \oplus k \oplus \operatorname{rev}(k)$$ where $\operatorname{rev}(k)$ is the reversed binary of $k$, how would one prove that the cipher is not perfectly secret.

I know that the definition of perfect secrecy is $P(M = m \mid C = c) = P(M = m)$ for all $m$ and $c$ and that each key is only used once.

Clearly the intuition comes in when the key is symmetric as then $k \oplus \operatorname{rev}(k) = 0$, but given the definition above how can I show this formally using the definition above?

Thank you! This is a homework question.

My work so far is along the lines of $P(M = m) = 1/2^n$ where $n$ is the number of bits and $$ P(M = m \mid C = c) \\= P(M = m \text{ and } C = c) / P(C = c) \\= 2^n \cdot P(M = m \text{ and } C = c) \\= 2^n \cdot (1/2^n \cdot 1/2^{n/2}) \text, $$ however this doesn't seem very formal.

Answer 1

While the other answer is correct, there are multiple ways to disprove a theorem.

In your case you want to disprove $$\Pr[\mathcal M=m|\mathcal C=c]=\Pr[\mathcal M=m]$$ holds for $$c=m\oplus k \oplus \operatorname{rev}(k)$$.

The first one is to argue using the probabilities and show that the above equation doesn't hold for this scheme.
The second (formally correct) approach is to find a counter-example. Note that counter-examples alway disprove theorems while they can never be used to prove them (this is how sciences like physics work).

Now consider the following message space $\mathcal M=\{(0,1),(1,1)\}$ with $\Pr[\mathcal M=m]=\frac{1}{2}$ (i.e. both messages are equally possible). For the next step observe that $$c_0\oplus c_1 = m_0\oplus k_0 \oplus \operatorname{rev}(k)\oplus m_1\oplus k_1 \oplus \operatorname{rev}(k)= m_0\oplus k_0 \oplus k_1 \oplus m_1\oplus k_1 \oplus k_0=m_0\oplus m_1$$ as was noted by Maarten in the comments. $m_0,m_1$ here denote the first and second bit of the message space and $c_0,c_1,k_0,k_1$ the respective cipher text and key bits.

Now observe that the first message always yields a $1$ when applying the above $\oplus$ and that the second one always yields $0$ when applying it. So you know that $$\Pr[\mathcal M=m|\mathcal C=c]\neq \frac{1}{2}=\Pr[\mathcal M=m]$$ and thus the scheme isn't perfectly secure. The first probability follows trivially from the fact that you can you know exactly which message was encrypted given a particular cipher text.

Answer 2

You know that the definition of perfect secrecy is $P(M = m \mid C = c) = P(M = m)$ for all $m$ and $c$ and that each key is only used once. This mean that know about $c$ not affect $P(M=m)$ and if you know $c$ you can't access any information about $m$. But as yyyyyyy mentioned,since $k\oplus \operatorname{rev}(k)$ is symmetric, if $\operatorname{Enc}(k,m)$ was symmetric we know $m$ is symmetric and else, $m$ is not symmetric. So we can gain some information about $m$ and this system is not perfectly secret.

If you delete $\operatorname{rev}(k)$ this system have Perfect Secrecy.