SAT and SMT Solvers for Automated Cryptanalysis

21 concepts14 papers2 proposals

Cryptographic algorithms are designed to behave like mathematical black boxes, transforming plaintexts into seemingly random ciphertexts. To achieve this, they rely on the principles of "confusion" (making the relationship between the key and ciphertext complex) and "diffusion" (spreading the influence of single bits across the entire state). However, beneath this superficial chaos, every symmetric cipher, hash function, or authenticated encryption scheme is a deterministic circuit of simple logical operations: XORs, ANDs, ORs, and bit shifts.

If we treat these operations not as a sequential program to execute, but as a static network of logical assertions, cryptanalysis undergoes a fundamental shift. Instead of guessing keys and running a cipher forward, we can frame key recovery or collision finding as a constraint satisfaction problem. By fixing the input (plaintext) and output (ciphertext) variables, the secret key bits become the unknown variables in a massive system of Boolean equations. Finding the key is then equivalent to finding a satisfying assignment for this system—a task perfectly suited for modern Boolean Satisfiability (SAT) and Satisfiability Modulo Theories (SMT) solvers.

From Logic Gates to Conjunctive Normal Form

To hand a cryptographic problem to a SAT solver, the cipher's internal mechanics must be translated into Conjunctive Normal Form (CNF)—a product of clauses where every clause must evaluate to true.

This methodology dates back to early foundational experiments in automated reasoning. Fabio Massacci demonstrated that the Data Encryption Standard (DES) could be entirely mapped into propositional logic formulas, converting its complex internal rounds, substitutions, and permutations into a massive SAT instance (Using Walk-SAT and Rel-Sat for Cryptographic Key Search; Using Walk-SAT and RelAT for Cryptographic Key).

In a modern encoding pipeline, as described by Ashutosh Dhar Dwivedi et al., every wire in a cipher's circuit represents a Boolean variable. Linear operations like XOR gates are straightforwardly expanded into CNF clauses. Non-linear components, such as substitution boxes (S-boxes), are converted into truth tables and minimized into equivalent logic gate representations before being written out as CNF constraints. Once the entire cipher structure is encoded, providing a known plaintext-ciphertext pair binds the input and output variables, leaving the solver to navigate the internal state variables and isolate the master key.

[Plaintext Bits (Fixed)] + [Ciphertext Bits (Fixed)]
                       │
                       ▼
         ┌───────────────────────────┐
         │  CNF Constraint Formula   │ ──► [SAT Solver] ──► [Secret Key Bits]
         │ (S-Boxes, XORs, Rounds)   │
         └───────────────────────────┘

Why Solvers Succeed: Sparsity and Structure

If cryptography is mathematically optimized to resist analysis, why don't SAT solvers simply choke on the exponential search space? The answer lies in the structural properties of real-world primitives and the mechanics of Conflict-Driven Clause Learning (CDCL) solvers.

Many lightweight ciphers yield sparse, low-degree systems of equations when translated into logic. For instance, Nicolas T. Courtois et al. executed the first successful algebraic attack on a full-round commercial block cipher, KeeLoq, by modeling its non-linear feedback functions as a system of multivariate quadratic equations. Because the connections between rounds are sparse, a CDCL solver does not blindly guess keys. Instead, it makes tentative assignments, propagates their implications logically, and when a contradiction occurs, learns a new clause that prunes an entire subspace of invalid keys.

To accelerate this process, researchers have bridged traditional cryptanalytic strategies with automated solving. Alexander A. Semenov et al. introduced a framework using Inverse Backdoor Sets (IBS). This approach formally links automated logic solvers with manual "guess-and-determine" strategies, identifying optimal subsets of variables to guess so that the solver can instantly resolve the remaining system in polynomial time.

Automated Fault Analysis

The power of constraint-based cryptanalysis becomes most apparent when analyzing physical implementations via fault injection. In traditional Differential Fault Analysis (DFA), an attacker injects a physical glitch (like a laser pulse or voltage spike) into a device to corrupt an internal state, then manually derives complex mathematical equations to trace how that error propagates to the final ciphertext.

