Full diffusion or Partial diffusion between s-box applications?

Question

In regards to maximizing active s-boxes: is it advantageous to apply the non-linear layer after complete diffusion of the state, rather after then partial diffusion?

Using AES as an example, with the well known mixColumns and shiftRows combination: What if this linear diffusion layer were applied twice in succession between s-box applications, instead of just once?

Doing the math for the regular AES with 2 rounds is simple: \begin{align} 1 + 4 &= 5\\ 4 + 16 &= 20 \\ 5 + 20 &= 25\\ \end{align}

• The first number in each row is the number of different s-boxes at the input of the round.
• The second is the number of differences at the output of the round.
• The third is the sum of the two.
• The first row represents round 1
• The second row represents round 2
• Finally, the two rounds are summed to give the total minimum number of active s-boxes.

So to simulate a double application of the linear diffusion layer, I tried substituting 16 for 4, but was unsure of how to proceed: \begin{align} 1 + 16 &= 17\\ 16 + 256 &= 272\\ 17 + 272 &= 289\\ \end{align}

or should it be:

\begin{align} 1 + 16 &= 17\\ 16 + 32 &= 48\\ 17 + 48 &= 65\\ \end{align}

Or something else entirely? How many active s-boxes over the course of two rounds would such a variant of AES have?

Put succinctly, I guess I really want to know: Is there an cryptanalytic advantage to diffusing the entire state before applying the s-box layer? Or is it better to apply s-boxes more frequently, with "just enough" diffusion between them?

Answer 1

If the linear diffusion layer were applied twice without applying the s-boxes between them, it is possible there might be an iterative differential characteristic with only four active s-boxes per modified 'round' (i.e. instead of a provable minimum of 25 active s-boxes over 4 rounds there could be as few as 16 active s-boxes over 4 'rounds').

Consider for example a state where all four bytes in a single row are active. After SubBytes, all four bytes are still active. After ShiftRows, all four bytes in that same row are still active. Then after MixColumns all sixteen bytes in the state are active. Applying ShiftRows again doesn't change the fact that all sixteen bytes are active. But applying MixColumns again might (assuming the bytes differences are just right) result in a single row of active bytes. If that row is the same row as the one we started with, and if the resulting differences of the active bytes are the same as the differences we started with, then that is an iterative characteristic that only activates 4 s-boxes in each 'round'.

If you want complete diffusion in a single round while still retaining provable minimum numbers of active s-boxes, you should use a 16 x 16 MDS matrix with a branch number of 17, such as this one. But even with such a beast, you can only prove a minimum number of 34 active s-boxes over 4 rounds.