DOI: 10.3923/itj.2014.2482.2488

**
Abstract: **
In this study, according to the inverse transformation principle and the affine transformation principle of Rijndael S-box, a new approach to generating the multivariate quadratic equation system over GF(2) is proposed and the generation process is given explicitly. According to the algebraic expression of the new Rijndael S-box, an equation system over GF(2^{8}) is proposed to describe Rijndael. By comparing with other existing systems, this system has stronger resistance against algebraic attacks. So, the equation system of the new Rijndael S-box is much securer than other existing equation systems.

**INTRODUCTION**

Since, Rijndael (Cheon and Lee, 2004; Demirci *et al*., 2013), the SPN-Structure block cipher algorithm designed by Vincent Rijmen and Joan Danmen was chosen by NIST as the Advanced Encryption Standard (AES) on October, 2, 2000, many schemes have been proposed to attack it (Zhang *et al*., 2011; Kim *et al*., 2007; Chen *et al*., 2011). It has been proved that Rijndael has the security against differential attack and linear attack which are the most well known attacks on block ciphers. Because of the simple algebraic structure of Rijndael S-box, many cryptanalysts focus on the algebraic attack which may be an efficient method. As the only nonlinear component of Rijndael, S-box is a crucial element and it determines the performance of Rijndael.

Many researchers devote time to design and improve the algebraic cryptanalysis scheme (Zhang *et al*., 2007; Ghosh and Das, 2012; Cheon and Lee, 2004). Courtois and Pieprzyk (2002) analyzed the overdefined system and proposed XSL attack on Rijndael. Hussain *et al*. (2013) analyzed the algebraic structure of Rijndael S-box and proposed a new S-box structure. Much study has concentrated on Rijndael S-box, however they did not explicitly give the approach to generating its multivariate quadratic equation system over GF(2). Murphy and Robshaw (2002) showed that the Rijndael preserves algebraic curves and that it can be expressed as a very simple system of multivariate quadratic equations over GF(2^{8}). Cheon and Lee (2004) proposed a new system of multivariate quadratic equations over GF(2^{8}) to describe completely Rijndael in 2004. There have been few research results of the equation system optimization in recent years.

In this study a new approach to generating the multivariate quadratic equations of Rijndael S-box over GF(2) is given explicitly and an equation system over GF(2^{8}) is proposed to describe the new Rijndael S-box. This study is organized into sections: Principle of Rijndael S-box, new approach to generating multivariate quadratic equation system of Rijndael S-box, the optimization of Rijndael S-box equation system and conclusion.

**PRINCIPLE OF RIJNDAEL ****S-BOX**

Looking upon 8-bit bytes as elements in GF(2^{8}), Rijndael S-box is a combination of an inverse function I(x) which is the multiplicative inverse modulo the irreducible polynomial x^{8}+x^{4}+x^{3}+x+1 and an affine transformation function A(x). The I(x) and A(x) are as follows:

• | The inverse function I(x) is defined as: |

• | The affine transformation function A(x) is defined as: |

where, x_{i}(i = 0,…, 7) are the bits of the byte x and x_{7} is the most significant bit. Therefore, Rijndael S-box can be denoted by:

From the construction principle of Rijndael S-box, the algebraic expression of Rijndael S-box can be derived as follow:

S(x) = 05x^{FE}+09x^{FD}+F9x^{FB}+25x^{F7}+F4x^{EF}+01x^{DF}+

B5x^{BF}+8Fx^{7F}+63

**NEW APPROACH TO ****GENERATING MQ EQUATION SYSTEM OF RIJNDAEL S-BOX**

Rijndael S-box is a composition of the “patched” inverse in GF(2^{8}) with 0 mapped on itself with a multivariate affine transformation GF(2^{8})→GF(2^{8}). We call these functions, respectively g and f and we call S = fBg. We note x an input value and y = g(x) the corresponding output value. We will also note z = S(x) = f(y) = f(g(x)).

