# Algebraic Cryptanalysis Scheme of AES-256 Using Gröbner Basis

Authors: Kaixin Zhao; Jie Cui; Zhiqiang Xie
Journal: Journal of Electrical and Computer Engineering
 (2017)

---

## Abstract

The zero-dimensional Gröbner basis construction is a crucial step in Gröbner basis cryptanalysis on AES-256. In this paper, after performing an in-depth study on the linear transformation and the system of multivariate polynomial equations of AES-256, the zero-dimensional Gröbner basis construction method is proposed by choosing suitable term order and variable order. After giving a detailed construction process of the zero-dimensional Gröbner basis, the necessary theoretical proof is presented. Based on this, an algebraic cryptanalysis scheme of AES-256 using Gröbner basis is proposed. Analysis shows that the complexity of our scheme is lower than that of the exhaustive attack.


---

## Body

## 1. Introduction

On October 2, 2000, the Rijndael algorithm, which was designed by Daemen and Rijmen, was determined by the National Institute of Standards and Technology (NIST) for the Advanced Encryption Standard (AES) [1]. It has been of concern to the cryptographic community since the Rijndael algorithm was proposed, and there have been many attack methods. However, there is no successful attack on the full Rijndael algorithm up to now [2, 3].Cryptanalysis and cryptography not only are mutually antagonistic, but also promote each other. Because of the great advantages of algebraic cryptanalysis technology, it has become a hot research topic in recent years. Algebraic attack is mainly composed of two steps: the first step is to establish a system of algebraic equations to describe the relationship among the plaintext, the ciphertext, and the key in cryptographic algorithm; the second step is to solve the system of equations to obtain the key by some of the known plaintext-ciphertext pairs. The first step has already obtained some research results, and many scholars have proposed many kinds of equation systems of AES algorithm [4, 5]. In the second step, the multivariate equation system is still a problem to be solved. Although solving the multivariate equation system is an NP-hard problem, the complexity of solving a sparse overdetermined system of equations is far lower than that of the NP-hard problem.At present, the methods of solving the high order multivariate equation system mainly include XL, XSL, and Gröbner basis. Since the algebraic expression of AES algorithm is sparse and structured, it is inefficient to apply XL attacks directly. In 2002, Courtois et al. proposed an XSL attack method and claimed to break the key length of 256-bit AES algorithm in theory. However, the number of linear independent equations generated by XSL attacks in the academic field is disputed, and the validity of the attack is questioned [6, 7]. Gröbner basis is an effective method for solving the high order multivariate equation system, which is proposed by Buchberger. Its essence is to set up a set of arbitrary ideals in polynomial rings, describe and compute a set of generators with good properties, and then study the ideal structure and carry out the ideal computation [3].Gröbner basis is a standard representation method of polynomial ideals, which has some useful properties [8]. Gröbner basis exists in any ideal, and the Gröbner basis of any ideal can be computed by the Buchberger algorithm or F4 or F5 algorithm [6]. Lexicographic order is a commonly used elimination order. The coefficient matrix of the basis is triangular when using lexicographical Gröbner basis in the computation, and the last row solves single-variable equations. This is the reason why lexicographical Gröbner basis can solve the equation system. But the direct computation of lexicographic Gröbner basis will produce excessive coefficients.Common practice is to compute the total degree order Gröbner basis of the ideal firstly and then convert the total degree order Gröbner basis to lexicographical Gröbner basis using Gröbner basis conversion algorithm. Gröbner basis conversion algorithms include the Gröbner Walk [7] and the FGLM algorithm [6]. Compared with the Gröbner Walk, FGLM algorithm is simple and efficient, but the FGLM algorithm only works for zero-dimensional ideals [9, 10]. Therefore, constructing the zero-dimensional Gröbner basis of AES algorithm is crucial to implement Gröbner basis cryptanalysis. In 2013, the zero-dimensional Gröbner basis construction method of Rijndael-192 was proposed [11]. However, how to construct the zero-dimensional Gröbner basis of AES-256 and how to apply Gröbner basis cryptanalysis to AES-256 are still open questions. In this paper, the authors perform some particular studies on the linear transformation and the system of multivariate polynomial equations of AES-256 and propose its zero-dimensional Gröbner basis construction method through choosing suitable term order and variable order. After presenting the construction method of the Gröbner basis, the authors give the necessary theoretical proof. Moreover, the authors propose an algebraic cryptanalysis of AES-256 using Gröbner basis. Analysis suggests that the complexity of our scheme is lower than the exhaustive attack. The main contributions are given as follows:(1)
The zero-dimensional Gröbner basis construction method is proposed by choosing suitable term order and variable order.(2)
The necessary theoretical proof is given, and it shows that the set of polynomials is a zero-dimensional Gröbner basis.(3)
The effective algebraic cryptanalysis scheme of AES-256 using Gröbner basis is proposed.The rest of this paper is formed as follows. The mathematical model of AES-256 is shown in Section2. Section 3 demonstrates the Gröbner basis theory. The equation system of AES-256 is given in Section 4. In Section 5, the Gröbner basis construction method of AES-256 and the algebraic cryptanalysis scheme of AES-256 are proposed. Finally, the paper is concluded in Section 6.


## 2. Mathematical Model of AES-256

The block length and key length of AES can be specified independently as 128 bits, 192 bits, or 256 bits, and the corresponding round time is 10, 12, or 14. Each round consists of 4 transformations: theS-box substitution (ByteSub), ShiftRow, MixColumn, and AddRoundKey. With AES starting from the AddRoundKey, with 13 rounds of iteration, the final round is equal to the round with the MixColumn step removed. AES is an iterated block cipher with a variable block length and a variable key length. In this paper, both the block length and the key length are specified to 256 bits.


### 2.1.S-Box Substitution

