Attaque XSL

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En cryptographie, l'attaque XSL est une méthode heuristique de cryptanalyse contre les chiffrements par bloc. Elle a été publiée en 2002 par Nicolas Courtois et Josef Pieprzyk.

Fonctionnement[modifier | modifier le code]

L'attaque XSL est basée sur la résolution d'un système d'équations quadratiques qui symbolisent la structure du chiffrement. Le système est typiquement très gros, plus de 8000 équations avec 1600 variables pour un AES de 128 bits. Plusieurs méthodes pour résoudre de tels systèmes sont connues (en particulier les bases de Gröbner) et une nouvelle technique a été proposée dans le papier sous le nom de eXtended Sparse Linearisation (XSL). Malgré ces découvertes, l'attaque reste purement théorique car elle demande une trop grande puissance de calcul.

Controverse[modifier | modifier le code]

Cette méthode a causé une controverse quant à sa réelle efficacité : les auteurs prétendaient que XSL pouvait potentiellement casser Rijndael (vainqueur de AES). Si la communauté des cryptologues est restée sceptique face à cette attaque, elle a eu le mérite de relancer les doutes au sujet de la simplicité algébrique de AES.

Don Coppersmith affirma au sujet de cette attaque (traduction de la citation anglaise) :

Je crois que le travail de Courtois-Pierprzyk a un défaut. Ils surestiment le nombre d'équations linéairement indépendantes. En conséquence, ils n'ont pas assez d'équations linéaires à disposition pour résoudre le système et la méthode ne casse pas Rijndael. La méthode a un certain mérite et il est intéressant de l'examiner plus en avant mais elle ne casse pas Rijndael en l'état actuel.