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).

Tableau SINE de MD5
iABS(SIN(i))232 * ABS(SIN(i))T[i]

 

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.

16 opérations du round 1
opération 1
[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] |
oopération 5
[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] |
oopération 9
[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] |
oopération 13
[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 ]

16 opérations du round 2
[ABCD 1 5 17] | [DABC 6 9 18] | [CDAB 11 14 19] | [BCDA 0 20 20] |
o[ABCD 5 5 21] | [DABC 10 9 22] | [CDAB 15 14 23] | [BCDA 4 20 24] |
o[ABCD 9 5 25] | [DABC 14 9 26] | [CDAB 3 14 27] | [BCDA 8 20 28] |
o[ABCD 13 5 29] | [DABC 2 9 30] | [CDAB 7 14 31] | [BCDA 12 20 32] |

Round 3

formule à appliquer en fonction du tableau :

a = b + [ (a + H(b,c,d) + X[k] + T[i]) <<<s ]

16 opérations du round 3
[ABCD 5 4 33] | [DABC 8 11 34] | [CDAB 11 16 35] | [BCDA 14 23 36] |
o[ABCD 1 4 37] | [DABC 4 11 38] | [CDAB 7 16 39] | [BCDA 10 23 40] |
o[ABCD 13 4 41] | [DABC 0 11 42] | [CDAB 3 16 43] | [BCDA 6 23 44] |
o[ABCD 9 4 45] | [DABC 12 11 46] | [CDAB 15 16 47] | [BCDA 2 23 48] |

Round 4

formule à appliquer en fonction du tableau :

a = b + [ (a + I(b,c,d) + X[k] + T[i]) <<<s ]

16 opérations du round 4
[ABCD 0 6 49] | [DABC 7 10 50] | [CDAB 14 15 51] | [BCDA 5 21 52] |
o[ABCD 12 6 53] | [DABC 3 10 54] | [CDAB 10 15 55] | [BCDA 1 21 56] |
o[ABCD 8 6 57] | [DABC 15 10 58] | [CDAB 6 15 59] | [BCDA 13 21 60] |
o[ABCD 4 6 61] | [DABC 11 10 62] | [CDAB 2 15 63] | [BCDA 9 21 64] |

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.

 

Document créé le 24/06/05 02:16, dernière modification le 23/03/18 09:27
Source du document imprimé : https://www.gaudry.be/crypto-md5.html

L'infobrol est un site personnel dont le contenu n'engage que moi. Le texte est mis à disposition sous licence CreativeCommons(BY-NC-SA). Plus d'info sur les conditions d'utilisation et sur l'auteur.