23
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Polynomial
    Nov 23, 2011 at 14:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – Polynomial
    Nov 23, 2011 at 14:52
  • $\begingroup$ this seems to be a good paper about s-box: sans.org/reading_room/whitepapers/vpns/… $\endgroup$
    – woliveirajr
    Nov 23, 2011 at 15:00
  • $\begingroup$ 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. $\endgroup$
    – Polynomial
    Nov 23, 2011 at 15:05
  • $\begingroup$ let us continue this discussion in chat $\endgroup$
    – woliveirajr
    Nov 23, 2011 at 15:20

5 Answers 5

Reset to default
19
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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"? $\endgroup$
    – Polynomial
    Nov 24, 2011 at 6:58
  • 1
    $\begingroup$ @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. $\endgroup$
    – Ilmari Karonen
    Nov 24, 2011 at 12:16
11
$\begingroup$

Desirable Properties

For simplicity, I’m skipping some of the details here… but the main criteria of a good s-box are: miul

  • It should have balanced component functions,
  • The non-linearity of its component functions should be high,
  • The non-zero linear combinations of its component functions should be balanced and highly non-linear,
  • It should satisfy SAC (strict avalanche criterion),
  • It should have a high algebraic degree.

Yet, it’s hardly possible to achieve all those goals 100%. Nevertheless, there is somewhat of a consensus on what properties an “Ideal S-Box Properties” would possess…

Ideal S-Box Properties

  • All linear combinations of s-box columns are bent.
  • All entries in the s-box XOR table are 0 or 2.
  • The s-box satisfies MOSAC (aka „Maximum order SAC“).
  • The s-box satisfies MOBIC (aka “Maximum order BIC”).
  • The set of weights of rows has a binomial distribution with mean $m / 2$.
  • The set of weights of all pairs of rows has a binomial distribution with mean $m / 2$.
  • The columns each have Hamming weight $2^{(n− 1)}$.

At least, that would be the expected properties in an ideal world.

Practically, making sure s-boxes satisfy all desired properties is hard already and working towards satisfying all “ideal” properties is definitely a goal, but chances are you might not reach all “ideal” goals to your fullest satisfaction. Especially when cryptography isn’t your day job where you happen to have plenty of R&D resources to back your efforts.

I guess this also explains to you why they call it “designing” s-boxes. Fact is, you can’t just throw some shuffled byte-values into a 2D array and expect s-box creation to be completed. An s-box is a part of the cipher you create it for. An s-box is meant to add security. Depending on the individual cipher algorithm design, a low-quality s-box can break the neck of each and every person that might use the cipher. Therefore, it’s utterly important that you don’t mess things up along the lines of “oh, that 2D array of values looks random enough to me”.

Make No Mistake – S-Boxes Are Not Random

You have to realize that the most important thing an s-box adds to a block cipher is “non-linearity“. And you can trust in the fact that the chances that you’ll manage to create a good s-box randomly by using your current criteria are very minimal… very, very minimal!

See, an s-box is not just a randomly permuted set of values (may it be bits, words, integers, or whatever) with some equalized bits to make it look somewhat balanced. Creating s-boxes can be seen as a mathematical design step. It involves working with and checking on things like boolean functions, truth tables, hamming weights, the distance between the function and the set of all affine functions, etc.

In short: an s-box is not something you quickly wrap up in an afternoon, and it’s certainly not something you can create “randomly” or with the specifics you’ve defined. The reason is simple: your whole block cipher depends on the non-linearity and other characteristics of that s-box. Such s-boxes are rare, while the rest of potential combinations is either linear or completely distinguishable from randomness. As you might have read here and there: if an adversary can pinpoint one or more distinguishers, the adversary gains knowledge that can potentially be used to successfully break a way into your ciphertext. Cipher algorithms using s-boxes rely on s-box non-linearity to be secure. If you replace the s-box(es) without knowing what you’re doing, you’re risking to break a once perfectly secure cipher by removing its heart.

Personal Advise

Please, do not simply create a random s-box that fits your listed criteria and throw it into some cipher algorithm. The chance that you introduce a wide-open door for attackers is too big to even consider it.

Literature

To be sure you get the right idea about what an s-box is and how s-boxes are created, I would like to point you to the following papers:

Personally, I'd like to advise you to start reading “The Design Of S-Boxes” by Cheung, as that will most probably make it easier for you to grasp the whole concept… while getting a clear picture of what you might already know and what you still need to do some research on. After all, there are dozens of papers out there that handle s-box design. Depending on your personal knowledge level, you’ll surely find yourself reading additional papers that handle certain specifics of s-box design and analysis.

Get The Picture

If you want to dive in head-first and quickly see what I’m talking about, visit YouTube at “Mod-01 Lec-17 Overview on S-Box Design Principles” where Prof. Mukhopadhyay (Department of Computer Science and Engineering, IIT Kharagpur) roughly explains it. Even if you can’t follow him, it’ll surely give you a good, first impression why s-box design is a bit more complicated than randomly shuffling an array.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I have not seen an s-box that satisfies SAC, the target is to minimize the distance from SAC in the negative direction, and maximize the number of entries in the strict avalanche table that meet or exceed $2^{n-1}$ $\endgroup$
    – Richie Frame
    Sep 2, 2014 at 3:45
  • $\begingroup$ @RichieFrame Honestly, it doesn’t surprise me you haven’t seen them yet (for example: DES and AES s-boxes don’t satisfy SAC). But nevertheless, I think we’re talking somewhat about the same thing here. See, I never said all criteria can be attained to their maximum effect. It’s well known that we can’t achieve all good properties we would like. In practice, we have to decide which properties are more important. (As D.W. correctly noted in his answer: it depends on the application.) But that doesn’t change the list of desirable properties. $\endgroup$
    – e-sushi
    Sep 2, 2014 at 15:29
  • $\begingroup$ What do you mean by "component functions"? $\endgroup$
    – Melab
    Jan 19, 2018 at 2:12
  • $\begingroup$ @Melab Component functions are the linear combinations (with non all-zero coefficients) of the coordinate functions of the S-box. Their set is the vector space spanned by the coordinate functions, deprived of the null function if the coordinate functions are F2-linearly independent. For further reading, use your favorite search engine and look for "s-box component functions". $\endgroup$
    – e-sushi
    Jan 19, 2018 at 5:05
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

I would just like to add that another important property of S-boxes when using directly on input (e.g. in Substitution-Permutation networks) is resistance to differential cryptoanalysis. Differential cryptoanalysis depends on the fact that a certain differential characteristic between two chosen inputs (I0 and I1) propogates to a differential characteristic between two outputs. A wonderful demonstration and easy to understand explanation can be seen here where a flawed S-box is generated to demonstrate this fact. There are very few good S-boxes, for instance, 4-bit S-boxes were all enumarated of which only 16 optimal ones were found (and among those there are few most optimal), this means that out of a possible 16! (approx. 2^44.2) only 2^4 acceptable ones were found.

Improve this answer
$\endgroup$
0
$\begingroup$

Criteria of Good S-Box **• Balanced Component functions

• Non-linearity of Component functions high

• Non-zero linear combinations of Component functions balanced and highly non-linear

• Satisfies SAC

• High Algebraic degree**

Hope it helps

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I don't think that this is helpful if you don't supply any information that supports your claim. $\endgroup$
    – miracle173
    Jul 20, 2016 at 10:19
  • 1
    $\begingroup$ Not only is any kind of logical reasoning missing from this list, the keywords also are too unspecific to add any new information. Considering there are already well-written answers and this is the 3rd revival of the question (see answer dates), five years after the question, this seems a little pointless. $\endgroup$
    – tylo
    Jul 21, 2016 at 13:38

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