S-box

In cryptography , a designated S-box ( English substitution box ) a basic component of symmetric cryptosystems .

use

An m × n S-Box is a - usually non-linear - substitution operation in which an m-digit binary number is replaced by an n-digit binary number. For example, it can be implemented with a table that contains 2 ^{m of} cells. Depending on the application, it may be necessary for this mapping to be invertible (in the sense of bijective ).

S-boxes are used in block ciphers such as DES and Blowfish to blur the relationship between plain text and ciphertext ( called confusion in cryptological terminology ).

The DES algorithm uses eight different S-boxes, some of which also implement Shannon's principle of diffusion . This can be easily understood: Changing an input bit changes at least 2 output bits. This behavior is due to the design of the S-boxes. In the case of complete diffusion, on the other hand, the strict Avalanche Criterion (SAC) would be met and changing an input bit would change every output bit with a probability of 0.5.

S-boxes must be designed very carefully in order to withstand cryptanalysis , especially linear and differential cryptanalysis .

conditions

An S-Box should meet the following requirements:

• Completeness : Each output bit is dependent on each input bit.
• Avalanche : A change in an input bit results in an average change in half of all output bits.
• Non-linearity : No output bit is linearly or affinely dependent on an input bit. This should not even be the case.
• Correlation immunity : As long as only some of the input bits are known, no conclusions can be drawn about the output bits. And vice versa.

Static or dynamic

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

implementation

The obvious solution is the implementation as an array with elements, each of which contains a b- bit long output. The a input bits are interpreted as a number that designates the array element with the associated output. ${\displaystyle 2^{a}}$

The S-Box can also be implemented with Boolean operations . The input bits are each in the same bit position in a data words, and the b output bits are calculated by combining these data words with bit-wise operators . With a word length of w bits, w substitutions occur in parallel. Serpent is a block cipher designed for this method.

example

An example is this static 6 × 4-bit S-Box (S ₅ ) from DES:

S 5		Middle 4 bits of the input value
		0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
Outer bits	00	0010	1100	0100	0001	0111	1010	1011	0110	1000	0101	0011	1111	1101	0000	1110	1001
	01	1110	1011	0010	1100	0100	0111	1101	0001	0101	0000	1111	1010	0011	1001	1000	0110
	10	0100	0010	0001	1011	1010	1101	0111	1000	1111	1001	1100	0101	0110	0011	0000	1110
	11	1011	1000	1100	0111	0001	1110	0010	1101	0110	1111	0000	1001	1010	0100	0101	0011

An input value with 6 bits is assumed here. The 4-bit output value results from the line with the two outer bits and the column with the 4 inner bits of the input value. In the example, the input value " 0 1101 1 " has the outer bits " 01 " and the inner bits "1101". The associated output value would therefore be "1001".

Individual evidence

1. ↑ Walter Fumy, Hans Peter Rieß: Kryptographie : Design and analysis of symmetrical cryptosystems . Oldenbourg, Munich / Vienna 1988, ISBN 3-486-20868-3 .
2. ↑ Bruce Schneier: Applied Cryptography . Protocols, Algorithms and Source Code in C. 2nd edition. John Wiley & Sons, New York 1996, ISBN 0-471-11709-9 , pp. 349-350 .