Cryptanalyse différentielle-linéaire

Cet article est une ébauche concernant la cryptologie.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Introduite par Martin Hellman et Susan K. Langford en 1994, la cryptanalyse différentielle-linéaire combine la cryptanalyse différentielle avec la cryptanalyse linéaire.

L'attaque différentielle sert à produire une approximation linéaire de l'algorithme, cette estimation a une probabilité de succès de 1 mais ne concerne qu'une partie du chiffrement (la probabilité de réussite serait bien inférieure sur l'ensemble du chiffrement).

Attaque sur DES

Avec cette attaque, Hellman et Langford ont pu casser avec 80 % de réussite un DES de 8 rondes avec seulement 512 textes en clair et quelques secondes sur un PC de l'époque. Ce résultat monte à 95 % de succès avec 768 textes. Finalement, il est possible d'obtenir 10 bits de la clé ou même plus selon le taux de réussite désiré et le nombre de messages à disposition (avec 768 textes, on peut obtenir 16 bits de la clé avec 85 % de réussite).

La première estimation concerne les trois premiers tours de DES via la cryptanalyse différentielle. Après avoir trouvé une caractéristique différentielle adéquate (on connait le comportement des différences du texte clair après trois tours), l'attaque produit une approximation linéaire pour les trois tours suivants. L'attaque doit donc quand même procéder à une recherche exhaustive sur les 2⁴⁰ à 2⁴⁶ clés restantes, ce qui n'est pas négligeable.

Autres attaques

Cette méthode a également été employée pour trouver des clés faibles dans IDEA. Ce type de cryptanalyse a été améliorée par Eli Biham et al. en 2002.

Liens externes

• (en) Enhancing Differential-Linear Cryptanalysis
• (en) Courte description par Alex Biryukov

• Portail de la cryptologie