PICSI

L'attaque par interpolation a été introduite par T. Jacobsen et L. Knudsen dans [1]. Cette attaque monovariable est applicable aux algorithmes dont les sorties peuvent être exprimées comme un polynôme de faible degré algébrique n en les entrées, ce qui peut par exemple se produire lorsque le degré de l'algorithme étudié est égal au produit des degrés algébriques des boîtes S de chaque étage.

La propriété d'interpolation ainsi obtenue peut être utilisée comme un distingueur à r étages dans une attaque contre un chiffrement à r+1 étages ou plus. Les attaques par interpolation peuvent être considérées comme un cas particulier monovariable des attaques par linéarisation, applicables lorsque le nombre de monômes des expressions multivariables des sorties en fonction des entrées est suffisamment faible. Dans l'article initial, T. Jacobsen et L. Knudsen donnent l'exemple d'un chiffrement nommé PURE composé de r étages d'un schéma de Feistel, dont la fonction d'étage F_K est définie de GF(32) dans lui-même par : F_K(x)=f(x ⊕k) avec f(x)=x³ dans GF(32). Ce chiffrement est prouvé sûr contre les cryptanalyses différentielle et linéaire pour un nombre suffisant d'étages. En revanche, l'attaque par interpolation fonctionne pour un nombre d'étages allant jusqu'à 32. Pour cette attaque par rencontre dans le milieu, on exprime tout d'abord la sortie de l'étage s que l'on notera z (s ≤ r−1) comme un polynôme g(x) fonction du texte clair x composé de au plus n₁ coefficients et dont on peut estimer le degré ici égal à au plus n₁−1 par multiplication du degré des boîtes S successivement traversées. On exprime ensuite cette même sortie z comme un polynôme h(y) en la sortie y du dernier étage composé de au plus n₂ coefficients. On a alors g(x)=h(y). Cette équation dont le nombre de coefficients inconnus est n=n₁+ n₂ permet de construire un système en au plus n−2 inconnues car on suppose que les termes constants valent 0 et que les coefficients de plus haut degré valent 1 afin d'obtenir une solution unique et non-trivial. Le nombre de paires de clairs/chiffrés nécessaires pour résoudre ce système est alors égal à n−2. On chiffre un texte clair de plus afin de vérifier que le système trouvé est le bon. Pour obtenir la valeur de y, on applique l'inverse de la fonction du r-ième étage au chiffré C pour chaque valeur des b bits de la clé k_r impliqués dans la relation entre C et y, et pour chacune de ces valeurs on calcule les coefficients du système. La bonne valeur est celle pour laquelle la vérification faite à partir de la paire supplémentaire de clair/chiffré fonctionne. La complexité d'une telle attaque est donc de 2^b−1(n−1) chiffrements pour (n−1) paires de clairs/chiffrés. Dans le cas de l'algorithme PURE à 32 étages, on fixe la partie droite de 32 bits de l'entrée et on exprime la sortie de gauche du 22ème étage comme un polynôme de degré au plus 3²⁰ de la partie gauche de l'entrée. Puis, on exprime la sortie du 31ème étage comme un polynôme dont le nombre de coefficients est au plus de 3¹⁹. Le nombre de coefficients de l'équation obtenue par l'égalité des deux polynômes est d'au plus 2³². Cette attaque par interpolation permet de retrouver 32 bits d'information sur la clé du dernier étage. Elle utilise 2³² clairs choisis et sa complexité est de 2⁶³ calculs.

 

Références

[1]

T. Jacobsen and L.R. Knudsen. The interpolation attack on block ciphers. In Fast Software Encryption'97, Haifa, Israël, pages 28-40. Lectures Notes in Computer Science 1267, Springer-Verlag, 1997.