For inverse transformation y = g(x), obviously xy = 1 when x ≠ 0. i.e.:

(1) |

Expanding the Eq. 1, we have:

(2) |

where, m(t) = t^{8}+t^{4}+t^{3}+t+1.

Comparing the both sides coefficients of t^{k}(0≤k<8) in Eq. 1, we can obtain the 8 multivariate quadratic equations of inverse transformation. Since,

Now, we give the generation principle of Rijndael S-box equation system. Multiplying x by y and the multiplication result modulo m(t), we can obtain the coefficients c_{7},…, c_{0} of t^{k}(0≤k<8). Firstly, we give the computation process of the coefficients c_{7},…, c_{0}.

We note (x_{7},…, x_{0}) = x, (y_{7},…, y_{0}) = y and (z_{7},…, z_{0}) = z. i.e.,:

We have:

The multiplication result modulo m(t) one by one and we give the process in detail as follows:

**Step 1:**x⊗y modulo:

x_{7}y_{7}•t^{14}+x_{7}t_{7}•t^{10}+x_{7}y_{7}•t^{9}+x_{7}y_{7}•t^{7}+x_{7}y_{7}•t^{6} = R1

**Step 2:**R1 modulo:

(x_{7}y_{6}+x_{6}y_{7})•t^{13}+(x_{7}y_{6}+x_{6}y_{7})•t^{9}+(x_{7}y_{6}+x_{6}y_{7})•t^{8}+(x_{7}y_{6}+x_{6}y_{7})•

t^{6}+(x_{7}y_{6}+x_{6}y_{7})•t^{5} = R2

**Step 3:**R2 modulo:

(x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})•t^{12}+(x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})•t^{8}+

(x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})•t^{7}+(x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})•t^{5}+(x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})

t^{4 }= R3

**Step 4:**R3 modulo:

(x_{7}y_{4}+x_{6}y_{5}+x_{5}y_{6}+x_{4}y_{7})•t^{11}+(x_{7}y_{4}+x_{6}y_{5}+x_{5}y_{6}+x_{4}y_{7})•t^{7}+

(x_{7}y_{4}+x_{6}y_{5}+x_{5}y_{6}+x_{4}y_{7})•t^{6}+(x_{7}y_{4}+x_{6}y_{5}+x_{5}y_{6}+x_{4}y_{7})•t^{4}+

(x_{7}y_{4}+x_{6}y_{5}+x_{5}y_{6}+x_{4}y_{7})•t^{3} = R4

**Step 5:**R4 modulo:

(x_{7}y_{3}+x_{6}y_{4}+x_{5}y_{5}+x_{4}y_{6}+x_{3}y_{7}+x_{7}y_{7})•t^{10}+

(x_{7}y_{3}+x_{6}y_{4}+x_{5}y_{5}+x_{4}y_{6}+x_{3}y_{7}+x_{7}y_{7})•t^{6}+

(x_{7}y_{3}+x_{6}y_{4}+x_{5}y_{5}+x_{4}y_{6}+x_{3}y_{7}+x_{7}y_{7})•t^{5}+

(x_{7}y_{3}+x_{6}y_{4}+x_{5}y_{5}+x_{4}y_{6}+x_{3}y_{7}+x_{7}y_{7})•t^{3}+

(x_{7}y_{3}+x_{6}y_{4}+x_{5}y_{5}+x_{4}y_{6}+x_{3}y_{7}+x_{7}y_{7})•t^{2} = R5

**Step 6:**R5 modulo:

(x_{7}y_{2}+x_{6}y_{3}+x_{5}y_{4}+x_{4}y_{5}+x_{3}y_{6}+x_{2}y_{7}+x_{7}y_{7}+

x_{7}y_{6}+x_{6}y_{7})•t^{9}+(x_{7}y_{2}+x_{6}y_{3}+x_{5}y_{4}+x_{4}y_{5}+x_{3}y_{6}+

x_{2}y_{7}+x_{7}y_{7}+x_{7}y_{6}+x_{6}y_{7})•t^{5}+(x_{7}y_{2}+x_{6}y_{3}+

x_{5}y_{4}+x_{4}y_{5}+x_{3}y_{6}+x_{2}y_{7}+x_{7}y_{7}+x_{7}y_{6}+x_{6}y_{7})•t^{4}+(x_{7}y_{2}+

x_{6}y_{3}+x_{5}y_{4}+x_{4}y_{5}+x_{3}y_{6}+x_{2}y_{7}+x_{7}y_{7}+x_{7}y_{6}+x_{6}y_{7})•

t^{2}+(x_{7}y_{2}+x_{6}y_{3}+x_{5}y_{4}+x_{4}y_{5}+x_{3}y_{6}+x_{2}y_{7}+x_{7}y_{7}+x_{7}y_{6}+x_{6}y_{7})•

t = R6

**Step 7:**R6 modulo:

(x_{7}y_{1}+x_{6}y_{2}+x_{5}y_{3}+x_{4}y_{4}+x_{3}y_{5}+x_{2}y_{6}+x_{1}y_{7}+x_{7}y_{6}+

x_{6}y_{7}+x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})•t^{8}+(x_{7}y_{1}+x_{6}y_{2}+

x_{5}y_{3}+x_{4}y_{4}+x_{3}y_{5}+x_{2}y_{6}+x_{1}y_{7}+

x_{7}y_{6}+x_{6}y_{7}+x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})•t^{4}+(x_{7}y_{1}+

x_{6}y_{2}+x_{5}y_{3}+x_{4}y_{4}+x_{3}y_{5}+x_{2}y_{6}+x_{1}y_{7}+

x_{7}y_{6}+x_{6}y_{7}+x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})•t^{3}+(x_{7}y_{1}+

x_{6}y_{2}+x_{5}y_{3}+x_{4}y_{4}+x_{3}y_{5}+x_{2}y_{6}+x_{1}y_{7}+x_{7}y_{6}+

x_{6}y_{7}+x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})•t+(x_{7}y_{1}+x_{6}y_{2}+x_{5}y_{3}+

x_{4}y_{4}+x_{3}y_{5}+x_{2}y_{6}+x_{1}y_{7}+x_{7}y_{6}+x_{6}y_{7}+

x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7}) = R7

R7 = (x_{7}y_{0}+x_{6}y_{1}+x_{5}y_{2}+x_{4}y_{3}+x_{3}y_{4}+x_{2}y_{5}+x_{1}y_{6}+

x_{0}y_{7}+x_{7}y_{7}+x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7}+x_{7}y_{4}+x_{6}y_{5}+x_{5}y_{6}+

x_{4}y_{7})•t^{7}+x_{6}y_{0}+x_{5}y_{1}+x_{4}y_{2}+x_{3}y_{3}+x_{2}y_{4}+x_{1}y_{5}+x_{0}y_{6}+

x_{7}y_{6}+x_{6}y_{7}+x_{7}y_{4}+x_{6}y_{5}+x_{5}y_{6}+x_{4}y_{7}+x_{7}y_{3}+

x_{6}y_{4}+x_{5}y_{5}+x_{4}y_{6}+x_{3}y_{7})•t^{6}+(x_{5}y_{0}+x_{4}y_{1}+x_{3}y_{2}+x_{2}y_{3}+

x_{1}y_{4}+x_{0}y_{5}+x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7}+x_{7}y_{3}+x_{6}y_{4}+x_{5}y_{5}+x_{4}y_{6
}+x_{3}y_{7}+x_{7}y_{2}+x_{6}y_{3}+x_{5}y_{4}+x_{4}y_{5}+x_{3}y_{6}+x_{2}y_{7})•t^{5}+(x_{4}y_{0}+

x_{3}y_{1}+x_{2}y_{2}+x_{1}y_{3}+x_{0}y_{4}+x_{7}y_{4}+x_{6}y_{5}+x_{5}y_{6}+x_{4}y_{7}+

x_{7}y_{2}+x_{6}y_{3}+x_{5}y_{4}+x_{4}y_{5}+x_{3}y_{6}+x_{2}y_{7}+x_{7}y_{7}+x_{7}y_{1}+x_{6}y_{2}+

x_{5}y_{3}+x_{4}y_{4}+x_{3}y_{5}+x_{2}y_{6}+x_{1}y_{7})•t^{4}+(x_{3}y_{0}+x_{2}y_{1}+x_{1}y_{2}+

x_{0}y_{3}+x_{7}y_{4}+x_{6}y_{5}+x_{5}y_{6}+x_{4}y_{7}+x_{7}y_{3}+x_{6}y_{4}+x_{5}y_{5}+x_{4}y_{6
}+x_{3}y_{7}+x_{7}y_{7}+x_{7}y_{1}+x_{6}y_{2}+x_{5}y_{3}+x_{4}y_{4}+x_{3}y_{5}+x_{2}y_{6}+x_{1}y_{7}+

x_{7}y_{6}+x_{6}y_{7}+x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})•t^{3}+(x_{2}y_{0}+x_{1}y_{1}+x_{0}y_{2}+x_{7}y_{3}+x_{6}y_{4}+

x_{5}y_{5}+x_{4}y_{6}+x_{3}y_{7}+x_{7}y_{2}+x_{6}y_{3}+x_{5}y_{4}+x_{4}y_{5}+x_{3}y_{6}+x_{2}y_{7}+x_{7}y_{6}+x_{6}y_{7})

•t^{2}+(x_{1}y_{0}+x_{0}y_{1}+x_{7}y_{2}+x_{6}y_{3}+x_{5}y_{4}+x_{4}y_{5}+x_{3}y_{6}+x_{2}y_{7}+

x_{7}y_{7}+x_{7}y_{1}+x_{6}y_{2}+x_{5}y_{3}+x_{4}y_{4}+x_{3}y_{5}+x_{2}y_{6}+x_{1}y_{7}+x_{7}y_{5}+

x_{6}y_{6}+x_{5}y_{7})•t+(x_{0}y_{0}+x_{7}y_{1}+x_{6}y_{2}+x_{5}y_{3}+x_{4}y_{4}+x_{3}y_{5}+x_{2}y_{6}+x_{1}y_{7}+

x_{7}y_{6}+x_{6}y_{7}+x_{7}y_{5}+x_{6}y_{6}+x_{5}y_{7})

Now we obtain the coefficients c_{7},…, c_{0} from R7 as Eq. 3.

(3) |

Then, we give the generation process of the 24 multivariate quadratic equations. According to the principle of Rijndael S-box, the relationship between z and y can be denoted as:

z = Ay+‘63’

We can get:

y = A^{-1}z+A^{-1}. ‘63’ = A^{-1}z+‘05’

Where:

Then we get:

(4) |

Substituting Eq. 4 into 3, we obtain 8 multivariate quadratic equations of S-box as Eq. 5:

(5) |

Since, there is no nonzero const term in 7 of these equations in Eq. 5, for x = 0, these 7 equations are true with probability 1. The 8th equation is true when, x ≠ 0, so this equation is true with probability 255/256.

Since, xy = 1(∀x ≠ 0) we can get:

∀x ≠ 0 x = x^{2}y

Obviously, this equation is also true when x = 0, so we have:

(6) |

We might as well choose the last equation in Eq. 6. It is symmetric with respect to the exchange of x and y, so we can obtain the following two equations:

Then we have two equations over GF(2^{8}) are true with probability 1. Because

(7) |

From Eq. 7 and 8, we have 23 quadratic equations between x_{i} and z_{j} that are true with probability 1. We have explicitly generated these equations have verified that they are all linearly independent and have also verified that there are no more such equations. It is easy to find that there is no terms in x_{i}x_{j} or z_{i}z_{j} in the above 23 equations and the terms present in these equations are t = 81: these are {x_{1}z_{1},…x_{8}z_{8}, z_{1},…z_{8}, x_{1},…x_{8}, 1}:

(8) |

**OPTIMIZATION OF RIJNDAEL S-BOX EQUATION SYSTEM**

**Definition 1:** Cheon and Lee (2004). For r equations in t terms over GF(2^{n}), the Resistance of Algebraic Attacks (RAA) is denoted by Γ and is defined as follow:

Γ = ((t-r)/n)^{j(t-r)/nk}

The resistance of algebraic attacks reflects a difficulty of solving multivariate equations. Thus we will use this quantity to measure the resistance of algebraic attacks in this study.

**Definition 2:** An Affine-Inverse-Affine (AIA) S-box is defined as follow:

where, A denotes the affine transformation and I denotes the inverse transformation in GF(2^{8}).

**Equation system of the AIA structure rijndael S-box:** In the Cui *et al*. (2011), we designed a new Rijndael S-box structure named Affine-Inverse-Affine (AIA) to increase the algebraic complexity of Rijndael S-box. Now we analyze the equation system of the new Rijndael S-box.

We obtain the coefficients of the algebraic expression of the new Rijndael S-box as Table 1.

From Table 1 and the algebraic expression of Rijndael S-box, it can be seen that the algebraic expression of Rijndael S-box is very simple (i.e., only 9 terms are involved) while the new Rijndael S-box involves 255 terms and is very complex.

From Table 1, it is easy to see that the algebraic expression of the new Rijndael S-box is as follow:

S’(x) = Fax^{∞}+A6x^{01}+A9x^{02}+…+E7x^{FC}+26x^{FD}+12x^{FE
}= FA+A6(x^{-1})^{254}+A9(x^{-1})^{253}+…+E7(x^{-1})^{3}+26(x^{-1})^{2}+12x^{-1
}= FA+A6y_{253}+A9y_{252}+…+E7y_{2}+26y_{1}+12y_{0}

where, y_{0} = x^{-1}, y_{1} = (x^{-1})^{2}, y_{2} = (x^{-1})^{3},…, y_{252} = (x^{-1})^{253}, y_{253} = (x^{-1})^{254} and it can be denoted as S(x) = g(y_{0}, y_{1},…, y_{252}, y_{253}).

We denote by ^{8}):

(9) |

where, 0≤i≤9, 0≤j, k≤3.

Table 1: | Coefficients of algebraic expression of the new Rijndael S-box |

Table 2: | Comparisons of equation systems of Rijndael S-box |

The last linear equation can be seen as another linear transformation after S-box transformation. From the Eq. 9, it can be seen that each S-box has 255 quadratic equations. Then, the total 255 quadratic equations of the new Rijndael S-box are obtained.

These 255 quadratic equations comprise a total of 510 terms: 1,

For the new Rijndael S-box, it is easy to obtain that t = 510, r = 255, n = 8. According to the definition 1, it can be obtained that Γ = 31.875^{32} ≈ 2^{160}.

**Comparison with the existing equation systems:** Table 2 shows the comparison results. As can be seen from Table 2 for each S-box, the equation system (Murphy and Robshaw, 2002) comprises 24 quadratic equations of 41 terms over GF(2^{8}) and the equation system (Li and Chen, 2004) comprises 17 quadratic equations of 34 terms over GF(2^{8}) while our equation system comprises 255 quadratic equations of 510 terms over GF(2^{8}).

According to the definition of RAA, we can obtain that the RAA of the equation system (Murphy and Robshaw, 2002; Li and Chen, 2004; Xiao and Zhang, 2008) are 9.6, 9.6 and 2^{8}, respectively. However, our equation system has the following property: Γ = 2^{160}. Cheon and Lee (2004) pointed out that should be greater than 2^{32 }for secure ciphers.

