Substitution box

In cryptography, a S-Box (Substitution-box) is a basic component of symmetric-key algorithms. In block ciphers, the S-Boxes are used to make the relation between the key and the ciphertext (coded text) difficult to understand–Shannon's property of confusion. The S-Boxes are carefully chosen to resist cryptanalysis (decoding).

In general, an S-Box takes some number of input bits, m, and transforms them into some number of output bits, n: an m×n S-Box can be implemented as a lookup table with 2^m words of n bits each. Fixed tables are normally used, as in the Data Encryption Standard (DES), but in some ciphers the tables are generated dynamically from the key; e.g. the Blowfish and the Twofish encryption algorithms. Bruce Schneier describes IDEA's modular multiplication step as a key-dependent S-Box.

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

S₅		Middle (inner) 4 bits of input
S₅		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

Given a 6-bit input, the 4-bit output is found by selecting the row using the outer two bits, and the column using the inner four bits. For example, an input "011011" has outer bits "01" and inner bits "1101"; the corresponding output would be "1001".

The 8 S-Boxes of DES were the subject of intensive studies for many years cause of a concern that a method of bypassing the DES cipher to obtaining access to the plaintext–a vulnerability (susceptibility) known only to its designers–might have been planted (inserted) in the cipher. In 1994, the S-Box design criteria were finally published by its designers after the public rediscovery of differential cryptanalysis, showing that they had been carefully tuned the design to increase resistance against differential cryptanalysis attacks. Other research had already indicated that even a very small modification to one of the 8 S-Box used by the DES could weaken it very much.

The design of good S-Boxes was the subject of a great amount of research; now much more is understood about their use in block ciphers than when the DES S-Boxes were released.

Related pages

Substitution cipher

References

Kaisa Nyberg (1991). "Perfect nonlinear S-boxes" (PDF). Advances in Cryptology - EUROCRYPT '91. Brighton. pp. 378–386. Archived from the original (PDF) on 2007-09-26. Retrieved 2007-02-20.
Don Coppersmith (1994). "The Data Encryption Standard (DES) and its strength against attacks" (PDF). IBM Journal of Research and Development. 38 (3): 243–250. doi:10.1147/rd.383.0243. Retrieved 2007-02-20.
S. Mister and C. Adams (1996). "Practical S-Box Design". Workshop on Selected Areas in Cryptography (SAC '96) Workshop Record. Queens University. pp. 61–76. Archived from the original (PostScript) on 2006-08-31. Retrieved 2007-02-20.
Schneier, Bruce (1996). Applied Cryptography, Second Edition. John Wiley & Sons. pp. 296–298, 349. ISBN 0-471-11709-9.

Other websites

This short article about mathematics can be made longer. You can help Wikipedia by adding to it.