Construction Merkle–Damgård - Merkle–Damgård construction

En cryptographie , la construction Merkle-Damgård ou fonction de hachage Merkle-Damgård est une méthode de construction de fonctions de hachage cryptographiques résistantes aux collisions à partir de fonctions de compression unidirectionnelles résistantes aux collisions . Cette construction a été utilisée dans la conception de nombreux algorithmes de hachage populaires tels que MD5 , SHA-1 et SHA-2 .

La construction Merkle-Damgård a été décrite dans le doctorat de Ralph Merkle . thèse en 1979. Ralph Merkle et Ivan Damgård ont prouvé indépendamment que la structure est saine : c'est-à-dire que si un schéma de remplissage approprié est utilisé et que la fonction de compression est résistante aux collisions , alors la fonction de hachage sera également résistante aux collisions.

La fonction de hachage Merkle-Damgård applique d'abord une fonction de remplissage conforme à MD pour créer une entrée dont la taille est un multiple d'un nombre fixe (par exemple 512 ou 1024) - c'est parce que les fonctions de compression ne peuvent pas gérer les entrées de taille arbitraire. La fonction de hachage divise ensuite le résultat en blocs de taille fixe, et les traite un par un avec la fonction de compression, combinant à chaque fois un bloc de l'entrée avec la sortie du tour précédent. Afin de sécuriser la construction, Merkle et Damgård ont proposé que les messages soient rembourrés avec un rembourrage qui encode la longueur du message d'origine. C'est ce qu'on appelle un rembourrage de longueur ou un renforcement Merkle-Damgård .

Construction de hachage Merkle–Damgård

Dans le diagramme, la fonction de compression unidirectionnelle est désignée par f et transforme deux entrées de longueur fixe en une sortie de la même taille que l'une des entrées. L'algorithme démarre avec une valeur initiale, le vecteur d'initialisation (IV). L'IV est une valeur fixe (spécifique à l'algorithme ou à l'implémentation). Pour chaque bloc de message, la fonction de compression (ou compactage) f prend le résultat jusqu'à présent, le combine avec le bloc de message et produit un résultat intermédiaire. Le dernier bloc est complété par des zéros au besoin et des bits représentant la longueur de l'ensemble du message sont ajoutés. (Voir ci-dessous pour un exemple détaillé de rembourrage de longueur.)

Pour durcir davantage le hachage, le dernier résultat est ensuite parfois alimenté via une fonction de finalisation . La fonction de finalisation peut avoir plusieurs objectifs tels que la compression d'un état interne plus grand (le dernier résultat) en une taille de hachage de sortie plus petite ou pour garantir un meilleur effet de mélange et d' avalanche sur les bits de la somme de hachage. La fonction de finalisation est souvent construite en utilisant la fonction de compression. (Notez que dans certains documents, une terminologie différente est utilisée : l'acte de remplissage de longueur est appelé « finalisation ».)

Caractéristiques de sécurité

La popularité de cette construction est due au fait, prouvé par Merkle et Damgård , que si la fonction de compression unidirectionnelle f est résistante aux collisions , alors la fonction de hachage construite en l'utilisant l'est aussi. Malheureusement, cette construction a aussi plusieurs propriétés indésirables :

• Les attaques de deuxième préimage contre les messages longs sont toujours beaucoup plus efficaces que la force brute.
• Les multicollisions (de nombreux messages avec le même hachage) peuvent être trouvées avec seulement un peu plus de travail que les collisions.
• « Herding attack s », qui combine la construction en cascade pour la recherche de multicollisions (similaire à ce qui précède) avec les collisions trouvées pour un préfixe donné (collisions avec préfixe choisi). Cela permet de construire des documents de collision très spécifiques, et cela peut être fait pour plus de travail que de trouver une collision, mais beaucoup moins que ce à quoi on pourrait s'attendre pour un oracle aléatoire .
• Extension de longueur : Étant donné le hachage d'une entrée inconnue X , il est facile de trouver la valeur de , où pad est la fonction de remplissage du hachage. C'est-à-dire qu'il est possible de trouver des hachages d'entrées liées à X même si X reste inconnu. Les attaques par extension de longueur ont en fait été utilisées pour attaquer un certain nombre de schémas commerciaux d'authentification de messages Web tels que celui utilisé par Flickr .${\style d'affichage H(X)}$${\displaystyle H({\mathsf {Pad}}(X)\|Y)}$

Construction de tuyaux larges

La construction de hachage à pipe large. Les valeurs intermédiaires de chaînage ont été doublées.

En raison de plusieurs faiblesses structurelles de la construction Merkle-Damgård, en particulier le problème d'extension de longueur et les attaques multicollisions, Stefan Lucks a proposé l'utilisation du hachage à tuyau large au lieu de la construction Merkle-Damgård. Le hachage à tube large est très similaire à la construction Merkle-Damgård mais a une taille d'état interne plus grande, ce qui signifie que la longueur de bit utilisée en interne est plus grande que la longueur de bit de sortie. Si un hachage de n bits est souhaité, la fonction de compression f prend 2n bits de valeur de chaînage et m bits du message et les compresse en une sortie de 2n bits.

Par conséquent, dans une dernière étape, une seconde fonction de compression compresse la dernière valeur de hachage interne ( 2n bits) en la valeur de hachage finale ( n bits). Cela peut être fait aussi simplement que de rejeter la moitié de la dernière sortie de 2n bits. SHA-512/224 et SHA-512/256 prennent cette forme car ils sont dérivés d'une variante de SHA-512. SHA-384 et SHA-224 sont dérivés de la même manière de SHA-512 et SHA-256, respectivement, mais la largeur de leur tuyau est bien inférieure à 2n .

