# Desirable S-box properties

What desirable properties should an S-box have?

My current standard selection process is to just pick them at random and verify that they fit the following criteria:

• The probability that any random two bits $S[a]_b$ and $S[c]_d$ are equal (for any random $a$, $b$, $c$ and $d$) is 50%.
• The probability that any random two bits $S[a]_n$ and $a_n$ are equal (for any random $a$ and $n$) is 50%.
• No entries exist such that $S[a] = a$
• No entries exist such that $S[a] = \bar{a}$

Are there any other important properties that need to be applied?

Edit My reasons for asking are that I wish to combine this S-Box design with a CBC mode cipher as discussed on this question.

-

My rational is that `S[a] = a` provides no benefit and `S[a] = !a` will always maintain the same bit "pattern" as its input. Since the idea of an S-box is to provide "confusion" (as defined by Shannon), it seems reasonable to ensure that neither of these cases are allowed. I may, however, be incorrect. – Polynomial Nov 23 '11 at 14:41
The output of the cipher has the avalanche property and appears random, but the construction of the S-box is not random. It's a case of not allowing any correlation, rather than specifying that a particular output is not allowed. – Polynomial Nov 23 '11 at 14:52
– woliveirajr Nov 23 '11 at 15:00
It doesn't really explain why they made the choices they did, though. It just says "this is the S-box and these are the choices we made". I'm really looking for answers that provide both an explanation of the facts and the reasoning behind making the choices. – Polynomial Nov 23 '11 at 15:05
– woliveirajr Nov 23 '11 at 15:20

## 2 Answers

The following information about the DES S-Box might be useful (taken from here):

DES Design Criteria

• there were 12 criterion used, resulting in about 1000 possible S-Boxes, of which the implementers chose 8

• these criteria are CLASSIFIED SECRET

• however, some of them have become known

The following are design criterion:

R1: Each row of an S-box is a permutation of 0 to 15

R2: No S-Box is a linear of affine function of the input

R3: Changing one input bit to an S-box results in changing at least two output bits

R4: S(x) and S(x+001100) must differ in at least 2 bits

The following are said to be caused by design criteria

R5: S(x) [[pi]] S(x+11ef 00) for any choice of e and f

R6: The S-boxes were chosen to minimize the difference between the number of 1's and 0's in any S-box output when any single input is held constant

R7: The S-boxes chosen require significantly more minterms than a random choice would require

For Rijndael, things were different as the S-Box in Rijndael had to meet certain requirements mathematically and cryptanalytically

-

Could you explain criteria R5 and R7, please? And is criteria R2 essentially "No S[x] must exist for x where the result is a rotation of x, e.g. `01010010 -> 10010100`"? – Polynomial Nov 24 '11 at 6:58
@Polynomial: There are many more linear and affine functions than just rotations.  Basically, R2 says (assuming the mean linear/affine over $\{0,1\}$) that no S-box may be writable as $S(x) = a_0 \oplus a_1x_1 \oplus \dotsb \oplus a_nx_n$, where $x_1 \dotsc x_n$ are the bits of $x$ and $a_0 \dotsc a_n$ are arbitrary bitstrings. – Ilmari Karonen Nov 24 '11 at 12:16

The answer is: it depends.

It depends on how you plan to use your S-box. Presumably you are going to use your S-box in some block cipher. In that case, you have to look at what properties you need from the S-box, and then generate the S-box accordingly.

You can't separate the design of the S-box from the design of the rest of the cipher. There is no universal set of criteria that make for a good S-box. For instance, AES had one set of criteria for their S-boxes. DES had a totally different set of criteria.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 17, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9486016035079956, "perplexity_flag": "middle"}