Cryptanalyse

La cryptanalyse est la technique qui consiste à déduire un texte en clair d’un texte chiffré sans posséder la clé de chiffrement. Le processus par lequel on tente de comprendre un message en particulier est appelé une attaque.

Marian Rejewski, Jerzy Różycki, et Henryk Zygalski 3 cryptanalistes polonais(ca. 1928-1932)

Une attaque est généralement caractérisée selon les données qu'elle nécessite :

• attaque sur texte chiffré seul (ciphertext-only attack en anglais) : le cryptanalyste possède des exemplaires chiffrés des messages, il peut faire des hypothèses sur les messages originaux qu'il ne possède pas. La cryptanalyse est plus ardue de par le manque d'informations à disposition ;
• attaque à texte clair connu (known-plaintext attack en anglais) : le cryptanalyste possède des messages ou des parties de messages en clair ainsi que les versions chiffrées. La cryptanalyse linéaire fait partie de cette catégorie ;
• attaque à texte clair choisi (chosen-plaintext attack en anglais) : le cryptanalyste possède des messages en clair, il peut créer les versions chiffrées de ces messages avec l'algorithme que l'on peut dès lors considérer comme une boîte noire. La cryptanalyse différentielle est un exemple d'attaque à texte clair choisi ;
• attaque à texte chiffré choisi (chosen-ciphertext attack en anglais) : le cryptanalyste possède des messages chiffrés et demande la version en clair de certains de ces messages pour mener l'attaque.

Familles d'attaques cryptanalytiques

Il existe plusieurs familles d'attaques cryptanalytiques, les plus connues étant l'analyse fréquentielle, la cryptanalyse différentielle et la cryptanalyse linéaire.

L'analyse fréquentielle

L'analyse fréquentielle, découverte au IX^e siècle par Al-Kindi, examine les répétitions des lettres du message chiffré afin de trouver la clé. Elle est inefficace contre les chiffrements modernes tels que DES, RSA, etc. Elle est principalement utilisée contre les chiffrements mono-alphabétiques qui substituent chaque lettre par une autre et qui présentent un biais statistique, c'est-à-dire que le cryptanalyste peut déduire quelles lettres sont représentées par quel(s) symbole(s) grâce à leur fréquence moyenne dans une langue naturelle donnée. Les messages plus longs sont plus vulnérables à ce type d'attaque.

L'indice de coïncidence

L'indice de coïncidence, inventé en 1920 par William F. Friedman, permet de calculer la probabilité de répétitions des lettres du message chiffré. Il est souvent couplé avec l'analyse fréquentielle. Cela permet de savoir le type de chiffrement d'un message (chiffrement mono-alphabétique ou poly-alphabétique) ainsi que la longueur probable de la clé.

L'attaque par mot probable

L'attaque par mot probable consiste à supposer l'existence d'un mot probable dans le message chiffré. Il est donc possible d'en déduire la clé du message si le mot choisi est correct. Ce type d'attaque a été mené contre la machine Enigma durant la Seconde Guerre mondiale.

L'attaque par dictionnaire

L'attaque par dictionnaire consiste à tester tous les mots d'une liste comme mot clé. Elle est souvent couplée à l'attaque par force brute.

L'attaque par force brute

L'attaque par force brute consiste à tester toutes les solutions possibles de mots de passe ou de clés. C'est le seul moyen de récupérer la clé dans les algorithmes les plus modernes et encore inviolés comme AES. Il est peu utilisé pour des mots de passe possédant un très grand nombre de caractères car le temps nécessaire au déchiffrement devient alors trop important.

Attaque par paradoxe des anniversaires

Le paradoxe des anniversaires est un résultat probabiliste qui est utilisé dans les attaques contre les fonctions de hachage. Ce paradoxe permet de donner une borne supérieure de résistance aux collisions d’une telle fonction. Cette limite est de l'ordre de la racine de la taille de la sortie, ce qui signifie que, pour un algorithme comme MD5 (empreinte sur 128 bits), trouver une collision quelconque avec 50 % de chance nécessite 2⁶⁴ hachages d'entrées distinctes.

