Substitution box

	Email		Print
	Bookmark		Link

Substitution box

In cryptography

Cryptography

Cryptography is the practice and study of hiding information. In modern times cryptography is considered a branch of both mathematics and computer science and is affiliated closely with information theory, computer security and engineering....
, an S-box is a basic component of symmetric key algorithms which performs substitution. In block cipher

Block cipher

In cryptography, a block cipher is a symmetric key algorithm cipher which operates on fixed-length groups of bits, termed blocks, with an unvarying transformation....
s, they are typically used to obscure the relationship between the Key

Key

Key may refer to:...
and the ciphertext — Shannon's property of confusion

Confusion and diffusion

In cryptography, confusion and diffusion are two properties of the operation of a secure cipher which were identified by Claude Elwood Shannon in his paper, "Communication Theory of Secrecy Systems" published in 1949....
. In many cases, the S-boxes are carefully chosen to resist cryptanalysis

Cryptanalysis

Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information which is normally required to do so....
.

In general, an S-box takes some number of input bit

Bit

A bit is a binary numeral system numerical digit, taking a value of either 0 or 1. Binary digits are a basic unit of information Computer data storage and transmission in digital computing and digital information theory....
s, m, and transforms them into some number of output bits, n: an m×n S-box can be implemented as a lookup table

Lookup table

In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation....
with 2^m words of n bits each.

Discussion

Ask a question about 'Substitution box'

Start a new discussion about 'Substitution box'

Answer questions from other users

Full Discussion Forum

Encyclopedia

In cryptography

Cryptography

Block cipher

Key

Key may refer to:...
and the ciphertext — Shannon's property of confusion

Confusion and diffusion

Cryptanalysis

Bit

Lookup table

Data Encryption Standard

The Data Encryption Standard is a block cipher that was selected by National Bureau of Standards as an official Federal Information Processing Standard for the United States in 1976 and which has subsequently enjoyed widespread use internationally....
(DES), but in some cipher

Cipher

In cryptography, a cipher is an algorithm for performing encryption and decryption — a series of well-defined steps that can be followed as a procedure....
s the tables are generated dynamically from the key; e.g. the Blowfish

Blowfish (cipher)

In cryptography, Blowfish is a key ed, symmetric key algorithm block cipher, designed in 1993 by Bruce Schneier and included in a large number of cipher suites and encryption products....
and the Twofish

Twofish

In cryptography, Twofish is a Symmetric-key algorithm block cipher with a block size of 128 bits and key sizes up to 256 bits. It was one of the five finalists of the Advanced Encryption Standard process, but was not selected for standardisation....
encryption algorithms. Bruce Schneier

Bruce Schneier

Bruce Schneier is an American cryptographer, computer security specialist, and writer. He is the author of several books on computer security and cryptography, and is the founder and chief technology officer of BT Counterpane, formerly Counterpane Internet Security, Inc....
describes IDEA

International Data Encryption Algorithm

In cryptography, the International Data Encryption Algorithm is a block cipher designed by Xuejia Lai and James Massey of ETH Zurich and was first described in 1991....
's modular multiplication step as a key-dependent S-box.

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

S₅		0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
S₅		Middle 4 bits of input
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 intense study for many years out of a concern that a backdoor — a vulnerability

Cryptanalysis

Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information which is normally required to do so....
known only to its designers — might have been planted in the cipher. The S-box design criteria were eventually published (Don Coppersmith

Don Coppersmith

Don Coppersmith is a cryptographer and mathematician. He was involved in the design of the Data Encryption Standard block cipher at IBM, particularly the design of the S-box, strengthening them against differential cryptanalysis....
, 1994) after the public rediscovery of differential cryptanalysis

Differential cryptanalysis

Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions....
, showing that they had been carefully tuned to increase resistance against this specific attack. Other research had already indicated that even small modifications to an S-box could significantly weaken DES.

There has been a great deal of research into the design of good S-boxes, and much more is understood about their use in block ciphers than when DES was released.

Substitution box

See also

External links