TheS-box transformation is a nonlinear byte substitution, operating on each of the state bytes independently. TheS-box is invertible and is constructed by the composition of two transformations:(1)
Seeking the inverse operation of multiplication inGF(28)=Z2x/x8+x4+x3+x+1 field, that is, input ω∈GF28 and output υ∈GF28, to meet(1)ω∗υ=1mod⁡x8+x4+x3+x+1,then(2)υ=ω-1=ω254,ω≠0,0,ω=0.(2)
Let element components ofx=υ in GF(2)8 be (x7,x6,x5,x4,x3,x2,x1,x0); the affine transformations are as follows:(3)y=La×x+“63”=1111100001111100001111100001111110001111110001111110001111110001x7x6x5x4x3x2x1x0+01100011.The selection of constant “63” is to ensure theS-box is not a fixed point Sa=a and an opposite fixed point Sa=a¯.S-box has the ability to resist linear attacks and differential attacks [1].


### 2.2. ShiftRow and MixColumn Transformations

The 4 × 8-byte matrix is obtained byS-box substitution, where Si,j is the byte in the ith row and the jth column, 0≤i≤3, 0≤j≤7. SR (ShiftRow) shift i bytes to the left for the ith row of the matrix:(4)s0,0s0,1s0,2s0,3s0,4s0,5s0,6s0,7s1,0s1,1s1,2s1,3s1,4s1,5s1,6s1,7s2,0s2,1s2,2s2,3s2,4s2,5s2,6s2,7s3,0s3,1s3,2s3,3s3,4s3,5s3,6s3,7⟶s0,0s0,1s0,2s0,3s0,4s0,5s0,6s0,7s1,1s1,2s1,3s1,4s1,5s1,6s1,7s1,0s2,2s2,3s2,4s2,5s2,6s2,7s2,0s2,1s3,3s3,4s3,5s3,6s3,7s3,0s3,1s3,2.MC (MixColumn) transforms the independent operation of each column for the purpose of causing confusion. Each byte in each column is mapped to the new value; this value is 4 bytes in the column with the function obtained. Transformation is as follows:(5)s0,0′s0,1′s0,2′s0,3′s0,4′s0,5′s0,6′s0,7′s1,0′s1,1′s1,2′s1,3′s1,4′s1,5′s1,6′s1,7′s2,0′s2,1′s2,2′s2,3′s2,4′s2,5′s2,6′s2,7′s3,0′s3,1′s3,2′s3,3′s3,4′s3,5′s3,6′s3,7′=D·s0,0s0,1s0,2s0,3s0,4s0,5s0,6s0,7s1,0s1,1s1,2s1,3s1,4s1,5s1,6s1,7s2,0s2,1s2,2s2,3s2,4s2,5s2,6s2,7s3,0s3,1s3,2s3,3s3,4s3,5s3,6s3,7,where(6)D=02030101010203010101020303010102.For mathematical convenience, we use a column vector instead of the original matrix to represent intermediate states and keys. The mapping relationship between the elements in column vector and the elements in the original matrix is as follows:(7)φ:F4×8⟶F32,s0,0s0,1s0,2s0,3s0,4s0,5s0,6s0,7s1,0s1,1s1,2s1,3s1,4s1,5s1,6s1,7s2,0s2,1s2,2s2,3s2,4s2,5s2,6s2,7s3,0s3,1s3,2s3,3s3,4s3,5s3,6s3,7⟼s0,0,s1,0,…,s0,1,s1,1,…T.The finite fieldGF28 is denoted as F in this paper. Introducing a 32×32 0-1 transformation matrix MSR, the SR transform is equivalent to left multiplication by the matrix MSR. There is only one element in each column and each row of the matrix is 1 and all the others are 0. Similarly, by introducing a new transformation matrix MMC, the MC transform is equivalent to left multiplication by the matrix MMC. The construction principle of MMC is MMC=D⊗I8∈F32×32, where ⊗ denotes tensor product and I8 denotes 8-order identity matrix. The composite transformation of the SR transform and the MC transform is denoted as M, and then M=MMC·MSR. It is easy to get(8)M=MMC·MSR=02000000010000000100000003000000000300000002000000010000000100000000010000000300000002000000010000000001000000010000000300000002000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000010000000100000003000000000300000002000000010000000100000000010000000300000002000000010000000001000000010000000300000002000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000010000000100000003000000000300000002000000010000000100000000010000000300000002000000010000000001000000010000000300000002000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000010000000100000003000000000300000002000000010000000100000000010000000300000002000000010000000001000000010000000300000002000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000010000000100000003000000000300000002000000010000000100000000010000000300000002000000010000000001000000010000000300000002000000010000000100000003000000020000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000010000000100000003000000000300000002000000010000000100000000010000000300000002000000010000000100000003000000020000000100000000010000000100000003000000020000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000010000000100000003000000000300000002000000010000000100000003000000020000000100000001000000000100000003000000020000000100000000010000000100000003000000020000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000010000000100000003000000.Thus, the linear transformation consisting of the SR transform and the MC transform can be expressed as(9)s0,0′′,s1,0′′,…,s0,1′′,s1,1′′,…T=M·s0,0,s1,0,…,s0,1,s1,1,…T.


### 2.3. AddRoundKey

In this operation, a round key is applied to the state by a simple bitwise EXOR. The round key is derived from the cipher key by means of the key schedule. It can be denoted asY=X⊕K, where K is the round key.


### 2.4. Key Schedule Algorithm

Key schedule consists of two modules: key expansion and round key selection. The block length and key length are denoted asNb and Nk, respectively, and the unit is a 4-byte word. That is, Nb = block length/32 and Nk = key length/32. The number of rounds is denoted by R.For AES-256,Nb=8, Nk=8, and R=14. The key expansion of AES-256 is to extend eight 4-byte key words into 90 4-byte words W[·], where W[0],…,W[7] is the cipher key. The expansion algorithm is as shown in Algorithm 1.Algorithm 1:Key expansion algorithm of AES-256.
(1)fori=8;i<90;i++do (2)ifi%8=0 then (3)Wi=Wi-8⊕BS(RotByteWi-1)⊕const(i/8); (4)else (5)Wi=Wi-8⊕Wi-1; (6)end if (7)end for (8)returnW8,W9,…,W89;


