Tell me more ×
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.
up vote 7 down vote favorite
3

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

2 Answers

up vote 7 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
@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
up vote 3 down vote

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

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.