Contrainte globale abstractXOR: résultats de complexité et algorithmes de propagation

Papier Citer
2019
Constraint Programming
JFPC

Abstract

Les algorithmes de chiffrement symétrique par bloc utilisent une clé secrète pour chiffrer un texte. Le but de l’attaque related-key est d’évaluer s’il est possible de retrouver la clé en étudiant la propagation des différences entre des textes et des clés donnés. Pour cela, les cryptanalystes doivent calculer des chemins différentiels maximaux. Ce problème est résolu en deux étapes : dans une première étape, chaque octet est abstrait par un booléen indiquant si l’octet contient une différence ou non et on recherche des solutions abstraites ; dans une second eétape, on recherche une solution concrète optimale pourcha que solution abstraite. Certaines solutions abstraites peuvent ne pas admettre de solution concrète, et un enjeu important est de limiter au maximum le nombre de solutions abstraites incohérentes au niveau concret. La perte de précision au niveau abstrait vient essentiellement du fait que le chiffrement utilise massivement des XOR (ou exclusif bit à bit), et que cette opération est très mal abstraite lors de la première étape. Pour améliorer cela, nous proposons d’introduire une contrainte permettant de propager un ensemble de XOR de façon globale.

Nous étudions tout d’abord la complexité du problème consistant à décider si un ensemble de XOR admet une solution concrète. Nous montrons que si le problème est polynomial lorsque les variables ne sont pas contraintes, il devient NP-complet si on contraint certaines variables à prendre une valeur comprise entre 1 et une borne supérieure donnée. Nous introduisons ensuite la contrainte globale abstractXOR qui est satisfaite s’il existe une solution abstraite pouvant être concrétisée dans le cas où les variables ne sont pas contraintes par une borne supérieure, et nous introduisons des algorithmes polynomiaux pour propager cette contrainte. Nous montrons comment utiliser cette contrainte globale pour modéliser un problème de recherche de chemin différentiel maximal pour Midori, et nous comparons les performances du modèle utilisant cette contrainte globale avec d’autres modèles.