Cryptanalyse differentielle

Cryptanalyse differentielle

Cryptanalyse différentielle

La cryptanalyse différentielle est une méthode générique de cryptanalyse qui peut être appliquée aux algorithmes de chiffrement itératif par blocs, mais également aux algorithmes de chiffrement par flots et aux fonction de hachage.

Dans son sens le plus large, elle consiste en l'étude sur la manière dont les différences entre les données en entrée affectent les différences de leurs sorties. Dans le cas d'un chiffrement itératif par blocs, le terme se rapporte à l'ensemble des techniques permettant de retracer les différences à travers le réseau des transformations, découvrant ainsi où l'algorithme montre un comportement prédictible et exploitant ainsi ces propriétés afin de retrouver la clé secrète.

Sommaire

Origines de la cryptanalyse différentielle

La découverte de la cryptanalyse différentielle est généralement attribuée à Eli Biham et Adi Shamir à la fin des années 1980. Ces derniers publièrent alors un grand nombre d'attaques contre divers algorithmes de chiffrement itératif par blocs et diverses fonctions de hachage ; ces articles comprenaient la présentation d'une faiblesse théorique dans l'algorithme DES.

Il a été alors noté que DES était particulièrement résistant à cette attaque et en particulier que de petites modifications dans ses paramètres l'affaiblissaient. Ce constat a fait naître la rumeur que ses concepteurs (travaillant pour IBM) connaissaient déjà cette méthode dans les années 1970. Effectivement, plusieurs personnes ayant participé à sa conception ont depuis admis que la défense contre la cryptanalyse différentielle était bien un des buts recherchés alors (Don Coppersmith, 1994). Il semblerait même que la NSA qui contribua également à la conception de DES, avait même connaissance de cette technique avant sa redécouverte par IBM. La NSA exigea même que le processus de la conception soit tenu secret afin d'éviter la propagation de cette méthode. À l'intérieur d'IBM, la cryptanalyse différentielle était connue sous le nom de T-attack, abréviation de Tickling attack, l'attaque par chatouillement car elle consistait à chatouiller les entrées pour voir l'effet sur les sorties [1].

Alors que DES avait été conçu pour résister à la cryptanalyse différentielle, d'autres algorithmes conçus à la même époque se sont révélés particulièrement vulnérables. Une des premières cibles fut FEAL, qui illustra la puissance de la méthode. Sa version originale, constituée de quatre itérations (FEAL-4), peut être compromise avec seulement huit messages en clair choisis avec soin. Cela va même plus loin. En effet, FEAL est susceptible d'être attaqué par cette méthode dans toutes ses versions avec 31 itérations ou moins.

Description de l'attaque

La cryptanalyse différentielle s'effectue en général dans un contexte de texte clair choisi, ce qui signifie que l'attaquant est en mesure d'obtenir les résultats chiffrés de textes clairs de son choix. Il existe des variantes qui fonctionnent dans d'autres modes d'attaque : à texte clair connu ou à texte chiffré seulement. La cryptanalyse repose sur des paires de textes clairs qui ont une différence constante. L'opération de différence peut être définie de diverses manières, la Fonction OU exclusif est la plus courante. L'attaquant calcule ensuite les différences dans les textes chiffrés, afin d'en extraire des motifs pouvant indiquer un biais. Les différences en sortie du chiffrement sont nommées des différentielles. Leurs propriétés statistiques dépendent de la nature des boîtes-S de l'algorithme de chiffrement. Pour chaque boîte de substitution S, l'attaquant peut calculer une paire de différentielles (\Delta_X, \Delta_Y)~ avec :

\Delta_Y = S(X) \oplus S(X \oplus \Delta_X) = la différence en sortie
\Delta_X~ est la différence appliquée au texte en entrée.

