Attaque par glissement

L'attaque par glissement tire son inspiration d'un premier travail sur la cryptanalyse du chiffre New Data Seal en 1978[4] 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[5] et la cryptanalyse de LOKI par Lars Knudsen[6] 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[1], et dans plusieurs travaux à la suite[2] - [3]. Le nom d'« attaque par glissement » a été suggéré par Bruce Schneier[1].

Pour illustrer le principe, considérons un chiffrement par blocs consistant en la répétition d'une permutation ${\displaystyle F_{k}}$ dépendant d'une clé inconnue ${\displaystyle k}$. En pratique la clé ${\displaystyle 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 ${\displaystyle k}$ est bien constante. On va supposer qu'en tant que permutation, ${\displaystyle F_{k}}$ est relativement faible face à une attaque à clairs connus : plus spécifiquement, étant donné deux valeurs ${\displaystyle F_{k}(x_{1}),F_{k}(x_{2})}$ pour des valeurs de ${\displaystyle x_{1},x_{2}}$ connues de l'adversaire, il est facile de retrouver la clé ${\displaystyle 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 ${\displaystyle F_{k}}$[1].

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

$${\displaystyle {\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 ${\displaystyle X_{0}'=X_{1}}$, alors on a pour toute la suite ${\displaystyle X_{j}=X_{j-1}'}$. On cherche alors une paire ${\displaystyle (P,C),(P',C')}$ telle que ${\displaystyle F_{k}(P)=P'}$ et ${\displaystyle F_{k}(C)=C'}$. Une telle paire peut toujours être trouvée en au plus ${\displaystyle 2^{n/2}}$ chiffrements aléatoires, où ${\displaystyle n}$ est la taille du bloc, par le théorème des anniversaires, ou en ${\displaystyle 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 ${\displaystyle (P,C),(P',C')}$ trouvée, par hypothèse sur ${\displaystyle F_{k}}$, on retrouve ${\displaystyle k}$.

L'attaque par glissement est une attaque générique qui montre que la permutation élémentaire ${\displaystyle 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[7], un MAC, la technique donne une attaque en ${\displaystyle 2^{32}}$ clairs connus et ${\displaystyle 2^{44}}$ opérations[1]. Elle a depuis été améliorée pour ne nécessiter que ${\displaystyle 2^{11}}$ clairs connus[8].
• Appliquée à Blowfish[9], 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 ${\displaystyle 2^{27}}$ clairs connus et ${\displaystyle 2^{27}}$ opérations[1]. 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[3].

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