My studies in cryptography have been quite detailed so far, however, one area that hasn't been explained to me is how S-Boxes are typically designed. Typically, the S-boxes are provided "as is" by the developers of the algorithm, but I am looking for information on what type of considerations cryptographers evaluate when they design an S-box. Are the numbers in the lookup table chosen at random? Are they generated mathematically? If so, what are some types of maths used and why? Feel free to choose an example cipher or two in your explanation.
2 Answers
The main consideration is to ensure no strong differential or affine properties.
Random S-Boxes are actually not bad in this regard though not necessarily optimal.
However Most would not trust "Random" S-boxes and prefer a Nothing-Up-My-Sleeve choice. For fear the designer may have cleverly selected the values to enable some unknown attack. We want some plausible explanation for why the specific values were chosen.
The AES S-boxes are such, they were selected based on a simple mathematical formula, and yet can be shown to be fairly resilient to differential and linear cryptanalysis.
-
$\begingroup$ How is a "Nothing-Up-My-Sleeve choice" different to a random choice? You'd still be picking one of many funky polynomials out of the blue, or making up a weird affine transformation. Is it that it's difficult to explain a random shuffle? You could use a really obvious NUMS seed for a PRNG. $\endgroup$ Aug 11, 2018 at 21:06
-
$\begingroup$ If you are using a well known PRNG and a simple seed (e.g zero) that would qualify. The idea is that it adds n extra layer of difficulty to not only come up with sinister values but also have a simple explanation for them. I should be able to explain the selection of values in a simple sentence understandable by most CS majors. $\endgroup$ Aug 12, 2018 at 2:46
you mainly consider cryptographically properties such as differential, linear , algebraic and others. However, there are different ways to generate sbox , one way is to do the inverse in galois field and affine transformation, another is using genetic algorithm (ref), also another way is to create larger s-boxes from smaller s-boxes. the later way is good when you have constrains such as size especially when you implement the sbox with masking.