S-box Cryptanalytic Resistance

Question

In DES, different S-boxes were tested for cryptanalytic resistance and the most secure one was chosen for the algorithm itself.

How do different S-boxes offer different levels of security against cryptanalysis and how is this tested?

Answer 1

This is only a partial answer to the question, but still: The S-boxes where chosen to maximize confusion and to create an avalanche of change. For example, there were specific properties chosen to make the S-boxes resistant against differential cryptanalysis, by making sure that small differences between different inputs lead to larger differences in the outputs (i.e. the Hamming weight of the difference increases). IIRC, the more straight-forward criteria about differentials include:

1. $HammingWeight(input_1 \oplus input_2) = 1 \Longrightarrow HammingWeight(output_1 \oplus output_2) \geq 2$
2. for any input difference $a$ and output difference $b$: $input_1 \oplus input_2 = a \Longrightarrow Probability(output_1 \oplus output_2 = b) \leq \frac{1}{4}$

Also note that the S-box design interacts with the design of the permutation P. P makes sure that changes are distributed across all the S-boxes.

Some of the properties were chosen to resist specific attacks. For example, the DES S-boxes could have been made more resistant against linear cryptanalysis, but they were not, because the designers were not aware of linear cryptanalysis at the time.

A paper describing the design rationale of the DES S-boxes was published in 1994.