Construction de Merkle-Damgård

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher


Dans le cadre des fonctions de hachage cryptographiques, la construction de Merkle-Damgård est une construction algorithmique qui permet de résoudre le problème du hachage cryptographique en acceptant un message de taille quelconque tout en produisant une sortie de taille fixe, et en satisfaisant les contraintes de sécurité liées à la cryptographie :

  • résistance aux collisions (difficulté de trouver deux messages distincts qui produisent la même empreinte)
  • résistance aux attaques sur les préimages (difficulté de trouver un message à partir de son empreinte, difficulté de forger un deuxième message produisant la même empreinte que le premier)
Construction de Merkle-Damgård avec la fonction de compression f et le vecteur d'initialisation IV

La construction de Merkle-Damgård emploie une fonction de compression avec une entrée et une sortie de taille fixe, et divise le message à hacher en blocs de taille fixe. Les blocs sont ensuite envoyés les uns après les autres dans la fonction de compression. Le résultat de chaque compression est ensuite transmis au bloc suivant selon plusieurs schémas :

Le premier bloc utilise un vecteur d'initialisation constant puisque aucun autre bloc ne le précède.

La construction de Merkle-Damgård produit un hachage résistant aux collisions pour autant que la fonction de compression utilisée soit également résistante aux collisions. De la qualité de la fonction de compression dépendra la résistance de l'algorithme à la cryptanalyse. Le principe de Merkle-Damgård est utilisé notamment dans MD5 et SHA-1.