Attaque de rebond - Rebound attack

L' attaque par rebond est un outil de cryptanalyse des fonctions de hachage cryptographique . L'attaque a été publiée pour la première fois en 2009 par Florian Mendel, Christian Rechberger, Martin Schläffer et Søren Thomsen. Il a été conçu pour attaquer des fonctions similaires à AES telles que Whirlpool et Grøstl , mais il a ensuite été démontré qu'il était également applicable à d'autres conceptions telles que Keccak , JH et Skein .

L'attaque

L'attaque de rebond est un type d'attaque statistique sur les fonctions de hachage , utilisant des techniques telles que la cryptanalyse rotationnelle et différentielle pour trouver des collisions et d'autres propriétés intéressantes.

L'idée de base de l'attaque est d'observer une certaine caractéristique différentielle dans un chiffrement par blocs (ou dans une partie de celui-ci), une permutation ou un autre type de primitive . La recherche de valeurs répondant à la caractéristique est obtenue en divisant la primitive en trois parties telles que . s'appelle la phase entrante et et ensemble s'appellent la phase sortante. L'attaquant choisit alors des valeurs qui réalisent une partie de la caractéristique différentielle dans la phase entrante de manière déterministe, et remplissent le reste de la caractéristique de manière probabiliste. ${\ displaystyle E}$${\ displaystyle E = E _ {\ text {fw}} \ circ E _ {\ text {in}} \ circ E _ {\ text {bw}}}$${\ displaystyle E _ {\ text {in}}}$${\ displaystyle E _ {\ text {fw}}}$${\ displaystyle E _ {\ text {bw}}}$

Ainsi, l'attaque de rebond se compose de 2 phases:

1. La phase entrante (ou match-in-the-middle) , couvre la partie de la caractéristique différentielle qui est difficile à satisfaire de manière probabiliste. Le but ici est de trouver de nombreuses solutions pour cette partie de la caractéristique avec une complexité moyenne faible . Pour y parvenir, le système d'équations correspondant, qui décrit la caractéristique dans cette phase, doit être sous-déterminé. Lors de la recherche d'une solution, il existe donc de nombreux degrés de liberté, donnant de nombreuses solutions possibles. La phase entrante peut être répétée plusieurs fois pour obtenir un nombre suffisant de points de départ pour que la phase sortante réussisse.
2. Dans la phase sortante, chaque solution de la phase entrante est propagée vers l'extérieur dans les deux sens, tout en vérifiant si la caractéristique tient également dans cette phase. La probabilité de la caractéristique dans la phase sortante doit être aussi élevée que possible.

L'avantage d'utiliser une phase entrante et deux phases sortante est la possibilité de calculer les parties difficiles de la caractéristique différentielle dans la phase entrante d'une manière efficace. De plus, il garantit une probabilité élevée dans la phase sortante. La probabilité globale de trouver une caractéristique différentielle devient donc plus élevée que l'utilisation de techniques différentielles standard.

Description détaillée de l'attaque des fonctions de hachage avec des fonctions de compression de type AES

Considérons une fonction de hachage qui utilise un chiffrement par bloc de substitution-permutation de type AES comme fonction de compression . Cette fonction de compression consiste en un certain nombre de tours composés de S-boîtes et de transformations linéaires. L'idée générale de l'attaque est de construire une caractéristique différentielle qui a sa partie la plus coûteuse en calcul au milieu. Cette partie sera alors couverte par la phase entrante, tandis que la partie la plus facile à réaliser de la caractéristique est couverte dans la phase sortante. Le système d'équations, qui décrivent la caractéristique dans la phase entrante, devrait être sous- déterminé , de sorte que de nombreux points de départ pour la phase sortante puissent être générés. Puisque la partie la plus difficile de la caractéristique est contenue dans la phase entrante, il est possible d'utiliser ici des différentiels standard, alors que des différentiels tronqués sont utilisés dans la phase sortante pour obtenir des probabilités plus élevées.

La phase entrante aura généralement quelques nombres d' octets d' état actifs ( octets avec des différences non nulles) au début, qui se propagent ensuite à un grand nombre d' octets actifs au milieu du tour, avant de revenir à un faible nombre d' octets actifs octets à la fin de la phase. L'idée est d'avoir le grand nombre d' octets actifs à l'entrée et à la sortie d'une S-box au milieu de la phase. Les caractéristiques peuvent ensuite être calculées efficacement en choisissant des valeurs pour les différences au début et à la fin de la phase entrante, en les propageant vers le milieu et en recherchant des correspondances dans l'entrée et la sortie de la S-box . Pour les chiffrements comme AES, cela peut généralement être fait par ligne ou par colonne, ce qui rend la procédure relativement efficace. Le choix de valeurs de début et de fin différentes conduit à de nombreuses caractéristiques différentielles différentes dans la phase entrante.

