# How to prove that the Permutation cipher is not CPA secure?

Encryption scheme is called a permutation cipher if every plaintext string with letters $a_1,\ldots, a_n$ is encrypted as $a_{\pi(1)}, \ldots, a_{\pi(n)}$ for some (not necessarily uniform) permutation $\pi$.

To break this cipher, one has to distinguish two messages based on their encryptions. I'm trying to solve this by playing a game.

# Two players A and U.

A: send a plaintext message to U (in this example A sends followashore)

U: Encrypt this message and send the cipher text to A

• Input size of $\pi$: m = 6
• $\pi$: $\begin{array}2 &1 &2 &3 &4 &5 &6 \\ &3 &5 &1 &6 &4 &2\end{array}$
• Ciphertext: LEFOOLHEARSO

A: Changes this ciphertext by appending text $p$ of length $l$, which is a multiple of the length of the original plaintext. Let's say A sends LEFOOLHEARSOLEFOOLHEARSO (concatenated the ciphertext with itself)

U: Encrypt this message using the previous permutation?

I'm not sure where to go from here.

• Hint: What are odds that the all-X plaintext gives the all-X ciphertext for a Permutation CIpher? For a random permutation? – fgrieu Sep 15 '15 at 12:17
• For all given plaintext, the cipher will return ciphertext for all? Let's say that you send the same message twice, then what if the cipher returns two different cipher text. – Pete Sep 15 '15 at 12:24
• In a Chosen Plaintext Attack, the attacker chooses the Plaintext that gets enciphered, and the cipher is assumed to supply a corresponding ciphertext. In general, ciphertext might change in different experiments using the same plaintext, except when plaintext and ciphertext belong to spaces of the same size. But my hint suggests an experiment where a single plaintext (consisting of the letter X for every plaintext symbol) is submitted, thus this consideration is secondary. – fgrieu Sep 15 '15 at 12:54
• I really don't get why you would send a ciphertext for U to encrypt unless you want to create a distributed hash function or PRNG. Putting a ciphertext into a PRP will generate a random block of garbage as the ciphertext itself should be indistinguishable from random. Besides that, I've got the strong feeling that you are missing the obvious attacks for $M_1 = M_2$ and $M_1 \neq M_2$ – Maarten Bodewes Sep 15 '15 at 14:25

If $a_i = c$ for all $i$, then clearly $a_{\pi(i)} = c$ for all $i$ as well, regardless of the permutation $\pi$.
Thus, you can choose your two messages $a$ and $b$ such that, say, $a_i = 0$ and $b_i = 1$ for all $i$. This will then also be true for their encryptions under any permutation cipher, allowing you to trivially distinguish the encrypted messages with 100% certainty.