- S-box Description and Properties

Substitution process holds an important role in the security of data. Substitution is a nonlinear transformation which performs confusion of bits. It provides the cryptosystem with the confusion property described by Shannon. He suggested that strong ciphers could be built by combining substitutions with transposition repeatedly. In modern encryption algorithm, a nonlinear transformation is essential and is proved to be a strong cryptographic primitive against linear and differential cryptanalysis. An example of a nonlinear transformation algorithm is Advanced Encryption Standard (AES). In this Rijndael algorithm, s-box is the most important part because of the encryption algorithm which means that it requires the key to be the same length as the message to be encoded.

The static s-box will use the same s-box in each round while for key-dependent or dynamic s-box it will change in round of s-box depends on the key and number of rounds. The dependent key or dynamic algorithm should be generated to increase the cryptographic strength of the AES cipher system. S-box with key dependent properties are slower, but more secure than independent ones. The s-box mapping represent with input *X *and output *Y*.

The properties s-box have been widely used as base of new encryption strategies such as nonlinearity, differential uniformity, and strict avalanche criterion. A(*x,y*) s-box is a map, *S :*{0,1}x → {0,1}y. It comprises of n-variable component Boolean functions : *(f1(x1, …., xn), f2(x1, …., xn), ….., fn(x1, …., xn)) *each of which need to satisfy s-box properties. The several properties in s-box are robustness, balancing, strict avalanche criterion, nonlinearity, differential uniformity, linear approximation, algebraic complexity, fixed and opposite fixed points, and bit independence criterion.

Most of researchers always construct their s-box to resist against linear cryptanalysis and differential cryptanalysis attacks where every new cipher should be tested in the case of the weak keys. Several s-box are already tested with linear and differential cryptanalysis, it attacks the s-box properties based on the linear approximation and avalanche effect. The approach in linear cryptanalysis is to determine expression of the form above which has a high or low probability of occurrence.

- Strength S-box Criterion

The strong and secure S-box is needed to protect the number of rounds, a key, confusion and round function in s-box. As a result, the key should be difficult to discover in order to show that the more secure of the s-boxes mechanism. To prevent linear and differential attacks, the s-box in block cipher should hide the characteristics of the language. A good s-box should satisfy a lot of criteria, for example nonlinear properties to determine the performance of the whole block cipher. Actually, there is no specific guideline exist to analyse the s-box properties based on previous studies. For example, studied by Chandrasekharappa, one of the most important characteristics of a s-box is an avalanche criterion that is a bit change in the input byte of an s-box must result in a change in the output byte at least by 50% bits. While in the other hand, it is said that two of most important characteristics which decides the strength of an s-box are robustness and SAC, both of which are derived from the Difference Distribution Table (DDT).

The criterion that need to be satisfied from an s-box so it can be considered as cryptographically strong are balancing, high nonlinearity, low differential uniformity, high algebraic degree, low linear approximation, high algebraic complexity, and low/no fixed and opposite fixed points. Those entire criterions can be simplified as five important criterions as follows :

- Completeness and Avalanche Criteria

Every input bit depends on every output bit if a cryptographic transformation is complete. Whereas it is not complete, it can be possible to find a pair of input and output bits such that flipping the input does not cause a change in the output bit for all input vectors. Avalanche is a desirable cryptography property which is necessary to ensure that small difference between two plaintexts results in a seemingly random difference between the two corresponding ciphertexts. If avalanche criterion used to be satisfied, when some input value is concerned, changing one bit in the value, half of the output bits is expected to change.

- Strict Avalanche Criterion

This criterion is combined from completeness and
avalanche by Webster and Tavares. A function satisfies SAC when flipping input
bit *i *changes output bit *j *with the probability of exactly ½. It
is easy to say that an s-box satisfies SAC, it must satisfy both Completeness
and Avalanche Criteria, but the satisfaction of Avalanche Criteria does not
necessarily imply that SAC is satisfied.

- Bit Independence Criterion

The
idea of this criterion was introduced by Webster and Tavares, which for a given
set of avalanche vectors generated by complementing a single plaintext bit, all
avalanche should be pairwise independent. The bit independence parameter
corresponding to the effect of the *i ^{th}
*input bit change on the

*j*

^{th}and

*k*

^{th}bits of

*D*is the absolute value of this correlation coefficient:

^{ei}*BIC(f)* is defined in the range [0,1]. It is ideally equal to zero, and in the
worst case it is equal to one.

- XOR Table Distribution

The information about security of the block cipher
against differential cryptanalysis is given in the XOR table. The work of
differential attack is that it exploits particular high valued entries in the
XOR tables of s-boxes employed by a block cipher. The XOR table a size 2^{n}x2^{m}
matrix. The rows of the matrix represent the change in the output of the s-box.
An entry in the XOR table of an s-box indexed by (δ,b) indicates the number of
input vectors P which when changed by δ, result in the output difference of b =
*f*(P) ⊕ *f*(P ⊕ δ). Note that an entry in the XOR table can only take
an even value and the sum of all values in a row always 2^{n}. The
entries of XOR table are very useful to be an immune to differential
cryptanalysis.

- Nonlinearity

The nonlinearity parameter is defined as the number of cases over all cipher inputs such that the affine function and the nonzero linear combination differ from each other. Nonlinearity is required to be as close as possible to its maximum value for a cipher to be susceptible to linear cryptanalysis. When the nonlinearity values is small around zero, it is show that the cipher is close to affine functions and susceptible to linear cryptanalysis.

- S-box Construction

There are a lot of s-box construction methods have been done to produce a strong s-box. Some examples of the s-box construction methods are using general method, recursive method, and dynamic s-box dependent of master key method, multiple s-box method, pseudorandom s-box generation method, and many others. The main purpose of all the methods is to generate new strong s-box. But the result is until now, there is no s-box stronger that AES s-box.