Using Walk-SAT and RelAT for Cryptographic Key

IJCAI 1999

TL;DR

This paper proposes using the Data Encryption Standard (DES) as a benchmark for propositional satisfiability (SAT) solvers. By encoding DES key search as a SAT problem, the authors demonstrate that even state-of-the-art AI search techniques struggle with full-strength cryptographic problems, highlighting the need for improved SAT solvers capable of handling "real-world" structured problems.

What Problem Does This Paper Address?

Securing digital information is paramount, and its strength relies heavily on cryptographic algorithms. A critical challenge in this domain is "cryptographic key search," where adversaries attempt to find the secret key used in encryption. This is a problem of significant interest to governments and corporations. While AI search techniques have made strides in solving complex problems, their effectiveness on real-world cryptographic challenges, which are often highly structured and computationally intensive, remains an open question. The authors aim to bridge this gap by using cryptographic key search as a rigorous benchmark for propositional reasoning and search, specifically for SAT solvers.

Methods

The core of the paper involves encoding the Data Encryption Standard (DES) into propositional logic. This encoding represents each bit of the plaintext, ciphertext, and key as a propositional variable. The complex operations within DES rounds are then transformed into boolean formulas, minimized using CAD tools, and generated dynamically. This allows for the creation of "solved" SAT instances where the key is known, effectively framing the cryptographic key search problem as a SAT problem.

The authors then evaluate two prominent SAT solvers on these encoded DES problems:

  • Walk-SAT: A local search algorithm that starts with a random assignment and iteratively flips variable values to satisfy more clauses. It's known for its speed but can get stuck in local minima.
  • Rel-SAT: A systematic SAT solver that combines the Davis-Putnam algorithm with back-jumping and learning. It aims to systematically explore the search space and learn from contradictions.

Datasets

The paper does not introduce new datasets in the traditional sense. Instead, it proposes a method for generating an "endless stream" of "real-world" SAT instances by:

  1. Generating random keys and plaintext blocks.
  2. Using the DES algorithm to produce the corresponding ciphertext.
  3. Substituting these known values into the propositional encoding of DES.

This process creates "solved" instances of the SAT problem, where finding a satisfying assignment is equivalent to finding the correct key. The instances are parameterized by the number of DES rounds and the number of plaintext/ciphertext blocks used, allowing for the generation of problems of varying difficulty and structure.

Key Insights and Ideas

  • DES as a SAT Benchmark: Cryptographic key search, specifically for DES, offers a unique benchmark for SAT solvers. It combines the complexity of "real-world" problems with the ability to generate an unlimited number of instances, addressing a known limitation of current SAT benchmarks.
  • AI Search Limitations: Even state-of-the-art SAT solvers like Walk-SAT and Rel-SAT struggle significantly with full-strength DES problems. This suggests that current AI search techniques, while powerful, are not yet equipped to tackle the inherent structure and complexity of modern cryptography.
  • The "Affine Subproblem" Challenge: The paper identifies that the core difficulty for SAT solvers lies in handling the "affine subproblem" within cryptographic algorithms, particularly those involving XOR operations. This is a key insight into why standard SAT solvers falter.
  • Learning vs. Structure: For Rel-SAT, the effectiveness of learning heuristics was found to be dependent on the number of constraints. Learning is crucial with few constraints but less impactful when many constraints (blocks) are present, suggesting that the problem structure itself becomes more dominant.

Key Results

  • Walk-SAT: Successfully cracked DES up to 2 rounds. At 3 rounds, it failed to find a solution, even with extensive search and perturbations. Adding more constraints (blocks) actually made the problem harder for Walk-SAT.
  • Rel-SAT: Performed better than Walk-SAT, cracking 3-round DES in under ten minutes. However, it failed to solve the full 16-round DES within 12 hours, even with optimizations. The performance of Rel-SAT improved with an increasing number of blocks, mirroring the behavior of traditional cryptanalysis.

Limitations and Future Work

  • Limitations:
    • Current SAT solvers are not competitive with specialized cryptographic techniques for breaking DES.
  • The paper highlights that the "affine subproblem" is a significant hurdle for SAT solvers.
  • The performance of Walk-SAT degraded with increased constraints, contrary to expectations.
  • Future Work:
    • Challenge 1 (Feasible): Develop specialized search heuristics to crack the commercial 16-round DES within 56 hours using off-the-shelf hardware.
  • Challenge 2 (Moderate): Design SAT solvers that can handle Feistel-type ciphers with data-independent rounds, building on the ability to solve affine subproblems.
  • Challenge 3 (Difficult): Create efficient SAT encodings for data-dependent Feistel-type ciphers like RC5.
  • Challenge 4 (Very Difficult): Develop efficient propositional logic encodings for public-key algorithms like RSA, which are rooted in number theory.
  • A more philosophical challenge is the potential for successful SAT algorithms to be deemed "dangerous weapons" and face export restrictions.

Summary updated

BibTeX
@inproceedings{1999using,
  title = {{Using Walk-SAT and RelAT for Cryptographic Key}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure