La construction de Merkle-Damgård

Comment construit-on concrètement une fonction qui avale un message de taille quelconque et rend une empreinte fixe ? La réponse historique dominante s'appelle la construction de Merkle-Damgård, du nom de ses deux inventeurs en 1979.

Le principe : compresser par petits morceaux

L'idée est de ne pas traiter tout le message d'un coup, mais de le découper en blocs de taille fixe et de les « digérer » un à un, en gardant à chaque étape un état interne qui résume tout ce qui a été vu jusque-là.

Le cœur du dispositif est une fonction de compression notée f. Elle prend deux entrées de taille fixe — l'état courant et un bloc de message — et rend un nouvel état de la même taille :

f(état, bloc) -> nouvel état

Le rembourrage (padding)

Le message a rarement une taille multiple exacte de la taille d'un bloc. On le rembourre donc : on ajoute des bits pour compléter le dernier bloc. Le rembourrage classique de Merkle-Damgård ajoute un bit 1, puis des 0, puis code la longueur du message d'origine sur les derniers bits.

message :  [ ..... utile ..... ]
rembourré: [ ..... utile ..... 1 0 0 ... 0 | longueur ]
                                            \-- bloc complété --/

Coder la longueur à la fin (renforcement de Merkle-Damgård) est essentiel : cela lie l'empreinte à la taille du message et bloque certaines attaques.

Le chaînage

Une fois rembourré, le message est découpé en blocs M1, M2, ..., Mk. On part d'une constante fixée par la norme, la valeur initiale ou IV. Puis on applique f en chaîne :

 IV ---> f ---> f ---> f ---> ... ---> f ---> empreinte
          ^      ^      ^               ^
          |      |      |               |
         M1     M2     M3     ...       Mk

état0 = IV
état1 = f(état0, M1)
état2 = f(état1, M2)
...
étatk = f(état(k-1), Mk)   -> empreinte finale

Chaque étape mélange le bloc courant avec tout le passé. Comme la fonction de compression a le bon effet d'avalanche, la moindre modification d'un bloc se propage à tout l'état et donc à l'empreinte finale.

Une famille entière repose dessus

Cette construction est celle de MD5, SHA-1 et de toute la famille SHA-2 (dont SHA-256). Elle a un immense avantage : si la fonction de compression f résiste aux collisions, alors la fonction de hachage complète y résiste aussi — c'est un théorème démontré par Merkle et Damgård.

Mais elle a aussi des faiblesses structurelles héritées de ce chaînage, notamment l'attaque par extension de longueur, que nous verrons au chapitre 2.

En résumé

Merkle-Damgård construit une fonction de hachage à partir d'une simple fonction de compression : on rembourre le message (en y codant sa longueur), on le découpe en blocs, puis on chaîne la compression depuis un IV. C'est la structure de MD5, SHA-1 et SHA-2, solide par théorème mais porteuse de faiblesses propres au chaînage.