# Midori block cipher design: importance of $S_b$ as the S-box

With a use of almost MDS the Midori cipher provides a good diffusion. But why $$S_b$$ is used as S-box and what is its actual importance?

• Did you mean an MDS matrix? I'm -eh- somewhat confused. Commented Jan 6 at 21:35

The lightweight Midori block cipher is a subtitution-permutation network where a round of cipher has a substitution phase where chunks of state are used as inputs to the $$S$$-box and the outputs represent the new state and a permutation phase where the bits of state are passed through an invertible linear function (in particular this function which makes the output chunks dependent on multiple input chunks and vice-versa, a property referred to as diffusion).
It is well-established that block ciphers with linearly combined key need to be highly non-linear in many senses. For example, a purely linear (or affine) block cipher with block size $$B$$ can be broken by collecting roughly $$B$$ matched plain and cipher pairs and applying Gaussian elimination. As the permutation step is a purely linear function, the non-linearity of the cipher can only arise from the $$S$$-box, making it an absolutely critical component of the design.
How then do we specify what properties an appropriately non-linear $$S$$-box should have? The two main lines of attack that use linear structure are linear cryptanalysis and differential cryptanalysis.
To block linear cryptanalysis, we would like for all pairs of non-zero masks $$\alpha$$ and $$\beta$$ (for 4-bit $$S$$-boxes we can think as these masks as 4-bit quantities $$A_3A_2A_1A_0$$ and $$B_3B_2B_1B_0$$) the proportion of $$S$$-box input-output pairs $$(x,y)$$ with $$\alpha\cdot x\oplus\beta\cdot y=1$$ (again, for 4-bit $$S$$-boxes think $$A_3x_3\oplus A_2x_2\oplus A_1x_1\oplus A_0x_0\oplus B_3y_3\oplus B_2y_2\oplus B_1y_1\oplus B_0y_0=1$$) is roughly 0.5.
To block differential cryptanalysis, we would like for all pairs of non-zero differences $$D$$ and $$E$$ that the proportion of input-output pairs such that $$S(x\oplus D)=y\oplus E$$ is close to zero.
There is some tension between these two goals. In the case of 4-bit $$S$$-boxes, it is possible to analyse all possible $$S$$-boxes for their linear and differential characteristics and this was done by Saarinen who showed that the best possible 4-bit $$S$$-boxes have some masks where the probability of the linear form being zero is at worst 0.25 or 0.75 and also have some differences where the proportion of undesirable pairs is 0.25. Given that these characteristics cannot be avoided, the Midori designers aimed to find $$S$$-boxes which were of this optimal form, but which were also involutions (so that the same $$S$$-box can be used for encryption and decryption) while being efficient in an energy consumption sense (see section 4.2 of their paper).