Cryptanalyse moderne

Dès les années 1970 apparaissent les méthodes de chiffrement modernes par blocs comme DES. Il a été passablement étudié et attaqué, ce qui a causé des attaques majeures dans le monde de la cryptographie. Les méthodes présentées ci-dessous ne sont pas vraiment génériques et des modifications sont nécessaires pour attaquer un type de chiffrement donné.

Souvent, on ne s'attaque pas à une version complète de l'algorithme de chiffrement mais une variante avec moins de tours (dans le cas des schémas de type Feistel ou les fonctions de hachage). Cette analyse préliminaire, si elle permet de déceler des vulnérabilités, laisse entrevoir une attaque sur l'algorithme complet.

Cryptanalyse linéaire

La cryptanalyse linéaire, due à Mitsuru Matsui, consiste à faire une approximation linéaire de la structure interne de la méthode de chiffrement. Elle remonte à 1993 et s'avère être l'attaque la plus efficace contre DES. Les algorithmes plus récents sont insensibles à cette attaque.

Cryptanalyse différentielle

La cryptanalyse différentielle est une analyse statistique des changements dans la structure de la méthode de chiffrement à la suite d'une modification légère des entrées. Avec un très grand nombre de perturbations, il est possible d'extraire la clé. Cette attaque date de 1990 (présentée à la conférence Crypto 90). Elle est due à Eli Biham et Adi Shamir. Toutefois, on sait maintenant que les concepteurs de DES connaissaient une variante de cette attaque nommée attaque-T. Les algorithmes récents (AES, IDEA, etc.) sont conçus pour résister à ce type d'attaque. Les attaques différentielles sont aussi possibles sur les fonctions de hachage, moyennant des modifications dans la conduite de l'attaque. Une telle attaque a été menée contre MD5.

Cryptanalyse différentielle-linéaire

Introduite par Martin Hellman et Langford en 1994, la cryptanalyse différentielle-linéaire combine les deux principes. L'attaque différentielle produit une approximation linéaire de l'algorithme. Avec cette attaque, Hellman et Langford ont pu attaquer un DES de 8 rondes avec seulement 512 textes en clair et quelques secondes sur un PC de l'époque. Cette méthode a également été employée pour trouver des clés faibles dans IDEA. Ce type de cryptanalyse a été amélioré par Eli Biham en 2002.

Cryptanalyse χ²

La cryptanalyse χ², concept dû à Serge Vaudenay, permet d'obtenir des résultats similaires à des attaques linéaires ou différentielles. L'analyse statistique associée permet de s'affranchir des défauts de ces dernières en évitant d'avoir à connaître le fonctionnement exact du chiffrement.

Cryptanalyse quadratique

La cryptanalyse quadratique est une invention récente de Nicolas Courtois et Josef Pieprzyk. Cette attaque (nommée attaque XSL) vise en particulier AES et les autres chiffrements basés sur Rijndael. L'attaque XSL est le sujet de beaucoup de controverses quant à sa véritable efficacité de par sa nature heuristique. Elle consiste à résoudre un système d'équations de très grande taille.

Cryptanalyse modulo n

Suggérée par Bruce Schneier, David Wagner et John Kelsey en 1999, cette technique consiste à exploiter les différences de fonctionnement (selon une congruence variable) des algorithmes qui utilisent des rotations binaires.

Attaques par canal auxiliaire

Les attaques par canal auxiliaire font partie d'une vaste famille de techniques cryptanalytiques qui exploitent des propriétés inattendues d'un algorithme de cryptographie lors de son implémentation logicielle ou matérielle. En effet, une sécurité théorique ne garantit pas forcément une sécurité lors de l'utilisation en pratique. Les attaques portent sur différents paramètres : le temps, le bruit, la consommation électrique, etc.

Compromis temps/mémoire

