cryptography Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...

, an S-box (substitution-box) is a basic component of symmetric key algorithms which performs substitution. In

block cipher In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called ''blocks''. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage a ...

s, they are typically used to obscure the relationship between the key and the

ciphertext In cryptography, ciphertext or cyphertext 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 ...

, thus ensuring Shannon's property of

confusion In psychology, confusion is the quality or emotional state of being bewildered or unclear. The term "acute mental confusion"

. Mathematically, an S-box is a nonlinear

vectorial Boolean function In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth functi ...

. In general, an S-box takes some number of input bits, ''m'', and transforms them into some number of output bits, ''n'', where ''n'' is not necessarily equal to ''m''. An ''m''×''n'' S-box can be implemented as a

lookup table In computer science, a lookup table (LUT) is an array data structure, array that replaces runtime (program lifecycle phase), runtime computation of a mathematical function (mathematics), function with a simpler array indexing operation, in a proc ...

with 2^''m'' words of ''n'' bits each. Fixed tables are normally used, as in the

Data Encryption Standard The Data Encryption Standard (DES ) is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cryp ...

(DES), but in some

cipher In cryptography, a cipher (or cypher) 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''. To encipher or encode i ...

s the tables are generated dynamically from the key (e.g. the Blowfish and the Twofish encryption algorithms).

Example

One good example of a fixed table is the S-box from DES (S₅), mapping 6-bit input into a 4-bit output: 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".

Analysis and properties

When DES was first published in 1977, the design criteria of its S-boxes were kept secret to avoid compromising the technique of

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 information input can a ...

(which was not yet publicly known). As a result, research in what made good S-boxes was sparse at the time. Rather, the eight S-boxes of DES were the subject of intense study for many years out of a concern that a '' backdoor'' (a

vulnerability Vulnerability refers to "the quality or state of being exposed to the possibility of being attacked or harmed, either physically or emotionally." The understanding of social and environmental vulnerability, as a methodological approach, involves ...

known only to its designers) might have been planted in the cipher. As the S-boxes are the only nonlinear part of the cipher, compromising those would compromise the entire 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 such that it was no better than brute force. Biham and Shamir found that even small modifications to an S-box could significantly weaken DES. Any S-box where any linear combination of output bits is produced by a bent function of the input bits is termed a perfect S-box. S-boxes can be analyzed using

linear cryptanalysis In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine Affine may describe any of various topics concerned with connections or affinities. It may refer to: * Affine, a Affinity_(law)#Terminology, relat ...

and

in the form of a Linear approximation table (LAT) or Walsh transform and ''Difference Distribution Table'' (DDT) or autocorrelation table and spectrum. Its strength may be summarized by the ''nonlinearity'' (bent, almost bent) and ''differential uniformity'' (perfectly nonlinear, almost perfectly nonlinear).

References

Sources

External links

A literature survey on S-box design

"Substitution Box Design based on Gaussian Distribution"
{{Cryptography navbox , block Cryptographic algorithms

Example

Analysis and properties

See also

References

Further reading

Sources

External links