Modélisation MILP pour la Cryptographie Symétrique – OREO

En cryptographie symétrique, une technique populaire pour prouver la résistance aux attaques cryptographiques est de modéliser le comportement de la primitive en un problème d'optimisation linéaire sur les nombres entiers (Mixed Interger Linear Programming, MILP) et de le résoudre à l'aide d'un solveur générique. Cette méthode a été appliquée pour la première fois par Mouha et al. et par Wu et al. pour déterminer le nombre minimum de S-boites actives dans les cadres de la cryptanalyse différentielle et linéaire, fournissant ainsi une preuve de résistance à ces attaques classiques. Depuis, l'utilisation de solveurs MILP aussi bien pour la conception de primitives cryptographiques que pour la cryptanalyse n'a cessé de se développer. En effet, nombre de problèmes de cryptanalyses sont relativement faciles à décrire à l'aide de contraintes linéaires (le plus souvent sur les bits des états internes) et les solveurs MILP (notamment Gurobi et CPLEX) sont particulièrement efficaces pour les résoudre.

Actuellement, les solveurs MILP sont principalement utilisés pour la cryptanalyse différentielle, incluant la recherche de distingueurs relativement complexes comme les boomerangs, ainsi que pour les attaques intégrales basées sur des propriétés de division. Mais nous avons atteint un point où décrire naïvement un problème cryptographique n'est plus suffisant pour espérer le résoudre en temps raisonnable. Ainsi il y a plusieurs problèmes ouverts relatifs à la programmation linéaire par contraintes appliquée à la cryptographie et le but de ce nouveau projet ANR est de les résoudre. Notre objectif principal est de gérer des problèmes cryptographiques plus complexes en améliorant les techniques de cryptanalyses et les modèles MILP d'autre part. Ce projet est composé de 4 axes de recherche: gérer des problèmes cryptographiques plus complexes, définir des modèles MILP pour chercher directement des attaques, les attaques par canaux auxiliaires et la conception de primitives.