Skip to content
Retour aux résultats

Cryptanalyse linéaire

Introduite par
Mitsuru Matsui
Année
1993
Type
linear approximation attack
Famille
Cryptanalytic technique

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

La cryptanalyse linéaire est une attaque à texte clair connu qui exploite les approximations linéaires des transformations non linéaires d'un chiffrement pour récupérer des bits de clé secrète.

Introduite par Mitsuru Matsui en 1993, la cryptanalyse linéaire permet des attaques pratiques sur des chiffrements comme le DES avec une complexité de calcul inférieure à celle de la force brute. La technique analyse les biais statistiques dans la manière dont les combinaisons linéaires de bits de texte clair et de texte chiffré se rapportent aux bits de clé, permettant la récupération de clé avec des exigences de données réduites.

L’intuition derrière la méthode

La cryptanalyse linéaire trouve des équations linéaires reliant les bits de texte clair, les bits de texte chiffré et les bits de clé. En raison d'un mélange non parfait dans les rondes du chiffrement, ces équations linéaires sont valides avec une probabilité légèrement supérieure au hasard. En collectant de nombreuses paires texte clair-texte chiffré et en observant quelles valeurs de clé font que ces équations sont valides plus souvent, l'attaquant peut réduire l'ensemble des clés possibles pour trouver la bonne.

Histoire

La cryptanalyse linéaire a été introduite par Matsui en 1993 comme une attaque à texte clair connu sur le DES. En 1994, Matsui a démontré la première cryptanalyse expérimentale du standard DES en utilisant la cryptanalyse linéaire, récupérant une clé avec 2^43 textes clairs connus. Cette percée a démontré des attaques pratiques contre un standard déployé et a influencé le développement de l'AES avec des bornes de résistance prouvées.

Quand l’utiliser

La cryptanalyse linéaire est utilisée dans la recherche en cryptanalyse et l'évaluation de la conception de chiffrements. Elle guide les concepteurs de chiffrements dans le choix des S-boxes et des transformations qui résistent aux approximations linéaires. Les chiffrements modernes sont conçus avec des bornes prouvées sur la force de l'approximation linéaire.

Limites et points d’attention

  • Les chiffrements modernes (AES) sont soigneusement conçus pour résister à la cryptanalyse linéaire avec des bornes prouvables
  • Nécessite des paires texte clair-texte chiffré connues, qui peuvent ne pas être disponibles dans tous les scénarios
  • Les exigences computationnelles et de données peuvent dépasser la faisabilité pratique pour les chiffrements bien conçus
  • La découverte d'approximations linéaires fortes pour les chiffrements modernes est extrêmement difficile

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Attaque pratique sur le DES nécessitant 2^43 paires texte clair-texte chiffré et 2^39 opérations
  • Cadre mathématique bien formalisé (lemme d'empilement) pour l'analyse des biais d'approximation
  • Complète la cryptanalyse différentielle, en trouvant des faiblesses que l'analyse différentielle pourrait manquer
  • Façonne les exigences de conception de chiffrement pour la sélection des S-boxes et la transformation des rondes

Applications

  • Cryptanalyse des chiffrements par blocs évaluant les propriétés de sécurité dans la recherche et la normalisation
  • Conception de chiffrements et sélection de S-boxes pour assurer des bornes d'approximation linéaire adéquates
  • Validation des standards cryptographiques (NIST, ETSI) nécessitant une analyse de la résistance linéaire
  • Évaluation des chiffrements hérités pour les décisions de retrait et de remplacement

Comment ça marche

Comment ça marche

1

Trouver des approximations linéaires : des relations linéaires entre les bits de texte clair, les bits de texte chiffré et les bits de clé qui sont valides avec une probabilité significativement différente de 0,5.

2

Estimer le biais (déviation par rapport à 0,5) de chaque approximation linéaire en utilisant l'analyse statistique des transformations de ronde.

3

Pour les valeurs de clé candidates, compter la fréquence à laquelle l'approximation linéaire est valide dans les paires texte clair-texte chiffré connues. La clé correcte est celle qui rend l'approximation valide le plus fréquemment.

4

Vérifier les bits de clé récupérés en déchiffrant le texte chiffré et en vérifiant l'exactitude.

Pièges courants

  • Supposer que toutes les approximations linéaires sont exploitables ; les approximations faibles n'offrent qu'un avantage minimal
  • Sous-estimer la difficulté pratique de l'attaque lorsque les exigences théoriques en matière de données semblent raisonnables
  • Négliger l'interaction entre les propriétés linéaires et différentielles dans l'analyse des chiffrements

Questions fréquentes

Qu'est-ce que le lemme d'empilement ?

Le lemme d'empilement fournit une méthode pour calculer le biais des approximations linéaires sur plusieurs rondes en combinant les biais des approximations de rondes individuelles. Il est fondamental pour la cryptanalyse linéaire.

Comment l'AES résiste-t-il à la cryptanalyse linéaire ?

L'AES utilise des S-boxes choisies pour minimiser la probabilité maximale d'approximation linéaire et une couche de diffusion assurant une diffusion rapide des biais linéaires à travers les rondes. Des bornes prouvées garantissent l'absence d'approximations linéaires pratiques.

Quelle est la différence entre la cryptanalyse linéaire et différentielle ?

L'analyse différentielle étudie les différences entrée-sortie, tandis que l'analyse linéaire étudie les approximations linéaires (XOR des bits de texte clair et de texte chiffré). Les deux exploitent les faiblesses structurelles des chiffrements.

La cryptanalyse linéaire peut-elle casser les chiffrements modernes ?

Pas de manière pratique. Les chiffrements modernes comme l'AES ont des bornes prouvables sur les approximations linéaires, rendant les attaques infaisables sur le plan computationnel.

Comment évaluer la résistance linéaire dans la conception de mon chiffrement ?

Analysez les tables d'approximation linéaire des S-boxes et calculez le biais maximal à travers les rondes en utilisant le lemme d'empilement. Assurez-vous que le biais maximal est négligeable pour toutes les approximations linéaires possibles.

Méthodes associées

Sources

  1. Matsui, M. (1993). Linear cryptanalysis method for DES cipher. In Advances in Cryptology - EUROCRYPT 1993, LNCS 765, pp. 386-397.

    Ouvrir la référence DOI
    Copié.
  2. Matsui, M. (1994). The first experimental cryptanalysis of the Data Encryption Standard. In Advances in Cryptology - CRYPTO 1994, LNCS 839, pp. 1-11.

    Ouvrir la référence DOI
    Copié.