Attaque par glissement

L'attaque par glissement, ou slide attack, est une méthode cryptanalytique introduite en 1999 par David Wagner et Alex Biryukov[1],[2],[3]. Elle repose sur l'observation que de nombreuses constructions cryptographiques et notamment les chiffrements par blocs fonctionnent en répétant une même opération un nombre fixé de fois (entre 10 et 12 pour AES, par exemple), se contentant d'utiliser une clé dérivée pour chaque tour. Or la dérivation de clé est souvent manipulable par un adversaire, ce qui permet à l'analyste de forcer par exemple que toutes les clés dérivées soient identiques, ou liées par une relation simple. L'attaque par glissement permet alors d'attaquer directement la permutation élémentaire, indépendamment du nombre de tours. L'existence de cette attaque montre en particulier que l'opinion répandue selon laquelle il suffit d'augmenter le nombre de tours pour augmenter la sécurité d'un chiffrement par blocs, n'est pas fondée[1].

Depuis son introduction, l'attaque a été étendue pour s'appliquer à tout système cryptographie basé sur la répétition d'opérations simples, comme les fonctions de hachage de type Merkle-Damgård, ou les chiffrements par flux.

Histoire

L'attaque par glissement tire son inspiration d'un premier travail sur la cryptanalyse du chiffre New Data Seal en 1978[4] par Edna Grossman et Bryant Tuckerman. En particulier, leur attaque montre comment casser un chiffre de Feistel affaibli par une attaque en clairs choisis, de manière complètement indépendante du nombre de tours. Les travaux d'Eli Biham sur les attaques par clés apparentées[5] et la cryptanalyse de LOKI par Lars Knudsen[6] en 1991 peuvent être vus comme des développements naturels de ces techniques.

David Wagner et Alex Biryukov ont pour la première fois systématisé l'attaque et mesuré son potentiel en 1999[1], et dans plusieurs travaux à la suite[2],[3]. Le nom d'« attaque par glissement » a été suggéré par Bruce Schneier[1].

Principe

