💻 computer science

A Novel Memory-Efficient MitM Attack on Ascon-Hash

This paper proposes a novel memory-efficient Meet-in-the-Middle attack on round-reduced Ascon-Hash that leverages SAT modeling, Gaussian elimination, and triangulation to significantly reduce memory complexity while maintaining the best-known time complexities.

Original authors: Zhiguo Wu, Bo Gao, Jianxiong Wan, Chuyi Liu, Xiaodong Zhang

Published 2026-08-31

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhiguo Wu, Bo Gao, Jianxiong Wan, Chuyi Liu, Xiaodong Zhang

Original paper licensed under CC BY 4.0 (https://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

In the digital world, security often relies on a delicate balance between strength and efficiency. For the billions of tiny, battery-powered devices that make up the Internet of Things—sensors in factories, smart meters, and medical monitors—computing power is scarce, and memory is even scarcer. These devices need cryptographic tools that are robust enough to keep data safe but light enough to run without draining a battery or filling up a tiny chip. Ascon is a leading solution for this challenge, a family of encryption and hashing methods designed specifically for these resource-constrained environments. To ensure Ascon remains safe, researchers constantly test it against sophisticated attacks, trying to find the shortest path to break its code. One of the most powerful tools in this arsenal is the "meet-in-the-middle" attack, a strategy where an attacker works backward from the final result and forward from the starting point, hoping to meet in the middle with a match. However, this strategy has traditionally required a massive amount of memory to store the millions of intermediate steps, a requirement that often made the attack impractical for the very devices Ascon is meant to protect.

A team of researchers has now developed a new way to execute this attack that drastically cuts down the memory needed, making the test far more realistic for lightweight systems. In a study focused on the Ascon-Hash function, the authors demonstrated that they could perform the attack on a reduced version of the system using significantly less storage space than previously thought possible, without sacrificing the speed of the calculation. By treating the problem as a complex puzzle of logical constraints, they found a way to filter out unnecessary data before it ever needed to be stored. Their work shows that for a three-round version of the hash, the memory required can be reduced from a complexity of 2^24 down to 2^14. For a four-round version, the reduction is even more dramatic, dropping the requirement from a complexity of 2^34 to 2^12. This achievement does not just lower the cost of the attack; it provides a sharper, more accurate picture of how secure Ascon truly is when facing an adversary with limited resources.

The researchers began by acknowledging that previous attempts to break Ascon using automated search tools had hit a wall of memory usage. While computers had become faster at finding the right path through the encryption, the process still demanded that the attacker keep a vast library of intermediate results in memory, much like trying to solve a maze by writing down every single turn you take on a separate piece of paper. If the maze is large enough, you run out of paper long before you find the exit. The team realized that the key to solving this was not just finding the path faster, but being smarter about what they wrote down. They used a method called satisfiability solving, which is essentially a way of asking a computer to find a set of conditions that makes a complex logical statement true. This allowed them to map out the specific points in the encryption process where the forward and backward calculations could potentially meet.

Once they had mapped out these potential meeting points, the researchers applied a series of algebraic filters to clean up the data. They noticed that many of the constraints governing the encryption could be separated into simple, linear relationships and more complex, nonlinear ones. The linear parts were straightforward; they could be simplified using standard mathematical techniques to remove redundant information, effectively shrinking the list of possibilities the computer had to track. The nonlinear parts were trickier, but the team developed a method to rearrange them into a triangular shape, allowing them to solve for certain variables based on others. This process eliminated the need to explicitly calculate and store those specific variables, further reducing the memory footprint.

The most significant innovation came in how they handled the remaining complex constraints that could not be easily simplified. Instead of storing every possible outcome, the researchers used these remaining constraints to create a "residual index," a kind of digital tag or label. As they generated the list of potential forward paths, they assigned each one a tag based on its specific properties. Crucially, they realized that the backward path could only match with a forward path if their tags were compatible. This meant that the computer did not need to keep every single forward path in memory; it only needed to keep the ones that carried a tag that the backward path could possibly reach. In the specific configurations they tested, this filtering was so effective that it reduced the entire list of necessary forward paths to a single, tiny bucket of data.

The results of this new approach were striking. When applied to a three-round version of Ascon-Hash, the method maintained the same speed as previous attacks but reduced the memory requirement from a complexity of 2^24 to 2^14. For the four-round version, the reduction was even more profound, cutting the memory need from a complexity of 2^34 to 2^12 compared to the previous best method. The researchers verified that this aggressive filtering did not accidentally discard valid solutions; they checked that the remaining data still satisfied all the original rules of the encryption system. The study confirms that by carefully analyzing the structure of the encryption and applying these logical filters, it is possible to perform deep security tests with a fraction of the resources previously thought necessary. This work suggests that the security margin of Ascon in resource-limited environments is being evaluated with greater precision, ensuring that the cryptographic standards protecting our connected world are as robust as they appear.

Technical Summary: A Novel Memory-Efficient MitM Attack on Ascon-Hash

Problem Statement
Ascon is a lightweight cryptographic standard selected by NIST and standardized in SP 800-232, specifically designed for resource-constrained environments such as the Internet of Things (IoT). In these settings, memory is often a more critical constraint than computation. While Meet-in-the-Middle (MitM) attacks are a primary tool for evaluating the preimage resistance of reduced-round Ascon, existing automated approaches face significant memory bottlenecks. Previous SAT-based frameworks, such as the one proposed by Degré et al., successfully reduced time complexity but still required substantial memory (e.g., $2^{34}$ for 4-round Ascon-Hash) to store intermediate values in hash tables during the online phase. This paper addresses the challenge of minimizing the total memory usage of MitM attacks on Ascon-Hash while preserving the best-known time complexities.

Methodology
The authors propose a novel framework that builds upon SAT-based MitM search but introduces a post-processing algebraic refinement stage to drastically reduce the size of the stored RED-side table. The methodology proceeds in the following steps:

SAT-Based Configuration Search: The process begins by using a SAT solver to identify valid MitM configurations (defining RED-side variables, BLUE-side variables, matching positions, and cancellation positions) that achieve a target time exponent.
Algebraic Separation: For each time-optimal configuration found, the induced cancellation relations are reconstructed and separated into linear and nonlinear parts based on their algebraic forms.
Linear Reduction: Linear cancellation relations (XOR constraints) are extracted and reduced using Gaussian elimination over GF(2). The rank of this linear system determines the reduction in the number of free RED-side variables.
Triangulation of Nonlinear Relations: Nonlinear cancellation relations are processed using a triangulation algorithm over Boolean polynomials. This step attempts to express certain RED-side variables as functions of others, effectively eliminating them from explicit enumeration.
Residual-Index Filtering: For nonlinear relations that cannot be eliminated via triangulation, the authors define a "residual index." This index partitions the RED-side assignments into buckets. During the attack, only RED buckets whose indices are consistent with the values computable from the BLUE side are retained. This filtering step discards incompatible RED assignments before the final matching phase.
Compatibility Verification: The authors verify that the filtering process does not alter the solution set of the matching equations. They prove that if the mixed RED-BLUE monomials in the matching expressions vanish on the retained domain, the separable join used in the MitM attack remains equivalent to solving the full matching equations.

Key Contributions

Memory Optimization Framework: The paper introduces a systematic method to refine SAT-derived MitM configurations by algebraically processing cancellation relations, specifically targeting the reduction of online memory complexity.
Triangulation and Filtering: The integration of Boolean polynomial triangulation and residual-index filtering allows for the elimination of variables and the pruning of the search space without increasing time complexity.
Validation of Separability: The work provides a formal check (Proposition 1) ensuring that the memory reduction techniques do not compromise the correctness of the MitM attack by verifying the vanishing of mixed terms on the retained domain.

Experimental Results
The authors evaluated their method on 3-round and 4-round Ascon-Hash, comparing their results against the SAT-based baseline by Degré et al. [1].

3-Round Ascon-Hash:
- Time Complexity: Preserved at $2^{114}$ .
- Memory Complexity: Reduced from $2^{24}$ (baseline) to $2^{14}$ .
- Mechanism: The configuration utilized 14 RED variables. After linear rank reduction (rank 1) and residual-index filtering (retaining only the zero-index bucket), the retained RED table size was reduced to $2^7$ in the symmetry-reduced model, corresponding to $2^{14}$ in the full setting.
4-Round Ascon-Hash:
- Time Complexity: Preserved at $2^{124}$ .
- Memory Complexity: Reduced from $2^{34}$ (baseline) to $2^{12}$ .
- Mechanism: The configuration utilized 38 RED variables. Triangulation eliminated 5 variables, and residual-index filtering further reduced the retained table. The final memory complexity in the full 64-column setting was $2^{12}$ .

Table 1 in the paper summarizes these improvements, showing a consistent reduction in memory exponents while maintaining the time exponents of the previous state-of-the-art.

Significance and Claims
The paper claims that its primary significance lies in providing a more precise evaluation of the reduced-round security margin of Ascon in the context of memory-constrained environments. Since Ascon is designed for IoT and embedded systems where memory is scarce, demonstrating that MitM attacks can be executed with significantly lower memory requirements (e.g., reducing from $2^{34}$ to $2^{12}$ for 4 rounds) is crucial for accurate security assessment.

The authors state that their framework demonstrates that beyond finding time-optimal configurations, further algebraic processing of cancellation relations can effectively reduce online storage requirements. They do not claim to break the full Ascon standard but rather to refine the analysis of its reduced-round variants. The work suggests that future research could extend this approach to more rounds, other Ascon modes, and other sponge-based lightweight primitives.

Technical Summary: A Novel Memory-Efficient MitM Attack on Ascon-Hash

More like this