Utilisateur:Qwyvin/Attaque par interpolation

En cryptographie, une attaque par interpolation est un type d'attaque cryptanalytique contre les chiffrements par blocs.

Après que deux types d'attaques, la cryptanalyse différentielle et la cryptanalyse linéaire, ont été présentées sur les chiffrements par blocs, de nouveaux chiffrements par blocs ont été introduits, créés pour être sûrs contre ces attaques. Parmi ceux-ci, il y a des chiffrements itératifs par blocs tels que le KN-Cipher et le chiffrement SHARK. Cependant, Thomas Jakobsen et Lars Knudsen ont montré à la fin des années 1990 que ces chiffrements étaient faciles à casser en introduisant une nouvelle attaque appelée attaque par interpolation.

Dans cette attaque, on utilise une fonction algébrique pour représenter une S-box. Il peut s'agir d'une fonction quadratique, polynomiale ou rationnelle sur un corps de Galois. Ses coefficients peuvent être déterminés par des techniques d'interpolation lagrangienne, en utilisant des textes clairs connus comme points de données. Des textes clairs choisis peuvent également être utilisés pour simplifier les équations et optimiser l'attaque.

Dans sa version la plus simple, une attaque par interpolation exprime le texte chiffré comme un polynôme du texte en clair. Si le polynôme a un nombre relativement faible de coefficients inconnus, alors le polynôme peut être reconstruit avec une collection de paires texte clair/texte chiffré (p/c). Grâce au polynôme reconstruit, l'attaquant dispose alors d'une représentation du chiffrement sans connaissance exacte de la clé secrète.

Exemple

Soit un chiffrement itéré donné par

$c_{i}=(c_{i-1}\oplus k_{i})^{3},$

où $c_{0}$ est le texte clair, $c_{i}$ la sortie du $i$-ème tour, $k_{i}$ la $i$-ème sous-clé (dérivée de la clé secrète $K$ par un key schedule), et pour un chiffrement itéré à $r$ tours, $c_{r}$ est le texte chiffré.

Considérons un chiffrement à 2 tours. Soit $x$ le message, et $c$ le texte chiffré.

Le résultat du premier tour devient alors

$c_{1}=(x+k_{1})^{3}=(x^{2}+k_{1}^{2})(x+k_{1})=x^{3}+k_{1}^{2}x+x^{2}k_{1}+k_{1}^{3},$

et la sortie du deuxième tour devient

${\begin{aligned}c_{2}=c&=(c_{1}+k_{2})^{3}=(x^{3}+k_{1}^{2}x+x^{2}k_{1}+k_{1}^{3}+k_{2})^{3}\\&=x^{9}+x^{8}k_{1}+x^{6}k_{2}+x^{4}k_{1}^{2}k_{2}+x^{3}k_{2}^{2}+x^{2}(k_{1}k_{2}^{2}+k_{1}^{4}k_{2})+x(k_{1}^{2}k_{2}^{2}+k_{1}^{8})+k_{1}^{3}k_{2}^{2}+k_{1}^{9}+k_{2}^{3}\end{aligned}}$

L'expression du texte chiffré sous forme de polynôme du texte en clair donne

$p(x)=a_{1}x^{9}+a_{2}x^{8}+a_{3}x^{6}+a_{4}x^{4}+a_{5}x^{3}+a_{6}x^{2}+a_{7}x+a_{8},$

où les $a_{i}$ sont des constantes dépendant de la clé.

En utilisant autant de paires texte clair/texte chiffré que le nombre de coefficients inconnus dans le polynôme $p(x)$, on peut construire le polynôme. Cela peut par exemple être fait par interpolation lagrangienne. Lorsque les coefficients inconnus ont été déterminés, on a une représentation $p(x)$ du chiffrement, sans connaissance de la clé secrète $K$.

Existence

Pour un chiffrement par bloc de $m$-bits, il y a $2^{m}$ textes clairs possibles, et donc $2^{m}$ paires distinctes $p/c$. S'il y a $n$ coefficients inconnus dans $p(x)$, puisque l'on a besoin d'autant de paires $p/c$ que de coefficients inconnus dans le polynôme, alors une attaque par interpolation n'existe que si $n\leq 2^{m}$.

Complexité temporelle

