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)?
-
3$\begingroup$ attacks are easier? at a certain point, the workload becomes less than brute force, and the cipher is considered broken $\endgroup$– Richie FrameDec 7, 2017 at 6:54
1 Answer
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.