## 2.1.S-Box Substitution

TheS-box transformation is a nonlinear byte substitution, operating on each of the state bytes independently. TheS-box is invertible and is constructed by the composition of two transformations:(1)
Seeking the inverse operation of multiplication inGF(28)=Z2x/x8+x4+x3+x+1 field, that is, input ω∈GF28 and output υ∈GF28, to meet(1)ω∗υ=1mod⁡x8+x4+x3+x+1,then(2)υ=ω-1=ω254,ω≠0,0,ω=0.(2)
Let element components ofx=υ in GF(2)8 be (x7,x6,x5,x4,x3,x2,x1,x0); the affine transformations are as follows:(3)y=La×x+“63”=1111100001111100001111100001111110001111110001111110001111110001x7x6x5x4x3x2x1x0+01100011.The selection of constant “63” is to ensure theS-box is not a fixed point Sa=a and an opposite fixed point Sa=a¯.S-box has the ability to resist linear attacks and differential attacks [1].


## 2.2. ShiftRow and MixColumn Transformations

The 4 × 8-byte matrix is obtained byS-box substitution, where Si,j is the byte in the ith row and the jth column, 0≤i≤3, 0≤j≤7. SR (ShiftRow) shift i bytes to the left for the ith row of the matrix:(4)s0,0s0,1s0,2s0,3s0,4s0,5s0,6s0,7s1,0s1,1s1,2s1,3s1,4s1,5s1,6s1,7s2,0s2,1s2,2s2,3s2,4s2,5s2,6s2,7s3,0s3,1s3,2s3,3s3,4s3,5s3,6s3,7⟶s0,0s0,1s0,2s0,3s0,4s0,5s0,6s0,7s1,1s1,2s1,3s1,4s1,5s1,6s1,7s1,0s2,2s2,3s2,4s2,5s2,6s2,7s2,0s2,1s3,3s3,4s3,5s3,6s3,7s3,0s3,1s3,2.MC (MixColumn) transforms the independent operation of each column for the purpose of causing confusion. Each byte in each column is mapped to the new value; this value is 4 bytes in the column with the function obtained. Transformation is as follows:(5)s0,0′s0,1′s0,2′s0,3′s0,4′s0,5′s0,6′s0,7′s1,0′s1,1′s1,2′s1,3′s1,4′s1,5′s1,6′s1,7′s2,0′s2,1′s2,2′s2,3′s2,4′s2,5′s2,6′s2,7′s3,0′s3,1′s3,2′s3,3′s3,4′s3,5′s3,6′s3,7′=D·s0,0s0,1s0,2s0,3s0,4s0,5s0,6s0,7s1,0s1,1s1,2s1,3s1,4s1,5s1,6s1,7s2,0s2,1s2,2s2,3s2,4s2,5s2,6s2,7s3,0s3,1s3,2s3,3s3,4s3,5s3,6s3,7,where(6)D=02030101010203010101020303010102.For mathematical convenience, we use a column vector instead of the original matrix to represent intermediate states and keys. The mapping relationship between the elements in column vector and the elements in the original matrix is as follows:(7)φ:F4×8⟶F32,s0,0s0,1s0,2s0,3s0,4s0,5s0,6s0,7s1,0s1,1s1,2s1,3s1,4s1,5s1,6s1,7s2,0s2,1s2,2s2,3s2,4s2,5s2,6s2,7s3,0s3,1s3,2s3,3s3,4s3,5s3,6s3,7⟼s0,0,s1,0,…,s0,1,s1,1,…T.The finite fieldGF28 is denoted as F in this paper. Introducing a 32×32 0-1 transformation matrix MSR, the SR transform is equivalent to left multiplication by the matrix MSR. There is only one element in each column and each row of the matrix is 1 and all the others are 0. Similarly, by introducing a new transformation matrix MMC, the MC transform is equivalent to left multiplication by the matrix MMC. The construction principle of MMC is MMC=D⊗I8∈F32×32, where ⊗ denotes tensor product and I8 denotes 8-order identity matrix. The composite transformation of the SR transform and the MC transform is denoted as M, and then M=MMC·MSR. It is easy to get(8)M=MMC·MSR=02000000010000000100000003000000000300000002000000010000000100000000010000000300000002000000010000000001000000010000000300000002000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000010000000100000003000000000300000002000000010000000100000000010000000300000002000000010000000001000000010000000300000002000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000010000000100000003000000000300000002000000010000000100000000010000000300000002000000010000000001000000010000000300000002000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000010000000100000003000000000300000002000000010000000100000000010000000300000002000000010000000001000000010000000300000002000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000010000000100000003000000000300000002000000010000000100000000010000000300000002000000010000000001000000010000000300000002000000010000000100000003000000020000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000010000000100000003000000000300000002000000010000000100000000010000000300000002000000010000000100000003000000020000000100000000010000000100000003000000020000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000010000000100000003000000000300000002000000010000000100000003000000020000000100000001000000000100000003000000020000000100000000010000000100000003000000020000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000010000000100000003000000.Thus, the linear transformation consisting of the SR transform and the MC transform can be expressed as(9)s0,0′′,s1,0′′,…,s0,1′′,s1,1′′,…T=M·s0,0,s1,0,…,s0,1,s1,1,…T.


## 2.3. AddRoundKey

In this operation, a round key is applied to the state by a simple bitwise EXOR. The round key is derived from the cipher key by means of the key schedule. It can be denoted asY=X⊕K, where K is the round key.


## 2.4. Key Schedule Algorithm

