License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2021.40
URN: urn:nbn:de:0030-drops-153314
URL: https://drops.dagstuhl.de/opus/volltexte/2021/15331/
Go to the corresponding LIPIcs Volume Portal


Libralesso, Luc ; Delobel, Fran├žois ; Lafourcade, Pascal ; Solnon, Christine

Automatic Generation of Declarative Models For Differential Cryptanalysis

pdf-format:
LIPIcs-CP-2021-40.pdf (1 MB)


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.

BibTeX - Entry

@InProceedings{libralesso_et_al:LIPIcs.CP.2021.40,
  author =	{Libralesso, Luc and Delobel, Fran\c{c}ois and Lafourcade, Pascal and Solnon, Christine},
  title =	{{Automatic Generation of Declarative Models For Differential Cryptanalysis}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{40:1--40:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15331},
  URN =		{urn:nbn:de:0030-drops-153314},
  doi =		{10.4230/LIPIcs.CP.2021.40},
  annote =	{Keywords: Constraint Programming, SAT, ILP, Differential Cryptanalysis}
}

Keywords: Constraint Programming, SAT, ILP, Differential Cryptanalysis
Collection: 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)
Issue Date: 2021
Date of publication: 15.10.2021
Supplementary Material: Software (Source Code): https://gitlab.limos.fr/iia_lulibral/tagada/ archived at: https://archive.softwareheritage.org/swh:1:dir:43b1382c69c9612241160a8bfb9e019e90927539
Dataset (Models and Results): https://gitlab.limos.fr/iia_lulibral/experiment-results archived at: https://archive.softwareheritage.org/swh:1:dir:f691fc943675263dab923d092f5a6508bae79ff6


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI