Rijndael algorithm was selected as the advanced encryption standard in 2001 after five year long security evaluation; it is well proven in terms of its strength and efficiency. The substitution box is the back bone of the cipher and its strength lies in the simplicity of its algebraic construction. The present paper is a study of the construction of Rijndael Substitution box and the effect of varying the design components on its cryptographic properties.

Keywords:    Advanced encryption standard,   Rijndael,   Rijndael algorithm,   substitution box,   cryptographic properties  

 

The advanced encryption standard (AES)* Developed by Joan Daemen and Vincent Rijmen, Rijndael^{1, 2} was selected by national institute of standards and technology (NIST) as in 2001. It is a symmetric block cipher-based on the Shannon substitution-permutation network. AES has long been an area of interest for the researchers due to its:

• Well proven security: A a 5-year evaluation procedure by NIST and it is designed to be resistant to linear, differential and mount attacks.

• Efficiency: The speed of encryption and decryption of AES is the fastest compared to any other cipher of similar strength.

• Design simplicity: The cipher has a simple and elegant structure that can easily be split into its components.

Most of the earlier works relating to AES are linked to its performance evaluation and straight forward implementation ^3-7including the various pipelined architecture. Some simplification ^8,9in the AES algorithm had been attempted. However, this simplifications lead to vulnerabilities ¹⁰ in the algorithm. A great amount of work has also been done in fast pipelined implementation ^11-15 of the algorithm. Rijmen proposal of AES S-box implementation based on the composite fields ¹⁶ was a significant step to compact AES. Some work in optimum construction ¹⁷of these composite fields has been done. Some study on the replacement ¹⁸ of the design parameters of the Rijndael algorithm has been done. It was suggested that this leads to creation of new ciphers equivalent in strength to the original. However, certain properties¹⁹ of substitution box (S-box) has been identified, which are profoundly affected by the changes in design components. Recent works relating to AES S-box include the optimised implementation of the S-box using residues of prime numbers ²⁰, a lightweight mix columns implementation for AES ²¹ and a proposal of a new algorithm to construct secure keys for AES²² is published.

This paper focuses on the study of the algebraic construction of the S-box of the AES algorithm, which is the main strength of the cipher. The effect of the change in the design components of the S-box on its cryptographic properties has been analysed. It provides an insight to the AES S-box construction to generate a conceptual framework for all future customization of the algorithm targeted at the S-box design level.

Full description of the AES algorithm can be obtained in FIPS² 197. The input and the output for AES are each bit sequences containing 128-bits. However, AES allows cipher keys of all 128-bits, 192-bits, or 256-bits lengths. The input 128 bits are arranged in a 4x4 matrix, termed the ‘state’ and all byte operations are performed in the Galois field GF(2⁸). The cipher is specified in terms of repetitions of processing steps that are applied to make up rounds of keyed transformations between the input plain-text and the final output cipher-text. A set of reverse rounds are applied to transform cipher-text back into the original plain-text using the same encryption key. The encryption of data is done in number of rounds:

a. Initial round: AddRoundKey

b. Rounds: SubBytes, ShiftRows, MixColumns and AddRoundKey

c. Final round: SubBytes, ShiftRows and AddRoundKey

Addroundkey : Addroundkey is a XOR of the key with the array.

ShiftRows : ShiftRows cyclicly shifts the elements of the i^th row of the state C_i elements to the right, where, Ci are fixed constants C_i = 0, 1, 2 and 3.

MixColumns : The columns of the state are considered as polynomials over GF(2⁸) and multiplied modulo x⁴+1 by 03.x³+x²+02 to give a new column array.

SubBytes : SubBytes is a nonlinear byte substitution, operating on each of the state bytes independently.

In all these operations, the SubBytes deserve a special mention as this step involves the S-box. The S-box is the back bone of the cipher; it provides nonlinearity in the encryption process and plays an important role in key scheduling. Construction of AES S-box has been explained in the next section.

For the study of algebraic construction of the S-box a theorem is stated here without proof.

