MILP for Cryptography

La cryptographie est utilisée tous les jours pour garantir la confidentialité et l’intégrité des communications. On distingue deux grandes familles de problèmes : le design et la cryptanalyse. Dans le premier cas on cherche à concevoir une primitive cryptographique (fonction de hachage, chiffrement, MAC, …) sure et efficace. Parfois des contraintes additionnelles sont prises en compte comme la taille de l’implémentation ou la latence. En cryptanalyse le but est d’attaquer une primitive pour estimer son niveau de sécurité. Cela revient à chercher un algorithme permettant de retrouver la clé secrète ou à tout le moins de distinguer la primitive d’une fonction aléatoire, plus rapidement que par recherche exhaustive sur la clé. La majorité des primitives cryptographiques étant des fonctions itérées, une méthode classique pour évaluer la sécurité est de déterminer le nombre maximum de tours que l’on peut attaquer.

Chercher la meilleure attaque contre une primitive issue de la cryptographie symétrique revient le plus souvent à appliquer les techniques de cryptanalyse classique type analyse différentielle, linéaire, algébrique, ... éventuellement adaptées pour tenir compte des spécificités de la cible. Le problème c’est qu’il y a un nombre exponentiel de façons d’appliquer ces techniques et l’objectif est de trouver la meilleure. Depuis quelques années, la direction prise par une partie de plus en plus grande de la communauté est de reformuler le problème en un modèle MILP (Mixed Integer Linear Programming) à optimiser.  En effet, cette approche s’est montré efficace pour rechercher des chemins différentiels [1], des boomerangs [2], des cube attacks [3], ...

L’objectif de cette thèse est de continuer dans cette direction et en particulier d’affiner les modèles et les techniques de cryptanalyse. Par exemple dans [4] on a montré qu’on pouvait écrire un modèle MILP pour chercher des boomerangs sans spécifier de « tours du milieu » habituellement traités à part pour gérer les  dépendances entre les 2 chemins composant le boomerang. Cette technique peut vraisemblablement être appliquée à la recherche de distingueurs type différentiel-linéaire combinant un chemin différentiel et un chemin linéaire et ce sera le premier travail du doctorant. A plus long terme, l’objectif est de lever au moins partiellement deux verrous pour la modélisation MILP :
1) programmation dynamique/symétries: les primitives cryptographiques étant des fonctions itérées elles se prêtent bien à la programmation dynamique pour certaines propriétés. Mais il semble que les solveurs MILP n’en tirent pas le maximum. Par exemple, rechercher le meilleur chemin différentiel tronqué sur SKINNY prend 1s en programmation dynamique contre plusieurs heures en MILP [5].
2) problème de rang : pour des raisons d’efficacité, les primitives cryptographiques reposent largement sur des composants linéaires et déterminer la complexité de certaines attaques nécessite de calculer le rang de systèmes linéaires sur un corps fini [6]. Ce type de contraintes est difficilement modélisable en MILP et représente un frein à la recherche d’attaques. La solution utilisée aujourd’hui est de supposer que le rang des systèmes est à chaque fois maximal [7] ce qui ne garantit pas l’optimalité de la solution.

Pour résoudre ces 2 problèmes principaux nous investiguerons différentes pistes : analyse théorique plus poussée, génération de contraintes non-triviales (à l’aide de MILP ou d’outils ad-hoc), division du modèle en sous-modèles, … mais toujours en essayant d’être le plus générique possible pour faciliter la réutilisation des codes/modèles à d’autres primitives.