Pour illustrer le principe, considérons un chiffrement par blocs consistant en la répétition d'une permutation dépendant d'une clé inconnue . En pratique la clé est susceptible de changer à chaque application (c'est une clé dérivée) mais dans de nombreux cas on peut exploiter la structure de la dérivation de clé pour s'assurer que est bien constante. On va supposer qu'en tant que permutation, est relativement faible face à une attaque à clairs connus : plus spécifiquement, étant donné deux valeurs pour des valeurs de connues de l'adversaire, il est facile de retrouver la clé .

Un tel modèle est en fait tout à fait réaliste, puisque DES réduit à trois tours, ou IDEA réduit à un tour et demi sont de telles fonctions [1].

L'attaque consiste alors à considérer deux exécutions du chiffrement « glissées » l'une par rapport à l'autre :

en observant que s'il se produit une collision, par exemple , alors on a pour toute la suite . On cherche alors une paire telle que et . Une telle paire peut toujours être trouvée en au plus chiffrements aléatoires, où est la taille du bloc, par le théorème des anniversaires, ou en chiffrements en exploitant la structure d'un réseau de Feistel. Pour certains chiffrements, il est possible de trouver une telle paire bien plus efficacement, et dans tous les cas il est facile de la reconnaître.

Une fois la paire trouvée, par hypothèse sur , on retrouve .

Applications

L'attaque par glissement est une attaque générique qui montre que la permutation élémentaire n'est pas « sauvée » contre une attaque par clairs choisis en augmentant le nombre de tours. Elle s'applique donc à tous les chiffrements par blocs qui utilisent un tour faible. Mais la techniques s'étend également aux chiffrements par flux, aux codes d'authentification, et aux fonctions de hachage.

  • Appliquée à TREYFER[7], un MAC, la technique donne une attaque en clairs connus et opérations[1]. Elle a depuis été améliorée pour ne nécessiter que clairs connus[8].
  • Appliquée à Blowfish[9], un chiffrement par blocs, la technique montre qu'un algorithme chiffrement ne peut pas espérer tirer sa sécurité d'une S-box dépendant de la clé, avec une attaque sur une variante en clairs connus et opérations[1]. Ce fut historiquement la première attaque efficace contre cette famille de chiffrements.
  • De nombreuses variantes de DES sont cassées par l'attaque par glissement, parfois en utilisant moins de 128 clairs, et même pour un nombre de tours arbitrairement large[3].

Des améliorations de l'attaque par glissement ont été appliquées à DES-X[3], à GOST[3],[10],[11],[12] (cassé à la suite de ces travaux), et aux constructions de type Even-Mansour[3].

Notes et références

  1. a b c d e f et g (en) Alex Biryukov et David Wagner, « Slide Attacks », Fast Software Encryption, Springer, Berlin, Heidelberg, série Lecture Notes in Computer Science,‎ , p. 245–259 (ISBN 3540485198, DOI 10.1007/3-540-48519-8_18, lire en ligne, consulté le 28 février 2018)
  2. a et b (en) Alex Biryukov, Encyclopedia of Cryptography and Security, Springer, Boston, MA, (DOI 10.1007/978-1-4419-5906-5_617, lire en ligne), p. 1221–1222
  3. a b c d e et f (en) Alex Biryukov et David Wagner, « Advanced Slide Attacks », Advances in Cryptology — EUROCRYPT 2000, Springer, Berlin, Heidelberg, série Lecture Notes in Computer Science,‎ , p. 589–606 (ISBN 3540455396, DOI 10.1007/3-540-45539-6_41, lire en ligne, consulté le 28 février 2018)
  4. (en) Edna K. Grossman et Bryant Tuckerman, « Analysis of a weakened Feistel-like cipher », International Conference on Communications, vol. 46, no. 1,‎ , p. 46.3.1-46.3.5
  5. (en) Eli Biham et Adi Shamir, « Differential Cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer », Advances in Cryptology — CRYPTO ’91, Springer, Berlin, Heidelberg, série Lecture Notes in Computer Science,‎ , p. 156–171 (ISBN 3540467661, DOI 10.1007/3-540-46766-1_11, lire en ligne, consulté le 28 février 2018)
  6. (en) Lars Ramkilde Knudsen, « Cryptanalysis of LOKI 91 », Advances in Cryptology — AUSCRYPT '92, Springer, Berlin, Heidelberg, série Lecture Notes in Computer Science,‎ , p. 196–208 (ISBN 3540572201, DOI 10.1007/3-540-57220-1_62, lire en ligne, consulté le 28 février 2018)
  7. (en) Gideon Yuval, « Reinventing the travois: Encryption/MAC in 30 ROM bytes », Fast Software Encryption, Springer, Berlin, Heidelberg, série Lecture Notes in Computer Science,‎ , p. 205–209 (ISBN 9783540632474, DOI 10.1007/bfb0052347, lire en ligne, consulté le 28 février 2018)
  8. A. Kircanski et A. M. Youssef, « A Related-Key Attack on TREYFER », 2008 Second International Conference on Emerging Security Information, Systems and Technologies,‎ , p. 213–217 (DOI 10.1109/securware.2008.51, lire en ligne, consulté le 28 février 2018)
  9. (en) Bruce Schneier, « Description of a new variable-length key, 64-bit block cipher (Blowfish) », Fast Software Encryption, Springer, Berlin, Heidelberg, série Lecture Notes in Computer Science,‎ , p. 191–204 (ISBN 3540581081, DOI 10.1007/3-540-58108-1_24, lire en ligne, consulté le 28 février 2018)
  10. (en) Eli Biham, Orr Dunkelman et Nathan Keller, « Improved Slide Attacks », Fast Software Encryption, Springer, Berlin, Heidelberg, série Lecture Notes in Computer Science,‎ , p. 153–166 (ISBN 9783540746171, DOI 10.1007/978-3-540-74619-5_10, lire en ligne, consulté le 28 février 2018)
  11. (en) Orhun Kara, « Reflection Cryptanalysis of Some Ciphers », Progress in Cryptology - INDOCRYPT 2008, Springer, Berlin, Heidelberg, série Lecture Notes in Computer Science,‎ , p. 294–307 (ISBN 9783540897538, DOI 10.1007/978-3-540-89754-5_23, lire en ligne, consulté le 28 février 2018)
  12. (en) Itai Dinur, Orr Dunkelman et Adi Shamir, Fast Software Encryption, Springer, Berlin, Heidelberg, coll. « Lecture Notes in Computer Science », (ISBN 978-3-642-34046-8 et 9783642340475, DOI 10.1007/978-3-642-34047-5_2, lire en ligne), p. 9–28