Theorem 1 : Let p be a non-zero element of a Principle Ideal Domain R then, R/(p) will be a field if and only if, p is irreducible²³.

According to this theorem, for a prime p Galios field $\begin{array}{c}\mathit{GF}\mathrm{(}{\mathit{p}}^{\mathit{n}}\mathrm{)}\hfill \end{array}$ is constructed by using a generating polynomial m(x) of degree n taking. In the AES algorithm, the irreducible polynomial ${\mathit{x}}^{\mathrm{8}}+{\mathit{x}}^{\mathrm{4}}+{\mathit{x}}^{\mathrm{3}}+\mathit{x}+\mathrm{1}$ is used to generate the underlying field $\begin{array}{c}\hfill \\ \mathit{GF}\mathrm{(}{\mathrm{2}}^{\mathrm{8}}\mathrm{)}\hfill \end{array}$ . All bytes in Rijndael are interpreted as elements of this field represented by a polynomial $\begin{array}{c}\hfill \\ {\mathit{a}}_{\mathrm{1}}+{\mathit{a}}_{\mathrm{2}}\mathit{x}+{\mathit{a}}_{\mathrm{3}}{\mathit{x}}^{\mathrm{2}}+{\mathit{a}}_{\mathrm{4}}{\mathit{x}}^{\mathrm{3}}+{\mathit{a}}_{\mathrm{5}}{\mathit{x}}^{\mathrm{4}}+{\mathit{a}}_{\mathrm{6}}{\mathit{x}}^{\mathrm{5}}+{\mathit{a}}_{\mathrm{7}}{\mathit{x}}^{\mathrm{6}}+{\mathit{a}}_{\mathrm{8}}{\mathit{x}}^{\mathrm{7}}\hfill \end{array}$ where, each bit $\begin{array}{c}\hfill \\ {\mathit{a}}_{\mathit{i}}\in \mathit{GF}\mathrm{(}\mathrm{2}\mathrm{)}\hfill \end{array}$ and $\mathit{b}\in \mathit{GF}\mathrm{(}{\mathrm{2}}^{\mathrm{8}}\mathrm{)}$ In this field, addition $\begin{array}{c}\oplus \hfill \end{array}$ and multiplication are defined by the XOR operation and polynomial multiplication modulo the generating polynomial respectively.

An S-box is a transformation $\begin{array}{c}\mathrm{\sigma }\mathrm{:}\mathit{GF}\mathrm{(}{\mathit{p}}^{\mathit{n}}\mathrm{)}\to \mathit{GF}\mathrm{(}{\mathit{p}}^{\mathit{n}}\mathrm{),}\hfill \end{array}$ In AES the S-box $\mathrm{\sigma }\mathrm{:}\mathit{GF}\mathrm{(}{\mathrm{2}}^{\mathrm{8}}\mathrm{)}\to$ $\mathit{GF}\mathrm{(}{\mathrm{2}}^{\mathrm{8}}\mathrm{)}$ is constructed by substituting each element with its inverse and applying a suitable affine transformation $\mathrm{\sigma }\mathrm{:}\mathit{X}\to {\mathit{AX}}^{\mathrm{-}\mathrm{1}}+\mathit{b}$ where, $\begin{array}{c}\mathit{A}\in {\mathit{GL}}_{\mathrm{8}}\left(\mathrm{2}\right)\mathrm{,}\hfill \end{array}$ the general linear group of degree 8 over GF(2) and $\mathit{b}\in \mathit{GF}\mathrm{(}{\mathrm{2}}^{\mathrm{8}}\mathrm{)}$ . Both of these A and b are fixed in AES:

$\mathit{A}=\left[\begin{array}{cccccccc}\mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}\\ \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{1}\\ \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{1}\\ \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}\\ \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{1}\end{array}\right]\mathrm{}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{}\mathit{b}=\left[\begin{array}{c}\mathrm{1}\\ \mathrm{1}\\ \mathrm{0}\\ \mathrm{0}\\ \mathrm{0}\\ \mathrm{1}\\ \mathrm{1}\\ \mathrm{0}\end{array}\right]$

The motivation for this S-box design is to be resistant to differential, linear cryptanalysis and interpolation attacks. The core design is a simple transformation $\mathit{x}\to {\mathit{x}}^{\mathrm{-}\mathrm{1}}$ in GF(2⁸), this mapping has a simple algebraic expression. However, the simplicity itself makes it vulnerable to attacks like the interpolation attack. Therefore, it is combined with a suitable affine transformation: $\begin{array}{c}\mathit{x}\to {\mathit{Ax}}^{\mathrm{-}\mathrm{1}}+\mathit{b}\mathrm{.}\hfill \end{array}$ The affine mapping is so chosen that, it has a very simple description, but a complicated algebraic expression. If combined with the ‘inverse’ mapping, it can be seen as modular polynomial multiplication followed by addition¹ $\begin{array}{c}\mathit{b}\left(\mathit{x}\right)=\left({\mathit{x}}^{\mathrm{7}}+{\mathit{x}}^{\mathrm{6}}+{\mathit{x}}^{\mathrm{2}}+\mathit{x}\right)+\mathit{a}\left(\mathit{x}\right)\left({\mathit{x}}^{\mathrm{7}}+{\mathit{x}}^{\mathrm{6}}+{\mathit{x}}^{\mathrm{5}}+{\mathit{x}}^{\mathrm{4}}+\mathrm{1}\right)\mathrm{mod}\mathrm{(}{\mathit{x}}^{\mathrm{8}}+\mathrm{1}\mathrm{).}\hfill \end{array}$ The purpose of the constant translation vector b is to ensure that $\begin{array}{c}\exists \hfill \end{array}$ no fixed and conjugate fixed points (i.e. $\begin{array}{c}\exists \hfill \end{array}$ no $\mathit{x}\in \mathit{GF}\mathrm{(}{\mathrm{2}}^{\mathrm{8}}\mathrm{)}$ such that s(x) = x or) in the S-box.

To study the characteristics of a good S-box $\begin{array}{c}\mathrm{\sigma }\mathrm{:}\mathit{GF}\mathrm{(}{\mathit{p}}^{\mathit{n}}\mathrm{)}\to \mathit{GF}\mathrm{(}{\mathit{p}}^{\mathit{n}}\mathrm{)}\hfill \end{array}$ , it is realised as vectorial Boolean function $\begin{array}{c}\mathrm{\sigma }\mathrm{(}\mathit{x}\mathrm{)}=\mathrm{(}{\mathrm{\sigma }}_{\mathrm{1}}\mathrm{(}\mathit{x}\mathrm{),}{\mathrm{\sigma }}_{\mathrm{2}}\mathrm{(}\mathit{x}\mathrm{),...}{\mathrm{\sigma }}_{\mathit{n}}\mathrm{(}\mathit{x}\mathrm{))}\hfill \end{array}$ where, each is a Boolean function of the Boolean variables $\begin{array}{c}{\mathit{x}}_{\mathrm{1}}\mathrm{,}{\mathit{x}}_{\mathrm{2}}\mathrm{.....,}{\mathit{x}}_{\mathit{n}}\hfill \end{array}$ .

Characteristics of the good S-box are:

• It be balanced.

• It satisfy propagation criterion

• It satisfy correlation immunity criteria

• It have input/output bit-to-bit entropy (H) = 1.

• Its nonlinearity (N) has to be = 120

Each of these criteria’s are explained in the following subsection. However, most of these are satisfied only for an ideal case and not in practical level. So, biases from each of these criterions are derived.

4.1. Balancedness Property

This property states that each of the Boolean functions of the S-box should be balanced i.e. the number of ones and zeros in the truth table of the Boolean function must be equal.

4.2. Propagation Criteria

A Boolean function is said to satisfy propagation criteria of degree k and order m, if any function obtained by keeping m input bits fixed f(x) changes with probability half, whenever i (1≤i≤k) bits of x are complemented.

