Introduction
In the field of cryptanalysis, "guess-and-determine" attacks represent a classic strategy: an attacker guesses the values of a small subset of secret variables and then employs an efficient algorithm to determine if the remaining variables can be uniquely identified. If the guess is incorrect, the process repeats. While powerful, these attacks have traditionally required significant manual effort from human experts to identify the optimal variables for guessing.
This paper introduces Inverse Backdoor Sets (IBS), a novel framework that leverages Boolean Satisfiability (SAT) solvers to automate and optimize these attacks. By statistically estimating a cipher's resistance to such methods, the authors demonstrate improved attack complexities on weakened versions of the Trivium, AES, and Magma encryption algorithms.
The Inverse Backdoor Set Framework
The authors propose three major technical contributions to formalize and automate SAT-based cryptanalysis:
- Inverse Backdoor Sets (IBS): Traditional "Strong Backdoors" require sub-problems to be solvable by simple, polynomial-time algorithms like Unit Propagation. In contrast, IBS allows the use of state-of-the-art Conflict-Driven Clause Learning (CDCL) solvers. Crucially, an IBS is designed to be effective for any output of a function, transforming it into a general-purpose attack tool rather than a message-specific solution.
- The Resistance Function: To evaluate the quality of a backdoor set, the authors define a "resistance function." Using Monte Carlo sampling, they estimate the probability that a SAT solver can crack a sub-problem within a specific time limit ($t$). This allows for the statistical prediction of total attack time without executing the full exponential-time search.
- Automated Search via Tabu Search: Identifying the optimal subset of variables to guess is a massive combinatorial challenge. The researchers utilize a Tabu search algorithm to navigate the Boolean hypercube of input variables, minimizing the resistance function to "evolve" the most efficient attack configuration.
Experimental Evaluation
The approach was evaluated on three prominent symmetric ciphers, converted into Conjunctive Normal Form (CNF) using the Transalg tool:
- Trivium: A stream cipher from the eSTREAM portfolio; the task involved recovering the 288-bit initial state from a 300-bit keystream.
- AES-128: The industry standard; tested on a reduced 2.5-round version.
- Magma (GOST 28147-89): A 32-round block cipher; tested on an 8-round variant.
Experiments were conducted using the ROKK SAT solver to measure the time required to solve the resulting sub-problems.
Results
The automated IBS approach produced competitive or state-of-the-art results for the targeted cipher variants. Notably, for Magma (8 rounds), the IBS approach achieved an estimated attack time of $3.55 \times 10^{22}$ seconds, outperforming the previous best-known attack (PBA) of $1.17 \times 10^{23}$ seconds. For AES-128 (2.5 rounds), the search identified an IBS of size 42 with an estimated attack time of $1.45 \times 10^{15}$ seconds.
As shown in the table above, the IBS method maintains "negligible" memory requirements compared to some algebraic attacks that require massive precomputed tables. While the specialized "Characteristic Set" method remains superior for Trivium, the IBS approach provided a significantly more efficient general-purpose attack ($2.04 \times 10^{41}$s) than prior automated attempts ($4.31 \times 10^{55}$s).
Conclusion and Future Work
The paper successfully bridges the gap between SAT backdoors and manual cryptanalysis, providing a rigorous mathematical framework for automated guess-and-determine attacks. A key insight is that statistical extrapolation from a few thousand random guesses can accurately predict total attack complexity.
Future research directions include expanding the search space to include "auxiliary variables" (internal cipher states) and developing deterministic measures of complexity to replace time-based resistance, which can be sensitive to specific hardware and solver implementations.
Summary updated