Return to Answer

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).

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).

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 wrong.

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=3\\ 177&\text{ if }x=0\\ 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 wrong in hard sciences).

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).

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 wrong.

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=3\\ 177&\text{ if }x=0\\ 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 7 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 wrong in hard sciences).

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 wrong.

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=3\\ 177&\text{ if }x=0\\ 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 wrong in hard sciences).