Key schedule consists of two modules: key expansion and round key selection. The block length and key length are denoted asNb and Nk, respectively, and the unit is a 4-byte word. That is, Nb = block length/32 and Nk = key length/32. The number of rounds is denoted by R.For AES-256,Nb=8, Nk=8, and R=14. The key expansion of AES-256 is to extend eight 4-byte key words into 90 4-byte words W[·], where W[0],…,W[7] is the cipher key. The expansion algorithm is as shown in Algorithm 1.Algorithm 1:Key expansion algorithm of AES-256.
(1)fori=8;i<90;i++do (2)ifi%8=0 then (3)Wi=Wi-8⊕BS(RotByteWi-1)⊕const(i/8); (4)else (5)Wi=Wi-8⊕Wi-1; (6)end if (7)end for (8)returnW8,W9,…,W89;


## 3. Gröbner Basis Theory

LetR be a ring; for a nonempty ideal I⊂R, its Gröbner basis is generally not unique [12, 13]. The Gröbner basis is related to the selection of term orders. Related definitions are given below.Definition 1.
Order≤ on a set TR is called term order, if and only if ≤ is a linear order, and satisfies two properties:(1)
For allt∈TR,  t≥1.(2)
For anys,t1,t2∈TR,  if t1≤t2, then  st1≤st2.
In a term order≤, the largest element of a polynomial p is called the head term of p, denoted as HTp.
The set of natural numbers isN, and n is a given positive integer, and x1,x2,…,xn are n variables in ring R. Let the set of terms be(10)TR=x1α1x2α2⋯xnαn∣αi∈N,i=1,2,…,n.
That is,TR is the power product set of n variables. The degree of term t=x1α1x2α2⋯xnαn∈TR is denoted as deg⁡t=∑i=1nαi. Let X=x1,x2,…,xn; then, the definitions of three common term orders will be given below.Definition 2.
T R   x 1 > x 2 > ⋯ > x n on lexicographical order, denoted as lex, is defined as follows.
Forα=α1,α2,…,αn, β=β1,β2,…,βn∈Nn, then Xα<lexXβ⇔ let αj=βj,j=0,1,…,k, and αk+1<βk+1α0=β0, where 0≤k≤n-1.Definition 3.
T R   x 1 > x 2 > ⋯ > x n on degree lexicographical order, denoted as deglex, is defined as follows.
Forα=(α1,α2,…,αn), β=β1,β2,…,βn∈Nn, then(11)
X
α
<
d
e
g
l
e
x
X
β
⟺
∑
i
=
1
n
α
i
<
∑
i
=
1
n
β
i
or
∑
i
=
1
n
α
i
=
∑
i
=
1
n
β
i
,
and according to the lexicographic order.
X
α
<
l
e
x
X
βDefinition 4.
T R   x 1 > x 2 > ⋯ > x n on degree reverse lexicographical order, denoted as degrevlex, is defined as follows.
Forα=α1,α2,…,αn, β=β1,β2,…,βn∈Nn, then(12)Xα<degrevlexXβ⟺∑i=1nαi<∑i=1nβi,or∑i=1nαi=∑i=1nβi,αn=βn,…,αi+1=βi+1,αi≠βi,αi>βi,betweenαandβ,the first different coords from right side,αi>βi.Definition 5.
LetR be a ring and let I be one nonzero ideal in R, G=g1,…,gm⊂I. G is called the Gröbner basis of ideal I if and only if(13)HTg1,…,HTgm=HTp:p∈I.
The Gröbner basis of any nonzero ideal can be obtained by using the Buchberger algorithm [12]. In the implementation of the Buchberger algorithm, the Buchberger rule can be used to eliminate unnecessary polynomials [12, 14]. Based on the Buchberger rule, the following conclusions can be obtained.Theorem 6.
LetG be a set of polynomials, H=HTf:f∈G; if all elements in H are pairwise prime, then G is a Gröbner basis.Proof.
See [15].A zero-dimensional ideal is an ideal that has a finite number of solutions over the closure of the field. It usually is advantageous to have this property for Gröbner basis computations. By using Corollary  6.56 of [16], we can determine whether an ideal I is zero-dimensional. Below we state a reduced version of this corollary.Theorem 7.
LetG be a Gröbner basis of the ideal I; then, dim⁡I=0 if and only if, for any 1≤i≤n, there exists a polynomial g∈G, so that HTg=xidi.


## 4. Equation System of AES-256

Letp0,…,p31,c0,…,c31∈F32×F32 be a known pair of plaintext and ciphertext in this paper. We call xi,j the jth element of the output of the AddRoundKey in the ith round transformation. We denote by ki,j the jth element of the ith round key. It is easy to see that k0,j denotes the cipher key, 0≤i≤14,0≤j≤31. The equation system on GF28 consists of the following four parts:(1)
Initial round (round 0) equations and the cipher equations:(14)x0,0+k0,0+p0=0x14,0+c0=0⋮⋮x0,31+k0,31+p31=0x14,31+c31=0.(2)
The equations of intermediate rounds, that is, the encryption equation of theith round, 1≤i≤13:(15)xi,0+ki,0xi,1+ki,1⋮xi,31+ki,31+M·Sxi-1,0Sxi-1,1⋮Sxi-1,31=0.(3)
The equations of the final round:(16)x14,0+k14,0x14,1+k14,1⋮x14,31+k14,31+MSR·Sx13,0Sx13,1⋮Sx13,31=0.(4)
Key scheduling equations:(17)ki,0ki,1ki,2ki,3ki,4ki,5⋮ki,31=ki-1,0+Ski-1,29+ξi-1ki-1,1+Ski-1,30ki-1,2+Ski-1,31ki-1,3+Ski-1,28ki-1,4+ki,0ki-1,5+ki,1⋮ki-1,31+ki,27,where ξi-11≤i≤14 is a round constant.


## 5. Algebraic Cryptanalysis Scheme of AES-256

Definition 8.
Denote the finite domainGF28 as F; the multivariate polynomial ring on F, R is defined as(18)R≔Fxi,j,ki,j:0≤i≤31,0≤j≤14.
To construct AES-256 Gröbner basis, the multivariate equation system obtained in Section4 must be improved to meet the requirements of Gröbner basis; that is, the head terms of the polynomial on the left-hand side of the equation are pairwise prime.