Ce concept a été introduit par Martin Hellman en 1980. Il a été amélioré en 1993 par Philippe Oechslin avec le concept de table arc-en-ciel. Ce système lui a permis, entre autres, d'attaquer des mots de passe de session sur Windows, lorsqu'ils sont stockés au format LanManager, comme c'est encore le plus souvent le cas. Il s'agit d'un compromis entre une attaque par force brute et l'utilisation de dictionnaires. Une recherche exhaustive nécessite en effet beaucoup de temps et un dictionnaire de tous les mots de passe possibles nécessiterait énormément de place. Grâce à des procédés algorithmiques, cette méthode parvient à trouver un juste milieu entre ces deux principes par la construction de tables de taille gérable.

Attaques sur les modes opératoires

Les chiffrements par bloc comme DES ou AES ne peuvent chiffrer qu'un bloc de taille donnée (128 bits dans le cas d'AES). Pour chiffrer des données plus longues, on utilise des modes opératoires. Un mode opératoire est la manière de chaîner plusieurs blocs ensemble pour obtenir un chiffrement par flux. Par exemple, on peut découper les données en blocs de 128 bits et les chiffrer séparément. C'est le mode ECB qui est vulnérable parce que la présence de deux blocs chiffrés identiques indique que les deux blocs respectifs dans le message original sont également identiques. D'autres modes évitent ce problème, mais ils ne sont pas totalement exempts de vulnérabilités. On utilise alors des vecteurs d'initialisation, qui permettent d'éviter la répétition de séquences identiques entre plusieurs messages chiffrés.

Les chiffrements par flot (par exemple RC4) utilisent aussi un vecteur d'initialisation pour les mêmes raisons. Une telle attaque a été récemment menée à ce propos sur le chiffrement des documents de la suite Microsoft Office, qui emploie RC4. Le vecteur d'initialisation y est toujours le même pour un document donné. Ainsi, un grand nombre d'informations peut être récupéré en comparant le chiffré d'un document au chiffré de ce même document légèrement modifié.

Attaque par rencontre au milieu

Chiffrer deux fois avec le même algorithme mais via deux clés différentes n'est pas équivalent à un chiffrement avec une clé deux fois plus longue (dans le cas de DES, on ne passe pas de 2⁵⁶ à 2¹¹² opérations pour casser le chiffrement) à cause d'une attaque dite par rencontre au milieu, de type compromis temps-mémoire.

L'attaque fonctionne théoriquement de la façon suivante. Dans le cas d'un double chiffrement, on suppose connus un texte clair M et un texte chiffré C, C étant obtenu par deux applications d'un même chiffrement avec deux clés à priori distinctes. Il s'agit de déterminer un couple de clés qui permet de passer de M à C par double chiffrement. L'opération peut être réitérée sur d'autres couples de texte clair et texte chiffré, s'il ne reste pas qu'un seul couple de clés possibles. Les couples de clés candidates sont ceux qui permettent d'obtenir le même bloc par un seul chiffrement de M d'une part, par un seul déchiffrement de C d'autre part : c'est la rencontre au milieu.

Vue ainsi, l'attaque permet un compromis temps-mémoire. Pour toutes les clés possibles, elle nécessite de stocker le bloc obtenu en effectuant une seule opération de chiffrement sur M. Ensuite, pour toutes les clés possibles et pour chaque bloc obtenu en appliquant une seule opération de déchiffrement à C, il faut chercher parmi les blocs stockés lors de l'étape précédente un bloc identique.

Le couple des deux clés qui ont permis d'obtenir ce bloc intermédiaire (l'une en chiffrant M, l'autre en déchiffrant C) est alors candidat à être la clé du double chiffrement.

Dans le cas du DES et pour un bloc de donnée de 64 bits, la première étape demande 2⁵⁶ opérations de chiffrement (et un espace mémoire de 2⁵⁶ blocs de 64 bits), et la seconde, 2⁵⁶ opérations (plus à chaque fois la recherche du bloc).

La complexité de l'attaque par rencontre au milieu sur le double chiffrement a été seulement multipliée par 2 (en négligeant l'étape finale de comparaison) vis-à-vis de l'attaque par recherche exhaustive sur le chiffrement simple, tandis que l'attaque par force brute en fait le carré. Elle nécessite cependant un espace mémoire considérablement augmenté, mais certains ajustements sont possibles (ce sont des compromis temps-mémoire dits moins radicaux) si l'espace mémoire demandé est trop important.

