Cryptanalyse linéaire
| Image manquante Key-crypto-sideways.png | Cet article est une ébauche concernant la cryptologie, vous pouvez partager vos connaissances en le modifiant. |
La cryptanalyse linéaire est une technique inventée par Mitsuru Matsui, chercheur chez Mitsubishi. Elle date de 1993 et fut développée à l'origine pour casser l'algorithme de chiffrement symétrique DES.
La cryptanalyse linéaire est plus efficace que la cryptanalyse différentielle mais moins pratique pour la simple et bonne raison que l'attaquant ne dispose pas de la boîte noire symbolisant l'algorithme de chiffrement et qu'il ne peut pas soumettre ses propres textes. Dans le cas de DES, cette attaque nécessitait à l'origine 247 couples (tous chiffrés avec la même clé) que l'attaquant a pu récupérer par un moyen ou un autre. Par la suite, Matsui améliore son algorithme en 1994 et propose une solution avec 243 couples. La complexité avec une bonne implémentation est toutefois inférieure et de l'ordre de 239 opérations DES.
La cryptanalyse linéaire consiste à faire une approximation linéaire de l'algorithme de chiffrement en le simplifiant. En augmentant le nombre de couples disponible, on améliore la précision de l'approximation et on peut en extraire la clé. Tous les nouveaux algorithmes de chiffrement doivent veiller à être résistants à ce type d'attaques. DES n'était pas conçu pour empêcher ce genre de méthode, les tables de substitution (S-Boxes) présentent en effet certaines propriétés linéaires alors qu'elles étaient justement prévues pour ajouter une non-linéarité à DES.
Elle a par la suite été appliquée avec succès sur plusieurs algorithmes comme Loki, Feal ou une version simplifiée de Serpent. Les algorithmes plus récents comme AES, IDEA et bien d'autres encore sont insensibles à une attaque linéaire. La complexité de l'attaque est dans ces cas largement supérieure à celle d'une recherche exhaustive.
Références
- M. Matsui. Linear cryptanalysis method for DES cipher. Proc. Eurocrypt '93, volume 765 of LNCS, pages 386--397. Springer, 1993.
- (en) Version scannée du papier de Matsui
- (en) Une liste des papiers consacrés à la cryptanalyse linéaire
- (en) Thèse de Pascal Junod sur la cryptanalyse linéaire et une implémentation rapide pour DES
- (en) "How far can we go beyond linear cryptanalysis", Pascal Junod, Thomas Baignères et Serge Vaudenay
- (en) "On Matsui's linear cryptanalysis", analyse de l'attaque par Eli Biham
| Image manquante Key-crypto-sideways.png | Portail Cryptologie - Accédez d'un seul coup d’œil à toute la série des articles « Cryptologie » de Wikipédia. |