### 5.1. The Gröbner Basis Construction Method of AES-256

The Gröbner basis of AES-256 is constructed as follows.Step 1.
The purpose of this step is to construct the polynomial set of theS-box and the inverseS-box. In this step, we make use of the algebraic expression of theS-box and the inverseS-box.
AESS-box is constructed based on evident mathematical theory, so it can be written in the form of an algebraic expression. The sparse algebraic expression of theS-box in F is as follows: (19)S:F⟶F,x⟼05xFE+09xFD+F9xFB+25xF7+F4xEF+B5xDF+B9xBF+8Fx7F+63.
The nonsparse algebraic expression of the inverseS-box contains 255 terms. The coefficients of the algebraic expression of AES inverseS-box are shown in Table 1. The abbreviated form of the algebraic expression of AES inverseS-box can be expressed as follows:(20)S-1:F⟶F,x⟼∑i=0254cixi,where ci is the coefficient of the term with degree i.Table 1
Coefficients of algebraic expression of AES inverseS-box (Hex).
C (mn) 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 52 F3 7E 1E 90 BB 2C 8A 1C 85 6D C0 B2 1B 40 23 1 F6 73 29 D9 39 21 CF 3D 9A 8A 2F CF 7B 04 E8 C8 2 85 7B 7C AF 86 2F 13 65 75 D3 6D D4 89 8E 65 05 3 EA 77 50 A3 C5 01 0B 46 BF A7 0C C7 8E F2 B1 CB 4 E5 E2 10 D1 05 B0 F5 86 E4 03 71 A6 56 03 9E 3E 5 19 18 52 16 B9 D3 38 D9 04 E3 72 6B BA E8 BF 9D 6 1D 5A 55 FF 71 E1 A8 8E FE A2 A7 1F DF B0 03 CB 7 08 53 6F B0 7F 87 8B 02 B1 92 81 27 40 2E 1A EE 8 10 CA 82 4F 09 AA C7 55 24 6C E2 58 BC E0 26 37 9 ED 8D 2A D5 ED 45 C3 EC 1C 3E 2A B3 9E B7 38 82 A 23 2D 87 EA DA 45 24 03 E7 C9 E3 D3 4E DD 11 4E B 81 91 91 59 A3 80 92 7E DB C4 20 EC DB 55 7F A8 C C1 64 AB 1B FD 60 05 13 2C A9 76 A5 1D 32 8E 1E D C0 65 CB 8B 93 E4 AE BE 5F 2C 3B D2 0F 9F 42 CC E 6C 80 68 43 09 23 C5 6D 1D 18 BD 5E 1B B4 85 49 F BC 0D 1F A6 6B D8 22 01 7A C0 55 16 B3 CF 05 00Step 2.
The purpose of this step is to construct the polynomial set of linear transformations (i.e., ShiftRow and MixColumn). In this step, we use the equation system given in Section4.
By (14), the plaintext equations, that is, the initial round equation system, can be obtained as (21), and the ciphertext equations can be obtained as (22). Hence,(21)x0,i+k0,i+pi=0,pi∈F,0≤i≤31,(22)x14,i+ci=0,ci∈F,0≤i≤31.
Sincex0,i and k0,i have the same degree, the head term of polynomials in (21) is x0,i or k0,i. If the selected term order is x0,i<k0,i, then the head term of polynomial is k0,i, 0≤i≤31. For (22), the head term of polynomial is x14,i, 0≤i≤31.
It is needed to improve (15) and (16) to meet the requirements of Gröbner basis. From (15), it is easy to get 24 polynomial equations of round i1≤i≤13 as shown in(23)Sxi-1,0Sxi-1,1⋮Sxi-1,31+M-1·xi,0+ki,0xi,1+ki,1⋮xi,31+ki,31=0.
Similarly, from (16), the 32 polynomial equations of the final round can be obtained as shown in(24)Sx13,0Sx13,1⋮Sx13,31+MSR-1·x14,0+k14,0x14,1+k14,1⋮x14,31+k14,31=0.
For degree lexicographical order, the head term of polynomial in (23) and (24) is xi,j254, 0≤i≤13, 0≤j≤31. It is easy to see that the head term has no nontrivial common factor; that is, the greatest common factor is 1.Step 3.
The purpose of this step is to construct the polynomial set of the key schedule algorithm. In this step, we also use the equation system given in Section4.
In order to get the polynomial Gröbner basis of the whole encryption algorithm, the equation system of the key schedule algorithm needs to be improved. It is easy to deduce (25) from (17). Hence,(25)ki,0ki,1ki,2ki,3ki,4ki,5⋮ki,31=ki-1,0ki-1,1ki-1,2ki-1,3ki-1,4ki-1,5⋮ki-1,31+Ski-1,29Ski-1,30Ski-1,31Ski-1,28ki,0ki,1⋮ki,27+ξi-100000⋮0.
In order to ensure that the head terms of key schedule polynomials are pairwise prime, applying the inverseS-box transformation to (25) is needed. The transformation results are shown in(26)S-1ki,0+ki-1,0+ξi-1S-1ki,1+ki-1,1S-1ki,2+ki-1,2S-1ki,3+ki-1,3ki,4+ki-1,4ki,5+ki-1,5⋮ki,31+ki-1,31+ki-1,29ki-1,30ki-1,31ki-1,28ki,0ki,1⋮ki,27=0.
According to the algebraic expression of the inverseS-box, all the equations included in (26) can be obtained. If the selected term order is (27)ki,31>ki,30>⋯>ki,0>ki-1,31>⋯>ki-1,1>ki-1,0,where 1≤i≤14, then the set of polynomial head terms of the key schedule equation (26) is(28)ki,j254,ki,h:1≤i≤14,0≤j≤3,4≤h≤31.
It is easy to see that the elements of the head term set have no nontrivial common factor.Step 4.
The purpose of this step is the reasonable selection of term order and variable order. If we choose a degree lexicographical order over reasonable variable order, we can make the polynomial head terms of the whole encryption algorithm pairwise prime.
The left-hand sides of (21), (22), (23), (24), and (26) constitute a set of polynomials denoted as A, and the degree lexicographical order <A over the following variable order makes the head terms of polynomials in A pairwise prime. Hence,(29)x0,0<⋯<x0,31︸initial round state variables<k0,0<⋯<k0,31︸initial key variable<k1,0<⋯<k1,31︸first round key variables<⋯<k14,0<⋯<k14,31︸last round key variables<x1,0<⋯<x1,31︸first round internal state variables<⋯<x13,0<⋯<x13,31︸11th round internal state variables<x14,0<⋯<x14,31︸ciphertext variables.
After these four steps, the polynomial setA in the term order <A is a Gröbner basis of the ideal A in ring R. The following will give the relevant properties and their theoretical proof.


