Why does consecutive permutations or consecutive substitutions not enhance security?

Question

My professor stated that permutations which are done repeatedly does not further enhance security than just one permutation. He also stated that fact this applies to consecutive substitutions as well. Algorithms such as AES which intertwine permutation and substitution in each round does in fact increase security. I understand this is because if they are intertwined, then the substitution effect will be diffused by the following permutation. However, if he were to ask this question in a test: why does repeated permutations or substitutions not enhance security? I won't be able to think of a good answer.

Answer 1

Perhaps the professor was misquoted; the assertion that (in the context of constructing cryptographic algorithms) "permutations which are done repeatedly does not further enhance security than just one permutation" is false.

Proof by an extreme example: consider a variant of DES where we insert after permutation $P$ another permutation $Q=P^{-1}$. This DES variant is unsafe (we removed the diffusion effect of $P$, because $Q\circ P$ is identity). However if in this variant we perform $P$ twice instead of once, we are back to DES (because because $Q\circ(P\circ P)=P)$ and thus iterating $P$ more than once has markedly increased security.

A less contrived example: in a block cipher employing 8-bit S-boxes, the substitution $S$ of $\{0,1\}^8$ (assimilated to $[0\dots255]$) defined as $$S(x)=\begin{cases} 157&\text{ if }x=6\\ 162&\text{ if }x=5\\ 167&\text{ if }x=1\\ 172&\text{ if }x=0\\ 177&\text{ if }x=3\\ 182&\text{ if }x=4\\ 187&\text{ if }x=2\\ 5x+157\bmod256&\text{ otherwise} \end{cases}$$ is likely to make the construction less secure than if $S$ was iterated $97$ times (that's because $S$ matches the linear function $x\to5x+157\bmod256$ for most points, but in $S^{97}$ a majority of inputs have fallen at least once in one of the seven special haphazard cases, so there's no longer a valid linear approximation).

However, iterating a permutation (or substitution) chosen at random (independently of the rest of the algorithm) is unlikely to increase security. It's rather likely to reduce security, especially for highly composites number of iterations (such as $n=60=2\cdot2\cdot3\cdot5$), for that significantly increases the likelihood of at least one undesirable characteristic of the resulting permutation: having a high number of fixed points.

---

If asked in an exam question about cryptographic algorithms "why does repeated permutations or substitutions not enhance security?", one could

• point (as does the other answer) that chaining permutations (resp. substitutions) leads to permutation (resp. substitution), and thus that we could have chosen to perform that permutation (resp. substitution) in the first place, baring difficulty to implement it as a single step;
• explain that repeating the same permutation/substitution leads to a permutation/substitution belonging to a subset of all possible permutations/substitutions (and a narrow one for some iteration counts), which is not in general desirable for security;
• but that in some constructs, iterating a permutation or substitution could be necessary for security, hence the assertion of the exam question is not strictly true (a polite euphemism for false in hard sciences).

Answer 2

The reason two permutations in a row don't increase security is that there is always a third permutation that's equivalent to performing the two permutations in a row. For instance, suppose we have 5 elements, and the following two permutations: $$\begin{align} \sigma_1 &: 12345\to34251 \\ \sigma_2 &: 12345\to43512 \end{align}$$

Then if we apply $\sigma_1$ followed by $\sigma_2$, we send $1$ to $5$ by $\sigma_1$ and then to $3$ by $\sigma_2$; if we work out all of the 5 elements, we get $$\sigma_2\circ\sigma_1 :12345\to52134$$

This is just another permutation (using more common cycle notation, $\sigma_1=(13245)$, and $\sigma_2=(14)(235)$, so $\sigma_2\circ\sigma_1 =(1543)(2)$). As you can see, composing the two permutations just popped out a third permutation; from an attacker's point of view, the fact that we did two permutations is irrelevant, because he can treat it as just one permutation.

With substitutions, it's similar: composing two substitutions gives a third (single) substitution, so there's no difference from an attackers point of view.