Dans la phase sortante, l'objectif est de propager les caractéristiques trouvées dans la phase entrante vers l'arrière et vers l'avant, et de vérifier si les caractéristiques souhaitées sont respectées. Ici, des différentiels tronqués sont généralement utilisés, car ils donnent des probabilités plus élevées, et les valeurs spécifiques des différences ne sont pas pertinentes pour l'objectif de trouver une collision . La probabilité que la caractéristique suive le modèle souhaité de la phase sortante dépend du nombre d' octets actifs et de la manière dont ils sont disposés dans la caractéristique. Pour obtenir une collision , il ne suffit pas que les différentiels de la phase sortante soient d'un type spécifique; tous les octets actifs au début et à la fin de la caractéristique doivent également avoir une valeur telle que toute opération d'anticipation est annulée. Par conséquent, lors de la conception de la caractéristique, un nombre quelconque d' octets actifs au début et à la fin de la phase sortante doit être à la même position. La probabilité que ces octets s'annulent s'ajoute à la probabilité de la caractéristique sortante.

Dans l'ensemble, il est nécessaire de générer suffisamment de caractéristiques dans la phase entrante pour obtenir un nombre attendu de caractéristiques correctes supérieur à un dans la phase sortante. De plus, des quasi-collisions sur un plus grand nombre de rounds peuvent être obtenues en commençant et en terminant la phase sortante avec plusieurs octets actifs qui ne s'annulent pas.

Exemple d'attaque sur Whirlpool

L'attaque rebond peut être utilisée contre la fonction de hachage Whirlpool pour trouver des collisions sur des variantes où la fonction de compression (le chiffrement par bloc de type AES , W) est réduite à 4,5 ou 5,5 tours. Les quasi-collisions peuvent être trouvées sur 6,5 et 7,5 coups. Voici une description de l'attaque de 4,5 rounds.

Pré-calcul

Nombre de solutions	La fréquence
0	39655
2	20018
4	5043
6	740
8	79
256	1

