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
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
–  woliveirajr Nov 23 '11 at 15:20

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