Mathematically, by fixing m number of bits $\begin{array}{c}{}^{\mathit{n}}\mathit{C}_{\mathit{m}}{\mathrm{2}}^{\mathit{m}}\hfill \end{array}$ set of functions g are obtained from f, let it be denoted by F. Let $\begin{array}{c}\mathrm{\alpha }\in \mathit{GF}\mathrm{(}{\mathrm{2}}^{\mathit{n}}\mathrm{):}\mathit{W}\mathrm{(}\mathrm{\alpha }\mathrm{)}\in \mathrm{[}\mathrm{1}\mathrm{,}\mathit{k}\mathrm{]}\hfill \end{array}$ then a function is said to satisfy the propagation criteria of degree k and order m, if for each g $\begin{array}{c}\mathrm{}\mathit{}\in \mathit{F}\mathrm{,}\mathrm{}\mathit{g}\mathrm{(}\mathit{x}\mathrm{)}\oplus \mathit{g}\mathrm{(}\mathit{x}\oplus \mathrm{\alpha }\mathrm{)}\mathrm{}\hfill \end{array}$ is balanced.

The propagation criterion is the measure of randomness of the differences in output pairs to the input pairs. This is a very important criterion as the bias of the distribution of the differences of the output pairs and the input pairs is utilised in the differential cryptanalysis of the conventional ciphers.

Definition: Propagation criterion bias of a Boolean function of degree k and order m is defined by¹⁹:

$\begin{array}{c}{\mathit{PCB}}_{{\mathrm{\sigma }}_{\mathit{i}}}\mathrm{(}\mathit{k}\mathrm{,}\mathit{m}\mathrm{)}=\underset{\mathrm{\alpha }\mathrm{\in }\mathit{A}\mathrm{}\mathit{g}\mathrm{\in }\mathit{F}}{\max }\mathrm{|}\underset{\mathit{x}\mathrm{\in }\mathit{F}_{\mathrm{2}}{}^{\mathit{n}}}{\sum }\mathrm{(}\mathit{g}\mathrm{(}\mathit{x}\mathrm{)}\oplus \mathit{g}\mathrm{(}\mathit{x}\oplus \mathrm{\alpha }\mathrm{)}\mathrm{)}-{\mathrm{2}}^{\mathit{n}\mathrm{-}\mathit{m}\mathrm{-}\mathit{k}}\mathrm{|}\hfill \end{array}$

$\begin{array}{c}\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{,}\mathrm{}\mathit{A}=\mathrm{\{}\mathrm{\alpha }\in \mathit{GF}\mathrm{(}{\mathrm{2}}^{\mathit{n}}\mathrm{):}\mathit{w}\mathrm{(}\mathrm{\alpha }\mathrm{)}\in \mathrm{[}\mathrm{1}\mathrm{,}\mathit{k}\mathrm{]\}.}\hfill \end{array}$

For the S-box: $\begin{array}{c}{\mathit{PCB}}_{\mathrm{\sigma }}\mathrm{(}\mathit{k}\mathrm{,}\mathit{m}\mathrm{)}=\underset{{\mathrm{\sigma }}_{\mathit{i}}}{\max }{\mathit{PCB}}_{{\mathrm{\sigma }}_{\mathit{i}}}\mathrm{(}\mathit{k}\mathrm{,}\mathit{m}\mathrm{)}\hfill \end{array}$

The propagation criteria of degree one and order zero is very well known criterion, termed as the strict avalanche criterion (SAC). The criterion is satisfied, if whenever a single input bit is complemented, each of the output bits changes with a probability .

4.3. Correlation Immunity Criteria

A Boolean function is to satisfy a correlation immune of order m, if it is statistically independent of combination of any m input bits. Mathematically, if m input bits are fixed then the functions g obtained from Boolean function f must satisfy:
$\begin{array}{c}\mathit{W}\left(\mathit{g}\right)=\frac{\mathit{W}\left(\mathit{f}\right)}{{\mathrm{2}}^{\mathit{m}}}\hfill \end{array}$
where, W(f) denotes the Hamming weight of a Boolean function given by the number of x for which the function attains a non-zero value.

