Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve 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
    
this seems to be a good paper about s-box: sans.org/reading_room/whitepapers/vpns/… –  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
    
let us continue this discussion in chat –  woliveirajr Nov 23 '11 at 15:20

3 Answers 3

up vote 8 down vote accepted

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

share|improve this answer
    
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
1  
@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.

share|improve this answer

Desirable Properties

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

  • 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.

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’ld 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 on what you might already know and what you might 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.

share|improve this answer
    
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}$ –  Richie Frame Sep 2 at 3:45
    
@RichieFrame Nice… you know, 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. –  e-sushi Sep 2 at 15:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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