Worldlex Wiki La cryptanalyse différentielle est une forme générale de cryptanalyse applicable principalement aux chiffrements par blocs, mais aussi aux chiffrements par flux et aux fonctions de hachage cryptographiques. Au sens le plus large, il s'agit de l'étude de la manière dont les différences dans les informations d'entrée peuvent affecter la différence résultante à la sortie. Dans le cas d'un chiffrement par blocs , elle fait référence à un ensemble de techniques permettant de tracer les différences à travers le réseau de transformation, de découvrir où le chiffrement présente un comportement non aléatoire et d'exploiter ces propriétés pour récupérer la clé secrète (clé de cryptographie).
Histoire
La découverte de la cryptanalyse différentielle est généralement attribuée à Eli Biham et Adi Shamir à la fin des années 1980, qui ont publié un certain nombre d'attaques contre divers chiffrements par blocs et fonctions de hachage, notamment une faiblesse théorique dans la norme de chiffrement des données (DES). Biham et Shamir ont noté que DES était étonnamment résistant à la cryptanalyse différentielle, mais de petites modifications de l'algorithme le rendraient beaucoup plus vulnérable.
En 1994, Don Coppersmith , membre de l'équipe IBM DES originale , a publié un article affirmant que la cryptanalyse différentielle était connue d'IBM dès 1974 et que la défense contre la cryptanalyse différentielle avait été un objectif de conception. Selon l'auteur Steven Levy , IBM avait découvert la cryptanalyse différentielle par elle-même et la NSA était apparemment bien au courant de la technique. IBM a gardé certains secrets, comme l'explique Coppersmith : « Après des discussions avec la NSA, il a été décidé que la divulgation des considérations de conception révélerait la technique de la cryptanalyse différentielle, une technique puissante qui pourrait être utilisée contre de nombreux chiffrements. Cela affaiblirait à son tour l'avantage concurrentiel dont jouissaient les États-Unis sur d'autres pays dans le domaine de la cryptographie. » Au sein d'IBM, la cryptanalyse différentielle était connue sous le nom d'« attaque T » ou « attaque Tickle ».
Bien que DES ait été conçu pour résister à la cryptanalyse différentielle, d'autres chiffrements contemporains se sont révélés vulnérables. L'une des premières cibles de l'attaque était le chiffrement par blocs FEAL . La version originale proposée avec quatre tours (FEAL-4) peut être cassée en utilisant seulement huit textes en clair choisis , et même une version de FEAL à 31 tours est susceptible d'être attaquée. En revanche, le schéma peut cryptanalyser DES avec succès avec un effort de l'ordre de 2 47 textes en clair choisis.
Mécanique d'attaque
La cryptanalyse différentielle est généralement une attaque par texte clair choisi , ce qui signifie que l'attaquant doit être capable d'obtenir des textes chiffrés pour un ensemble de textes clairs de son choix. Il existe cependant des extensions qui permettraient une attaque par texte clair connu ou même par texte chiffré uniquement . La méthode de base utilise des paires de textes clairs liés par une différence constante . La différence peut être définie de plusieurs manières, mais l' opération OU exclusif (XOR) est habituelle. L'attaquant calcule ensuite les différences des textes chiffrés correspondants, en espérant détecter des modèles statistiques dans leur distribution. La paire de différences résultante est appelée différentielle . Leurs propriétés statistiques dépendent de la nature des boîtes S utilisées pour le chiffrement, de sorte que l'attaquant analyse les différentiels où (et ⊕ désigne un ou exclusif) pour chaque boîte S S de ce type . Dans l'attaque de base, une différence de texte chiffré particulière est censée être particulièrement fréquente. De cette façon, le chiffrement peut être distingué d' un aléatoire . Des variations plus sophistiquées permettent de récupérer la clé plus rapidement qu'une recherche exhaustive .
Dans la forme la plus basique de récupération de clés par cryptanalyse différentielle, un attaquant demande les textes chiffrés pour un grand nombre de paires de texte en clair, puis suppose que le différentiel est valable pour au moins r − 1 tours, où r est le nombre total de tours. L'attaquant déduit ensuite quelles clés de tour (pour le tour final) sont possibles, en supposant que la différence entre les blocs avant le tour final est fixée. Lorsque les clés de tour sont courtes, cela peut être réalisé en déchiffrant simplement de manière exhaustive les paires de textes chiffrés un tour avec chaque clé de tour possible. Lorsqu'une clé de tour a été considérée comme une clé de tour potentielle beaucoup plus souvent que toute autre clé, elle est supposée être la bonne clé de tour.
Pour tout chiffrement particulier, la différence d'entrée doit être soigneusement sélectionnée pour que l'attaque réussisse. Une analyse des éléments internes de l'algorithme est entreprise ; la méthode standard consiste à tracer un chemin de différences hautement probables à travers les différentes étapes du chiffrement, appelées caractéristique différentielle .
Depuis que la cryptanalyse différentielle est devenue une connaissance publique, elle est devenue une préoccupation fondamentale des concepteurs de chiffrement. On s'attend à ce que les nouvelles conceptions soient accompagnées de preuves que l'algorithme est résistant à cette attaque et de nombreuses d'entre elles, y compris l' Advanced Encryption Standard , se sont avérées sûres contre cette attaque.
L'attaque en détail
L'attaque repose principalement sur le fait qu'un modèle de différence d'entrée/sortie donné ne se produit que pour certaines valeurs d'entrées. En général, l'attaque est appliquée essentiellement aux composants non linéaires comme s'il s'agissait d'un composant solide (généralement, il s'agit en fait de tables de correspondance ou de boîtes S ). L'observation de la différence de sortie souhaitée (entre deux entrées en texte clair choisies ou connues) suggère des valeurs clés possibles.
Par exemple, si un différentiel de 1 => 1 (impliquant une différence dans le bit le moins significatif (LSB) de l'entrée conduit à une différence de sortie dans le LSB) se produit avec une probabilité de 4/256 (possible avec la fonction non linéaire dans le chiffrement AES par exemple), alors pour seulement 4 valeurs (ou 2 paires) d'entrées, ce différentiel est possible. Supposons que nous ayons une fonction non linéaire où la clé est XOR'ed avant l'évaluation et que les valeurs qui permettent le différentiel sont {2,3} et {4,5}. Si l'attaquant envoie les valeurs de {6, 7} et observe la différence de sortie correcte, cela signifie que la clé est soit 6 ⊕ K = 2, soit 6 ⊕ K = 4, ce qui signifie que la clé K est soit 2 soit 4.
En substance, pour protéger un chiffrement contre l'attaque, pour une fonction non linéaire à n bits, il faudrait idéalement chercher à se rapprocher le plus possible de 2 −( n − 1) pour obtenir une uniformité différentielle . Lorsque cela se produit, l'attaque différentielle nécessite autant de travail pour déterminer la clé que le simple forçage brut de la clé.
La fonction non linéaire AES a une probabilité différentielle maximale de 4/256 (la plupart des entrées sont cependant soit 0 soit 2). Cela signifie qu'en théorie, on pourrait déterminer la clé avec la moitié du travail nécessaire par la force brute. Cependant, la branche haute de l'AES empêche toute trace de probabilité élevée d'exister sur plusieurs tours. En fait, le chiffrement AES serait tout aussi immunisé contre les attaques différentielles et linéaires avec une fonction non linéaire beaucoup plus faible . La branche incroyablement haute (nombre de boîtes S actives) de 25 sur 4R signifie que sur 8 tours, aucune attaque n'implique moins de 50 transformations non linéaires, ce qui signifie que la probabilité de succès ne dépasse pas Pr[attaque] ≤ Pr[meilleure attaque sur la boîte S] 50 . Par exemple, avec la S-box actuelle, AES n'émet aucun différentiel fixe avec une probabilité supérieure à (4/256) 50 ou 2 −300, ce qui est bien inférieur au seuil requis de 2 −128 pour un chiffrement par bloc de 128 bits. Cela aurait laissé la place à une S-box plus efficace, même si elle est uniforme sur 16 bits, la probabilité d'attaque aurait toujours été de 2 −200 .
Il n'existe pas de bijections pour des entrées/sorties de taille paire avec une uniformité 2. Elles existent dans les corps impairs (tels que GF(2 7 )) en utilisant soit le cubage, soit l'inversion (il existe d'autres exposants qui peuvent également être utilisés). Par exemple, S(x) = x 3 dans tout corps binaire impair est immunisé contre la cryptanalyse différentielle et linéaire. C'est en partie pourquoi les conceptions MISTY utilisent des fonctions 7 et 9 bits dans la fonction non linéaire 16 bits. Ce que ces fonctions gagnent en immunité aux attaques différentielles et linéaires, elles le perdent face aux attaques algébriques. C'est-à-dire qu'elles peuvent être décrites et résolues via un solveur SAT . C'est en partie pourquoi AES (par exemple) a une application affine après l'inversion.