3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ actually with AES, that may not be entirely accurate, as the permutation layer does not provide complete diffusion. performing it twice will diffuse the input better $\endgroup$ – Richie Frame Mar 15 '15 at 6:31
3
$\begingroup$

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).
| improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I disagree with the answer, which as written would allow to wrongly conclude that 3DES is no safer than DES, on the grounds that 3DES is 3 times DES performed in sequence and is a permutation (or substitution) since DES is one. $\;$ Also I'm reading the question as about the different assertion that iterating the same permutation (or substitution) does not increase security (which is wrong). $\endgroup$ – fgrieu Mar 15 '15 at 12:36
  • $\begingroup$ @fgrieu I guess this could be meant to apply to unkeyed permutations/substitutions only? $\endgroup$ – Paŭlo Ebermann Mar 15 '15 at 13:20
  • $\begingroup$ @PaŭloEbermann: a public/unkeyed permutation/substitution is not, by itself, safe. It can lead to safety of a cryptographic algorithm embedding it (and that's the context of the question). In that context, for some permutation/substitution and cryptographic algorithm, iterating the permutation/substitution can increase safety, as illustrated in the second paragraph of my answer. While the example detailed is contrived, I could construct a natural one, with a simple public/unkeyed permutation/substitution increasing security when iterated. $\endgroup$ – fgrieu Mar 15 '15 at 14:20

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.