Rencontre au milieu et compromis temps-mémoire

Les attaques MITM divisent un chiffrement en deux moitiés et les attaquent indépendamment. L'attaquant construit une table depuis une extrémité, puis cherche depuis l'autre extrémité une correspondance. La complexité de l'attaque passe de O(2^{2n}) à O(2^n), au prix d'une mémoire de O(2^n).

Double-DES applique DES deux fois : C = DES_{K2}(DES_{K1}(P)). Espace des clés : 2^{112}. Attaque MITM : pour les 2^{56} valeurs de K1, calculez DES_{K1}(P) et stockez le résultat. Pour les 2^{56} valeurs de K2, calculez DES_{K2}^{-1}(C) et recherchez le résultat dans la table. Correspondance → candidat (K1, K2). Seulement 2^{57} opérations au total.

Étape 1 : chiffrez le texte en clair P avec toutes les valeurs possibles de K1 → table T[DES_{K1}(P)] = K1. Étape 2 : pour chaque K2, déchiffrez le texte chiffré C : v = DES^{-1}_{K2}(C). Vérifiez si v ∈ T. Si T[v] = K1 existe, vérifiez (K1, K2) sur une seconde paire texte en clair-texte chiffré. Prévoyez 1 à 2 fausses correspondances et éliminez-les.

Triple-DES (3DES) utilise trois clés K1,K2,K3 : C = DES_{K3}(DES^{-1}_{K2}(DES_{K1}(P))). MITM reste applicable, mais de manière moins efficace : 3DES à deux clés (K3=K1) nécessite 2^{112} opérations. Pour 3DES à trois clés, une attaque MITM en 2^{112} opérations existe, ce qui explique pourquoi 3DES n'offre qu'environ 112 bits de sécurité effective malgré une clé de 168 bits.

Hellman (1980) : précalculez une table de chaînes (point de départ, point d'arrivée) pour accélérer la recherche de clés hors ligne. Étant donné un hachage ou un texte chiffré cible, recherchez dans la table de Hellman une chaîne qui le contient. Compromis : P = N (temps × mémoire = constante d'espace). C'est le fondement des tables arc-en-ciel.

Les tables arc-en-ciel (Oechslin, 2003) améliorent les tables de Hellman en utilisant différentes fonctions de réduction à chaque position de chaîne, ce qui élimine les fausses alertes (chaînes fusionnées). Elles sont efficaces pour casser des hachages de mots de passe non salés. Une recherche prend un temps de O(taille_de_la_table/longueur_de_la_chaîne).

Un sel est une valeur aléatoire ajoutée au début du mot de passe avant le hachage : H(salt||password). Des sels différents produisent des hachages différents pour un même mot de passe : une table arc-en-ciel pour « password » est inutile si un autre sel a été utilisé. Les sels doivent être stockés avec le hachage.

Les attaques MITM contre AES-128 (10 tours) : les attaques connues se divisent au tour 5 ; elles chiffrent les 5 premiers tours vers l'avant, déchiffrent les 5 derniers vers l'arrière, puis se rejoignent au milieu. La meilleure attaque connue, fondée sur des bicliques, réduit 2^{128} à 2^{126.1} : elle n'est pas réalisable en pratique, mais montre qu'AES ne dispose d'aucune marge de sécurité contre les approches de type MITM.

Pour les fonctions de hachage de Merkle-Damgård, MITM peut trouver des préimages plus rapidement que la force brute dans certaines constructions. Attaque : construisez une table à partir des blocs de message en partant de l'IV ; effectuez une recherche vers l'arrière depuis le hachage cible. Contre SHA-256 avec tous ses tours : toujours environ 2^{255}, sans amélioration par rapport à la force brute.

L'attaque par dissection généralise MITM aux divisions en r parties. Pour une division en trois parties d'un chiffrement : chiffrez vers l'avant sur un tiers des tours, rejoignez le milieu de la chaîne, puis déchiffrez vers l'arrière sur un tiers. Elle nécessite un temps de O(2^{n*2/3}) et une mémoire de O(2^{n/3}), offrant un compromis plus équilibré.

Dans les protocoles, les attaques MITM peuvent être empêchées en utilisant : des clés longues dérivées par KDF à partir de mots de passe à forte entropie (ce qui réduit l'espace des clés pouvant être énumérées), des jetons matériels (FIDO2) dont la clé ne quitte jamais l'appareil, ou une authentification à clé publique (aucun secret partagé à énumérer).

Quelle est la sécurité effective de Double-DES (2 × DES, clé combinée de 112 bits) contre une attaque MITM ?

Les attaques MITM divisent les chiffrements en deux, réduisant le temps de 2^{2n} à 2^n avec une mémoire de 2^n. Elles cassent Double-DES ; 3DES les atténue, mais sa sécurité effective est de 112 bits. Les tables arc-en-ciel utilisent une logique MITM pour casser les mots de passe, mais le salage les neutralise. Ensuite : les attaques par temporisation et les attaques par canal auxiliaire.