I read that the S-boxes introduce the much needed nonlinear behavior to DES. Can someone give me a lay mans explanation of why the effect of the S-boxes is said to be non-linear?
$\begingroup$
$\endgroup$
-
$\begingroup$ because you can't achieve the same transformatios solely using XOR on bits and changing their position. $\endgroup$ – SEJPM♦ Dec 19 '15 at 19:58
$\begingroup$
$\endgroup$
If you take an Sbox and two different inputs $x_1,x_2$ (binary vectors of length 6) the exclusive or ("sum") of the two inputs is does not propagate to the output. So $$S(x_1)\oplus S(x_2) \neq S(x_1\oplus x_2)$$ in general. This means that there is no shortcut allowing one to predict outputs "bit by bit" and build efficient search tables, by just considering the list of outputs
$S(100000),S(010000),S(001000),S(000100),S(000010),S(000001)$$
and obtaining
$$S(a_1~a_2~a_3~a_4~a_5~a_6)=a_1 S(100000)+a_2 S(010000)+\cdots+a_6 S(000001).$$
by linearity. This would lead to very efficient attacks when applied to all 8 Sboxes.
