3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hint: $k\oplus\operatorname{rev}(k)$ is symmetric (i.e. a palindrome). $\endgroup$ – yyyyyyy Jan 10 '16 at 1:28
  • $\begingroup$ I saw that already. My problem is that I have no idea how to formalize this with respect to the equation. $\endgroup$ – Paul Herman Jan 10 '16 at 1:33
  • $\begingroup$ What is $P(M=m\mid C=c)$ if $m\oplus c$ is not symmetric? $\endgroup$ – yyyyyyy Jan 10 '16 at 1:46
  • 1
    $\begingroup$ 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? $\endgroup$ – Maarten - reinstate Monica Jan 10 '16 at 10:53
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Maarten - reinstate Monica Jan 10 '16 at 11:33
  • $\begingroup$ 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. $\endgroup$ – Paul Herman Jan 10 '16 at 13:21
  • $\begingroup$ First paragraph is a proof for your question. Last line just is a point. $\endgroup$ – Meysam Ghahramani Jan 10 '16 at 13:58
  • $\begingroup$ I agree that it is an intuitive proof, however that doesn't seem too formal. $\endgroup$ – Paul Herman Jan 10 '16 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.