Supposons que le temps nécessaire pour construire le polynôme $p(x)$ en utilisant $p/c$ les paires sont petites, en comparaison du temps nécessaire pour chiffrer les textes en clair requis. S'il y a $n$ coefficients inconnus dans $p(x)$, la complexité temporelle de cette attaque est alors $n$, et exige $n$ paires connues $p/c$ distinctes.

Attaque par interpolation par Meet-In-The-Middle

Compte tenu d'un chiffrement itéré à $r$ tours avec longueur de bloc $m$, soit $z$ la sortie du chiffrement après $s$ tours, $s<r$. On exprimera la valeur de $z$ comme un polynôme du texte clair $x$, puis comme polynôme du texte chiffré $c$. Soit $g(x)\in GF(2^{m})[x]$ l'expression de $z$ via le texte en clair, et laisse $h(c)\in GF(2^{m})[c]$ être l'expression de $z$ via le texte chiffré. Le polynôme $g(x)$ est obtenu en calculant en utilisant la formule itérée du chiffre jusqu'à l'arrondi $s$, et le polynôme $h(c)$ est obtenu en calculant à rebours à partir de la formule itérée du chiffre à partir du tour $r$ jusqu'au tour $s+1$.

L'égalité suivante devrait donc être vraie :

$g(x)=h(c),$

et si les deux $g$ et $h$ sont des polynômes avec un faible nombre de coefficients, alors on peut résoudre l'équation pour les coefficients inconnus.

Complexité temporelle

On suppose que $g(x)$ peut être exprimé par $p$ coefficients, et $h(c)$ peut être exprimé par $q$ coefficients. Il faudrait alors $p+q$ paires connues $p/c$distinctes pour résoudre l’équation en la mettant d'une équation matricielle. Cependant, cette équation matricielle est résoluble jusqu’à une multiplication et une addition près. Donc, pour être sûr d'obtenir une solution unique et non nulle, on fixe à un le coefficient correspondant au degré le plus élevé et le terme constant à zéro. Donc, $p+q-2$ paires connues $p/c$ distinctes sont nécessaires. La complexité temporelle de cette attaque est donc $p+q-2$, et exige $p+q-2$ paires connues $p/c$ distinctes.

Avec l'approche Meet-In-The-Middle, le nombre total de coefficients est généralement inférieur à celui de la méthode normale. Cela rend la méthode plus efficace, puisque moins de paires $p/c$ sont nécessaires.

Récupération de clé

On peut également utiliser l'attaque par interpolation pour récupérer la clé secrète $K$.

Si l'on supprime le dernier tour d'un chiffrement itéré à $r$ tours de longueur de bloc $m$, la sortie du chiffrement devient ${\tilde {y}}=c_{r-1}$ . On appellera ce chiffrement modifié le chiffrement réduit. L'idée est de "deviner" la sous-clé du dernier tour $k_{r}$, de sorte que l'on puisse décrypter un tour pour obtenir le résultat ${\tilde {y}}$ du chiffre réduit. Ensuite, pour vérifier l'hypothèse, on utilise l'attaque par interpolation sur le chiffre réduit.

Par la méthode normale, on exprime la sortie ${\tilde {y}}$ du chiffre réduit comme un polynôme du texte en clair $x$, qu'on appellera $p(x)\in GF(2^{m})[x]$. Alors si on peut exprimer $p(x)$ avec $n$ coefficients, puis en utilisant $n$ connu distinct $p/c$ paires, on peut construire le polynôme. Pour vérifier l’hypothèse de la dernière sous-clé, on vérifie ensuite avec une paire $p/c$ supplémentaire si l'égalité $p(x)={\tilde {y}}$ est vraie.

Si oui, alors avec une forte probabilité, l'hypothèse pour la dernière sous-clé était correcte. Si non, on fait une nouvelle hypothèse de la sous-clé.

Par la méthode Meet-In-The-Middle, on exprime le résultat $z$ du tour $s<r$ comme polynôme du texte clair $x$ et comme polynôme de la sortie du chiffre réduit ${\tilde {y}}$ . On appellera ces polynômes $g(x)$ et $h({\tilde {y}})$, et leur nombre de coefficients $p$ et $q$ coefficients, respectivement. Puis avec $q+p-2$ paires connues $p/c$ distinctes, on peut trouver les coefficients. Pour vérifier la supposition de la sous-clé du dernier tour, on vérifie avec une paire $p/c$ supplémentaire si l'égalité $g(x)=h({\tilde {y}})$ est vraie.