### 5.2. The Properties of AES-256 Gröbner Basis

Gröbner basis is the standard notation of polynomial ideal, and there are two useful properties: (1) given a Gröbner basis of an ideal, it is effective to determine whether a polynomial belongs to the ideal; (2) for reasonable term order, the ideal type can be calculated effectively, and the polynomial equation systems deduced from these ideals can be solved. The polynomial setA contains 720 polynomials, where 384 polynomials are with the degree 254 and 336 are linear polynomials that contain 720 variables xi,j,ki,j,0≤i≤14,0≤j≤31. For polynomial set A, there are the following conclusions.Theorem 9.
The set of polynomialsA is a Gröbner basis relative to degree lexicographical order <A.Proof.
Relative to the term order<A, the head term set of polynomials in (21) is H1=k0,i:0≤i≤31, the head term set of polynomials in (22) is H2=x14,i:0≤i≤31, the head term set of polynomials in (23) and (24) is H3=xi,j254:0≤i≤13,0≤j≤31, and the head term set of polynomials in (26) is H4=ki,j254,ki,h:1≤i≤14,0≤j≤3,4≤h≤31, so the head term set of polynomials A is H=H1∪H2∪H3∪H4. Since, ∀a,b∈H,gcda,b=1, elements in H are pairwise prime. According to Theorem 6, it can be obtained that the set of polynomials A is a Gröbner basis relative to term order <A.Theorem9 indicates that the set of polynomials A is a Gröbner basis of ideal A in ring R. This provides the possibility of carrying out the ideal calculation of AES-256.Theorem 10.
The idealA generated by Gröbner basis A of AES-256 is zero-dimensional.Proof.
The variable set of the AES-256 equation system isV=xi,j,ki,j:0≤i≤14,0≤j≤31, so the number of variables is V=720. It can be seen from the proof process of Theorem 9 that the head term set of polynomials set A is H. ∀x∈V, there exists 1≤d≤254 satisfying xd∈H; that is, all variables are in the form of a certain number of times in H. Based on this, for any variable x, there exists a polynomial g∈A, so that HTg=xd. According to Theorem 7, it is obvious that dim⁡A=0; that is, the ideal A generated by the Gröbner basis A is zero-dimensional.Theorem10 points out that the Gröbner basis A constructed by this paper is zero-dimensional. Due to the term order conversion algorithm FGLM can convert any term order Gröbner basis of zero-dimensional ideal into lexicographical Gröbner basis, so the FGLM algorithm can convert degree lexicographical Gröbner basis A into lexicographical Gröbner basis. The construction of zero-dimensional Gröbner basis is helpful to simplify Gröbner basis calculation, which makes it possible to reduce the complexity of solving multivariate equation system.


### 5.3. The Algebraic Cryptanalysis Scheme and Its Complexity

The algebraic cryptanalysis algorithm of AES-256 is shown in Algorithm2.Algorithm 2:Algebraic cryptanalysis algorithm of AES-256.
(1)   list the equation system of AES-256 algorithm; (2)  select a known plaintext and ciphertext pair, and substitute it into the equation system; (3)  construct Gröbner basis Ggrelex of the ideal relative to degree lexicographical order using the method in Section5.1; (4)  judge the solution structure of the Gröbner basis. Because the equation system contains the field equation, the equation is finite or no solution. (5)if and only if Ggrelex = (1) then (6)   the equation system is no solution; (7)if it is no solution, then (8)    select another plaintext and ciphertext pair to return to Step (3); (9)else continue; (10)end if (11)end if (12) convert degree lexicographical Gröbner basis Ggrelex to lexicographical Gröbner basis Glex by using FGLM algorithm; (13) solve the key variables; (14) verify the correctness of key by applying plaintext, ciphertext and key to AES-256 algorithm; (15)return the key value;The maximum degree when computing the Gröbner basis is no more thanN, where N is the number of the unknown variables in the equation system, so the upper bound of complexity of computing Gröbner basis is O2N. Since the upper bound of the complexity of our scheme depends on the complexity of the Gröbner basis computation, the upper bound of the complexity of our scheme is O2N. It can be seen from [17] that the complexity of exhaustively solving the equation system is ON2N. It is obvious that the complexity of our scheme is less than the complexity of exhaustive attack, which indicates that our scheme is a successful attack scheme. Moreover, taking into account the sparse and overdefined features of AES-256 equation system, the actual complexity will be far less than the exhaustive attack.Not all equations are always true in the equation system. For anS-box, there is an equation whose true probability is 255/256. For the full AES-256, the true probability of this kind of equation is 1/9. It needs 9 plaintext and ciphertext pairs to conduct computation 9 times in Step 3, and the equation system will have a finite set of solutions.


## 5.1. The Gröbner Basis Construction Method of AES-256

