CE39 - Sécurité globale, résilience et gestion de crise, cybersécurité

MILP Modelings for Symmetric Cryptography – OREO

Submission summary

In symmetric-key cryptography, a popular technique for proving resistance against classical attacks is to model the behaviour of the cipher as a Mixed Integer Linear Programming (MILP) problem and solve it by some MILP solver. This method was applied for the first time by Mouha et al. [MWGP11] and by Wu and Wang [WW11] for finding the minimum number of differentially and linearly active Sboxes and provides in such a way a proof of resistance against these two classical attacks. Since then, the use of MILP not only by designers but also by cryptanalysts has increased, the advantage being that many cryptanalytic problems are relatively easy to translate into linear constraints (typically on bits) and available solvers (e.g. Gurobi, CPLEX) are most often very efficient to solve them.

Currently, MILP solvers are mainly used for differential cryptanalysis, including the search of sophisticated boomerang distinguishers, and for integral cryptanalysis by exhausting division trails on a cipher. But we are reaching a point where describing the problem into a MILP model and solving it naively is not enough. Thus there are many open problems related to MILP applied to cryptography and the aim of this new ANR project is to tackle them. Our main objective is to handle more complex cryptographic problems, relying on both a theoretical work on cryptanalysis techniques and an improvement of MILP models. The project is composed of 4 axis: handling more complex cryptographic problems using MILP solvers, automatically search for key-recovery attacks, side-channels cryptanalysis and conception of cryptographic primitives.

Project coordination

Patrick Derbez (Université Rennes 1)

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.

Partner

IRISA Université Rennes 1
LORIA Institut national de la recherche en informatique et automatique
LMV Université Versailles Saint-Quentin-en-Yvelines

Help of the ANR 472,910 euros
Beginning and duration of the scientific project: - 48 Months

Useful links

Explorez notre base de projets financés

 

 

ANR makes available its datasets on funded projects, click here to find more.

Sign up for the latest news:
Subscribe to our newsletter