Dans l'attaque classique, une différence particulière dans le texte chiffré permet de distinguer le texte chiffré d'un flôt aléatoire (l'aléa en sortie est une propriété attendue dans tout chiffrement robuste). Des techniques plus sophistiquées permettent de diminuer la complexité de l'attaque comme dans le cas de DES. Le choix des différences appliquées en entrée est cruciale pour la réussite de l'attaque. Une analyse des rouages de l'algorithme permet de déterminer les différences qui ont la plus grande chance d'apparaître sur le cheminement des données et de déterminer une caractéristique différentielle.

Cryptanalyses

Cryptanalyse différentielle tronquée

Comme son nom l'indique, une telle cryptanalyse s'intéresse à des différences qui n'affectent qu'une partie des variables considérées.

Cryptanalyse différentielle d'ordre supérieur

La cryptanalyse différentielle originale est une différentielle de premier ordre. En introduisant l'équivalent des dérivées dans les fonctions cryptographiques, on peut mener une cryptanalyse avec des degrés supérieurs. Ce sont des « différences de différences de ... ».

Voir [2] pour les définitions formelles et un exemple d'attaque.

Cryptanalyse différentielle impossible

Au lieu de chercher les différences probables, on inverse le problème et l'on cherche les différences qui ne se produiront pas.

L'attaque boomerang

Article détaillé : Attaque boomerang.

L'attaque boomerang est une version améliorée de la cryptanalyse différentielle inventée par David Wagner. Elle consiste à attaquer les deux moitiés d'un algorithme de chiffrement par bloc et part du principe que certaines propriétés, après perturbations des entrées, ne se propagent pas à travers toute la structure.

L'attaque rectangle

Article détaillé : Attaque rectangle.

L'attaque rectangle est une extension de l'attaque boomerang, elle a été inventée en 2001 par Eli Biham et son équipe pour attaquer leur chiffrement Serpent, candidat pour le standard AES.

Voir aussi

  • Portail de la cryptologie Portail de la cryptologie
Ce document provient de « Cryptanalyse diff%C3%A9rentielle ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Cryptanalyse differentielle de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Cryptanalyse Différentielle — La cryptanalyse différentielle est une méthode générique de cryptanalyse qui peut être appliquée aux algorithmes de chiffrement itératif par blocs, mais également aux algorithmes de chiffrement par flots et aux fonction de hachage. Dans son sens… …   Wikipédia en Français

  • Cryptanalyse différentielle — La cryptanalyse différentielle est une méthode générique de cryptanalyse qui peut être appliquée aux algorithmes de chiffrement itératif par blocs, mais également aux algorithmes de chiffrement par flots et aux fonction de hachage. Dans son sens… …   Wikipédia en Français

  • Cryptanalyse Différentielle Impossible — En cryptanalyse, la cryptanalyse différentielle impossible ou cryptanalyse par différentielles impossibles est une technique basée sur la cryptanalyse différentielle (1990), elle a été proposée en 1999 par Eli Biham, Adi Shamir et Alex Biryukov… …   Wikipédia en Français

  • Cryptanalyse differentielle impossible — Cryptanalyse différentielle impossible En cryptanalyse, la cryptanalyse différentielle impossible ou cryptanalyse par différentielles impossibles est une technique basée sur la cryptanalyse différentielle (1990), elle a été proposée en 1999 par… …   Wikipédia en Français

  • Cryptanalyse Différentielle-linéaire — 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… …   Wikipédia en Français

  • Cryptanalyse differentielle-lineaire — Cryptanalyse différentielle linéaire 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 à… …   Wikipédia en Français

  • Cryptanalyse différentielle impossible — En cryptanalyse, la cryptanalyse différentielle impossible ou cryptanalyse par différentielles impossibles est une technique basée sur la cryptanalyse différentielle (1990), elle a été proposée en 1999 par Eli Biham, Adi Shamir et Alex Biryukov… …   Wikipédia en Français

  • Cryptanalyse différentielle-linéaire — 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… …   Wikipédia en Français

  • Cryptanalyse par différentielles impossibles — Cryptanalyse différentielle impossible En cryptanalyse, la cryptanalyse différentielle impossible ou cryptanalyse par différentielles impossibles est une technique basée sur la cryptanalyse différentielle (1990), elle a été proposée en 1999 par… …   Wikipédia en Français

  • Cryptanalyse Intégrale — La cryptanalyse intégrale est une technique formalisée par David Wagner et Lars Knudsen pour attaquer des chiffrements insensibles à la cryptanalyse différentielle. Elle nécessite de disposer d un grand nombre de paires de textes clairs et… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”