Attaque XSL

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

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 l'article 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

Cette méthode a causé une controverse quant à sa réelle efficacité : les auteurs prétendaient que XSL pouvait potentiellement casser Rijndael (vainqueur du concours pour l'AES), au sens où elle aurait été plus efficace que l'attaque par force brute. 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 :

« I believe that the Courtois-Pieprzyk work is flawed. They overcount the number of linearly independent equations. The result is that they do not in fact have enough linear equations to solve the system, and the method does not break Rijndael… The method has some merit, and is worth investigating, but it does not break Rijndael as it stands. »

« 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. »