L'attaque fonctionne également pour l'enchaînement de deux chiffrements différents, et il est possible de la pratiquer symétriquement.

Dans le cas de DES, on obtient une attaque théorique de l'ordre de 2⁵⁷ opérations de chiffrements, alors que sans modification, elle demanderait un espace mémoire de 2⁵⁶×64 bits. C'est à cause de cette attaque que le double DES n'est pas utilisé, mais aussi que l'on estime comme très fiable la sécurité du 3DES avec 3 clefs distinctes (168 bits) à 112 bits, car celui-ci demande un ordre de 2¹¹² opérations pour décrypter son chiffrement.

Attaques sur les systèmes asymétriques

Trouver la clé d'un chiffrement assuré par de la cryptographie asymétrique nécessite d'autres approches. Dans le cas de RSA, c'est la difficulté de la factorisation qui assure la résistance du chiffrement. Pour ElGamal, c'est le problème du logarithme discret qui est employé. Toutefois, certaines failles peuvent apparaître selon l'utilisation que l'on fait de ces algorithmes. RSA est vulnérable si des exposants de faible magnitude sont utilisés (attaques de Don Coppersmith et Wiener). Sous des conditions particulières, un surchiffrement avec RSA peut être attaqué. Le standard PKCS assure une utilisation plus robuste de RSA, même si les premières ébauches du standard étaient sensibles à des attaques par des canaux auxiliaires (Bleichenbacher).

Cryptanalyse quantique

Les ordinateurs quantiques, qui sont encore en phase de recherche et développement, pourront être utilisés en cryptanalyse.

L'algorithme de Shor pourrait servir à résoudre les problèmes de la factorisation et du logarithme discret en temps polynomial, brisant ainsi un grand nombre de cryptosystèmes à clé publique tels que RSA et ElGamal. Un projet de standardisation a été lancé par le NIST en 2016 afin de trouver des systèmes de chiffrement asymétrique qui pourraient résister à un attaquant doté d'un ordinateur quantique.

De même, l'algorithme de recherche de Grover permettrait d'accélérer quadratiquement les attaques sur les systèmes de chiffrement symétrique reposant sur le problème de recherche dans une base non ordonnée (voir la recherche de clé par force brute). Cependant, ce genre d'attaque peut facilement être contré en doublant la longueur de la clé.

Autres propriétés analysées

Certaines propriétés observées dans les algorithmes de chiffrement ne mènent pas forcément à des attaques mais permettent de déceler des faiblesses dans la conception, problèmes qui peuvent en cacher d'autres plus importants.

Clés faibles

Certains algorithmes sont susceptibles d'avoir des clés dites faibles. Si une telle clé est utilisée pour chiffrer un message une première fois et que l'on rechiffre le résultat, toujours avec la même clé, alors on obtient le message en clair. Plus formellement, E_k(E_k(m))=m. DES possède 4 clés de ce genre. Il y a aussi des clés dites semi-faibles. Dans ce cas, E_k1(E_k2(m))=m.

Biais statistique

On peut chercher si la structure de chiffrement produit des biais statistiques. En général, un algorithme de chiffrement est censé produire un résultat proche d'un générateur de nombres aléatoires uniformément distribués, de manière à donner le moins d'information possible et à maximiser l'entropie. Si un biais est observé (par exemple, on observe plus de bits à 1 que de bits à 0), alors des analyses supplémentaires peuvent parfois permettre de concevoir une attaque. On peut citer entre autres des attaques sur RC6 dont les permutations s'écartent sensiblement des caractéristiques normalement observées dans les générateurs de nombres pseudo-aléatoires.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Cryptanalysis » (voir la liste des auteurs).

Annexes

Articles connexes

• Histoire de la cryptologie
• Cryptographie
• Niveaux d'attaques

Liens externes

• Notice dans un dictionnaire ou une encyclopédie généraliste :

  • Britannica
• Notices d'autorité :

  • GND
• (en) Traité de cryptanalyse