S-box

Last updated

In cryptography, an S-box (substitution-box) is a basic component of symmetric key algorithms which performs substitution. In block ciphers, they are typically used to obscure the relationship between the key and the ciphertext, thus ensuring Shannon's property of confusion. Mathematically, an S-box is a nonlinear [1] vectorial Boolean function. [2]

Contents

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. [3] 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 ciphers 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 (S5), mapping 6-bit input into a 4-bit output:

S5Middle 4 bits of input
0000000100100011010001010110011110001001101010111100110111101111
Outer bits000010110001000001011110101011011010000101001111111101000011101001
011110101100101100010001111101000101010000111110100011100110000110
100100001000011011101011010111100011111001110001010110001100001110
111011100011000111000111100010110101101111000010011010010001010011

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". [4]

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 (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 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. [5]

The S-box design criteria were eventually published (in Coppersmith 1994) 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. [6]

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. [7]

S-boxes can be analyzed using linear cryptanalysis and differential cryptanalysis 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). [8] [9] [10] [2]

See also

Related Research Articles

<span class="mw-page-title-main">Advanced Encryption Standard</span> Standard for the encryption of electronic data

The Advanced Encryption Standard (AES), also known by its original name Rijndael, is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.

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 and exchange of data, where such data is secured and authenticated via encryption.

<span class="mw-page-title-main">Data Encryption Standard</span> Early unclassified symmetric-key block cipher

The Data Encryption Standard 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 cryptography.

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 affect the resultant difference at the output. In the case of a block cipher, it refers to a set of techniques for tracing differences through the network of transformation, discovering where the cipher exhibits non-random behavior, and exploiting such properties to recover the secret key.

<span class="mw-page-title-main">Serpent (cipher)</span>

Serpent is a symmetric key block cipher that was a finalist in the Advanced Encryption Standard (AES) contest, where it was ranked second to Rijndael. Serpent was designed by Ross Anderson, Eli Biham, and Lars Knudsen.

In cryptography, confusion and diffusion are two properties of the operation of a secure cipher identified by Claude Shannon in his 1945 classified report A Mathematical Theory of Cryptography. These properties, when present, work together to thwart the application of statistics and other methods of cryptanalysis.

<span class="mw-page-title-main">LOKI97</span> Block cipher

In cryptography, LOKI97 is a block cipher which was a candidate in the Advanced Encryption Standard competition. It is a member of the LOKI family of ciphers, with earlier instances being LOKI89 and LOKI91. LOKI97 was designed by Lawrie Brown, assisted by Jennifer Seberry and Josef Pieprzyk.

In cryptography, Square is a block cipher invented by Joan Daemen and Vincent Rijmen. The design, published in 1997, is a forerunner to Rijndael, which has been adopted as the Advanced Encryption Standard. Square was introduced together with a new form of cryptanalysis discovered by Lars Knudsen, called the "Square attack".

In cryptography, SHARK is a block cipher identified as one of the predecessors of Rijndael.

In cryptography, the eXtended Sparse Linearization (XSL) attack is a method of cryptanalysis for block ciphers. The attack was first published in 2002 by researchers Nicolas Courtois and Josef Pieprzyk. It has caused some controversy as it was claimed to have the potential to break the Advanced Encryption Standard (AES) cipher, also known as Rijndael, faster than an exhaustive search. Since AES is already widely used in commerce and government for the transmission of secret information, finding a technique that can shorten the amount of time it takes to retrieve the secret message without having the key could have wide implications.

<span class="mw-page-title-main">MacGuffin (cipher)</span> Block cipher

In cryptography, MacGuffin is a block cipher created in 1994 by Bruce Schneier and Matt Blaze at a Fast Software Encryption workshop. It was intended as a catalyst for analysis of a new cipher structure, known as Generalized Unbalanced Feistel Networks (GUFNs). The cryptanalysis proceeded very quickly, so quickly that the cipher was broken at the same workshop by Vincent Rijmen and Bart Preneel.

<span class="mw-page-title-main">Boolean function</span> Function returning one of only two values

In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set. Alternative names are switching function, used especially in older computer science literature, and truth function, used in logic. Boolean functions are the subject of Boolean algebra and switching theory.

<span class="mw-page-title-main">ICE (cipher)</span> Block cipher

In cryptography, ICE is a symmetric-key block cipher published by Kwan in 1997. The algorithm is similar in structure to DES, but with the addition of a key-dependent bit permutation in the round function. The key-dependent bit permutation is implemented efficiently in software. The ICE algorithm is not subject to patents, and the source code has been placed into the public domain.

Anubis is a block cipher designed by Vincent Rijmen and Paulo S. L. M. Barreto as an entrant in the NESSIE project, a former research program initiated by the European Commission in 2000 for the identification of new cryptographic algorithms. Although the cipher has not been included in the final NESSIE portfolio, its design is considered very strong, and no attacks have been found by 2004 after the project had been concluded. The cipher is not patented and has been released by the designers for free public use.

In cryptography, integral cryptanalysis is a cryptanalytic attack that is particularly applicable to block ciphers based on substitution–permutation networks. It was originally designed by Lars Knudsen as a dedicated attack against Square, so it is commonly known as the Square attack. It was also extended to a few other ciphers related to Square: CRYPTON, Rijndael, and SHARK. Stefan Lucks generalized the attack to what he called a saturation attack and used it to attack Twofish, which is not at all similar to Square, having a radically different Feistel network structure. Forms of integral cryptanalysis have since been applied to a variety of ciphers, including Hierocrypt, IDEA, Camellia, Skipjack, MISTY1, MISTY2, SAFER++, KHAZAD, and FOX.

In cryptography, Q is a block cipher invented by Leslie McBride. It was submitted to the NESSIE project, but was not selected.

The following outline is provided as an overview of and topical guide to cryptography:

In cryptography, a round or round function is a basic transformation that is repeated (iterated) multiple times inside the algorithm. Splitting a large algorithmic function into rounds simplifies both implementation and cryptanalysis.

<span class="mw-page-title-main">Bricklayer function</span> Decomposable function in cryptography

In cryptography, the bricklayer function is a part of a round function that can be decomposed into identical independent Boolean operations on the partitioned pieces of its input data, so called bundles. The term was introduced by Daemen and Rijmen in 2001.

In cryptography, the branch number is a numerical value that characterizes the amount of diffusion introduced by a vectorial Boolean function F that maps an input vector a to output vector . For the (usual) case of a linear F the value of the differential branch number is produced by:

  1. applying nonzero values of a to the input of F;
  2. calculating for each input value a the Hamming weight , and adding weights and together;
  3. selecting the smallest combined weight across for all nonzero input values: .

References

  1. ↑ Daemen & Rijmen 2013, p. 22.
  2. 1 2 Carlet, Claude (2010), Hammer, Peter L.; Crama, Yves (eds.), "Vectorial Boolean Functions for Cryptography", Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Encyclopedia of Mathematics and its Applications, Cambridge: Cambridge University Press, pp. 398–470, ISBN   978-0-521-84752-0 , retrieved 2021-04-30
  3. ↑ Chandrasekaran, J.; et al. (2011). "A Chaos Based Approach for Improving Non Linearity in the S-box Design of Symmetric Key Cryptosystems". In Meghanathan, N.; et al. (eds.). Advances in Networks and Communications: First International Conference on Computer Science and Information Technology, CCSIT 2011, Bangalore, India, January 2-4, 2011. Proceedings, Part 2. Springer. p. 516. ISBN   978-3-642-17877-1.
  4. ↑ Buchmann, Johannes A. (2001). "5. DES". Introduction to cryptography (Corr. 2. print. ed.). New York, NY [u.a.]: Springer. pp.  119–120. ISBN   978-0-387-95034-1.
  5. ↑ Coppersmith, D. (May 1994). "The Data Encryption Standard (DES) and its strength against attacks". IBM Journal of Research and Development. 38 (3): 243–250. doi:10.1147/rd.383.0243. ISSN   0018-8646.
  6. ↑ Gargiulo's "S-box Modifications and Their Effect in DES-like Encryption Systems" Archived 2012-05-20 at the Wayback Machine p. 9.
  7. ↑ RFC 4086. Section 5.3 "Using S-boxes for Mixing"
  8. ↑ Heys, Howard M. "A Tutorial on Linear and Differential Cryptanalysis" (PDF).
  9. ↑ "S-Boxes and Their Algebraic Representations — Sage 9.2 Reference Manual: Cryptography". doc.sagemath.org. Retrieved 2021-04-30.
  10. ↑ Saarinen, Markku-Juhani O. (2012). "Cryptographic Analysis of All 4 × 4-Bit S-Boxes". In Miri, Ali; Vaudenay, Serge (eds.). Selected Areas in Cryptography. Lecture Notes in Computer Science. Vol. 7118. Berlin, Heidelberg: Springer. pp. 118–133. doi: 10.1007/978-3-642-28496-0_7 . ISBN   978-3-642-28496-0.

Further reading

Sources

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.