Si oui, alors avec une forte probabilité, la dernière sous-clé était correcte. Si non, on fait une autre hypothèse de la sous-clé.

Une fois que l'on a trouvé la bonne dernière sous-clé, on peut alors continuer de la même manière avec les sous-clés restantes.

Complexité temporelle

Avec une sous-clé de longueur $m$, il y a $2^{m}$ clés différentes. Chacune a une probabilité $1/2^{m}$ d'être correcte si elle est choisie au hasard. On va donc en moyenne faire $1/2\cdot 2^{m}$ hypothèses avant de trouver la bonne clé.

La méthode normale a donc une complexité temporelle moyenne de $2^{m-1}(n+1)$, exigeant $n+1$ paires connues $c/p$ distinctes, et la méthode Meet-In-The-Middle a une complexité temporelle moyenne $2^{m-1}(p+q-1)$, exigeant $p+q-1$ paires connues $c/p$ distinctes.

Application pratique

Une variate de l'attaque Meet-in-the-middle peut être utilisée pour attaquer les S-box qui utilisent la fonction inverse, car une S-box de $m$ bits donne $S:f(x)=x^{-1}=x^{2^{m}-2}$ dans $GF(2^{m})$.

C'est par exemple le cas du chiffrement par bloc SHARK, qui résiste à la cryptanalyse différentielle et linéaire après un petit nombre de tours. Cependant, il a été cassé en 1996 par Thomas Jakobsen et Lars Knudsen, en utilisant une attaque par interpolation. Notons SHARK$(n,m,r)$ une version de SHARK de $r$ tours avec une taille de bloc $nm$ bits utilisant $n$ S-box parallèles de $m$ bits. Jakobsen et Knudsen ont découvert qu'il existe une attaque par interpolation sur SHARK $(8,8,4)$ (chiffrement par bloc de 64 bits) en utilisant environ $2^{21}$ textes clairs choisis, et une attaque par interpolation sur SHARK $(8,16,7)$ (chiffrement par bloc de 128 bits) en utilisant environ $2^{61}$ textes clairs choisis.

Thomas Jakobsen a également présenté une version probabiliste de l'attaque par interpolation qui utilise un algorithme de Madhu Soudan pour améliorer le décodage des codes de Reed-Solomon. Cette attaque peut fonctionner même lorsqu’une relation algébrique entre textes clairs et textes chiffrés ne s’applique qu’à une partie des valeurs.

Références

• Thomas Jakobsen, Lars Knudsen « The Interpolation Attack on Block Ciphers » (Janvier 1997) (lire en ligne, consulté le 3 juillet 2007) {{PDF/PostScript}}
  —4th International Workshop on Fast Software Encryption (FSE '97), LNCS 1267
• Thomas Jakobsen « Cryptanalysis of Block Ciphers with Probabilistic Non-linear Relations of Low Degree » (25 août 1998) (lire en ligne, consulté le 6 juillet 2007) Modèle:PDF/PostScript
  —Advances in Cryptology — CRYPTO '98 (Video of presentation at Google Video—uses Flash)
• Shiho Moriai et Toshinobu Kaneko « Interpolation Attacks of the Block Cipher: SNAKE » (Mars 1999) (DOI 10.1007/3-540-48519-8_20, lire en ligne, consulté le 6 novembre 2022)
  —FSE '99
• Amr M. Youssef et Guang Gong « On the Interpolation Attacks on Block Ciphers » (Avril 2000) (lire en ligne, consulté le 6 juillet 2007)
  —FSE 2000
• Kaoru Kurosawa et Viet Duong Quang « Root Finding Interpolation Attack » (Août 2000) (lire en ligne, consulté le 6 juillet 2007) Modèle:PDF/PostScript
  —Proceedings of the 7th Annual International Workshop on Selected Areas in Cryptography (SAC 2000)

[[Catégorie:Attaque cryptanalytique]] [[Catégorie:Pages avec des traductions non relues]] [[Catégorie:Cryptologie]]