Substitution box
Encyclopedia
In cryptography
, an S-Box (Substitution-box) is a basic component of symmetric key algorithms which performs substitution. In block cipher
s, they are typically used to obscure the relationship between the key and the ciphertext
— Shannon's property of confusion
. In many cases, the S-Boxes are carefully chosen to resist cryptanalysis
.
In general, an S-Box takes some number of input bit
s, m, and transforms them into some number of output bits, n: an m×n S-Box can be implemented as a lookup table
with 2m words of n bits each. Fixed tables are normally used, as in the Data Encryption Standard
(DES), but in some cipher
s 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 of a fixed table is this 6×4-bit S-Box from DES (S5):
Given a 6-bit input, the 4-bit output is found by selecting the row using the outer two bits (the first and last 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
known only to its designers — might have been planted in the cipher. The S-Box design criteria were eventually published (in ) after the public rediscovery of differential cryptanalysis
, 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.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, an S-Box (Substitution-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 cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
s, they are typically used to obscure the relationship between the key and the ciphertext
Ciphertext
In cryptography, ciphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher...
— 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 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 that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...
.
In general, an S-Box takes some number of input bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
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. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than...
with 2m words of n bits each. Fixed tables are normally used, as in the Data Encryption Standard
Data Encryption Standard
The Data Encryption Standard is a block cipher that uses shared secret encryption. It was selected by the 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. It is...
(DES), but in some cipher
Cipher
In cryptography, a cipher is an algorithm for performing encryption or decryption — a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. In non-technical usage, a “cipher” is the same thing as a “code”; however, the concepts...
s the tables are generated dynamically from the key; e.g. the Blowfish
Blowfish (cipher)
Blowfish is a keyed, symmetric block cipher, designed in 1993 by Bruce Schneier and included in a large number of cipher suites and encryption products. Blowfish provides a good encryption rate in software and no effective cryptanalysis of it has been found to date...
and the Twofish
Twofish
In cryptography, Twofish is a symmetric key 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 contest, 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 general security topics, computer security and cryptography, and is the founder and chief technology officer of BT Managed Security Solutions, formerly Counterpane Internet...
describes IDEA
International Data Encryption Algorithm
In cryptography, the International Data Encryption Algorithm is a block cipher designed by James Massey of ETH Zurich and Xuejia Lai and was first described in 1991. As a block cipher, it is also symmetric. The algorithm was intended as a replacement for the Data Encryption Standard[DES]...
's modular multiplication step as a key-dependent S-Box.
One good example of a fixed table is this 6×4-bit S-Box from DES (S5):
S5 | Middle 4 bits of input | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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 (the first and last 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 that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...
known only to its designers — might have been planted in the cipher. The S-Box design criteria were eventually published (in ) 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. In the broadest sense, it is the study of how differences in an input can affect the resultant difference at the output...
, 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.
See also
- BijectionBijectionA bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
- Boolean function
- Nothing up my sleeve numberNothing up my sleeve numberIn cryptography, nothing up my sleeve numbers are any numbers which, by their construction, are above suspicion of hidden properties. They are used in creating cryptographic functions such as hashes and ciphers. These algorithms often need randomized constants for mixing or initialization purposes...
- Substitution cipherSubstitution cipherIn cryptography, a substitution cipher is a method of encryption by which units of plaintext are replaced with ciphertext according to a regular system; the "units" may be single letters , pairs of letters, triplets of letters, mixtures of the above, and so forth...
- Rijndael S-boxRijndael S-boxThis article describes the S-box used by the Rijndael cryptographic algorithm.- Forward S-box :The S-box is generated by determining the multiplicative inverse for a given number in GF = GF[x]/, Rijndael's finite field...
- Permutation boxPermutation boxIn cryptography, a permutation box is a method of bit-shuffling used to permute or transpose bits across S-boxes inputs, retaining diffusion while transposing....