Attaque biclique - Biclique attack

Une attaque biclique est une variante de la méthode MITM (Meet -in-the- middle) de cryptanalyse . Il utilise une structure biclique pour augmenter le nombre de cartouches éventuellement attaquées par l'attaque MITM. Puisque la cryptanalyse biclique est basée sur des attaques MITM, elle est applicable à la fois aux chiffrements par blocs et aux fonctions de hachage (itérées) . Les attaques bicliques sont connues pour avoir brisé à la fois AES complet et IDEA complet , mais avec un léger avantage sur la force brute. Il a également été appliqué au chiffrement KASUMI et à la résistance à la pré -image des fonctions de hachage Skein-512 et SHA-2 .

L'attaque biclique est toujours (en avril 2019) l'attaque à clé unique la plus connue du public contre AES . La complexité de calcul de l'attaque est , et pour AES128, AES192 et AES256, respectivement. Il s'agit de la seule attaque à clé unique publiquement connue contre AES qui attaque le nombre total de tours. Les attaques précédentes ont attaqué des variantes à tour réduit (généralement des variantes réduites à 7 ou 8 tours).

Étant donné la complexité de calcul de l'attaque , il s'agit d'une attaque théorique, ce qui signifie que la sécurité d'AES n'a pas été interrompue et que l'utilisation d'AES reste relativement sécurisée. L'attaque biclique est néanmoins une attaque intéressante, ce qui suggère une nouvelle approche pour effectuer une cryptanalyse sur des chiffrements par blocs. L'attaque a également rendu plus d'informations sur AES, car elle a remis en question la marge de sécurité du nombre de cartouches utilisées.

Histoire

L'attaque originale du MITM a été suggérée pour la première fois par Diffie et Hellman en 1977, lorsqu'ils ont discuté des propriétés cryptanalytiques du DES. Ils ont fait valoir que la taille de la clé était trop petite et que la réapplication du DES plusieurs fois avec des clés différentes pourrait être une solution à la taille de la clé; cependant, ils ont déconseillé d'utiliser au minimum le double DES et le triple-DES suggéré, en raison des attaques MITM (les attaques MITM peuvent facilement être appliquées au double-DES pour réduire la sécurité de à juste , car on peut indépendamment bruteforce deuxième cryptage DES s'ils ont le texte clair et chiffré).

Depuis que Diffie et Hellman ont suggéré des attaques MITM, de nombreuses variantes sont apparues qui sont utiles dans les situations où l'attaque de base MITM est inapplicable. La variante d'attaque biclique a été suggérée pour la première fois par Dmitry Khovratovich , Rechberger et Savelieva pour une utilisation avec la cryptanalyse à fonction de hachage. Cependant, ce sont Bogdanov, Khovratovich et Rechberger qui ont montré comment appliquer le concept de bicliques au paramètre de clé secrète, y compris la cryptanalyse par chiffrement par bloc, lorsqu'ils ont publié leur attaque sur AES. Auparavant, les attaques MITM contre AES et de nombreux autres chiffrements par blocs avaient reçu peu d'attention, principalement en raison du besoin de bits de clé indépendants entre les deux `` sous-chiffrements MITM '' afin de faciliter l'attaque MITM - ce qui est difficile à réaliser avec beaucoup les horaires clés modernes, comme celui d'AES.

Le biclique

Pour une explication générale de ce qu'est une structure biclique, consultez l'article sur les bicliques .

Dans une attaque MITM, les keybits et , appartenant au premier et au second sous-chiffrement, doivent être indépendants; c'est-à-dire qu'ils doivent être indépendants les uns des autres, sinon les valeurs intermédiaires correspondantes pour le texte brut et chiffré ne peuvent pas être calculées indépendamment dans l'attaque MITM (il existe des variantes d'attaques MITM, où les blocs peuvent avoir des bits-clés partagés. Voir l' attaque MITM en 3 sous-ensembles ). Cette propriété est souvent difficile à exploiter sur un plus grand nombre de tours, du fait de la diffusion du chiffrement attaqué. En termes simples: plus vous attaquez de rounds, plus vous aurez de sous-cryptages. Plus vous avez de sous-chiffrements volumineux, moins il vous faudra de bits de clé indépendants entre les sous-chiffrements à forcer indépendamment. Bien entendu, le nombre réel de bits de clé indépendants dans chaque sous-chiffrement dépend des propriétés de diffusion du programme de clé.

