# Indistinguishability attack example

I want solve the next exercise. The author defined the experiment for the cryptosystem $\Pi$, the adversary $A$ and the security parameter $n$ as follows

$\mathsf{PRIV_{EAV}}(\Pi,A,n)$

1. The adversary $A$ get the input $1^n$ and choose two messages $m^{(0)}$, $m^{(1)} \in M$ with same length;
2. One key $k \in K$ is generated using $\mathsf{Gen}(1^n)$, and one bit is chosen uniformly at random. Then the message $m^{(b)}$ is encrypted and sent to $A$;
3. Eventually $A$ outputs b';
4. If $b=b'$, the experiment result is 1. Otherwise 0.

Definition A cryptosystem $\Pi$ has indistiguishable ciphertexts in the presence of an eavesdropper if for all adversaries $A$ there exist a negligible function $\mathsf{negl}$ such that

$$\Pr[\mathsf{PRIV_{EAV}}(\Pi,A,n)=1]\leq 1/2 + \mathsf{negl}(n).$$

My question: How will I be able to prove that the cryptosystem described below is not secure under the definition above.

Cryptosystem $\Pi$:

• $\mathsf{Gen}(1^n)$ chooses a bitstring $k \in \{0,1\}^n$ uniformly at random,
• $\mathsf{Enc}(m,k)$ works as follows: The message $m$ is split into blocks $m_0, m_1, \dots ,m_l$ of $n$ bits. Each block is encrypted separately, as $c_i = m_i \oplus k$. The ciphertext is then the concatenation of the encrypted blocks $c_0, c_1, \dots ,c_l$;
• $\mathsf{Dec}(c,k)$ is analogous to Enc, but permuting $c$ and $m$.

Notation

$K$ is the key space, $M$ the message space and $C$ the ciphertex space

-
Why my question have a -1 vote? –  juaninf May 5 '13 at 3:18
What you should do is proposing an attack and estimating its advantage. How does your adversary choose two plaintexts? –  xagawa May 6 '13 at 9:15

To prove that a scheme is not secure under such a definition you usually would propose an algorithm such that the experiment described in your question outputs $1$ with probability non-negligibly larger than $1/2$.
As this looks very much like a homework problem I will not give you a solution. However constructing the algorithm is actually very simple in this case. You only need to think about how you would choose the messages $m^{(0)},m^{(1)}$ in such a way that ypu would be able to distinguish their ciphertexts.
As a hint: The deterministic nature of the encryption-process could be a problem here, and you can actually distinguish with probability $1$.
Choosing $m_0=m_1$ will never help you. You have to distinguish between the two cases. If the two cases are exactly the same, then they are perfectly indistinguishable for obvious reasons. So no, they have to differ. –  Maeher May 6 '13 at 19:05
I think juaninf may be talking about $m_0$ and $m_1$ as two blocks in one of the plaintexts, in which case he is obviously on a better track. I revised the question to resolve the ambiguity of notation. The two choice messages in the security definition experiment are now $m^{(0)}$ and $m^{(1)}$, while $m_0$, etc refer to blocks of a single plaintext (so one could talk about $m^{(0)}_k$). Maeher: If you like the notation, perhaps consider updating your response? –  Mikero May 6 '13 at 22:25
If there is a choice of $m^{(0)}$ and $m^{(1)}$ that does not allow the adversary to distinguish, then the adversary would be pretty dumb to choose those two messages, wouldn't it? Especially when there are choices it can make that do allow it to distinguish. –  Mikero May 7 '13 at 2:02
@juaninf: $m^{(0)}=m^{(1)}$ is useless, since that guarantees that nobody can distinguish the messages (since they're identical!). Now, $m^{(0)}_0=m^{(0)}_1$, on the other hand... –  Ilmari Karonen May 7 '13 at 5:57
There seems to be some very basic misunderstanding of the experiment here. The adversary is absolutely free in their choice of $m^{(0)},m^{(1)}$. So even if there exists only a single pair that allows you to distinguish, that's fine because you can always choose that pair. Concerning your solution above: It was not the one I had in mind, but assuming that you choose $a,b,c,d$ such that $a \oplus b \neq c \oplus d$ it nevertheless should work. –  Maeher May 7 '13 at 6:25