Worldlex Wiki La cryptanalyse différentielle est une forme générale de cryptanalyse applicable principalement aux chiffrements par blocs , mais aussi aux chiffrements de flux et aux fonctions de hachage cryptographiques. Au sens large, elle étudie comment les différences dans les informations d'entrée peuvent affecter la différence résultante en sortie. Dans le cas d'un chiffrement par blocs , elle désigne un ensemble de techniques permettant de retracer 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 retrouver la clé secrète (clé cryptographique).
Histoire
La découverte et la divulgation publiques de la cryptanalyse différentielle sont généralement attribuées à Eli Biham et Adi Shamir à la fin des années 1980. Ils ont publié plusieurs attaques contre divers chiffrements par blocs et fonctions de hachage, notamment une faiblesse théorique du DES ( Data Encryption Standard ). Biham et Shamir ont constaté que le DES était étonnamment résistant à la cryptanalyse différentielle, mais que de petites modifications de l'algorithme le rendaient beaucoup plus vulnérable.
En 1994, Don Coppersmith , membre de l'équipe d'origine d'IBM DES, publia un article affirmant qu'IBM connaissait la cryptanalyse différentielle dès 1974 et que s'en prémunir constituait un objectif de conception. Selon l'auteur Steven Levy , IBM aurait découvert la cryptanalyse différentielle de manière indépendante et la NSA était apparemment parfaitement au courant de cette 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 pouvant être utilisée contre de nombreux chiffrements. Cela affaiblirait l'avantage concurrentiel dont bénéficiaient les États-Unis sur les 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 d'« attaque par chatouillement ».
Bien que le DES ait été conçu pour résister à la cryptanalyse différentielle, d'autres chiffrements contemporains se sont révélés vulnérables. Le chiffrement par blocs FEAL a été l'une des premières cibles de cette attaque . La version originale à quatre tours (FEAL-4) peut être cassée avec seulement huit textes clairs choisis , et même une version à 31 tours de FEAL est sensible à l'attaque. En revanche, ce schéma permet de cryptanalyser le DES avec un effort de l'ordre de 2⁴⁷ textes clairs choisis.
Mécanismes d'attaque
La cryptanalyse différentielle est généralement une attaque à texte clair choisi , ce qui signifie que l'attaquant doit pouvoir obtenir les textes chiffrés pour un ensemble de textes clairs de son choix. Il existe cependant des extensions permettant une attaque à texte clair connu , voire une attaque ne portant que sur les textes chiffrés . La méthode de base utilise des paires de textes clairs liés par une différence constante . Cette différence peut être définie de plusieurs manières, mais l' opération OU exclusif (XOR) est courante. L'attaquant calcule ensuite les différences des textes chiffrés correspondants, dans l'espoir de détecter des schémas 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 S-boxes utilisées pour le chiffrement ; l'attaquant analyse donc les différentielles.
Dans sa forme la plus simple de récupération de clé par cryptanalyse différentielle, un attaquant demande les textes chiffrés d'un grand nombre de paires de textes clairs, puis suppose que la différence est valable pendant au moins r − 1 tours, où r est le nombre total de tours. L'attaquant déduit ensuite les clés de tour possibles (pour le tour final), en supposant que la différence entre les blocs précédant le tour final est fixe. Lorsque les clés de tour sont courtes, cela peut se faire simplement en déchiffrant exhaustivement les paires de textes chiffrés, tour par tour, avec chaque clé de tour possible. Si une clé de tour est considérée comme potentielle beaucoup plus souvent que toute autre, elle est présumée être la bonne clé de tour.
Pour tout chiffrement donné, la différence d'entrée doit être soigneusement sélectionnée pour que l'attaque réussisse. Une analyse interne de l'algorithme est alors effectuée ; la méthode standard consiste à retracer un chemin de différences hautement probables à travers les différentes étapes du chiffrement, appelé caractéristique différentielle .
Depuis que la cryptanalyse différentielle est devenue publique, elle constitue une préoccupation majeure pour les concepteurs de systèmes de chiffrement. Les nouvelles conceptions doivent s'accompagner de preuves de la résistance de l'algorithme à cette attaque, et de nombreux systèmes, dont la norme de chiffrement avancée (AES) , ont démontré leur sécurité face à celle-ci.
Attaque en détail
L'attaque repose principalement sur le fait qu'un schéma de différence entrée/sortie donné n'apparaît que pour certaines valeurs d'entrée. Elle est généralement appliquée aux composants non linéaires comme s'il s'agissait d'un composant solide (il s'agit en réalité souvent de tables de correspondance ou de S-boxes ). L'observation de la différence de sortie souhaitée (entre deux entrées en clair choisies ou connues) suggère des valeurs clés possibles.
Par exemple, si une différence de 1 => 1 (impliquant qu'une différence dans le bit de poids faible (LSB) de l'entrée entraîne une différence dans le LSB de la sortie) se produit avec une probabilité de 4/256 (possible avec la fonction non linéaire du chiffrement AES, par exemple), alors cette différence n'est possible que pour 4 valeurs (ou 2 paires) d'entrées. Supposons une fonction non linéaire où la clé est combinée par un OU exclusif (XOR) avant évaluation et où les valeurs autorisant cette différence sont {2, 3} et {4, 5}. Si l'attaquant envoie les valeurs {6, 7} et observe la différence de sortie attendue, cela signifie que la clé est soit 6 ⊕ K = 2, soit 6 ⊕ K = 4, ce qui signifie que la clé K vaut soit 2, soit 4.
En substance, pour protéger un chiffrement contre l'attaque, pour une fonction non linéaire à n bits, on chercherait idéalement à se rapprocher le plus possible de 2 − ( n − 1) afin d'obtenir une uniformité différentielle . Dans ce cas, l'attaque différentielle exige autant de travail pour déterminer la clé que la simple recherche exhaustive de la clé.
La fonction non linéaire de l'AES a une probabilité différentielle maximale de 4/256 (la plupart des entrées étant cependant 0 ou 2). En théorie, cela signifie qu'il serait possible de déterminer la clé avec deux fois moins d'efforts qu'avec une attaque par force brute. Cependant, la branche haute de l'AES empêche l'existence de pistes à forte probabilité sur plusieurs tours. En réalité, le chiffrement AES serait tout aussi résistant aux attaques différentielles et linéaires avec une fonction non linéaire beaucoup plus faible . La branche extrêmement élevée (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 n'excède pas Pr[attaque] ≤ Pr[meilleure attaque sur la boîte S] ≤ 50. Par exemple, avec la boîte S actuelle, l'AES n'émet aucune différentielle fixe avec une probabilité supérieure à (4/256) ≥ 50 ou 2 <sup>-300 </sup> , ce qui est bien inférieur au seuil requis de 2 <sup>-128 </sup> pour un chiffrement par blocs de 128 bits. Cela aurait permis de faire place à une S-box plus efficace, même si elle est 16-uniforme, la probabilité d'attaque aurait toujours été de 2 −200 .
Il n'existe pas de bijections pour les entrées/sorties de taille paire avec une 2-uniformité. Elles existent dans les corps impairs (comme GF(2<sup> 7</sup> )) en utilisant soit la mise au cube, soit l'inversion (d'autres exposants peuvent également être utilisés). Par exemple, S(x) = x<sup> 3</sup> dans tout corps binaire impair est insensible à la cryptanalyse différentielle et linéaire. C'est en partie pourquoi les architectures MISTY utilisent des fonctions de 7 et 9 bits dans la fonction non linéaire de 16 bits. Ce que ces fonctions gagnent en résistance aux attaques différentielles et linéaires, elles le perdent face aux attaques algébriques. solveur SAT . C'est en partie pourquoi l'AES (par exemple) utilise une transformation affine après l'inversion.