PICSI

MD5 appartient à la famille des fonctions de hachage MDC. L'algorithme MD5 est le remplaçant de la fonction de hachage MD4. Il a été montré que cette dernière ne présentait pas les garanties suffisantes de sécurité exigées par les normes en matière de cryptographie. La fonction MD5 l'a donc remplacé. MD5 est donc basé sur la fonction MD4 avec certaines modifications qui, pour le moment, assurent à cette famille de bonnes garanties comme par exemple la difficulté de trouver des collisions. Ce paragraphe n'a pas pour but de donner une description détaillée de l'algorithme MD5 en vue d'une implémentation mais de donner une idée générale de cet algorithme. Une description complète et détaillée est fournie dans les standards disponibles sur internet. Avant de s'intéresser à l'algorithme lui même, nous allons énumérer les données constantes qui interviennent dans cet algorithme. Nous reprenons les notations de l'excellent Handbook of Applied Cryptography de A.J. Menezes, P.C. van Oorschot et S.A. Vanstone et celles de la RFC 1321 The MD5 Message-Digest Algorithm.

1  Les constantes de MD5.

On définit tout d'abord 4 chaînes de 32 bits, notées h₁, h₂, h₃, h₄ et appelées chaînes initiales, par :

• h₁=0x67452301
• h₂=0xefcdab89
• h₃=0x98badcfe
• h₄=0x10325476

Trois tableaux de 64 cases sont ensuite prédéfinis (48 cellules seulement pour MD4). Pour l'algorithme MD4 le tableau appelé y était formé seulement de 3 constantes : 0, racine carrée de 2 et racine carrée de 3. Pour optimiser la sécurité, ce tableau a été modifié dans la version MD5. Les constantes se basent désormais sur des calculs de sinus. Voici sa définition exacte (tous les éléments y[j] sont de taille 32 bits) :

y[j]=4294967296×|sin(j+1)|,  0 ≤ j ≤ 63

où · désigne la partie entière. Par exemple, y[0] est égal à 4294967296×|sin(1)| et comme les mesures sont à considérer en radian on a : |sin(1)| = 0.8414709848078965066525023216 et

y[0]=3614090360

d'où en hexadécimal :

y[0]=0xd76aa478

Le tableau appelé z correspond à :

• z[0…15] = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
• z[16…31] = [1,6,11,0,5,10,15,4,9,14,3,8,13,2,7,12]
• z[32…47] = [5,8,11,14,1,4,7,10,13,0,3,6,9,12,15,2]
• z[48…63] = [0,7,14,5,12,3,10,1,8,15,6,13,4,11,2,9]

et celui appelé s

• s[0…15] = [7,12,17,22,7,12,17,22,7,12,17,22,7,12,17,22]
• s[16…31] = [5,9,14,20,5,9,14,20,5,9,14,20,5,9,14,20]
• s[32…47] = [4,11,16,23,4,11,16,23,4,11,16,23,4,11,16,23]
• s[48…63] = [6,10,15,21,6,10,15,21,6,10,15,21,6,10,15,21]

Ce dernier tableau correspond aux rotations à gauche de l'algorithme.

2  Formatage des données en entrée.

Par définition, une fonction de hachage accepte en entrée une chaîne de caractères de longueur arbitraire. Pour MD5, le résultat de cette fonction est une empreinte ou un haché ou tout simplement une chaîne de caractères de longueur 128 bits soit 16 octets. Le message en entrée, noté x, doit donc subir quelques transformations pour le rendre "standard" et que les opérations de l'algorithme lui soit applicables. On note aussi l la longueur du message originale x. Il faut dans un premier temps agrandir le message de telle sorte que l'on obtienne un nouveau message de longueur un multiple de 512 bits. Cette opération s'appelle le "padding". La méthode de padding utilisée dans MD5 est très simple. On cherche d'abord la quantité t telle que la longueur de x plus t soit la plus petite logueur multiple de 512 bits. On prend le message x et on ajoute un bit à 1 (à gauche) de x. On rajoute alors t−65 bits égaux à zéros. Il reste donc 64 bits à remplir. Pour compléter ces 64 bits, on calcule :

l mod 264

On obtient un mot de 64 bits que l'on "coupe" en deux mots de 32 bits et qu'on intervertit (le premier mot va en deuxième position et réciproquement). Dans un langage plus scientifique, on intervertit les mots de poids faible et fort. On obtient donc finalement un mot, noté encore par défaut x, tel que

x=x0x1x1…x16m−1

où les x_i sont des mots de 32 bits et m est l'entier tel que :

l+t=512m

On peut vérifier que les x_i sont bien des mots de 32 bits puisque [512m/16m]=32.

3  Les étapes de l'algorithme.

1. Initialisation :
   • H₁← h₁
   • H₂← h₂
   • H₃← h₃
   • H₄← h₄
   • A← h₁
   • B← h₂
   • C← h₃
   • D← h₄
2. Pour i=0 à m−1 faire :
   1. X[j]← x_16i+j, 0 ≤ j ≤ 15
   2. Première phase : Pour j=0…15
      • t← (A+f(B,C,D)+X[z[j]]+y[j])
      • A← D
      • t← B+(t\curvearrowleft s[j])
      • D← C
      • C← B
      • B← t
   3. Deuxième phase : Pour j=16…31
      • t← (A+g(B,C,D)+X[z[j]]+y[j])
      • A← D
      • t← B+(t\curvearrowleft s[j])
      • D← C
      • C← B
      • B← t
   4. Troisième phase : Pour j=32…47
      • t← (A+h(B,C,D)+X[z[j]]+y[j])
      • A← D
      • t← B+(t\curvearrowleft s[j])
      • D← C
      • C← B
      • B← t
   5. Quatrième phase : Pour j=48…63
      • t← (A+k(B,C,D)+X[z[j]]+y[j])
      • A← D
      • t← B+(t\curvearrowleft s[j])
      • D← C
      • C← B
      • B← t
   6. H₁← A+H₁
   7. H₂← B+H₂
   8. H₃← C+H₃
   9. H₄← D+H₄
3. Concaténation finale (4×32 = 128 bits): MD5(x)=H₁||H₂||H₂||H₃||H₄