# S-boxes are not linear

By looking for the reason why the S-boxes are not linear, I found the following:

The mappings $B \mapsto S(B)$ are all non-linear, since it holds

$S(000000) \neq 0000$

We notice that at each of the 8 S-boxes $S_1, S_2, \dots, S_8$ , the number at the upper left-hand corner is not equal to zero and so $S$ cannot be linear.

Could you explain to me why at the S-boxes the number at the upper left-hand corner is not equal to zero ?

• Which S-boxes are you talking about ?
– Biv
Mar 2, 2017 at 19:11
• Some reading you might be interested in : sdsu-dspace.calstate.edu/bitstream/handle/10211.10/448/…
– Biv
Mar 2, 2017 at 19:12
• @Biv The ones we use in order to find the rounding function for an encryption system of type feistel. Mar 2, 2017 at 19:20

I don't believe you're really asking 'why did they select an SBox with 0 being mapped to something other than 0"; essentially, that's what the designers picked.

Instead, it is "why does $S(0) \ne 0$ prove that S is nonlinear".

And, the answer to that is, yes, it does, but only pedantically.

A function $S$ is linear if $S(a) + S(b) = S(a + b)$ for every $a, b$ (and some reasonable addition function "+", generally, we use bitwise xor). (And, this isn't quite sufficient if the range of $S$ is infinite, we never have to worry about that in crypto).

Now, if we select $a = b = 0$, this simplifies to $S(0) + S(0) = S(0+0) = S(0)$; or $S(0) = 0$.

Hence, if $S(0) \ne 0$, we know that the definition of linearity doesn't hold in all cases.

On the other hand, in crypto, when we talk about linear functions, we often really mean affine; the definition of this is $S(a) + S(b) = S(a + b) + c$, for all $a, b$ and some constant $c$ (which is independent of $a, b)$. The reason we're interested in this is that essentially all the mathematical tools an attacker can use against a linear function also work against an affine one, and so we tend not to make a strong distinction.

And, just looking at $S(0)$ won't tell you if a function is affine, as we have $S(0) = c$, and $c$ can be any value. If + is bitwise xor, you need to examine at least 4 values to prove that an Sbox is not affine.

• We have the following: For the 6-Bit block $B=b_1 b_2 b_3 b_4 b_5 b_6$ , the value $S(B) \in \mathbb{F}_2^4$ is computed as follows. The bitpair $b_1 b_6$ gets interpreted as a binary representation of a natural number $s \in \{ 0,1,2,3 \}$ and fixes the row s of the matrix S. The binary word $b_2 b_3 b_4 b_5$ gets interpreted as a binary interpretation and fixes the column $t \in \{0,1, \dots, 15\}$ of the matrix S. The number, that is at the s-th column and t-th row of the matrix S, is at the {0,1,..., 15} and so it is represented by 4 bits. This 4-bit word is then the desired value S(B). Mar 2, 2017 at 20:49
• So in this case where we have the word 000000, 00 represents the natural number 0 and so also the binary word 0000. And we consider the number at the 0-th column and 0-th row of the S-box to be non-zero, so that $S$ is not-linear. Have I understood it right? @poncho Mar 2, 2017 at 20:50
• @Evinda: actually, the mapping of the bitpattern to the integers isn't very relevant to the DES sboxes (except for looking up the mapping in the published tables). Also, you've shown that the sbox is nonlinear; you haven't shown that it isn't affine (it isn't; you just haven't shown that) Mar 2, 2017 at 22:14
• If we take into consideration the first definition that you wrote for the linear functions, then the reason I wrote that $F(k,R)=S_1(B_1)S_2(B_2) \dots S_8(B_8)$ is not linear is right, isn't it? @poncho Mar 3, 2017 at 9:28
• Also, what do you mean with: the mapping of the bitpattern to the integers isn't very relevant to the DES sboxes . You mean that we don't need the fact that 00 represents the natural number 0 and so also the binary word 0000? Don't we need this in order to set $S[0,0] \neq 0$ ? And because of the latter the F that we get is not linear? Or have I understood it wrong? @poncho Mar 3, 2017 at 10:27