Skip to Main content Skip to Navigation
Conference papers

Automatic Generation of Declarative Models for Differential Cryptanalysis

Abstract : When designing a new symmetric block cipher, it is necessary to evaluate its robustness against differential attacks. This is done by computing Truncated Differential Characteristics (TDCs) that provide bounds on the complexity of these attacks. TDCs are often computed by using declarative approaches such as CP (Constraint Programming), SAT, or ILP (Integer Linear Programming). However, designing accurate and efficient models for these solvers is a difficult, error-prone and time-consuming task, and it requires advanced skills on both symmetric cryptography and solvers. In this paper, we describe a tool for automatically generating these models, called Tagada (Tool for Automatic Generation of Abstraction-based Differential Attacks). The input of Tagada is an operational description of the cipher by means of black-box operators and bipartite Directed Acyclic Graphs (DAGs). Given this description, we show how to automatically generate constraints that model operator semantics, and how to generate MiniZinc models. We experimentally evaluate our approach on two different kinds of differential attacks (e.g., single-key and related-key) and four different symmetric block ciphers (e.g., the AES (Advanced Encryption Standard), Craft, Midori, and Skinny). We show that our automatically generated models are competitive with state-of-the-art approaches. These automatically generated models constitute a new benchmark composed of eight optimization problems and eight enumeration problems, with instances of increasing size in each problem. We experimentally compare CP, SAT, and ILP solvers on this new benchmark.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03320980
Contributor : Christine Solnon Connect in order to contact the contributor
Submitted on : Monday, August 16, 2021 - 6:12:23 PM
Last modification on : Thursday, September 16, 2021 - 11:39:37 AM

File

main.pdf
Publisher files allowed on an open archive

Identifiers

Citation

Luc Libralesso, François Delobel, Pascal Lafourcade, Christine Solnon. Automatic Generation of Declarative Models for Differential Cryptanalysis. CP 2021 - 27th International Conference on Principles and Practice of Constraint Programming, Oct 2021, Montpellier, France. ⟨10.4230/LIPIcs.CP.2021.19⟩. ⟨hal-03320980⟩

Share

Metrics

Record views

69

Files downloads

47