Composition of ciphers – Secgroup Ca' Foscari

So far, we have seen simple historical ciphers and we have discussed how to break them. Modern ciphers, however, are based on very simple operations, such as substitution, xor, …, that are combined in a smart way so to make the overall algorithm strong and really hard to analyse. It is important to keep in mind that combining simple ciphers does not always improve security. For example, consider the shift cipher composed twice. We first shift by k1 and then by k2 modulo 26.

$\begin{matrix} X & \rightarrow & \fbox{Shift} & \rightarrow & \fbox{Shift} & \rightarrow & Y\\ & & \uparrow & & \uparrow \\ & & k1 & & k2 \end{matrix}$

It is clear that this is equivalent to shifting by k1+k2 modulo 26, meaning that applying twice the cipher is the same as applying it once with a key given by the sum of the two keys.

$\begin{matrix} X & \rightarrow &\fbox{Shift}& \rightarrow & Y\\ & & \uparrow \\ & & \begin{matrix}{k1+k2}\\{\mod 26}\end{matrix} \end{matrix}$

This informal reasoning can be made more precise.

Definition (Composition). We consider two ciphers $S^1=({\cal P}^1,{\cal C}^1,{\cal K}^1,E^1,D^1)$ and $S^2=({\cal P}^2,{\cal C}^2,{\cal K}^2,E^2,D^2)$ . We let ${\cal P}^1={\cal C}^1={\cal P}^2={\cal C}^2$ , that we note as ${\cal P}$ and ${\cal C}$ in the following. In this way the output of one cipher is for sure a possible plaintext for the second cipher. We can now define composition as $S^1 \times S^2 = ({\cal P},{\cal C},{\cal K}^1\times{\cal K}^2,E,D)$ with

$\begin{array}{rcl}E_{(k1,k2)}(x) &=& E^2_{k2}(E^1_{k1}(x))\\D_{(k1,k2)}(y) &=& D^1_{k1}(D^2_{k2}(y))\end{array}$

Example. Consider the composition of the two shifts above. Formally we have that $E^1_k(x) = E^2_k(x) = x+k \mod 26$ . Thus,

$\begin{array}{r} E_{(k1,k2)}(x) = E^2_{k2}(E^1_{k1}(x)) = (x + k1 \mod 26) + k2 \mod 26\\ = x + (k1+k2 \mod 26) \mod 26 = E^1_{k1+k2 \mod 26}(x)\end{array}$

This proves that composing the shift cipher twice is equivalent to applying it once using as a key the sum of the two keys k1 and k2.

Exercise. Show that the composition of the shift cipher with the substitution cipher is still a substitution cipher with a different key. Give a constructive way to derive the new key. What happens if substitution is applied before shift?

Exercise. Consider the composition of Vigenére cipher with key ALICE with the shift cipher with key 8. Is the resulting cipher equivalent to a known one? If so, what is the resulting key?

Idempotent ciphers

We have seen that the shift cipher, when repeated twice is equivalent to itself with a different key. When this happens, the cipher $S$ is said to be idempotent, written $S \times S = S$ . In this case we know that iterating the cipher will be of no use to improve its security. Even if we repeat it n times we will still get the initial cipher, i.e., $S^n = S$ .

We have mentioned that modern ciphers are based on simple operations composed together. Another ingredient is, in fact, iteration. Almost any modern cipher repeats a basic core of operations for a certain number of rounds. It is thus necessary that such core operations do not constitute an idempotent cipher.

It can be proved that if we have two idempotent ciphers that commute, i.e., such that $S^1 \times S^2 = S^2 \times S^1$ , then their composition is also idempotent. In this case, we know that iterating their composition is useless. To see why this holds consider one iteration of their composition (recall that function composition is associative):

$\begin{array}{ll}(S^1 \times S^2) \times (S^1 \times S^2)\\ = S^1 \times (S^2 \times S^1) \times S^2 &\mbox{ associative property}\\ = S^1 \times (S^1 \times S^2) \times S^2 &\mbox{ commutative property}\\= (S^1 \times S^1) \times (S^2 \times S^2) &\mbox{ associative property}\\ = S^1 \times S^2 &\mbox{ idempotence of the initial ciphers} \end{array}$

Exercise. Apply the above result to show that the composition of Vigenére and the shift cipher is idempotent.

Lesson learned

We have seen examples of how algebraic properties, such as commutativity, can help simplifying the analysis of a cipher. When developing a robust cipher we need to avoid as much as possible that operations can be rearranged, swapped, simplified.