3
$\begingroup$

I am reading about S-boxes.

enter image description here

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 ?

Improve this question
$\endgroup$
3
  • $\begingroup$ Which S-boxes are you talking about ? $\endgroup$ – Biv Mar 2 '17 at 19:11
  • $\begingroup$ Some reading you might be interested in : sdsu-dspace.calstate.edu/bitstream/handle/10211.10/448/… $\endgroup$ – Biv Mar 2 '17 at 19:12
  • $\begingroup$ @Biv The ones we use in order to find the rounding function for an encryption system of type feistel. $\endgroup$ – Evinda Mar 2 '17 at 19:20
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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). $\endgroup$ – Evinda Mar 2 '17 at 20:49
  • $\begingroup$ 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 $\endgroup$ – Evinda Mar 2 '17 at 20:50
  • $\begingroup$ @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) $\endgroup$ – poncho Mar 2 '17 at 22:14
  • $\begingroup$ 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 $\endgroup$ – Evinda Mar 3 '17 at 9:28
  • $\begingroup$ 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 $\endgroup$ – Evinda Mar 3 '17 at 10:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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