Construction rapide de tuyaux larges

La construction rapide de hachage de tuyau large. La moitié de la valeur de chaînage est utilisée dans la fonction de compression.

Il a été démontré par Mridul Nandi et Souradyuti Paul que la fonction de hachage Widepipe peut être rendue environ deux fois plus rapide si l'état Widepipe peut être divisé en deux de la manière suivante : une moitié est entrée dans la fonction de compression suivante tandis que l'autre moitié est combiné avec la sortie de cette fonction de compression.

L'idée principale de la construction de hachage est de transmettre la moitié de la valeur de chaînage précédente à XOR vers la sortie de la fonction de compression. Ce faisant, la construction prend des blocs de message plus longs à chaque itération que le Widepipe d'origine. Utilisant la même fonction f que précédemment, il prend n valeurs d'enchaînement de bits et n+m bits du message. Cependant, le prix à payer est la mémoire supplémentaire utilisée dans la construction pour le feed-forward.

Rembourrage conforme MD

Comme mentionné dans l'introduction, le système de rembourrage utilisé dans la construction Merkle-Damgård doit être choisi avec soin pour assurer la sécurité du système. Mihir Bellare donne des conditions suffisantes pour qu'un système de rembourrage possède pour garantir que la construction MD est sécurisée : il suffit que le schéma soit "conforme MD" (le schéma de rembourrage de longueur original utilisé par Merkle est un exemple de rembourrage conforme MD) . Conditions:

• ${\style d'affichage M}$ est un préfixe de ${\displaystyle {\mathsf {Pad}}(M).}$
• Si alors${\style d'affichage |M_{1}|=|M_{2}|}$${\displaystyle |{\mathsf {Pad}}(M_{1})|=|{\mathsf {Pad}}(M_{2})|.}$
• Si alors le dernier bloc de est différent du dernier bloc de${\style d'affichage |M_{1}|\neq |M_{2}|}$${\displaystyle {\mathsf {Pad}}(M_{1})}$${\displaystyle {\mathsf {Pad}}(M_{2}).}$

Avec ces conditions en place, nous trouvons une collision dans la fonction de hachage MD exactement quand nous trouvons une collision dans la fonction de compression sous-jacente. Par conséquent, la construction Merkle-Damgård est prouvée sécurisée lorsque la fonction de compression sous-jacente est sécurisée.

Exemple de rembourrage de longueur

Pour pouvoir transmettre le message à la fonction de compression, le dernier bloc doit être rempli avec des données constantes (généralement avec des zéros) jusqu'à un bloc complet. Par exemple, supposons que le message à hacher soit "HashInput" (chaîne de 9 octets, 0x48617368496e707574 en ASCII ) et que la taille de bloc de la fonction de compression soit de 8 octets (64 bits). Nous obtenons deux blocs (les octets de remplissage affichés avec une couleur de fond bleu clair) :

48 61 73 68 49 6e 70 75, 74 00 00 00 00 00 00 00

Cela implique que d'autres messages ayant le même contenu mais se terminant par des zéros supplémentaires à la fin donneront la même valeur de hachage. Dans l'exemple ci-dessus, un autre message presque identique (0x48617368496e7075 74 00 ) générera la même valeur de hachage que le message d'origine "HashInput" ci-dessus. En d'autres termes, tout message ayant des zéros supplémentaires à la fin le rend indiscernable avec celui sans eux. Pour éviter cette situation, le premier bit du premier octet de remplissage est remplacé par "1" (0x80), ce qui donne :

48 61 73 68 49 6e 70 75, 74 80 00 00 00 00 00 00

Pour le rendre résistant à l' attaque par extension de longueur , la longueur du message est ajoutée dans un bloc supplémentaire à la fin (affichée avec une couleur de fond jaune) :

48 61 73 68 49 6e 70 75, 74 80 00 00 00 00 00 00 , 00 00 00 00 00 00 00 09

Cependant, les implémentations les plus courantes utilisent une taille de bit fixe (généralement 64 ou 128 bits dans les algorithmes modernes) à une position fixe à la fin du dernier bloc pour insérer la valeur de longueur du message (voir pseudocode SHA-1 ). Une amélioration supplémentaire peut être apportée en insérant la valeur de longueur dans le dernier bloc s'il y a suffisamment d'espace. Cela évite d'avoir un bloc supplémentaire pour la longueur du message. Si nous supposons que la valeur de longueur est codée sur 5 octets (40 bits), le message devient :

48 61 73 68 49 6e 70 75, 74 80 00 00 00 00 00 09

Notez que le stockage de la longueur du message hors bande dans les métadonnées, ou autrement intégré au début du message est une atténuation efficace de l'attaque d'extension de longueur, tant que l'invalidation de la longueur du message et de la somme de contrôle sont toutes deux considérées comme un échec de l'intégrité vérification.

Les références

• Manuel de cryptographie appliquée par Menezes, van Oorschot et Vanstone (2001), chapitre 9.
• Introduction à la cryptographie moderne , par Jonathan Katz et Yehuda Lindell. Chapman et Hall/CRC Press, août 2007, page 134 (construction 4.13).
• Cryptography Made Simple par Nigel Smart (2015), chapitre 14.