S-Box

In cryptography, an S- Box ( substitution box english ) denotes a basic component of symmetric cryptosystems.

Use

An S-box is usually a non-linear substitution operation in which an m- digit binary number is replaced by an n- digit binary number. It can be implemented for example with a table containing 2m rows. Depending on the application it may be necessary that this map is invertible (in the sense of bijective ).

S-boxes are used in block ciphers such as DES, to blur the relationship between the plaintext and ciphertext ( specified in the cryptologic terminology confusion ).

The DES algorithm uses eight different S-boxes, even partially implement the Shannon principle of diffusion. This can be easily understood: the change of input bits changes at least two output bits. This behavior is in the design of S-boxes. With complete diffusion, however, the strict avalanche criterion (SAC ) would be met and the change of input bits would change each output bit with probability of 0.5.

S-boxes must be very carefully designed to resist cryptanalysis, especially the linear and differential cryptanalysis.

Requirements

An S- box should meet the following requirements:

• Completeness: Each output bit depends on every input bit.
• Avalanche: The change of an input attracts on average, the change half of all output bits by itself.
• Non-linearity: No output bit is linear or affine depending on an input bit. This should not even be approximately the case.
• Correlation immunity: As long as only one part of the input is known, no conclusions on the output bits can be drawn. And vice versa.

Static or Dynamic

A distinction is made between static and dynamic S- Boxes: While using many block ciphers such as DES or AES fixed (static ) S-boxes, initialize, for example, RC4 and Twofish from the key, the S-box dynamically (so-called: key -dependent S -box ). Static S-boxes have advantages in terms of hardware implementation in terms of speed and memory requirements; dynamic S-boxes can greatly complicate cryptanalysis.

Example

An example is this static 6 × 4 -bit S-box (S5 ) of DES:

Here an input value with 6-bit is assumed. The 4 -bit output value is obtained by the line with the two outer bits and the column with the four inner bits of the input value. In the example, the input value is " 011011 ", the outer bits "01" and the inner bit, " 1101 ". The corresponding output value would therefore be "1001".