Pour rendre l'attaque de rebond efficace, une table de recherche pour les différences de S-box est calculée avant l'attaque. Laissez représenter la boîte S- . Ensuite, pour chaque paire, nous trouvons les solutions (s'il y en a) à l'équation ${\ displaystyle S: \ {0,1 \} ^ {8} \ à \ {0,1 \} ^ {8}}$${\ displaystyle (a, b) \ in \ {0,1 \} ^ {8}}$${\ displaystyle x}$

${\ Displaystyle S (x) \ oplus S (x \ oplus a) = b}$,

où représente la différence d'entrée et représente la différence de sortie de la S-box . Cette table de 256 x 256 (appelée table de distribution des différences, DDT) permet de trouver des valeurs qui suivent la caractéristique pour toutes les paires d'entrée / sortie spécifiques qui passent par la S-box . Le tableau de droite montre le nombre possible de solutions à l'équation et leur fréquence. La première ligne décrit les différentiels impossibles, tandis que la dernière ligne décrit le différentiel nul. ${\ displaystyle a}$${\ displaystyle b}$

Réaliser l'attaque

Pour trouver une collision sur 4,5 coups de Whirlpool , une caractéristique différentielle du type indiqué dans le tableau ci-dessous doit être trouvée. Cette caractéristique a un minimum d'octets actifs (octets avec des différences non nulles), marqués en rouge. La caractéristique peut être décrite par le nombre d'octets actifs dans chaque tour, par exemple 1 → 8 → 64 → 8 → 1 → 1.

Caractéristique différentielle tronquée sur la fonction de hachage Whirlpool de 4,5 tours.

${\ displaystyle E _ {\ text {bw}}}$
${\ displaystyle E _ {\ text {in}}}$
${\ displaystyle E _ {\ text {fw}}}$

La phase entrante

Le but de la phase entrante est de trouver des différences qui remplissent la partie de la caractéristique décrite par la séquence d'octets actifs 8 → 64 → 8. Cela peut être fait en trois étapes:

1. Choisissez une différence arbitraire non nulle pour les 8 octets actifs à la sortie de l' opération MixRows au tour 3. Ces différences sont ensuite propagées vers l'arrière à la sortie de l' opération SubBytes au troisième tour. En raison des propriétés de l'opération MixRows, un l'état actif est obtenu. Notez que cela peut être fait pour chaque ligne indépendamment.
2. Choisissez une différence pour chaque octet actif dans l'entrée de l'opération MixRows au tour 2 et propagez ces différences vers l'entrée de l'opération Sous-octets au tour 3. Effectuez cette opération pour toutes les 255 différences non nulles de chaque octet. Encore une fois, cela peut être fait indépendamment pour chaque ligne.
3. Dans l' étape de correspondance au milieu , nous utilisons la table DDT pour trouver les différences d'entrée / sortie correspondantes (comme trouvé dans les étapes 1 et 2) à l'opération SubBytes au tour 3. Chaque ligne peut être vérifiée indépendamment, et la valeur attendue le nombre de solutions est de 2 par S-box . Au total, le nombre attendu de valeurs qui suivent la caractéristique différentielle est de 2 ⁶⁴ .

Ces étapes peuvent être répétées avec 2 ⁶⁴ valeurs de départ différentes à l'étape 1, ce qui donne un total de 2 ¹²⁸ valeurs réelles qui suivent la caractéristique différentielle dans la phase entrante. Chaque ensemble de 2 ⁶⁴ valeurs peut être trouvé avec une complexité de 2 ⁸ transformations rondes en raison de l'étape de précalcul.

La phase sortante

La phase sortante complète la caractéristique différentielle de manière probabiliste. La phase sortante utilise des différentiels tronqués , par opposition à la phase entrante. Chaque point de départ trouvé dans la phase entrante est propagé vers l'avant et vers l'arrière. Afin de suivre la caractéristique souhaitée, 8 octets actifs doivent se propager vers un seul octet actif dans les deux sens. Une telle transition 8 à 1 se produit avec une probabilité de 2 ^-56 , donc remplir la caractéristique a une probabilité de 2 ^-112 . Pour assurer une collision , les valeurs au début et à la fin de la caractéristique doivent s'annuler pendant l'opération d'anticipation. Cela se produit avec une probabilité d'environ 2 - ⁸ , et la probabilité globale de la phase sortante est donc de 2 - ¹²⁰ .

Pour trouver une collision , 2 ¹²⁰ points de départ doivent être générés dans la phase entrante. Comme cela peut être fait avec une complexité moyenne de 1 par point de départ, la complexité globale de l'attaque est de 2 ¹²⁰ .

Prolonger l'attaque

L'attaque de base de 4,5 rounds peut être étendue à une attaque de 5,5 rounds en utilisant deux états pleinement actifs dans la phase entrante. Cela augmente la complexité à environ 2 ¹⁸⁴ .

L'extension de la phase sortante pour qu'elle commence et se termine avec 8 octets actifs conduit à une quasi-collision en 52 octets sur Whirlpool réduite à 7,5 tours avec une complexité de 2 ¹⁹² .

En supposant que l'attaquant a le contrôle sur la valeur de chaînage, et donc l'entrée dans le programme de clé de Whirlpool , l'attaque peut être étendue à 9,5 coups dans une quasi-collision semi-libre sur 52 octets avec une complexité de 2 ¹²⁸ .

Remarques

Les références

• The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl par Florian Mendel, Christian Rechberger, Martin Schlaffer et Soren S. Thomsen (Fast Software Encryption 2009: 260-276)
• The Rebound Attack on Reduced Grøstl Hash Function par Florian Mendel, Christian Rechberger, Martin Schlaffer et Soren S. Thomsen (The Cryptographer's Track at RSA Conference 2010: 350-365)
• Attaque de rebond non alignée - Application à Keccak par Alexandre Duc, Jian Guo, Thomas Peyrin, Lei Wei (IACR Cryptology ePrint Archive Year 2011/420)
• Comment améliorer les attaques de rebond par María Naya-Plasencia FHNW, Windisch, Suisse (CRYPTO'11 Actes de la 31e conférence annuelle sur les progrès de la cryptologie, pages 188-205)
• The Rebound Attack and Subspace Distinguishers: Application to Whirlpool par Mario Lamberger, Florian Mendel, Christian Rechberger, Vincent Rijmen et Martin Schläffer (IACR Cryptology ePrint Archive, Année 2010/198).
• Cryptanalyse des fonctions de hachage basées sur AES Thèses de doctorat par Martin Schläffer