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 Frame Dec 7 '17 at 6:54

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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.