The Gröbner basis of AES-256 is constructed as follows.Step 1.
The purpose of this step is to construct the polynomial set of theS-box and the inverseS-box. In this step, we make use of the algebraic expression of theS-box and the inverseS-box.
AESS-box is constructed based on evident mathematical theory, so it can be written in the form of an algebraic expression. The sparse algebraic expression of theS-box in F is as follows: (19)S:F⟶F,x⟼05xFE+09xFD+F9xFB+25xF7+F4xEF+B5xDF+B9xBF+8Fx7F+63.
The nonsparse algebraic expression of the inverseS-box contains 255 terms. The coefficients of the algebraic expression of AES inverseS-box are shown in Table 1. The abbreviated form of the algebraic expression of AES inverseS-box can be expressed as follows:(20)S-1:F⟶F,x⟼∑i=0254cixi,where ci is the coefficient of the term with degree i.Table 1
Coefficients of algebraic expression of AES inverseS-box (Hex).
C (mn) 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 52 F3 7E 1E 90 BB 2C 8A 1C 85 6D C0 B2 1B 40 23 1 F6 73 29 D9 39 21 CF 3D 9A 8A 2F CF 7B 04 E8 C8 2 85 7B 7C AF 86 2F 13 65 75 D3 6D D4 89 8E 65 05 3 EA 77 50 A3 C5 01 0B 46 BF A7 0C C7 8E F2 B1 CB 4 E5 E2 10 D1 05 B0 F5 86 E4 03 71 A6 56 03 9E 3E 5 19 18 52 16 B9 D3 38 D9 04 E3 72 6B BA E8 BF 9D 6 1D 5A 55 FF 71 E1 A8 8E FE A2 A7 1F DF B0 03 CB 7 08 53 6F B0 7F 87 8B 02 B1 92 81 27 40 2E 1A EE 8 10 CA 82 4F 09 AA C7 55 24 6C E2 58 BC E0 26 37 9 ED 8D 2A D5 ED 45 C3 EC 1C 3E 2A B3 9E B7 38 82 A 23 2D 87 EA DA 45 24 03 E7 C9 E3 D3 4E DD 11 4E B 81 91 91 59 A3 80 92 7E DB C4 20 EC DB 55 7F A8 C C1 64 AB 1B FD 60 05 13 2C A9 76 A5 1D 32 8E 1E D C0 65 CB 8B 93 E4 AE BE 5F 2C 3B D2 0F 9F 42 CC E 6C 80 68 43 09 23 C5 6D 1D 18 BD 5E 1B B4 85 49 F BC 0D 1F A6 6B D8 22 01 7A C0 55 16 B3 CF 05 00Step 2.
The purpose of this step is to construct the polynomial set of linear transformations (i.e., ShiftRow and MixColumn). In this step, we use the equation system given in Section4.
By (14), the plaintext equations, that is, the initial round equation system, can be obtained as (21), and the ciphertext equations can be obtained as (22). Hence,(21)x0,i+k0,i+pi=0,pi∈F,0≤i≤31,(22)x14,i+ci=0,ci∈F,0≤i≤31.
Sincex0,i and k0,i have the same degree, the head term of polynomials in (21) is x0,i or k0,i. If the selected term order is x0,i<k0,i, then the head term of polynomial is k0,i, 0≤i≤31. For (22), the head term of polynomial is x14,i, 0≤i≤31.
It is needed to improve (15) and (16) to meet the requirements of Gröbner basis. From (15), it is easy to get 24 polynomial equations of round i1≤i≤13 as shown in(23)Sxi-1,0Sxi-1,1⋮Sxi-1,31+M-1·xi,0+ki,0xi,1+ki,1⋮xi,31+ki,31=0.
Similarly, from (16), the 32 polynomial equations of the final round can be obtained as shown in(24)Sx13,0Sx13,1⋮Sx13,31+MSR-1·x14,0+k14,0x14,1+k14,1⋮x14,31+k14,31=0.
For degree lexicographical order, the head term of polynomial in (23) and (24) is xi,j254, 0≤i≤13, 0≤j≤31. It is easy to see that the head term has no nontrivial common factor; that is, the greatest common factor is 1.Step 3.
The purpose of this step is to construct the polynomial set of the key schedule algorithm. In this step, we also use the equation system given in Section4.
In order to get the polynomial Gröbner basis of the whole encryption algorithm, the equation system of the key schedule algorithm needs to be improved. It is easy to deduce (25) from (17). Hence,(25)ki,0ki,1ki,2ki,3ki,4ki,5⋮ki,31=ki-1,0ki-1,1ki-1,2ki-1,3ki-1,4ki-1,5⋮ki-1,31+Ski-1,29Ski-1,30Ski-1,31Ski-1,28ki,0ki,1⋮ki,27+ξi-100000⋮0.
In order to ensure that the head terms of key schedule polynomials are pairwise prime, applying the inverseS-box transformation to (25) is needed. The transformation results are shown in(26)S-1ki,0+ki-1,0+ξi-1S-1ki,1+ki-1,1S-1ki,2+ki-1,2S-1ki,3+ki-1,3ki,4+ki-1,4ki,5+ki-1,5⋮ki,31+ki-1,31+ki-1,29ki-1,30ki-1,31ki-1,28ki,0ki,1⋮ki,27=0.
According to the algebraic expression of the inverseS-box, all the equations included in (26) can be obtained. If the selected term order is (27)ki,31>ki,30>⋯>ki,0>ki-1,31>⋯>ki-1,1>ki-1,0,where 1≤i≤14, then the set of polynomial head terms of the key schedule equation (26) is(28)ki,j254,ki,h:1≤i≤14,0≤j≤3,4≤h≤31.
It is easy to see that the elements of the head term set have no nontrivial common factor.Step 4.
The purpose of this step is the reasonable selection of term order and variable order. If we choose a degree lexicographical order over reasonable variable order, we can make the polynomial head terms of the whole encryption algorithm pairwise prime.
The left-hand sides of (21), (22), (23), (24), and (26) constitute a set of polynomials denoted as A, and the degree lexicographical order <A over the following variable order makes the head terms of polynomials in A pairwise prime. Hence,(29)x0,0<⋯<x0,31︸initial round state variables<k0,0<⋯<k0,31︸initial key variable<k1,0<⋯<k1,31︸first round key variables<⋯<k14,0<⋯<k14,31︸last round key variables<x1,0<⋯<x1,31︸first round internal state variables<⋯<x13,0<⋯<x13,31︸11th round internal state variables<x14,0<⋯<x14,31︸ciphertext variables.
After these four steps, the polynomial setA in the term order <A is a Gröbner basis of the ideal A in ring R. The following will give the relevant properties and their theoretical proof.


