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}}$)

  • $\begingroup$ That does look a lot like Enigma. I assume the key is some generator $G(k)=\{\sigma_1, \ldots, \sigma_n\}$? $\endgroup$
    – rath
    Apr 16 '14 at 19:44
  • 1
    $\begingroup$ Among many weaknesses: if $i$ and $j$ are in any segment where only the first permutation changed (including at least $i<255$ and $j<255$), then $c_i=c_j\Longleftrightarrow p_i+i≡p_j+j\pmod{256}$. E.g. "FED" encodes to 3 identical bytes. $\endgroup$
    – fgrieu
    Apr 16 '14 at 21:12
  • $\begingroup$ @rath: I am not sure that I understand. So in a sense the key consists of $sigma_1, \dots , \sigma_n$. It is assumed that these permutations are constructed randomly first. $\endgroup$
    – Thomas
    Apr 16 '14 at 21:42
  • $\begingroup$ @Thomas Okay, that clears things up. I was looking for a keyed generator rather than a purely random one, but it has no bearing on your scheme. $\endgroup$
    – rath
    Apr 16 '14 at 22:46

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?

  • $\begingroup$ I don't understand that last part. How can we recover the plaintext if we know $\sigma_1$? $\endgroup$
    – Thomas
    Apr 16 '14 at 21:41
  • $\begingroup$ @Thomas: if we know $\sigma_1$, we can compute $\sigma^{-1}(C)$ for the entire ciphertext in a generation. Within that generation, we know that $\sigma_2(\sigma_3(...\sigma_n(P))...)$ is a fixed permutation, hence $\sigma_1^{-1}(C_i) = \sigma_1^{-1}(C_j)$ (note: those two $\sigma_1$'s have a known shift in relationship to each other) iff the corresponding plaintext bytes are the same. Does this help??? $\endgroup$
    – poncho
    Apr 16 '14 at 22:03
  • $\begingroup$ Yes, I think that makes sense now. So you are saying the same as @fgrieu in this comment above? So one can't recover the entire plain text, but will be able to recover some. $\endgroup$
    – Thomas
    Apr 17 '14 at 19:08
  • $\begingroup$ @Thomas: actually, if you can recover $\sigma_1$, you can recover essentially everything. You can compute $\sigma_1^{-1}(Ciphertext)$, and that gives you essentially a simple substitution cipher within each generation; solving a substituion cipher given 256 bytes of encrypted ASCII English is trivial. $\endgroup$
    – poncho
    Apr 17 '14 at 19:14
  • $\begingroup$ Arh.. ok. Now I see. $\endgroup$
    – Thomas
    Apr 17 '14 at 19:17

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.