La façon dont le biclique aide à résoudre ce qui précède est qu'il permet, par exemple, d'attaquer 7 rounds d'AES en utilisant des attaques MITM, puis en utilisant une structure biclique de longueur 3 (c'est-à-dire qu'il couvre 3 rounds du chiffre), vous pouvez mapper l'état intermédiaire au début du tour 7 à la fin du dernier tour, par exemple 10 (si c'est AES128), attaquant ainsi le nombre total de tours du chiffrement, même s'il n'était pas possible d'attaquer ce montant de rounds avec une attaque MITM de base.

Le sens de la biclique est donc de construire efficacement une structure, qui peut mapper une valeur intermédiaire à la fin de l'attaque MITM sur le texte chiffré à la fin. Le texte chiffré auquel l'état intermédiaire est mappé à la fin dépend bien sûr de la clé utilisée pour le chiffrement. La clé utilisée pour mapper l'état au texte chiffré dans la biclique, est basée sur les keybits brutalisés dans le premier et le deuxième sous-chiffrement de l'attaque MITM.

L'essence des attaques bicliques est donc, outre l'attaque MITM, de pouvoir construire efficacement une structure biclique, cela dépendant des keybits et de pouvoir mapper un certain état intermédiaire sur le texte chiffré correspondant.

Comment construire le biclique

Force brute

Obtenez des états intermédiaires et des textes chiffrés, puis calculez les clés qui les mappent. Cela nécessite des récupérations de clé, car chaque état intermédiaire doit être lié à tous les textes chiffrés.

Différentiels clés liés indépendants

(Cette méthode a été suggérée par Bogdanov, Khovratovich et Rechberger dans leur article: Biclique Cryptanalysis of the Full AES)

Préliminaire:
rappelez-vous que la fonction de la biclique est de mapper les valeurs intermédiaires,, aux valeurs de texte chiffré,, en fonction de la clé telle que:

Procédure:
Première étape: un état intermédiaire ( ), un texte chiffré ( ) et une clé ( ) sont choisis tels que:, où est la fonction qui mappe un état intermédiaire à un texte chiffré en utilisant une clé donnée. Ceci est désigné comme le calcul de base.

Deuxième étape: deux ensembles de clés de taille associées sont choisis. Les clés sont choisies de telle sorte que:

  • Le premier ensemble de clés sont des clés, qui remplissent les exigences différentielles suivantes par rapport au calcul de base:
  • Le deuxième ensemble de clés sont des clés, qui remplissent les exigences différentielles suivantes par rapport au calcul de base:
  • Les clés sont choisies de telle sorte que les traînées des - et -différentiels soient indépendantes - c'est-à-dire qu'elles ne partagent aucune composante non linéaire active.

En d'autres termes:
une différence d'entrée de 0 doit correspondre à une différence de sortie inférieure à une différence clé de . Toutes les différences concernent le calcul de base. Une différence d'entrée de doit correspondre à une différence de sortie de 0 sous une différence de clé de . Toutes les différences concernent le calcul de base.

Troisième étape: Étant donné que les sentiers ne partagent pas tous les composants non-linéaires (tels que S-boîtes), les pistes peuvent être combinés pour obtenir: , qui est conforme aux définitions des deux différentiels de l' étape 2. Il est trivial de voir que le tuple du calcul de base est également conforme par définition aux deux différentiels, comme le sont les différentiels par rapport au calcul de base. Substituer dans l'une des deux définitions, donnera depuis et . Cela signifie que le tuple du calcul de base peut également être XOR aux chemins combinés:



Étape quatre: Il est trivial de voir que: Si cela est substitué dans les traînées différentielles combinées ci-dessus, le résultat sera: Ce qui est le même que la définition, il y avait plus tôt pour un biclique:






Il est ainsi possible de créer un biclique de taille ( puisque toutes les clés du premier jeu de clés, peuvent être combinées avec les clés du deuxième jeu de clés). Cela signifie qu'un biclique de taille peut être créé en utilisant uniquement des calculs des différentiels et plus . Si pour alors toutes les clés seront également différentes dans le biclique.

C'est ainsi que le biclique est construit dans la principale attaque biclique sur AES. Il existe quelques limitations pratiques dans la construction de bicliques avec cette technique. Plus le biclique est long, plus les pistes différentielles doivent couvrir de tours. Les propriétés de diffusion du chiffre, jouent ainsi un rôle crucial dans l'efficacité de la construction de la biclique.

Autres manières de construire le biclique

Bogdanov, Khovratovich et Rechberger décrivent également une autre façon de construire le biclique, appelée «Interleaving Related-Key Differential Trails» dans l'article: «Biclique Cryptanalysis of the Full AES».

Procédure d'analyse cryptographique Biclique

Première étape: l'attaquant regroupe toutes les clés possibles en sous-ensembles de clés de taille pour certains , où la clé d'un groupe est indexée comme dans une matrice de taille . L'attaquant divise le chiffrement en deux sous-chiffrements, et (tels que ), comme dans une attaque MITM normale. L'ensemble de clés pour chacun des sous-chiffrements est de cardinalité et est appelé et . La clé combinée des sous-chiffrements est exprimée avec la matrice susmentionnée .

Deuxième étape: l'attaquant crée un biclique pour chaque groupe de clés. Le biclique est de dimension-d, car il mappe les états internes ,, aux textes chiffrés,, à l' aide de clés. La section "Comment construire le biclique" suggère comment construire le biclique en utilisant des "Différentiels de clés liées indépendantes". Le biclique est dans ce cas construit en utilisant les différentiels de l'ensemble de clés, et , appartenant aux sous-chiffrements.

Troisième étape: L'attaquant prend les cryptogrammes possibles, et demande un décryptage-oracle de fournir les plaintexts correspondants, .

Quatrième étape: l'attaquant choisit un état interne et le texte en clair correspondant , et exécute l'attaque MITM habituelle par-dessus et en attaquant à partir de l'état interne et du texte en clair.

Cinquième étape: chaque fois qu'une clé candidate est trouvée qui correspond à , cette clé est testée sur une autre paire de texte clair / chiffré. si la clé valide sur l'autre paire, il est fort probable que ce soit la bonne clé.

Exemple d'attaque

L'exemple suivant est basé sur l'attaque biclique sur AES de l'article "Biclique Cryptanalysis of the Full AES".
Les descriptions de l'exemple utilisent la même terminologie que celle utilisée par les auteurs de l'attaque (c'est-à-dire pour les noms de variables, etc.).
Pour simplifier, c'est l'attaque de la variante AES128 qui est abordée ci-dessous.
L'attaque consiste en une attaque MITM de 7 rounds avec le biclique couvrant les 3 derniers rounds.

Partitionnement des clés

L'espace clé est partitionné en groupes de clés, où chaque groupe se compose de clés. Pour chacun des groupes, une clé de base unique pour le calcul de base est sélectionnée. La clé de base a deux octets spécifiques mis à zéro, indiqués dans le tableau ci-dessous (qui représente la clé de la même manière qu'AES le fait dans une matrice 4x4 pour AES128):


Les 14 octets restants (112 bits) de la clé sont ensuite énumérés. Cela produit des clés de base uniques; un pour chaque groupe de clés. Les clés ordinaires de chaque groupe sont ensuite choisies par rapport à leur clé de base. Ils sont choisis de telle sorte qu'ils soient presque identiques à la clé de base. Ils ne varient que dans 2 octets (le 's ou le ' s) des 4 octets ci-dessous:

Cela donne et qui donne combiné des clés différentes, . ces clés constituent les clés du groupe pour une clé de base respective.

Construction biclique

bicliques est construit en utilisant la technique des "Différentiels de clés liées indépendantes", comme décrit dans la section "Comment construire le biclique".
La condition pour utiliser cette technique était que les traînées différentielles avant et arrière qui doivent être combinées ne partageaient aucun élément non linéaire actif. Comment sait-on que c'est le cas?
En raison de la manière dont les clés à l'étape 1 sont choisies par rapport à la clé de base, les traînées différentielles utilisant les clés ne partagent jamais de S-box actives (qui est le seul composant non linéaire dans AES), les traînées différentielles utilisant clé . Il est donc possible de XOR les traînées différentielles et de créer la biclique.

Attaque MITM

Lorsque les bicliques sont créées, l'attaque MITM peut presque commencer. Avant de procéder à l'attaque MITM, les valeurs intermédiaires à partir du texte en clair: , les valeurs intermédiaires à partir du cryptogramme: , et les états intermédiaires et des sous-clés correspondant ou , sont précalculées et stockées, en revanche.



L'attaque MITM peut maintenant être effectuée. Pour tester une clé , il suffit de recalculer les parties du chiffrement, dont on sait qu'elles varieront entre et . Pour le calcul en arrière de à , ce sont 4 S-boîtes qui doivent être recalculées. Pour le calcul avant de à , il n'est que de 3 (une explication détaillée de la quantité de recalcul nécessaire peut être trouvée dans l'article "Biclique Cryptanalysis of the full AES", d'où cet exemple est tiré).

Lorsque les valeurs intermédiaires correspondent, un candidat clé entre et est trouvé. Le candidat clé est ensuite testé sur une autre paire de texte clair / chiffré.

Résultats

Cette attaque réduit la complexité de calcul d'AES128 à , qui est 3 à 5 fois plus rapide qu'une approche bruteforce. La complexité des données de l'attaque est et la complexité de la mémoire est .

Les références