Algebraic Representation in AES Cryptanalysis

Representing a block cipher with a shorter algebraic expression does not mean that the cipher has been broken. A more compact representation moves the attack problem into a different equation space. The real difficulty is solving the resulting system within a computational cost that permits recovery of the key. This distinction is decisive in algebraic cryptanalysis of AES.

Between 2020 and 2022, I had the opportunity to work particularly with cryptanalyst engineer Bekir Ünlü, whose research focused on AES. Under his coordination, I took part in a cryptanalysis project conducted outside a university and participated in development of the associated software. This work allowed me to observe directly the difference between implementing a cryptographic algorithm and examining the same algorithm through its algebraic structure.

A study by Bekir Ünlü published in 2019 in IET Information Security proposes a combined expression of the AES S-box through the multiplicative inverse of the input, selected bits, and finite-field elements. The paper examines whether this representation can provide new transformation paths for algebraic cryptanalysis. It was published on May 1, 2019, with DOI 10.1049/iet-ifs.2018.5051.

The algebraic structure of AES

AES is a block cipher operating on a 128-bit state and using 10, 12, or 14 rounds depending on key length. In AES-128, each normal round consists of the SubBytes, ShiftRows, MixColumns, and AddRoundKey transformations. MixColumns is omitted from the final round.

Three of these transformations are relatively regular from an algebraic perspective. ShiftRows is a permutation. MixColumns is multiplication by a fixed matrix over GF(2^8). AddRoundKey corresponds to bitwise XOR. The principal component complicating algebraic analysis is the nonlinear S-box transformation in SubBytes.

Each AES byte is interpreted as an element of the finite field with 256 elements. Addition is XOR. The polynomial resulting from multiplication is reduced modulo the polynomial defined by the AES standard:

m(x) = x^8 + x^4 + x^3 + x + 1

Every nonzero field element has a unique multiplicative inverse in this structure. The AES S-box takes the multiplicative inverse of the input byte in GF(2^8) and then applies an affine transformation to its bits. The zero input is specially mapped to zero before the same affine transformation is applied.

Because the S-box is nonlinear, it determines the algebraic degree and equation structure of AES. The remaining parts of the cipher can be expressed directly as finite-field equations when intermediate-state bytes are treated as variables. A central question in algebraic cryptanalysis is therefore:

Can the S-box be represented in another form that makes the equation system easier to solve?

Ünlü's study directs this question not only to one AES round, but to the combined system formed by the encryption process and key expansion. The paper defines intermediate-state variables through a three-round example. For the complete ten-round AES-128, it presents a system of 336 equations over GF(2^8) covering encryption and key-schedule variables. The system contains 200 separate S-box uses.

The equality of equation and variable counts does not show that the system is practically solvable. Equation degree, dependencies, number of terms, and memory requirements of the solving algorithm are decisive. The difficulty of algebraic cryptanalysis often comes not from generating equations, but from determining whether the generated system has a structure that can be solved.

Combined representation of the S-box

The main contribution of the paper is that it does not treat the S-box transformation only as a high-degree polynomial or only as bit-based quadratic equations. It combines byte, bit, and multiplicative-inverse information within the same expression.

Let X be the S-box input and Y = X^-1 its multiplicative inverse in GF(2^8). Let y_7, y_6, y_5, and y_4 denote the upper four bits of Y. The combined representation proposed in the paper is:

S(X) = "1F" * X^-1

• "96" * y_7
• "46" * y_6
• "2E" * y_5
• "1A" * y_4
• "63"

The hexadecimal constants are elements of GF(2^8). The y_i values are elements of GF(2). Addition and multiplication follow the rules of the relevant finite fields rather than ordinary integer arithmetic.

The interesting property of this expression is that it preserves the nonlinear core of the S-box directly through the X^-1 term while representing the remaining affine structure with only four bits and constant field elements. The term "combined" in the paper refers to the presence of these different representation levels in one equation.

In the classical representation, each S-box output bit can be expressed in algebraic normal form over the input bits. Alternatively, the relation between input and output can be modeled through multivariate quadratic equations. The combined representation does not simply replace these approaches. It opens additional paths for deriving equations.

The paper states that this representation can produce, with probability 1, either 23 bi-affine equations in 81 terms or 39 fully quadratic equations in 137 terms. The same section states that, under the algebraic-complexity measure being used, the number of terms in the S-box representation decreases from 9 to 6.

The values 9 and 6 do not represent AES security bits. They concern term counts in particular algebraic representations. An S-box expression with fewer terms does not prove that the complete AES equation system becomes proportionally easier to solve. As the system grows, intermediate variables, equation dependencies, and interactions among inverse functions create separate complexity.

The work uses the combined representation not only for local S-box analysis. It proposes applying finite-field operations externally to the complete set of equations. The two methods examined are:

• Multiplying each equation by a selected element of GF(2^8)
• Applying the field-trace operation to the equation system

In the first method, equations are multiplied by the hexadecimal field element FD. This transformation aims to reduce four residual bits into unknowns represented as half-bytes. A method capable of resolving the interaction among these new unknowns is still required. The paper itself states that the complexity estimate for the complete ten-round system depends on the assumption that the transformed system can be solved.

Transformation with the field trace

The field trace is a linear function mapping an element of GF(2^8) to an element of GF(2):

Tr(a) = a + a^2 + a^4 + a^8

• a^16 + a^32 + a^64 + a^128

The result can only be 0 or 1. The field trace is linear over addition:

Tr(a + b) = Tr(a) + Tr(b)