Definition: The correlation immunity bias of order m for a Boolean function is defined by¹⁹: $\begin{array}{c}{\mathit{CIB}}_{\mathit{f}}\mathrm{(}\mathit{m}\mathrm{)}=\underset{\mathit{f}\mathrm{\in }\mathit{A}}{\max }\mathrm{}\left|{\mathrm{2}}^{\mathit{m}}\times \mathit{W}\mathrm{(}\mathit{g}\mathrm{)}-\mathit{W}\mathrm{(}\mathit{f}\mathrm{)}\right|\hfill \end{array}$

The correlation immunity bias of S-box is given by $\begin{array}{c}{\mathit{CIB}}_{\mathrm{\sigma }}\mathrm{(}\mathit{m}\mathrm{)}=\underset{\mathit{i}\mathrm{\in }\mathrm{[}\mathrm{1}\mathrm{,}\mathit{s}\mathrm{]}}{\max }\mathrm{}{\mathit{CIB}}_{{\mathrm{\sigma }}_{\mathit{i}}}\mathrm{(}\mathit{m}\mathrm{)}\hfill \end{array}$ .

4.4. Input/output Bit-to-Bit Entropy

This parameter represents the amount of information about the value of input bit, if the value of the output bit is known. The entropy of a single output function is given by²⁴:
$\begin{array}{c}\mathit{H}\mathrm{(}{\mathit{P}}_{\mathit{i}}\mathrm{)}={\mathit{P}}_{\mathit{i}}{\log }_{\mathrm{2}}\mathrm{(}\frac{\mathrm{1}}{{\mathit{P}}_{\mathit{i}}}\mathrm{)}+\mathrm{(}\mathrm{1}\mathrm{}-{\mathit{P}}_{\mathit{i}}{\mathrm{)}\mathrm{l}\mathrm{o}\mathrm{g}}_{\mathrm{2}}\mathrm{(}\mathrm{1}-{\mathit{P}}_{\mathit{i}}\mathrm{)}\hfill \\ \hfill \end{array}$

where, P_i, is the fraction of 1’s in the output column of the truth table.

Definition 3: The (i,j)^th Input/output bit-to-bit entropy $\begin{array}{c}\mathit{H}\mathrm{(}{\mathit{x}}_{\mathit{i}}/{\mathrm{\sigma }}_{\mathit{i}}\mathrm{(}\mathit{x}\mathrm{))}\hfill \end{array}$ is computed and the parameter is defined¹⁹ by $\begin{array}{c}\mathit{H}=\underset{\mathit{i}\mathrm{,}\mathit{j}\mathrm{\in }\mathrm{[}\mathrm{1}\mathrm{,}\mathit{n}\mathrm{]}}{\min }\mathit{H}\mathrm{(}{\mathit{x}}_{\mathit{i}}/{\mathrm{\sigma }}_{\mathit{j}}\mathrm{(}\mathit{x}\mathrm{))}\hfill \end{array}$ .

4.5. Nonlinearity

An affine Boolean function does not provide an effective confusion. To overcome this, functions which are as far as possible from being an affine function are needed. The effectiveness of these functions is measured by a parameter called Nonlinearity.

Definition : Nonlinearity of a Boolean function is measured by the Hamming distance to the set of affine functions²⁵
$\begin{array}{c}\mathit{N}\mathrm{(}\mathit{f}\mathrm{)}={\mathrm{2}}^{\mathit{n}\mathrm{-}\mathrm{1}}-\frac{\mathrm{1}}{\mathrm{2}}\times \underset{\mathit{w}\mathrm{\in }\mathit{F}_{\mathrm{2}}{}^{\mathit{n}}}{\max }\mathit{F}\mathrm{(}\mathit{w}\mathrm{),}\hfill \end{array}$

