💻 computer science

Analyzing Linear Layers in Related-Differential Cryptanalysis

This paper systematically investigates the existence of related-differential structures in linear layers of AES-like ciphers, proving that such vulnerabilities are unavoidable for all non-MDS matrices, all odd-order symmetric MDS matrices, and most circulant matrices, while providing a complete characterization for $3 \times 3$ MDS matrices over $\mathbb{F}_{2^m}$ .

Original authors: Yogesh Kumar, Akshay Ankush Yadav, Susanta Samanta

Published 2026-05-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yogesh Kumar, Akshay Ankush Yadav, Susanta Samanta

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are building a high-security vault (a digital lock) to protect your secrets. To make sure no one can crack it, you use a special mixing machine called a Linear Layer. This machine takes your data, scrambles it, and spreads it out so that a tiny change in the input creates a huge, chaotic change in the output. This is called "diffusion."

For decades, cryptographers have used a specific type of mixing machine called an MDS Matrix because it is the "gold standard" for spreading things out perfectly. They thought, "If we use an MDS matrix, we are safe."

However, this paper reveals a hidden flaw in that thinking. It turns out that even if your mixing machine is the "gold standard" (MDS), it might still have a secret weakness called Related Differentials.

Here is the breakdown of what the authors discovered, using simple analogies:

1. The "Gold Standard" isn't Enough

Think of the MDS property as a guarantee that your mixing machine spreads a drop of ink across a whole page of paper.

The Old Belief: If the machine spreads the ink perfectly (MDS), it's secure.
The New Discovery: The authors proved that if a machine doesn't spread the ink perfectly (Non-MDS), it is guaranteed to have a secret weakness.
The Analogy: Imagine trying to hide a secret message in a room. If the room is small and cluttered (Non-MDS), a thief can easily find a pattern to sneak in. The authors proved that only a perfectly spacious, organized room (MDS) has a chance of being safe. But just having the spacious room doesn't guarantee safety; the room's shape matters too.

2. The "Symmetry Trap"

Many mixing machines are built to be Symmetric, meaning they look the same if you flip them over (like a butterfly). This is popular because it's easy to build.

The Discovery: The authors found that if a symmetric machine has an odd number of parts (like 3x3 or 5x5), it is always vulnerable.
The Analogy: Imagine a dance floor with an odd number of dancers. No matter how they try to pair up, one dancer is always left standing in the middle, creating a predictable pattern. The authors proved that for any odd-sized, symmetric machine, there is always a "leftover" pattern that a hacker can exploit. It doesn't matter how well you built it; the odd number makes it inherently weak against this specific type of attack.

3. The "Circular Pattern" Problem

Another popular design is the Circulant Matrix. Imagine a conveyor belt where the pattern of gears repeats in a circle. This is efficient and fast.

The Discovery: The authors looked at these circular machines and found a rule based on their size (called $n$ $n$ ).
- If the size of the circle is a multiple of 3 (like 3, 6, 9) or a multiple of 4 (like 4, 8, 12), it is vulnerable.
- In fact, they proved that unless the size is a very specific number (specifically, numbers that are not 2 or 10 away from a multiple of 12), the machine is vulnerable.
The Analogy: Think of a clock face. If you try to walk around the clock in steps of 3 or 4, you will eventually hit the same spots over and over in a predictable way. The authors showed that for most circular designs, a hacker can find a "shortcut" through the gears that bypasses the security.

4. The "Perfect Recipe" for 3x3 Machines

Finally, the authors focused on the smallest, most common size: 3x3 matrices.

The Problem: Previous attempts to find a "safe" 3x3 machine were incomplete. They gave a recipe that missed some ingredients.
The Solution: The authors wrote down a complete recipe consisting of 15 specific rules (mathematical equations).
The Analogy: Imagine baking a cake. Previous chefs said, "Don't use salt." The authors said, "Actually, you must avoid salt, sugar, flour, eggs, milk, and 11 other specific ingredients in exact combinations." They provided a checklist of 15 things to avoid. If your 3x3 machine follows all 15 rules, it is safe. If it breaks even one, it is vulnerable.
The Result: They counted how many 3x3 machines exist and how many are actually safe. They found that the "safe" ones are much rarer than we thought.

Summary of the Takeaway

This paper is like a safety inspector for digital locks. They told us:

