Non-Linearity of an Sbox

Question

Non-Linearity of an Sbox affects its resistance towards Linear Cryptanalysis. What happens, if an Sbox has low non-linearity (specially with respect to Linear Cryptanalysis)?

Answer 1

Consider a linear 8-bit s-box $S$:

$$ c=S\cdot p, $$

where $c$ and $p$ are 8-bit vectors, and thus $S$ is an $8\times8$ matrix. This means we can pick 64 different s-boxes in our design. This already gives an intuition on one weakness: there are $8!$ permutations for 8 bits, but we limit our design to "just" 64 of them.

Now on to the fun stuff: differential cryptanalysis. Linear s-boxes have the nice property that for ciphertexts $c, c'$ and their respective plaintexts $p, p'$:

$$ c\oplus c' = S\cdot p \oplus S\cdot p' = S\cdot (p \oplus p'), $$

which is a very much unwanted property of linear s-boxes. In usual symmetric cipher design, a non-linear s-box is the main element to counter this kind of differential cryptanalysis.

For what it's worth, the same can be said about affine s-boxes ($c=S\cdot p \oplus b$ for fixed $b$).

Now consider (simplified) AES, where the s-box is constructed as some form of inversion (technically a multiplicative inverse in the Rijndael finite field):

$$ c\oplus c' = p^{-1} \oplus p^{-1} \neq (p\oplus p')^{-1} $$

Here, the $(\cdot)^{-1}$ operator is not distributive, hence, this simplified attack does not hold.

---

Linear cryptanalysis uses a linear approximation of the s-box. It tries to "model" the $(\cdot)^{-1}$ operator (or the s-box of the studied cipher) as a linear map $S$, such that usually (with high probability) bits from plaintext map on ciphertext bits using this linear model.

If such a model can be found with a high bias, we may be able to distinguish ciphertexts, or even derive (part of) the used key.

AES is designed to be highly non-linear, exactly to resist this kind of attack; the multiplicative inverse is said to be highly non-linear.