where, F is the Walsh transformation of f,
$\mathrm{F}\mathrm{o}\mathrm{r}\mathrm{}\mathrm{}\mathrm{S}-\mathrm{b}\mathrm{o}\mathrm{x}\mathrm{}\mathit{N}=\underset{\mathit{i}\mathrm{\in }\mathrm{[}\mathrm{1}\mathrm{,}\mathit{n}\mathrm{]}}{\min }\mathrm{(}\mathit{N}\mathrm{(}{\mathit{f}}_{\mathit{i}}\mathrm{))}$

For good cryptographic properties of the S-box, these parameters should have the values¹⁹: H=1, PCB(1,0)=0, PCB(1,1)=0, CIB(1)=0 and Nonlinearity=120. However, values of these parameters for the AES S-box are: H=0.9887, PCB(1,0)=16, PCB(1,1)=20, CIB(1)=16 and Nonlinearity N=112. The values of these bias parameters are used to analyze the effect of changes in the design components of the AES S-box on its cryptographic properties. Different possible variations on the S-box components and their affects have been discussed in the next section.

The S-box is constructed by the transformation: $\mathit{x}={\mathit{Ax}}^{\mathrm{-}\mathrm{1}}+\mathit{b}\mathrm{,}\mathrm{}\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{,}\mathrm{}\mathrm{}\mathit{x}\in \mathit{GF}\mathrm{(}{\mathrm{2}}^{\mathrm{8}}\mathrm{),}\mathrm{}\mathit{A}\in {\mathrm{}\mathrm{G}\mathrm{L}}_8\mathrm{(}2\mathrm{)}\mathrm{}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{}\mathrm{}\mathit{b}\in \mathit{GF}\mathrm{(}{\mathrm{2}}^{\mathrm{8}}\mathrm{).}$

All the variations in its construction without altering the simple algebraic expression are looked into and their effects in the bias parameter values are analysed. One of the major changes that can be brought about without altering the algebraic expression is by changing the underlying field to isomorphic fields. Another option is to change the affine matrix A and third is changing the vector b.

5.1. Change in the Underlying Field to Isomorphic Fields

