Non-linearity of DES S-boxes
In normal arithmetic, we have the distributive property of multiplication over addition.
𝑎(𝑥 + 𝑦) = 𝑎𝑥 + 𝑎𝑦
This is true no matter what the values of the variables have.
In DES, addition is replaced by exclusive-or ⊕ and multiplication by the S-boxes. So the equation above would be written:
𝑆𝑖(𝑥 ⊕ 𝑦) = 𝑆𝑖(𝑥) ⊕ 𝑆𝑖(𝑦)
This is true for some values of 𝑥, 𝑦 but not for all! For
example:
In fact:
𝑆 (1)⊕𝑆 (2)=0⊕4=4 11
≠
𝑆 (1⊕2)=𝑆 (3)= 15 11
Count of unique pairs of 6-bit values:
2080
S box 1 equality: 145, 6.97%
S box 2 equality:
S box 3 equality:
S box 4 equality:
S box 5 equality:
S box 6 equality:
S box 7 equality:
S box 8 equality:
139, 6.68%
187, 8.99%
166, 7.98%
136, 6.54%
193, 9.28%
142, 6.83%
175, 8.41%