Attaque par glissement

L'attaque par glissement, ou slide attack, est une méthode cryptanalytique introduite en 1999 par David Wagner et Alex Biryukov. Elle repose sur l'observation que de nombreuses constructions cryptographiques et notamment les chiffrements par blocs fonctionnent en répétant une même opération un nombre fixé de fois (entre 10 et 12 pour AES, par exemple), se contentant d'utiliser une clé dérivée pour chaque tour. Or la dérivation de clé est souvent manipulable par un adversaire, ce qui permet à l'analyste de forcer par exemple que toutes les clés dérivées soient identiques, ou liées par une relation simple. L'attaque par glissement permet alors d'attaquer directement la permutation élémentaire, indépendamment du nombre de tours. L'existence de cette attaque montre en particulier que l'opinion répandue selon laquelle il suffit d'augmenter le nombre de tours pour augmenter la sécurité d'un chiffrement par blocs, n'est pas fondée.

Depuis son introduction, l'attaque a été étendue pour s'appliquer à tout système cryptographique basé sur la répétition d'opérations simples, comme les fonctions de hachage de type Merkle-Damgård, ou les chiffrements par flux.

Histoire

L'attaque par glissement tire son inspiration d'un premier travail sur la cryptanalyse du chiffre New Data Seal en 1978 par Edna Grossman et Bryant Tuckerman. En particulier, leur attaque montre comment casser un chiffre de Feistel affaibli par une attaque en clairs choisis, de manière complètement indépendante du nombre de tours. Les travaux d'Eli Biham sur les attaques par clés apparentées et la cryptanalyse de LOKI par Lars Knudsen en 1991 peuvent être vus comme des développements naturels de ces techniques.

David Wagner et Alex Biryukov ont pour la première fois systématisé l'attaque et mesuré son potentiel en 1999, et dans plusieurs travaux à la suite. Le nom d'« attaque par glissement » a été suggéré par Bruce Schneier.

Principe

Pour illustrer le principe, considérons un chiffrement par blocs consistant en la répétition d'une permutation $F_{k}$ dépendant d'une clé inconnue $k$. En pratique la clé $k$ est susceptible de changer à chaque application (c'est une clé dérivée) mais dans de nombreux cas on peut exploiter la structure de la dérivation de clé pour s'assurer que $k$ est bien constante. On va supposer qu'en tant que permutation, $F_{k}$ est relativement faible face à une attaque à clairs connus : plus spécifiquement, étant donné deux valeurs $F_{k}(x_{1}),F_{k}(x_{2})$ pour des valeurs de $x_{1},x_{2}$ connues de l'adversaire, il est facile de retrouver la clé $k$.

Un tel modèle est en fait tout à fait réaliste, puisque DES réduit à trois tours, ou IDEA réduit à un tour et demi sont de telles fonctions $F_{k}$.

L'attaque consiste alors à considérer deux exécutions du chiffrement « glissées » l'une par rapport à l'autre :

$${\begin{aligned}X_{0}{\xrightarrow {F_{k}}}&X_{1}{\xrightarrow {F_{k}}}X_{2}{\xrightarrow {F_{k}}}\cdots {\xrightarrow {F_{k}}}X_{n}\\&X_{0}'{\xrightarrow {F_{k}}}X_{1}'{\xrightarrow {F_{k}}}X_{2}'{\xrightarrow {F_{k}}}\cdots {\xrightarrow {F_{k}}}X_{n}'\end{aligned}}$$

en observant que s'il se produit une collision, par exemple $X_{0}'=X_{1}$, alors on a pour toute la suite $X_{j}=X_{j-1}'$. On cherche alors une paire $(P,C),(P',C')$ telle que $F_{k}(P)=P'$ et $F_{k}(C)=C'$. Une telle paire peut toujours être trouvée en au plus $2^{n/2}$ chiffrements aléatoires, où $n$ est la taille du bloc, par le théorème des anniversaires, ou en $2^{n/4}$ chiffrements en exploitant la structure d'un réseau de Feistel. Pour certains chiffrements, il est possible de trouver une telle paire bien plus efficacement, et dans tous les cas il est facile de la reconnaître.

Une fois la paire $(P,C),(P',C')$ trouvée, par hypothèse sur $F_{k}$, on retrouve $k$.

Applications

L'attaque par glissement est une attaque générique qui montre que la permutation élémentaire $F_{k}$ n'est pas « sauvée » contre une attaque par clairs choisis en augmentant le nombre de tours. Elle s'applique donc à tous les chiffrements par blocs qui utilisent un tour faible. Mais la technique s'étend également aux chiffrements par flux, aux codes d'authentification, et aux fonctions de hachage.

• Appliquée à TREYFER, un MAC, la technique donne une attaque en $2^{32}$ clairs connus et $2^{44}$ opérations. Elle a depuis été améliorée pour ne nécessiter que $2^{11}$ clairs connus.
• Appliquée à Blowfish, un chiffrement par blocs, la technique montre qu'un algorithme chiffrement ne peut pas espérer tirer sa sécurité d'une S-box dépendant de la clé, avec une attaque sur une variante en $2^{27}$ clairs connus et $2^{27}$ opérations. Ce fut historiquement la première attaque efficace contre cette famille de chiffrements.
• De nombreuses variantes de DES sont cassées par l'attaque par glissement, parfois en utilisant moins de 128 clairs, et même pour un nombre de tours arbitrairement large.

Des améliorations de l'attaque par glissement ont été appliquées à DES-X, à GOST (cassé à la suite de ces travaux), et aux constructions de type Even-Mansour.