Isomorphic fields to the underlying field can be generated by using different irreducible polynomials of the same degree. Number of irreducible polynomials of degree n over GF(p) is given by: $\frac{\mathrm{1}}{\mathit{n}}\underset{\mathit{d}/\mathit{n}}{\sum }\mathrm{\mu }\mathrm{(}\mathit{d}\mathrm{)}{\mathit{p}}^{\mathit{n}/\mathit{d}}\mathrm{,}\mathrm{}\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{}\mathrm{\mu }\mathrm{}\mathit{is}\mathrm{}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{}\mathrm{M}\mathrm{o}\mathrm{b}\mathrm{i}\mathrm{u}\mathrm{s}\mathrm{}\mathrm{f}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{.}$ $\mathrm{\mu }\mathrm{(}\mathit{n}\mathrm{)}\equiv \left\{\begin{array}{c}\mathrm{0}\\ \\ \end{array}\begin{array}{c}\\ \\ \end{array}\begin{array}{c}\mathrm{0}\\ \mathrm{1}\\ \mathrm{(}-\mathrm{1}{\mathrm{)}}^{\mathit{k}}\end{array}\begin{array}{c}\begin{array}{c}\mathrm{}\mathrm{i}\mathrm{f}\mathrm{}\mathit{n}\mathrm{}\mathrm{h}\mathrm{a}\mathrm{s}\mathrm{}1\mathrm{}\mathrm{o}\mathrm{r}\mathrm{}\mathrm{m}\mathrm{o}\mathrm{r}\mathrm{e}\mathrm{}\mathrm{r}\mathrm{e}\mathrm{p}\mathrm{e}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{d}\mathrm{}\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{}\hfill \\ \mathrm{factors}\hfill \end{array}\\ \mathrm{}\mathrm{i}\mathrm{f}\mathrm{}\mathit{n}=1\\ \mathrm{i}\mathrm{f}\mathrm{}\mathit{n}\mathrm{}\mathrm{i}\mathrm{s}\mathrm{}\mathrm{a}\mathrm{}\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{d}\mathrm{u}\mathrm{c}\mathrm{t}\mathrm{}\mathrm{o}\mathrm{f}\mathrm{}\mathit{k}\mathrm{}\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{c}\mathrm{t}\mathrm{}\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{s}\end{array}\right.$

Thus, a total of 30 irreducible polynomials of degree 8 over GF(2) including the one originally used. The irreducible polynomials are constructed by generating the polynomials and testing their irreducibility using the following theorem:

Theorem 2: Rabin’s Test for irreducibility²⁶

A polynomial of degree d is irreducible if and only if

The irreducible polynomials and the values of the bias parameters of the respective S-boxes constructed on isomorphic field generated by them are shown in Table 1.

It can be observed from Table 1 that values of the bias parameters can be enhanced on changing to isomorphic fields as in the case of the irreducible polynomial

5.2. Change in the Affine Matrix

Another variation in the S-box design component can be brought about by changing the affine matrix A. The affine matrix , the general linear group of degree 8 over GF(2) and the order of this group is: Hence, the number of matrix A available to be used for varying the S-box is numerous. So, to analyze the effect of such change on the bias parameter values instead of performing an exhaustive search over this group, a random search has been done. For this, a square binary matrix of size 8 is randomly generated. The matrix is discarded, if found to be singular and another matrix is generated again. This non-singular randomly generated matrix is used in the construction of S-box and the bias parameters are computed. This process is implemented in MatLab and is repeated 500 times. Few randomly generated affine matrices obtained on 500 such random searches are:

Some of the observed bias parameter values obtained due to the change in the affine matrix in the random search are shown in Table 2.

5.3. Change in the Translation Vector

The translation vector and O(GF(28)) = 256 therefore, total 256 different vector b (including the one used in the AES) that can be used in the S-box construction. However, it is observed that change in the translation vectors has no impact on the values of the bias parameters. Only the number of fixed and conjugate fixed points of the S-box varies with it. It was observed that the nonlinearity (N=112) of the AES S-box was not affected by any of the above mentioned changes.

Rijndael algorithm accepted as the AES is a well proven and an efficient cipher. The S-box forms a backbone of this cipher and is designed with a very simple algebraic expression. This paper studies the construction of its S-box and explores the possible design variations without altering its simple algebraic expression. The effect of these changes on the cryptographic properties of the S-box has also been analyzed. The main aim of this study is to provide an insight to the AES S-box construction to generate a conceptual framework for all possible customization on the cipher targeted at the S-box design level. It is observed that by changing the underlying field into the isomorphic fields improves the properties to some level. A similar effect is observed for the change in the affine matrix. However, change in the translation vector shows no effect in the cryptographic properties of the S-box.

The authors would like to thank Shri H.V. Srinivasa Rao Director, Institute for Systems Studies and Analyses, DRDO for his encouragement and support in this work. The authors would also like to thank Shri P.K. Bhatnagar and Shri Yogesh Chandra for their kind suggestions and guidance.

1. Daemen, J. & Rijmen, V. AES Proposal: Rijndael (Version 2), 1999. http://csrc.nist.gov/publications/ (Accessed on 9 June 2009).

2. National Institute of Standards and Technology, Advanced encryption standard (AES). (FIPS 197), 2001. http://csrc.nist.gov/.publications/.(Accessed on 11 June 2009).

3. Dandalis, A. Prasanna, V.K. Rolim, J.D. A comparative study of performance of AES final candidates using FPGAs. Cryptographic Hardware and Embedded Systems Workshop, Worcester, Massachusetts, 2000, 125-40.

4. Elbirt A. J.; Yip, W.; Chetwynd, B. & Paar, C. An FPGA implementation and performance evaluation of the AES block cipher candidate algorithm finalists. IEEE Trans. Very Large Scale Integration Syst., 2000, 9(4), 545-57.

5. Gaj, K. & Chodowiec, P. Hardware performance of the AES finalists-survey and analysis results. 2000, http://ece.gmu.edu/crypto/AES_survey.pdf. (Accessed on 28 June 2009).

6. Ichikawa, T. & Matsui, T. Hardware evaluation of the AES finalists. In 3^rd Advanced Encryption Standard Candidate Conference, New York, 2000, 279-85.

7. Mali, M.; Novak, F. & Anton, B. Hardware implementation of AES algorithm. J. Electrical Engg., 2005, 56(9-10), 265-69.

8. Feldhofer, M.; Wolkerstorfer, J. & Rijmen, V. AES implementation on a grain of sand. IEE Proc. Infor. Security, 2005, 152(1), 13-20.

9. Canright, D. A very compact Rijndael S-box. Naval Postgraduate School, Monterey, California, Report no. NPS-MA-04-001, May 2005.

10. Mansoori, S. D. & Bizaki, H. K. On the vulnerability of simplified AES algorithm against linear cryptanalysis. Inter. J. Comp. Sci. Network Security, 2007, 7(7). (page no.)

11. Fischer, V. & Drutarovsky, M. Two methods of Rijndael implementation in reconfigurable hardware, cryptographic hardware and embedded systems. In Proceedings of the 3^rd International Workshop on Cryptographic Hardware and Embedded Systems, Paris, 2001, 77-92.

12. McLoone, M. & McCanny, J.V. High performance single-chip FPGA Rijndael algorithm implementations. In Proceedings of the 3^rd International Workshop on Cryptographic Hardware and Embedded Systems, (Place), 2001, 65-76.

13. McLoone, M. & McCanny, J.V. Single-chip FPGA implementation of the advanced encryption standard algorithm, field-programmable logic and applications. In Proceedings of the 11^th International Conference on Field-Programmable Logic and Applications, UK, 2001, 152-61.

14. McLoone, W. & McCanny, J.V. Rijndael FPGA implementation utilizing look-up tables. In IEEE Workshop on Signal Processing Systems, 2001. (Place, page no.)

15. Chodowiec, P.; Gaj, K. & Mason, G. Very compact FPGA implementation of the AES algorithm. In the 5^th International Workshop on Cryptographic Hardware and Embedded Systems. USA, 2003, 319-33.

16. Rijmen, V. Efficient implementation of the Rijndael S-box, Belgium, http://www.comms. (Accessed on 28 June 2009)

17. Zhang, X. & Parhi, K.K. On the optimum constructions of composite field for the AES algorithm. IEEE Trans. Circuits and Systems-II, 2006, 53(10).(page no.)

18. Barkan, E. & Biham, E. In how many ways can you write Rijndael? In Proceedings of the 8^th International Conference on the Theory and Application of Cryptology and Information Security, 2002. (Place, page no.)

19. Otokar, G.; Spyros, M.; Jan, T. & Wandi, W. Is Rijndael really independent of the field polynomial? Tatra Mt. Publ 33, 2006. (page no.)

20. Abuelyman, E.S. & Alsehibani, A.S. An optimized implementation of the S-Box using residues of prime numbers. Inter. J. Comp. Sci. Network Security, 2008, 8(4), 304-09.

21. Ahmed, E. G.; Shaaban, E. & Hashem, M., Lightweight mix columns implementation for AES. In Proceedings of the 9^th International Conference on Applied Informatics and Communications 2009, (Pace) 253-58.

22. Mahmood, H. A new algorithm to construct secure keys for AES. Int. J. Contemporary Mathematical Sci., 2010, 5 (26), 1263-270.

23. Artin, M. Algebra. Massachusetts Institute of Technology, Mathematics Department, Cambridge, USA 1991, Prentice Hall Inc. (page no.)

24. Cheng, K. & Agrawal, V.D. An entropy measure for the complexity of multi-output boolean functions. In Proceedings of the 27^th ACM/IEEE Design Automation conference, 1991, 302-05.

25. Rothaus, O.S. On bent functions. J. Combinatorial Theory (A), 1976, 20, 300-05.

26. Jörg, A. Testing polynomial irreducibility without GCDs. Institut National De Recherche En Informatique Et En Automatique, May 2008.