Data Encryption Standard (DES) S-Boxes 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?
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.