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

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.

• Hint: $k\oplus\operatorname{rev}(k)$ is symmetric (i.e. a palindrome). – yyyyyyy Jan 10 '16 at 1:28
• I saw that already. My problem is that I have no idea how to formalize this with respect to the equation. – Paul Herman Jan 10 '16 at 1:33
• What is $P(M=m\mid C=c)$ if $m\oplus c$ is not symmetric? – yyyyyyy Jan 10 '16 at 1:46
• Eh, sorry to intrude in your calculations and all, but wouldn't you be able to XOR the first and final bits of the ciphertext (etc) and then get $m_0 \oplus m_{n-1}$ as result? – Maarten Bodewes Jan 10 '16 at 10:53

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.

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.

• Who exactly are you quoting? I think you see more because the first half of the XOR'ed key seems to be the second half in reverse. – Maarten Bodewes Jan 10 '16 at 11:33
• I think you misunderstood the question. I know that if I remove the reversed key it is perfectly secret, however I wanted to prove that this one is not. – Paul Herman Jan 10 '16 at 13:21
• First paragraph is a proof for your question. Last line just is a point. – Meysam Ghahramani Jan 10 '16 at 13:58
• I agree that it is an intuitive proof, however that doesn't seem too formal. – Paul Herman Jan 10 '16 at 14:33