Non-MDS machines are definitely unsafe. (You must use MDS).
Odd-sized Symmetric machines are definitely unsafe. (Don't use odd numbers if you want symmetry).
Most Circular machines are unsafe. (Unless the size is very specific).
For 3x3 machines, here is the exact checklist to ensure you aren't building a weak lock.

The authors didn't invent a new lock; they just gave us a better way to check if the locks we are already building have hidden cracks.

Technical Summary: Analyzing Linear Layers in Related-Differential Cryptanalysis

Problem Statement
In SPN-based block ciphers (e.g., AES), the linear diffusion layer is typically instantiated using Maximum Distance Separable (MDS) matrices to ensure optimal branch numbers and resistance against classical differential and linear cryptanalysis. However, recent work by Daemen and Rijmen (2009) and Bardeh and Rijmen (2022) revealed that MDS matrices can still exhibit "related-differential" structures. These structures allow for the construction of related-differential characteristics that can be exploited in attacks, such as the 7-round key-recovery attack on AES-128. While previous studies have identified related differentials in specific instances (e.g., 4×4 circulant matrices, 3×3 involutory matrices), a systematic understanding of which linear layer structures inherently avoid or admit these differentials remains incomplete. This paper investigates the conditions under which linear layers over finite fields avoid related differentials, aiming to identify matrix classes that are inherently resistant to this specific cryptanalytic vector.

Methodology
The authors employ a theoretical algebraic approach over finite fields of characteristic 2 ( $\mathbb{F}_{2^m}$ ). The methodology involves:

Defining Related Differentials: Utilizing the definitions from Daemen and Rijmen, where two differentials $(u, Mu)$ and $(v, Mv)$ are "related" if the input pair $(u, v)$ and output pair $(Mu, Mv)$ satisfy the condition $x_i \cdot y_i \cdot (x_i \oplus y_i) = 0$ for all coordinates.
Structural Analysis: Investigating the relationship between matrix properties (MDS status, symmetry, circulant structure) and the existence of nontrivial related differential pairs.
Polynomial Decomposition: For circulant matrices, the authors map the matrix operations to polynomial multiplication in the quotient ring $\mathbb{F}_{2^m}[X]/\langle X^n - 1 \rangle$ . They decompose the transformation polynomial based on modular arithmetic of exponents (modulo 2, 3, and 4) to construct specific input difference pairs that yield related output differences.
Case-by-Case Enumeration: For the $3 \times 3$ case, the authors utilize the decomposition of any MDS matrix into a representative form $M = D_1 M_1 D_2$ (where $D_i$ are diagonal and $M_1$ is a specific representative). They systematically analyze all possible Hamming weight patterns of input difference triplets $(u, v, u \oplus v)$ to derive necessary and sufficient algebraic conditions for the absence of related differentials.

Key Contributions and Results

Necessity of the MDS Property:
The paper proves that the MDS property is a necessary condition for avoiding related differentials. Specifically, Theorem 2 demonstrates that every non-MDS matrix admits at least one nontrivial pair of related differentials. This narrows the search space for resistant linear layers strictly to the class of MDS matrices.
Vulnerability of Symmetric Matrices:
The authors establish that symmetry in odd dimensions is an inherent vulnerability. Theorem 4 proves that every odd-order symmetric MDS matrix admits related differentials. This result rules out broad families of constructions, including Type 2 Cauchy-based MDS matrices and left-circulant matrices of odd order (Corollaries 2 and 3), as they are inherently symmetric and thus vulnerable.
Vulnerability of Circulant Matrices:
The paper provides a comprehensive characterization for circulant matrices. By analyzing the modular properties of the matrix order $n$ , the authors prove in Theorem 5 that a circulant MDS matrix of order $n$ admits related differentials whenever $n \not\equiv \pm 2 \pmod{12}$ . This generalizes previous findings for $3 \times 3$ and $4 \times 4$ cases, identifying a broad class of vulnerable orders.
Complete Characterization of $3 \times 3$ Matrices:
Revisiting the $3 \times 3$ case, the authors derive a complete algebraic characterization. Theorem 7 provides an explicit set of 15 necessary and sufficient polynomial constraints on the parameters of a representative $3 \times 3$ MDS matrix. If any of these 15 conditions are met, the matrix admits related differentials; if none are met, the matrix is resistant.
- The paper notes that previous characterizations (e.g., by Otal et al.) were incomplete.
- Using this characterization, the authors compute the exact number of $3 \times 3$ MDS matrices over various finite fields ( $\mathbb{F}_{2^m}$ ) that possess no related differentials, demonstrating that the set of resistant matrices is a strict subset of all MDS matrices (Table I).

Significance and Claims
The paper claims to provide a systematic investigation into the structural prerequisites for resisting related-differential cryptanalysis. Its primary significance lies in:

Establishing Limits: Proving that the MDS property alone is insufficient for resistance and that specific structural properties (odd-order symmetry, specific circulant orders) guarantee vulnerability.
Refining Design Criteria: Offering a concrete, verifiable set of 15 algebraic constraints for $3 \times 3$ matrices, enabling designers to exhaustively verify or construct resistant matrices in this dimension.
Guiding Future Construction: By identifying that non-MDS matrices are inherently vulnerable and that many common symmetric constructions fail, the work directs future research toward constructing MDS matrices that are both asymmetric (or even-order symmetric) and satisfy the specific algebraic constraints derived for resistance.

The authors conclude that while the $3 \times 3$ case is fully characterized, extending these results to $4 \times 4$ matrices and constructing lightweight, efficient MDS matrices without related differentials remain open challenges. They also note that the unresolved cases for circulant matrices (where $n \equiv \pm 2 \pmod{12}$ ) present a conjecture for future proof.