Algebraic Fault Analysis (AFA) completely automates this tedious process. Instead of manually tracing fault propagation through complex key schedules, the analyst simply appends a few logical constraints to the cipher's CNF model—for example, asserting that the difference between the healthy state and the faulty state has a specific Hamming weight.

This approach yields massive data efficiencies across different primitives:

  • Stream Ciphers: Subhamoy Maitra demonstrated that combining algebraic cryptanalysis with SAT solvers allows an attacker to recover the secret keys of the Grain stream cipher family using as few as 4 to 10 random faults, without needing precise control over fault timing or location (Differential Fault Attack against Grain family with very few faults and minimal assumptions). A similar approach successfully dismantled the Plantlet cipher using only four random faults (A Differential Fault Attack on Plantlet).
  • Hash Functions: Konstantinos Athanasiou et al. applied AFA to SHA-3, exploiting the clear algebraic structure of the Keccak permutation to bypass manual tracing and recover internal states with minimal fault attempts.
  • Persistent Faults: The technique extends beyond transient glitches. Fan Terry Zhang et al. developed Algebraic Persistent Fault Analysis (APFA), utilizing SAT solvers to resolve master keys by processing the complex bitwise relationships left behind by permanent hardware faults across multiple execution rounds.

Furthermore, this constraint-based modeling can be shifted directly to software binaries. Xiaolu Hou et al. developed a tool called TADA that extracts data-flow constraints directly from assembly code, modeling fault-induced leaks as logical constraints for an SMT solver. This allows for the automated discovery of implementation-specific vulnerabilities that theoretical, cipher-level analysis would miss entirely (Fully Automated Differential Fault Analysis on Software Implementations of Block Ciphers).

Beyond Boolean Logic: SMT and Constraint Programming

While pure SAT solvers excel at bit-level logic, modern ciphers often incorporate algebraic operations like modular addition (as seen in Addition-Rotation-XOR, or ARX, ciphers). Translating modular addition into pure CNF clauses creates dense, complex formulas that degrade SAT solver performance due to the long carry chains involved.

To overcome this, cryptanalysts have turned to Satisfiability Modulo Theories (SMT) and Constraint Programming (CP). SMT solvers allow operations to be modeled using higher-level bit-vector theories rather than raw bits. For example, Seyyed Arash Azimi et al. developed a bit-vector differential model for modular addition by a constant, providing the exact mathematical constraints needed for SMT solvers to efficiently search for differential characteristics in ARX ciphers.

Similarly, David Gérault et al. demonstrated that Constraint Programming can be applied to find optimal related-key differentials for block ciphers like AES. By treating the differential path search as a system of variables and constraints, generic CP solvers significantly outperformed dedicated, hand-crafted cryptanalytic tools, discovering optimal solutions that had eluded human experts.

Overcoming Combinatorial Bottlenecks

Ultimately, constraint solvers act as a mathematical safety valve when traditional cryptanalytic methods encounter combinatorial bottlenecks. A prime example occurred during the historic cryptanalysis of SHA-1. When searching for a full hash collision, traditional differential path generation methods struggle with highly over-defined systems of equations in the initial rounds of the hash function.

To bypass this, Marc Stevens et al. adapted SAT solvers specifically to overcome these bottlenecks. By utilizing the logical verification capabilities of the solver to efficiently find valid message bits for the early steps of the algorithm, the authors successfully generated the first real-world full SHA-1 collision, proving that automated reasoning tools are essential for mapping the practical security margins of modern digital communications.

Key Foundational Work

Algebraic and Slide Attacks on KeeLoq (2008) — contributed 2 concept elements to this direction.
Using Walk-SAT and RelAT for Cryptographic Key (1999) — contributed 2 concept elements to this direction.
Using Walk-SAT and Rel-Sat for Cryptographic Key Search (1999) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 14 papers
  2. Version 1 · 2026-10-04 · 14 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_sat_based_cryptanalysis_50c4d343,
  title = {SAT-based cryptanalysis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sat-based-cryptanalysis/rdr_50c4d34388b54633a54bb5fca63f6301},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_sat_based_cryptanalysis_50c4d343_v2,
  title = {SAT-based cryptanalysis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sat-based-cryptanalysis/rdr_50c4d34388b54633a54bb5fca63f6301/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake