Using Constraint Programming to solve a Cryptanalytic Problem

David Gérault, Marine Minier, Christine SolnonIJCAI 2017 · DOI

TL;DR

This paper introduces a novel approach using Constraint Programming (CP) to find optimal "related-key differentials" for the AES block cipher. Their CP models significantly outperform existing dedicated cryptanalysis tools in terms of speed and efficiency, and they even discover better solutions than those previously claimed to be optimal.

What Problem Does This Paper Address?

Cryptanalysis aims to break encryption algorithms. Differential cryptanalysis, a powerful technique, studies how differences in plaintext propagate through a cipher. "Related-key attacks" extend this by also considering differences in the encryption keys themselves. Finding the "optimal related-key differentials" for AES – specifically, the plaintext and key differences that maximize the probability of a certain output difference – is a computationally intensive problem. Existing methods, like graph traversal and Branch & Bound, struggle with scalability and can take days or weeks to find solutions, especially for longer AES key lengths. This paper tackles the challenge of finding these optimal differentials more efficiently and accurately.

Methods

The authors propose using Constraint Programming (CP) to model and solve this cryptanalytic problem. CP involves defining a problem using variables and constraints, which are then solved by generic solvers. They break the problem into two steps:

  • Step 1 (Boolean Level): This step focuses on finding a Boolean solution that satisfies the AES transformation rules, ignoring the non-linear SubBytes operation. This is done by defining Boolean variables for each differential byte and using XOR constraints for operations like AddRoundKey and KeySchedule. The objective is to minimize the number of non-zero differences.
  • Step 2 (Byte Level): This step converts the Boolean solutions into byte-level solutions. For each differential byte, if its corresponding Boolean variable is 0, the byte difference is 0. If it's 1, the algorithm searches for a byte value that satisfies the AES rules and maximizes the probability.

A key innovation is the introduction of "additional constraints" for Step 1. These constraints model equality relations between differential bytes, helping to filter out "byte-inconsistent" Boolean solutions early on, which significantly improves performance.

Datasets

Not discussed in the paper. The paper focuses on a theoretical problem and its algorithmic solution, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • CP as a powerful tool for cryptanalysis: The paper demonstrates that CP, typically used for combinatorial optimization, is highly effective for complex cryptanalytic problems like finding optimal differentials.
  • The power of Boolean abstraction: Breaking down the problem into a Boolean level first, and then refining it to the byte level, is a smart way to manage complexity.
  • Filtering byte-inconsistent solutions: The introduction of equality constraints at the Boolean level is crucial. It dramatically reduces the search space by eliminating solutions that cannot be translated into valid byte-level differences, a major bottleneck in previous approaches.
  • Discovering better-than-optimal solutions: The CP approach not only matches but surpasses previously published "optimal" results, highlighting the limitations of older methods.

Key Results

  • Speedup: The CP approach, particularly with the added constraints and the Chuffed solver, solves 128-bit AES instances in under an hour, a significant improvement over dedicated tools that take days.
  • Improved Optimality: The authors found a better byte-consistent solution for 4-round AES than those previously claimed to be optimal in [Biryukov and Nikolic, 2010] and [Fouque et al., 2013]. Their solution has a lower "cost" (objStep1 = 12 vs. 13) and a higher probability (2⁻⁷⁹ vs. 2⁻⁸¹).
  • Scalability: The CP models were extended to handle longer AES keys (192 and 256 bits), finding optimal solutions for all cases within reasonable timeframes (under 35 hours for Step 1). This is a significant advantage over methods that don't scale to larger key sizes.
  • Correction of previous findings: They also identified an inconsistency in a previously proposed solution for AES-192 and found improved solutions for AES-256, leading to better related-key attacks.

Limitations and Future Work

  • Model Complexity: The authors acknowledge that while CP is powerful, naive models may not scale well. Developing efficient CP models, especially those incorporating byte-level constraints, is challenging and requires significant expertise.
  • Future Work: They suggest the development of new CP frameworks specifically tailored for cryptanalysis problems. This would aim to simplify the modeling process and make it easier to develop efficient CP models for these complex tasks. They also hint at further improvements in related-key attacks on AES based on their findings.

Summary updated

BibTeX
@inproceedings{gerault2017using,
  author = {David Gérault and Marine Minier and Christine Solnon},
  title = {{Using Constraint Programming to solve a Cryptanalytic Problem}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/679},
}
Figure