This suggests that the complexity of solving our equation system is much more than that of solving other existing equation systems. Our work is helpful to improving the security of Rijndael cipher.

**CONCLUSION**

In this study, a new approach to generating the multivariate quadratic equation system over GF(2) is proposed and an equation system over GF(2^{8}) is proposed to describe the new Rijndael S-box. Firstly, the construction principle and the algebraic expression of Rijndael S-box are described. Secondly, a new approach to generating the multivariate quadratic equation system over GF(2) is proposed and the generation process of the multivariate quadratic equations is given explicitly. Finally, an equation system over GF(2^{8}) is proposed to describe the new Rijndael S-box and it suggest that the new equation system has stronger resistance against algebraic attacks than other existing equation systems.

**ACKNOWLEDGMENT**

The study was supported by the National Natural Science Foundation of China (No. 61173188, 61173187, 61272074), the Educational Commission of Anhui Province, China (No. KJ2013A017), the Research Fund for the Doctoral Program of Higher Education (No. 20133401110004) and the Doctoral Research Start-up Funds Project of Anhui University. The authors are very grateful to Chinchen Chang and the anonymous referees for their detailed comments and suggestions regarding this study.

Direct Link

Cheon, J.H. and D.H. Lee, 2004. Resistance of S-Boxes Against Algebraic Attacks. In: Fast Software Encryption, Roy, B. and W. Meier (Eds.)., Springer-Verlag, Berlin, Heidelberg, pp: 83-93.

Courtois, N.T. and J. Pieprzyk, 2002. Cryptanalysis of Block Ciphers with Overdefined Systems of Equations. In: Advances in Cryptology, Zheng, Y. (Ed.). Volume 2501, Springer, Heidelberg Germany, ISBN: 978-3-540-00171-3, pp: 267-287.

Cui, J., L. Huang, H. Zhong, C. Chang and W. Yang, 2011. An improved AES S-Box and its performance analysis. Int. J. Innov. Comput. Inform. Control, 7: 2291-2302.

Direct Link

Demirci, H., M.S. Sagiroglu and M.O. Kulekci, 2013. A time-memory trade-off approach for the solution of nonlinear equation systems. Turkish J. Electrical Eng. Comput. Sci., 21: 186-197.

Direct Link

Ghosh, S. and A. Das, 2012. Improvements of algebraic attacks based on structured gaussian elimination. https://eprint.iacr.org/2012/176.pdf.

Hussain, I., T. Shah, H. Mahmood and M.A. Gondal, 2013. A projective general linear group based algorithm for the construction of substitution box for block ciphers. Neural Comput. Applic., 22: 1085-1093.

CrossRef

Kim, J., S. Hong and B. Preneel, 2007. Related-key rectangle attacks on reduced AES-192 and AES-256. Proceedings of the 14th International Workshop on Fast Software Encryption, March 26-28, 2007, Luxembourg, pp: 225-241.

Li, N. and W. Chen, 2004. A new system of multivariate quadratic equations for rijndael. J. Electron. Inform. Technol., 26: 1990-1995.

Direct Link

Murphy, S. and M.J.B. Robshaw, 2002. Essential algebraic structure within the AES. Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, August 18-22, 2002, London, pp: 1-16.

Xiao, H.P. and G.J. Zhang, 2008. The improvement on algebraic system of multivariate quadratic equations for Rijndael. J. Electron. Inform. Technol., 30: 2459-2463.

Zhang, W., W. Wu, L. Zhang and D. Feng, 2007. Improved related-key impossible differential attacks on reduced-round AES-192. Proceedings of the 13th International Workshop on Selected Areas in Cryptography, August 17-18, 2006, Montreal, Canada, pp: 15-27.

Zhang, X., Q. Wang, B. Wang and H. Kan, 2011. A constructive method of algebraic attack with less Keystream bits. IEICE Trans. Fundamentals Electron. Commun. Comput. Sci., 94: 2059-2062.

Direct Link

© Science Alert. All Rights Reserved