Security of permutation cipher

Question

I would like to understand how secure the permutation cipher is.

I would specifically like to understand the following concrete setup: If the alphabet is $L = \{0,1,\dots , 255\}$ and $\sigma_1, \sigma_2, \dots, \sigma_n $ are permutations on $L$, then we can create a cipher by encrypting the first character in the plaintext by $\sigma_1(\sigma_2(\dots \sigma_n(a_1)))$. Then we can (like with the Enigma machine) rotate $\sigma_1$. That is if for example $$ \sigma_1 = \pmatrix{0 & 1 & 2 & \dots & 254 & 255 \\ 55 & 140 & 7 & \dots & 34 & 82} $$ we rotate so that $\sigma_1$ become $$ \pmatrix{0 & 1 & 2 & \dots & 254 & 255 \\ 140 & 7 & &\dots & 82 & 55} $$ When we have rotated $\sigma_1$ 255 times we rotate $\sigma_2$.

This means that the key basically consists of the permutations $\sigma_1, \dots, \sigma_n$.

My general questions is: How secure is this cipher? I understand that the security will depend on $n$, so if the question is too hard to answer, I would be OK with assuming that $n$ is "large enough". I also understand that this will depend on whether or not one reuses the same key several times, so

Another question is: How does the security depend on whether or not one reuses a key?

(By large enough one could just choose $n$ so that $255^n$ is greater than the size of the cipher text.)

(${\tiny\text{ I am not trying to roll my own crypto. I promise never to use this for anything serious besides trying to learn}}$)

Answer 1

How secure is this cipher?

At first glance, not very. It would appear to be vulnerable to a ciphertext-only attack, for example, the attacker can recover the plaintext given a ciphertext of about 10k (actually, he probably can deal with less), even assuming that all the attacker initially knows is that the plaintext is "ASCII English", and he has no initial knowledge of the $(\sigma_1, \sigma_2, ..., \sigma_n)$ permutations.

Since you're learning, I won't spell out the details. Here is how I started with:

• "ASCII English" is approximately 20% spaces; that is, 20% of the plaintext is the exact same byte value.

• Within a single generation (where "generation" means "within 255 consecutive times we shift only $\sigma_1$), $\sigma_2(\sigma_3(...\sigma_n(P))...)$ will be a fixed permutation; hence the result of that will be the same value 20% of the time.

How can we use that to attempt to reconstruct $\sigma_1$ (up to a circular shift)? How can we correlate data from different generations (hint: it's easier if we just assume that the $\sigma_2(\sigma_3(...\sigma_n(P))...)$ permutations from different generations are independent)? Once we've reconstructed $\sigma_1$, how can we immediately recover the plaintext?