This property allows terms in a large finite-field equation to be moved into the bit field. The paper first derives the trace of the basic S-box expression. The initial transformation, however, leaves the y_7 and y_5 bits. It then proposes an extended transformation that multiplies the S-box output by suitable field elements before taking the trace, eliminating the residual bits.

For example, when the field element C8 is used, the paper obtains:

Tr("C8" S(X)) = Tr("60" X^-1)

Under the trace, the four residual bits and constant term in the S-box expression disappear. The paper identifies other field elements with the same property.

The idea is not to invert the S-box directly. It is to transform every AES equation containing an S-box into another equation involving only multiplicative inverses and constants under the field trace. The attack problem is thereby moved into a different algebraic structure.

This transformation loses information. A byte in GF(2^8) is reduced to one bit by the field trace. One trace equation cannot determine the original byte value. The amount of information jointly carried by trace relations produced with different multipliers, and how this information propagates to key variables, must be studied separately. This is the main problem left open by the paper.

Boundary of the reduced-round attack

The concrete attack improvement in the study targets a six-round reduced version rather than full AES-128. The combined inverse-S-box representation is used to add information to an intermediate-state check in the Partial Sum Attack.

According to the calculations in the paper, the classical method eliminates incorrect key guesses at a ratio of 255/256 for one delta set, while the new check has an expected elimination ratio of 287/288. This difference reduces chosen-plaintext data complexity for determining five key bytes from:

6 * 2^32

to:

5 * 2^32

Time complexity remains approximately 2^44.

This improvement is significant, but its scope must be read correctly. The result concerns six-round AES-128. Standard AES-128 uses ten rounds. Reduced-round attacks are valuable for understanding security margins and structural properties of a cipher. They are not necessarily practical key-recovery attacks against the full version.

The paper explicitly accepts this boundary. Its conclusion states that the work does not define an attack on full AES, that the proposed methods depend on the solvability of a large system of multiplicative-inverse equations, and that further experiments are needed on small-scale AES derivatives. The relationship between variables in the system obtained by field tracing and the actual AES key variables is also identified as an open research problem.

This distinction is important in the language of cryptanalysis. A new representation can broaden the attack surface. New equations can provide more structure to a solver. A complete attack, however, requires extracting the key from this structure within practical time and memory costs.

Developing cryptanalysis software

Software development in this field requires a different way of thinking from writing AES encryption code. In a normal AES implementation, the relation among the correct key, plaintext, and ciphertext is known. Correctness can be verified with standard test vectors. In cryptanalysis software, intermediate variables are unknown. The objective is to generate, simplify, and transform relations among these unknowns into a form that solving tools can process.

Correct bit-level implementation of finite-field arithmetic is the first requirement. Although addition in GF(2^8) is XOR, multiplication is not ordinary byte multiplication. Polynomial reduction, inversion, squaring, and field trace must all use the same field definition. An error in bit order or hexadecimal representation can invalidate the entire equation system.

Each layer of the software should be verified independently:

1. Finite-field addition and multiplication
2. Multiplicative-inverse calculation
3. S-box and inverse-S-box generation
4. Affine transformation
5. Validation of the combined representation for all 256 inputs
6. Equation generation
7. Equation dependency and rank analysis
8. Reduced-round models
9. Measurement of attack complexity

The combined representation should not be validated with only a few sample values. Because the S-box input space contains 256 values, it can be exhaustively tested. The standard S-box output and the combined formula can be compared for every input. The same method can be applied to the inverse S-box.

Variable naming and round indices in equation generation must be deterministic. The same model should produce the same variable order and equation set in every execution. Otherwise, reliable comparison of rank, term counts, or solving time across two experiments becomes difficult.

Programming in this work did not mean only encoding mathematical formulas. Growth in equation count directly affected memory layout, data structures, and file formats. Storing sparse polynomials in dense matrices can exhaust memory before the solver is reached. Monomials must be maintained in canonical order, identical terms combined, and zero coefficients removed early.

A false improvement in cryptanalysis software is more dangerous than obtaining no result. A missing equation, incorrect field operation, or erroneous independence calculation can create an attack advantage that does not exist. It is therefore preferable that experimental code and validation code not share the same algorithm. Agreement between two independent implementations provides stronger evidence.

Cryptanalysis as a representation problem

My work with Bekir Ünlü showed that cryptanalysis is not merely a matter of using high computational power to search for a key. The variables and algebraic space chosen to express an algorithm change the attack methods that can be applied.

The same S-box can be represented as a table, a high-degree polynomial, a bit-level algebraic normal form, a quadratic equation system, or a combined expression containing a multiplicative inverse. Each representation defines the same function. Their equation counts, degrees, sparsity properties, and compatibility with solvers differ.

Ünlü's study does not claim that AES has been broken. It provides a narrower technical contribution. It constructs an alternative algebraic representation of the S-box, derives new equations through that representation, and proposes two transformations that can be applied to the complete AES system. It also demonstrates a measurable data-complexity improvement in a reduced-round attack.

For me, the lasting effect of this period was a change in how I viewed cryptographic software development. Application security requires correct implementation of the standard. Cryptanalysis requires reconstructing the algebraic structure behind the standard. The first problem demands a deterministic implementation. The second aims to represent the same function in a more explanatory and potentially solvable form.

Engineering discipline is decisive where these fields intersect. Mathematical equalities must be verified at bit level, experiments must be reproducible, and computational bounds must be reported explicitly. Only then can the distance between an algebraic simplification and a practical attack be measured correctly.

References

Unlu, B. (2019). Base for algebraic cryptanalysis based on combined representation of S-box. IET Information Security, 13, 249-257. DOI: 10.1049/iet-ifs.2018.5051.

National Institute of Standards and Technology. (2023). Advanced Encryption Standard. FIPS 197-upd1.