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(28) 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(28). Cheon and Lee (2004) proposed a new system of multivariate quadratic equations over GF(28) 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(28) 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(28), Rijndael S-box is a combination of an inverse function I(x) which is the multiplicative inverse modulo the irreducible polynomial x8+x4+x3+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, xi(i = 0,…, 7) are the bits of the byte x and x7 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) = 05xFE+09xFD+F9xFB+25xF7+F4xEF+01xDF+
B5xBF+8Fx7F+63
NEW APPROACH TO GENERATING MQ EQUATION SYSTEM OF RIJNDAEL S-BOX
Rijndael S-box is a composition of the “patched” inverse in GF(28) with 0 mapped on itself with a multivariate affine transformation GF(28)→GF(28). 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) = t8+t4+t3+t+1.
Comparing the both sides coefficients of tk(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 c7,…, c0 of tk(0≤k<8). Firstly, we give the computation process of the coefficients c7,…, c0.
We note (x7,…, x0) = x, (y7,…, y0) = y and (z7,…, z0) = 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:
x7y7•t14+x7t7•t10+x7y7•t9+x7y7•t7+x7y7•t6 = R1
Step 2:R1 modulo:
(x7y6+x6y7)•t13+(x7y6+x6y7)•t9+(x7y6+x6y7)•t8+(x7y6+x6y7)•
t6+(x7y6+x6y7)•t5 = R2
Step 3:R2 modulo:
(x7y5+x6y6+x5y7)•t12+(x7y5+x6y6+x5y7)•t8+
(x7y5+x6y6+x5y7)•t7+(x7y5+x6y6+x5y7)•t5+(x7y5+x6y6+x5y7)
t4 = R3
Step 4:R3 modulo:
(x7y4+x6y5+x5y6+x4y7)•t11+(x7y4+x6y5+x5y6+x4y7)•t7+
(x7y4+x6y5+x5y6+x4y7)•t6+(x7y4+x6y5+x5y6+x4y7)•t4+
(x7y4+x6y5+x5y6+x4y7)•t3 = R4
Step 5:R4 modulo:
(x7y3+x6y4+x5y5+x4y6+x3y7+x7y7)•t10+
(x7y3+x6y4+x5y5+x4y6+x3y7+x7y7)•t6+
(x7y3+x6y4+x5y5+x4y6+x3y7+x7y7)•t5+
(x7y3+x6y4+x5y5+x4y6+x3y7+x7y7)•t3+
(x7y3+x6y4+x5y5+x4y6+x3y7+x7y7)•t2 = R5
Step 6:R5 modulo:
(x7y2+x6y3+x5y4+x4y5+x3y6+x2y7+x7y7+
x7y6+x6y7)•t9+(x7y2+x6y3+x5y4+x4y5+x3y6+
x2y7+x7y7+x7y6+x6y7)•t5+(x7y2+x6y3+
x5y4+x4y5+x3y6+x2y7+x7y7+x7y6+x6y7)•t4+(x7y2+
x6y3+x5y4+x4y5+x3y6+x2y7+x7y7+x7y6+x6y7)•
t2+(x7y2+x6y3+x5y4+x4y5+x3y6+x2y7+x7y7+x7y6+x6y7)•
t = R6
Step 7:R6 modulo:
(x7y1+x6y2+x5y3+x4y4+x3y5+x2y6+x1y7+x7y6+
x6y7+x7y5+x6y6+x5y7)•t8+(x7y1+x6y2+
x5y3+x4y4+x3y5+x2y6+x1y7+
x7y6+x6y7+x7y5+x6y6+x5y7)•t4+(x7y1+
x6y2+x5y3+x4y4+x3y5+x2y6+x1y7+
x7y6+x6y7+x7y5+x6y6+x5y7)•t3+(x7y1+
x6y2+x5y3+x4y4+x3y5+x2y6+x1y7+x7y6+
x6y7+x7y5+x6y6+x5y7)•t+(x7y1+x6y2+x5y3+
x4y4+x3y5+x2y6+x1y7+x7y6+x6y7+
x7y5+x6y6+x5y7) = R7
R7 = (x7y0+x6y1+x5y2+x4y3+x3y4+x2y5+x1y6+
x0y7+x7y7+x7y5+x6y6+x5y7+x7y4+x6y5+x5y6+
x4y7)•t7+x6y0+x5y1+x4y2+x3y3+x2y4+x1y5+x0y6+
x7y6+x6y7+x7y4+x6y5+x5y6+x4y7+x7y3+
x6y4+x5y5+x4y6+x3y7)•t6+(x5y0+x4y1+x3y2+x2y3+
x1y4+x0y5+x7y5+x6y6+x5y7+x7y3+x6y4+x5y5+x4y6
+x3y7+x7y2+x6y3+x5y4+x4y5+x3y6+x2y7)•t5+(x4y0+
x3y1+x2y2+x1y3+x0y4+x7y4+x6y5+x5y6+x4y7+
x7y2+x6y3+x5y4+x4y5+x3y6+x2y7+x7y7+x7y1+x6y2+
x5y3+x4y4+x3y5+x2y6+x1y7)•t4+(x3y0+x2y1+x1y2+
x0y3+x7y4+x6y5+x5y6+x4y7+x7y3+x6y4+x5y5+x4y6
+x3y7+x7y7+x7y1+x6y2+x5y3+x4y4+x3y5+x2y6+x1y7+
x7y6+x6y7+x7y5+x6y6+x5y7)•t3+(x2y0+x1y1+x0y2+x7y3+x6y4+
x5y5+x4y6+x3y7+x7y2+x6y3+x5y4+x4y5+x3y6+x2y7+x7y6+x6y7)
•t2+(x1y0+x0y1+x7y2+x6y3+x5y4+x4y5+x3y6+x2y7+
x7y7+x7y1+x6y2+x5y3+x4y4+x3y5+x2y6+x1y7+x7y5+
x6y6+x5y7)•t+(x0y0+x7y1+x6y2+x5y3+x4y4+x3y5+x2y6+x1y7+
x7y6+x6y7+x7y5+x6y6+x5y7)
Now we obtain the coefficients c7,…, c0 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-1z+A-1. ‘63’ = A-1z+‘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 = x2y
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(28) are true with probability 1. Because
| (7) |
From Eq. 7 and 8, we have 23 quadratic equations between xi and zj 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 xixj or zizj in the above 23 equations and the terms present in these equations are t = 81: these are {x1z1,…x8z8, z1,…z8, x1,…x8, 1}:
| (8) |
OPTIMIZATION OF RIJNDAEL S-BOX EQUATION SYSTEM
Definition 1: Cheon and Lee (2004). For r equations in t terms over GF(2n), 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(28).
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∞+A6x01+A9x02+…+E7xFC+26xFD+12xFE
= FA+A6(x-1)254+A9(x-1)253+…+E7(x-1)3+26(x-1)2+12x-1
= FA+A6y253+A9y252+…+E7y2+26y1+12y0
where, y0 = x-1, y1 = (x-1)2, y2 = (x-1)3,…, y252 = (x-1)253, y253 = (x-1)254 and it can be denoted as S(x) = g(y0, y1,…, y252, y253).
We denote by
| (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.87532 ≈ 2160.
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(28) and the equation system (Li and Chen, 2004) comprises 17 quadratic equations of 34 terms over GF(28) while our equation system comprises 255 quadratic equations of 510 terms over GF(28).
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 28, respectively. However, our equation system has the following property: Γ = 2160. Cheon and Lee (2004) pointed out that should be greater than 232 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(28) 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(28) 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.