Cryptanalyse

Infos
La cryptanalyse s'oppose, en quelque sorte, à la cryptographie. En effet, si déchiffrer consiste à retrouver le clair au moyen d'une clé, cryptanalyser c'est tenter de se passer de cette dernière. Même si on décrit les cryptanalystes comme des « briseurs de codes », il convient de remarquer qu'un algorithme est considéré comme cassé lorsqu'une attaque permet de retrouver la clé en effectuant moins d'opérations que via une attaque par force bru
Cryptanalyse

La cryptanalyse s'oppose, en quelque sorte, à la cryptographie. En effet, si déchiffrer consiste à retrouver le clair au moyen d'une clé, cryptanalyser c'est tenter de se passer de cette dernière. Même si on décrit les cryptanalystes comme des « briseurs de codes », il convient de remarquer qu'un algorithme est considéré comme cassé lorsqu'une attaque permet de retrouver la clé en effectuant moins d'opérations que via une attaque par force brute. L'algorithme ainsi cassé ne devient pas inutile pour autant, mais son degré de sécurité, c'est-à-dire le nombre moyen d'opérations nécessaires pour le déchiffrer, s'affaiblit. Une attaque est souvent caractérisée par les données qu'elle nécessite :
- attaque sur texte chiffré seul (ciphertext-only) : 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) : 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) : le cryptanalyste possède des messages en clair, il peut générer 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) : le cryptanalyste possède des messages chiffrés et demande la version en clair de certains de ces messages pour mener l'attaque. voir l'article principal : Niveaux d'attaques

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 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. 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.

L'indice de coïncidence

L'indice de coïncidence 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ée 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 utiliser pour des mots de passes possedant un tres grand nombre de caracteres car le temps necesaire devient tres important. De même plusieur brevets rendent cette methode inefficace, comme celui de Bell ou d'IBM.

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 264 hachages d'entrées distinctes.

Cryptanalyse moderne

Dès les années 70 apparaissent les méthodes de chiffrement modernes par blocs comme DES. Il sera passablement étudié et attaqué ce qui mènera à 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 sur 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 après avoir légèrement modifié les 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 tronquée

Comme son nom l'indique, une telle cryptanalyse s'intéresse à des différences qui n'affectent qu'une partie des variables considérées.

Cryptanalyse différentielle d'ordre supérieur

La cryptanalyse différentielle originale est une différentielle de premier ordre. En introduisant l'équivalent des dérivées dans les fonctions cryptographiques, on peut mener une cryptanalyse avec des degrés supérieurs. Ce sont des « différences de différences de ... ». Voir pour les définitions formelles et un exemple d'attaque.

Cryptanalyse par différentielles impossibles

Au lieu de chercher les différences probables, on inverse le problème et l'on cherche les différences qui ne se produiront pas.

L'attaque boomerang

L'attaque boomerang est une version améliorée de la cryptanalyse différentielle inventée par David Wagner. Elle consiste à attaquer les deux moitiés d'un algorithme de chiffrement par bloc et part du principe que certaines propriétés, après perturbations des entrées, ne se propagent pas à travers toute la structure.

L'attaque rectangle

L'attaque rectangle est une extension de l'attaque boomerang, elle a été inventée en 2001 par Eli Biham et son équipe pour attaquer leur chiffrement Serpent, candidat pour le standard AES.

Cryptanalyse différentielle-linéaire

Introduite par Martin Hellman et Langford, 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ée par Eli Biham en 2002. Voir pour plus d'informations.

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. Voir cryptanalyse mod n pour l'article complet.

Attaques par canaux auxiliaires