## 5.2. The Properties of AES-256 Gröbner Basis

Gröbner basis is the standard notation of polynomial ideal, and there are two useful properties: (1) given a Gröbner basis of an ideal, it is effective to determine whether a polynomial belongs to the ideal; (2) for reasonable term order, the ideal type can be calculated effectively, and the polynomial equation systems deduced from these ideals can be solved. The polynomial setA contains 720 polynomials, where 384 polynomials are with the degree 254 and 336 are linear polynomials that contain 720 variables xi,j,ki,j,0≤i≤14,0≤j≤31. For polynomial set A, there are the following conclusions.Theorem 9.
The set of polynomialsA is a Gröbner basis relative to degree lexicographical order <A.Proof.
Relative to the term order<A, the head term set of polynomials in (21) is H1=k0,i:0≤i≤31, the head term set of polynomials in (22) is H2=x14,i:0≤i≤31, the head term set of polynomials in (23) and (24) is H3=xi,j254:0≤i≤13,0≤j≤31, and the head term set of polynomials in (26) is H4=ki,j254,ki,h:1≤i≤14,0≤j≤3,4≤h≤31, so the head term set of polynomials A is H=H1∪H2∪H3∪H4. Since, ∀a,b∈H,gcda,b=1, elements in H are pairwise prime. According to Theorem 6, it can be obtained that the set of polynomials A is a Gröbner basis relative to term order <A.Theorem9 indicates that the set of polynomials A is a Gröbner basis of ideal A in ring R. This provides the possibility of carrying out the ideal calculation of AES-256.Theorem 10.
The idealA generated by Gröbner basis A of AES-256 is zero-dimensional.Proof.
The variable set of the AES-256 equation system isV=xi,j,ki,j:0≤i≤14,0≤j≤31, so the number of variables is V=720. It can be seen from the proof process of Theorem 9 that the head term set of polynomials set A is H. ∀x∈V, there exists 1≤d≤254 satisfying xd∈H; that is, all variables are in the form of a certain number of times in H. Based on this, for any variable x, there exists a polynomial g∈A, so that HTg=xd. According to Theorem 7, it is obvious that dim⁡A=0; that is, the ideal A generated by the Gröbner basis A is zero-dimensional.Theorem10 points out that the Gröbner basis A constructed by this paper is zero-dimensional. Due to the term order conversion algorithm FGLM can convert any term order Gröbner basis of zero-dimensional ideal into lexicographical Gröbner basis, so the FGLM algorithm can convert degree lexicographical Gröbner basis A into lexicographical Gröbner basis. The construction of zero-dimensional Gröbner basis is helpful to simplify Gröbner basis calculation, which makes it possible to reduce the complexity of solving multivariate equation system.


## 5.3. The Algebraic Cryptanalysis Scheme and Its Complexity

The algebraic cryptanalysis algorithm of AES-256 is shown in Algorithm2.Algorithm 2:Algebraic cryptanalysis algorithm of AES-256.
(1)   list the equation system of AES-256 algorithm; (2)  select a known plaintext and ciphertext pair, and substitute it into the equation system; (3)  construct Gröbner basis Ggrelex of the ideal relative to degree lexicographical order using the method in Section5.1; (4)  judge the solution structure of the Gröbner basis. Because the equation system contains the field equation, the equation is finite or no solution. (5)if and only if Ggrelex = (1) then (6)   the equation system is no solution; (7)if it is no solution, then (8)    select another plaintext and ciphertext pair to return to Step (3); (9)else continue; (10)end if (11)end if (12) convert degree lexicographical Gröbner basis Ggrelex to lexicographical Gröbner basis Glex by using FGLM algorithm; (13) solve the key variables; (14) verify the correctness of key by applying plaintext, ciphertext and key to AES-256 algorithm; (15)return the key value;The maximum degree when computing the Gröbner basis is no more thanN, where N is the number of the unknown variables in the equation system, so the upper bound of complexity of computing Gröbner basis is O2N. Since the upper bound of the complexity of our scheme depends on the complexity of the Gröbner basis computation, the upper bound of the complexity of our scheme is O2N. It can be seen from [17] that the complexity of exhaustively solving the equation system is ON2N. It is obvious that the complexity of our scheme is less than the complexity of exhaustive attack, which indicates that our scheme is a successful attack scheme. Moreover, taking into account the sparse and overdefined features of AES-256 equation system, the actual complexity will be far less than the exhaustive attack.Not all equations are always true in the equation system. For anS-box, there is an equation whose true probability is 255/256. For the full AES-256, the true probability of this kind of equation is 1/9. It needs 9 plaintext and ciphertext pairs to conduct computation 9 times in Step 3, and the equation system will have a finite set of solutions.


## 6. Conclusions

Based on the characteristics of the round transformation in AES-256, the ShiftRow and MixColumn transformations are merged into left multiplication by a matrixM, making it in the form of linear transformation. In further research on AES-256, the linear transformation and multivariate equation system of AES-256 are further studied. The Gröbner basis is proposed and constructed by choosing reasonable term order and variable order. At the same time, we point out and prove that the Gröbner basis is zero-dimensional. Based on this, the Gröbner basis attack scheme is proposed, and the attack complexity is far lower than the brute force attack. Taking into account the fact that the complexity of our scheme is very high, our research results have a theoretical value. However, the discovery of the zero-dimensional Gröbner basis of AES-256 has guiding significance for further study on efficient Gröbner based attack scheme. The complexity of FGLM and the effectiveness of Gröbner basis attack still need to be further studied.



---

*Source: 9828967-2017-02-23.xml*