Algorithme de hashage MD5
Ron Rivest, un des inventeurs de RSA, a développé en 1991 le Message Digest 5 (MD5), plus lent que son prédécesseur MD4, mais plus fiable au niveau de la sécurité.
L'algorithme MD5 permet de réaliser une empreinte digitale de 128 bits d'un message d'une longueur indéterminée. Il ne s'agit pas ici de crypter un message, puisqu'il s'agit d'un algorithme irréversible (il n'est pas possible de reconstituer le fichier d'origine depuis son hash). Il a été développé en fonction de l'architecture matérielle la plus répandue au moment de sa conception, l'architecture 32 bits. C'est ce qui explique l'utilisation de tampons mémoire (buffers) de 32 bits, et la découpe du message en blocs de cette taille.
L'algorithme est basé sur une boucle (dont la longueur varie en fonction de la taille du message d'origine. Cette boucle est composée de 4 rounds qui comportent chacun 16 opérations.
Padding du message MD5
Explication
Le message original (m0) comporte un nombre de bits indéterminé. La première opération consiste à compléter ce nombre de bits pour atteindre un multiple de 512. Dans le cas où le message d'origine est déjà un multiple de 512, nous devrons quand-même ajouter 512 bits.
Nous devons de plus préserver 64 bits qui permettront de chiffrer la taille du message d'origine, et que nous ajouterons à la fin de ce dernier.
Donc, nous devrons toujours ajouter des bits, de telle sorte que la longueur de m0 soit un multiple de 512 (448 bits restants pour le dernier élément).
Le padding consistera à ajouter un bit à 1 suivi de bits à 0, pour constituer le message mp (m0 + padding).
Nous pouvons donc considérer le message comme un tableau composé de lignes de 512 bits.
Formules MD5
Calcul du padding :
mp = m0 + (1 à 512 bits) de telle sorte que n bits(mp)mod 512 = 448
Afin d'éviter que le codage de la taille du fichier ne dépasse les 64 bits prévus, nous devons calculer b :
b = m0 mod 264
Comme le renseignement de la taille du fichier est représenté sur 64 bits, ce bloc sera ajouté à mp (auquel il manque justement 64 bits pour atteindre un multiple de 512 bits) afin d'obtenir un bloc Mt dont le nombre de bits est un multiple de 512 :
Mt = mp + b
Chaque bloc de 512 bits est ensuite découpé en 16 blocs (aussi nommés mots) de 32 bits.
Comme nous nous sommes assurés d'avoir une taille pour Mt qui soit un multiple de 512, l'ensemble du message peut être décomposé en mots de 32 bits de la manière suivante :
Mt = M [0] + M [1] + M [2] + ... + M [n-1]
avec n qui représente le nombre de blocs de 32 bits de Mt, et qui est un multiple de 16.
Les 4 tampons mémoire de MD5 (buffers)
Quatre buffers (A, B, C, D) de 32 bits (rappelons que MD5 a été créé pour travailler principalement sur une architecture 32 bits) mémorisent 4 mots dont la totalité représente 128 bits, ce qui est la taille totale du hash final de notre message original.
Initialement, les tampons possèdent les valeurs hexadécimales suivantes :
- A0 = 01 23 45 67
- B0 = 89 ab cd ef
- C0 = fe dc ba 98
- d0 = 76 54 32 10
Les fonctions binaires de MD5
L'algorithme MD5 utilise 4 fonctions binaires différentes (F, G, H, I) qui traitent chacune 3 blocs de 32 bits en entrée, et fournissent un seul bloc de 32 bits en sortie.
- F(X,Y,Z) = [X AND Y] OR [NOT(X) AND Z]
- G(X,Y,Z) = [X AND Z] OR [Y AND NOT(Z)]
- H(X,Y,Z) = X XOR Y XOR Z
- I(X,Y,Z) = Y XOR [X OR NOT(Z)]
MD5 - Remarques
La première fonction (F) peut se traduire de la manière suivante : si X = 1 alors l'output sera Y, sinon l'output sera Z.
Pour chaque fonction, la chance d'obtenir un 1 est aussi grande que la chance d'obtenir un 0 (unbiaised). Ceci est nécessaire pour maintenir le lien (quasi) unique entre le message original et le hash.
Tableau SINE de MD5
Le tableau SINE de MD5 est un tableau de 64 lignes, construit par la fonction SINUS. Chaque nombre T[i] dans ce tableau sera calculé selon la formule suivante :
T[i] = INT[232 * ABS(SIN(i))] ( 232 = 4.294.967.296)
i étant le numéro de l'élément (le n° de ligne, de 1 à 64), et considéré comme une valeur radian (180° = PIrad) pour le calcul du sinus.
Le tableau nous fournit donc 64 nombres fixes (T[i]), qui ne seront jamais plus grand que 32 bits(en binaire).
Les phases de l'algorithme MD5
Rappels et notations
Le message complet ( mt ) est divisé en blocs de 512 bits.v = nombre de blocs de 512 bits.Chaque bloc de 512 bits est ensuite divisé en mots (words) de 32 bits, notés de 0 à 15.
w représente ce chiffre de 0 à 15 (position du mot de 32 bits au sein du bloc de 512 bits).Nous aurons donc v fois 16 index w de 0 à 15 pour notre message complet ( mt ), ainsi que v fois 4 rounds de 16 opérations chacun.Dans les formules suivantes, à chaque fois que le signe + sera utilisé, une opération d'addition modulo 232 sera exécutée en réalité, pour ne pas dépasser la capacité des buffers.A chaque fois que nous utiliserons le signe <<<s, cela signifiera une rotation à gauche d'un nombre binaire de s positions.
Phase 0 (v = 0)
Avant les rounds MD5
fonction :
X[w] = M[ (v*16 ) + w ] = M[w]Les nombres A0, B0, C0, et D0 sont mémorisés.
Round 1
formule à appliquer en fonction du tableau :
a = b + [ (a + F(b,c,d) + X[k] + T[i]) <<<s ]
a correspond au buffer qui sera modifié. Pour déterminer de quel buffer il s'agit, il faut se reporter au tableau correspondant (Si nous avons ABCD, a correspond au buffer A; si nous avons DABC, a correspond au buffer D, etc.).
F correspond à la fonction F = [X AND Y] OR [NOT(X) AND Z].b,c,d sont les buffers selon l'ordre du tableau.X[k] est l'index qui permet de situer le mot de 32 bits dans la ligne de 512 bits de notre message.T[i] est la valeur fixe déterminée par le tableau SINE de MD5.
[ABCD 0 7 1] | opération 2
[DABC 1 12 2] | opération 3
[CDAB 2 17 3] | opération 4
[BCDA 3 22 4] |
[ABCD 4 7 5] | opération 6
[DABC 5 12 6] | opération 7
[CDAB 6 17 7] | opération 8
[BCDA 7 22 8] |
[ABCD 8 7 9] | opération 10
[DABC 9 12 10] | opération 11
[CDAB 10 17 11] | opération 12
[BCDA 11 22 12] |
[ABCD 12 7 13] | opération 14
[DABC 13 12 14] | opération 15
[CDAB 14 17 15] | opération 16
[BCDA 15 22 16] |
Round 2
formule à appliquer en fonction du tableau :
a = b + [ (a + G(b,c,d) + X[k] + T[i]) <<<s ]
Round 3
formule à appliquer en fonction du tableau :
a = b + [ (a + H(b,c,d) + X[k] + T[i]) <<<s ]
Round 4
formule à appliquer en fonction du tableau :
a = b + [ (a + I(b,c,d) + X[k] + T[i]) <<<s ]
Après les 4 rounds MD5
A l'issue des 4 rounds, nous obtenons 4 nouvelles valeurs : Anew, Bnew, Cnew, Dnew.
Les 4 mots subissent alors les opérations suivantes :
- A1 = Anew + A0 (attention, le signe + signifie toujours une addition modulo 232)
- B1 = B new + B0
- C1 = C new + C 0
- D1 = D new + D 0
Phase 1
La fonction est identique, mais v est égal à 1 :
X[w] = M[ (v*16 ) + w ] = M[16 + w]Les nombres A1, B1, C1, et D1 sont mémorisés.Les 4 rounds sont ensuite appliqués selon les mêmes principes que pour la phase 0.
Phase v-1
Cette phase est la dernière, nous traitons le bloc M[v-1].
X[w] = M[ (v*16 ) + w ]
Les nombres Av-2, Bv-2, Cv-2, et Dv-2 sont mémorisés.
Les 4 rounds sont ensuite appliqués selon les mêmes principes que pour les phases précédentes.
A l'issue des 4 rounds, les nombres Av-1, Bv-1, Cv-1, et Dv-1 sont concaténés (ils sont simplement mis les uns à la suite des autres en respectant l'ordre ABCD) en un bloc de 128 bits 
notre hash MD5 du message original.
Deutsche Übersetzung
Sie haben gebeten, diese Seite auf Deutsch zu besuchen. Momentan ist nur die Oberfläche übersetzt, aber noch nicht der gesamte Inhalt.Wenn Sie mir bei Übersetzungen helfen wollen, ist Ihr Beitrag willkommen. Alles, was Sie tun müssen, ist, sich auf der Website zu registrieren und mir eine Nachricht zu schicken, in der Sie gebeten werden, Sie der Gruppe der Übersetzer hinzuzufügen, die Ihnen die Möglichkeit gibt, die gewünschten Seiten zu übersetzen. Ein Link am Ende jeder übersetzten Seite zeigt an, dass Sie der Übersetzer sind und einen Link zu Ihrem Profil haben.
Vielen Dank im Voraus.
Dokument erstellt 24/06/2005, zuletzt geändert 27/11/2019
Quelle des gedruckten Dokuments:https://www.gaudry.be/de/crypto-md5.html
Die Infobro ist eine persönliche Seite, deren Inhalt in meiner alleinigen Verantwortung liegt. Der Text ist unter der CreativeCommons-Lizenz (BY-NC-SA) verfügbar. Weitere Informationen auf die Nutzungsbedingungen und dem Autor.