voir l'article principal : attaque par canaux auxiliaires On distingue plusieurs attaques qui appartiennent à ce genre. Elles consistent à exploiter des propriétés inattendues d'un algorithme lors de sa mise en œuvre. En effet, une sécurité « mathématique » ne garantit pas forcément une sécurité lors de l'utilisation en « pratique ». Dans ce domaine, les attaques sont nombreuses et portent sur différents paramètres :
- temps mis pour effectuer certaines opérations (attaque temporelle)
- le bruit généré par un ordinateur qui chiffre, le processeur émet du bruit qui varie selon sa consommation et les opérations effectuées (cryptanalyse acoustique)
- la consommation électrique (analyse de consommation)
- introduction volontaire d'erreurs dans le système pour provoquer certains comportements révélateurs (attaque par faute) Une attaque basée sur les temps de réponse a été menée par Serge Vaudenay sur TLS/SSL, ce qui a forcé les concepteurs du standard à faire une mise à jour critique. Les constructeurs de puces de chiffrement visent à aplanir la courbe de consommation électrique pour dissimuler les opérations sous-jacentes.

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, qui lui a permis par exemple d'attaquer les mots de passe de sessions Windows, lorsqu'ils sont stockés au format LanManager, comme c'est encore le cas le plus souvent. 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 alors qu'un dictionnaire de tous les mots de passe possibles nécessiterait énormément de place. Grâce à des procédés algorithmiques, on cherche à trouver un juste milieu entre ces deux principes, en construisant des 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 puisque 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 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 Office de Microsoft, qui emploie RC4. Le vecteur d'initialisation y est toujours le même pour un document donné ; un grand nombre d'informations peuvent donc être récupérées en comparant le résultat du chiffrement d'un document après légère modification .

Attaque par rencontre au milieu

Chiffrer deux fois avec le même algorithme mais via deux clés différentes est une ouverture à une attaque de type rencontre au milieu. Contrairement à ce que l'on peut penser de prime abord, le chiffrement obtenu n'est pas équivalent à un chiffrement avec une clé deux fois plus longue (on ne passe pas de 256 à 2112 dans le cas de DES). Il suffit en effet d'essayer toutes les clés pour déchiffrer la première étape. On obtient un résultat, toujours chiffré, qui se trouve entre les deux blocs de chiffrement. Ce résultat est soumis à son tour à une recherche exhaustive avec toutes les clés possibles. Au final, la complexité est seulement multipliée par deux. Dans le cas de DES, on obtient une résistance de l'ordre de 257, c'est pourquoi on utilise 3DES qui a une complexité finale de 2112 opérations (malgré une clé plus longue de 3
-56 bits). Grâce à trois chiffrements, chaque sortie du deuxième bloc de chiffrement doit être essayée avec toutes les clés, ce qui augmente considérablement le nombre de possibilités.

Attaques sur les systèmes asymétriques

Casser 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).
- Attaque temporelle

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.

Les 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, Ek(Ek(m))=m. DES possède 4 clés de ce genre. Il y a aussi des clés dites semi-faibles. Dans ce cas, Ek1(Ek2(m))=m. Voir l'article principal : clé faible.

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. Citons 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.

Voir aussi

===
Sujets connexes
Adi Shamir   Algorithmique   Analyse de consommation (cryptographie)   Analyse fréquentielle   Attaque XSL   Attaque boomerang   Attaque par dictionnaire   Attaque par faute   Attaque par force brute   Attaque par mot probable   Attaque rectangle   Attaque temporelle   Biais   Bruce Schneier   Clé de chiffrement   Clé faible (cryptographie)   Congruence   Cryptanalyse acoustique   Cryptanalyse d'Enigma   Cryptanalyse différentielle   Cryptanalyse différentielle-linéaire   Cryptanalyse linéaire   Cryptanalyse χ²   Cryptographie   Cryptographie asymétrique   Cryptosystème de ElGamal   Data Encryption Standard   David Wagner   Don Coppersmith   Déchiffrer   Dérivée   Eli Biham   Entropie   Factorisation   Histoire de la cryptanalyse   Indice de coïncidence   John Kelsey   Josef Pieprzyk   Logarithme discret   MD5   Martin Hellman   Microsoft   Mise en œuvre   Mitsuru Matsui   Mode opératoire   Nicolas Courtois   Niveaux d'attaques   Office   PKCS   Paradoxe des anniversaires   RC4   RC6   Rijndael   Rivest Shamir Adleman   Seconde Guerre mondiale   Serge Vaudenay   Serpent (cryptographie)   Standard de chiffrement avancé   Surchiffrement   TLS   Table arc-en-ciel   Transport Layer Security   Triple DES   Vecteur d'initialisation  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^