MD5

L'algorithme de signature MD5, pour Message Digest 5, est une fonction de hachage encore très populaire, mais qui n'est plus considéré comme un algorithme sûr. On suggère maintenant d'utiliser plutôt un algorithme basé sur le SHA-1 ou de type RIPEMD-160. Le MD5 a été inventé par Ronald Rivest.

Sommaire
1 Introduction - Qu'est-ce que MD5 ?
2 Exemple
3 Attaques
4 Algorithme

4.1 Padding
4.2 Ajout de la taille
4.3 Calcul de l'empreinte

5 Conclusion
6 Annexe - La norme little endian
7 Annexe - Implémentation de MD5

7.1 Utilisation

7.1.1 Allocation mémoire
7.1.2 Taille des messages
7.1.3 Plate-forme

7.2 Fichiers

Introduction - Qu'est-ce que MD5 ?

MD5 (Message Digest version 5) est un algorithme d'identification qui permet d'obtenir pour chaque message une empreinte numérique (en l'occurrence une séquence de 128 bits) avec une probabilité forte que, pour deux messages différents, leurs empreintes soient différentes.

Deux messages très similaires (par exemple : un caractère différent) auront avec une très forte probabilité des empreintes totalement différentes. C'est un algorithme à sens unique car l'empreinte ne permet pas de retrouver facilement le message.

MD5 est utilisé comme un outil de vérification supplémentaire lors des téléchargements (par exemple, en FTP). Les sites affichent souvent la signature en MD5 de leurs fichiers. L'utilisateur peut donc valider l'intégrité de la version téléchargée grâce à l'empreinte. Ceci peut se faire avec un programme comme « md5sum ». Cette mesure permet d'éviter de télécharger une version contenant un virus ou tout autre code suspect provenant d'un site non-officiel.

MD5 peut aussi être utilisé pour enregistrer une empreinte d'un mot de passe. En effet, il est plus sûr de stocker des empreintes MD5 plutot que les mots de passe eux-mêmes, de sorte que si quelqu'un accède à cette liste, il ne puisse pas (ou difficilement) trouver les mots de passe.

Exemple

Voici la signature obtenue sur une phrase :

MD5("Wikipedia, l'encyclopedie libre et gratuite") = d6aa97d33d459ea3670056e737c99a3d

En modifiant un caractère, la signature change radicalement :

MD5("Wikipedia, l'encyclopedie libre et gratuitE") = 5da8aa7126701c9840f99f8e9fa54976

Attaques

Considéré comme sûr au départ, son efficacité s'est peu à peu effritée grâce à la découverte de failles potentielles dans son fonctionnement. Le MD5 a été cassé durant l'été 2004 par des chercheurs chinois, Xiaoyun Wang, Dengguo Feng, Xuejia Lai (co-inventeur du célèbre chiffrage IDEA) et Hongbo Yu. Leur attaque a permis de découvrir une collision complète sans passer par une méthode de type brute-force [1] [2]. Sur un système parallélisé, les calculs n'ont pris que quelques heures. Le MD5 n'est donc plus considéré comme sûr mais l'algorithme développé par les Chinois concerne des collisions quelconques et ne permet pas de forger une collision sur une signature spécifique. Un projet de calcul distribué lancé en mars 2004, MD5CRK, visait à découvrir une collision complète mais a été subitement arrêté après la découverte de l'équipe chinoise. La sécurité du MD5 n'étant plus garantie selon sa définition cryptographique, les spécialistes recommandent d'utiliser des fonctions de hachage plus récentes comme le SHA-256.

On peut désormais générer une infinité de collisions avec un texte quelconque qui se verra concaténé avec les deux messages formant la collision complète. On ne peut toutefois pas générer une signature particulière et la falsification de documents reste un exercice difficile. Un projet indépendant, nommé MD6 mais sans appui officiel semble-t-il, vise à améliorer le MD5 avec quelques modifications simples dans son architecture [3].

Algorithme

Padding

Le message, complété d'un bit supplémentaire obligatoire valant 1, doit avoir une taille en bits Tb telle que Tb = 448 modulo 512.

Si ça n'est pas le cas, on effectue un padding, en ajoutant autant de bits valant 0 que nécessaire. Dans le pire des cas, on ajoutera 512 bits au message, c'est-à-dire le bit obligatoire valant 1, suivi de 511 bits nuls.

Cette méthode de padding est semblable à celle utilisée dans la plupart des algorithmes de Message Digest des familles MD (MD2, MD4, MD5, RIPEMD, RIPEMD-128, RIPEMD-160, RIPEMP-256, RIPEMD-320) ou SHA (SHA-0, SHA-1, SHA-224, SHA-256, SHA-384, SHA-512) ou moins connus comme Haval et Whirlpool, mais différente de celle de l'algorithme Tiger qui utilise une convention dite Little endian d'ordonnancement des bits dans chaque octet.

Ajout de la taille

On ajoute ensuite la longueur du message en bits (sans le bit ajouté à 1 et sans le padding éventuel) à la fin du message étendu. Cette taille est ajoutée sur 64 bits en Little endian (cf. annexe).

Le message a maintenant une taille en bits multiple de 512, c'est-à-dire qu'il contient un multiple de 16 mots de 32 bits.

Calcul de l'empreinte

Initialisation

On considère les registres A, B, C et D suivants :

Ainsi que les fonctions suivantes :

(la 2e notation correspond au langage C)

(<<< s représente une rotation circulaire à gauche de s bits)

Notez qu'il est souvent plus optimal d'utiliser les fonctions équivalentes:

Et le tableau T suivant :

M représente le message (message original + padding + longueur du message original). M[n-1] représente le n-ième mot de 32 bits du message.
N est le nombre de mots de 32 bits.
X est un tableau de 16 mots de 32 bits.
AA, BB, CC et DD sont des registres tampons.

Calcul

Voici le pseudo-code correspondant aux calculs à effectuer : 

 Boucle i de 0 à N/16 - 1
  Faire
    Boucle j de 0 à 15
    Faire
      X[j] = M[i*16 + j]
    FinBoucle j
    AA = A
    BB = B
    CC = C
    DD = D
    
    /* Ronde 1 */
    FF(A, B, C, D, 0, 7, 0)
    FF(D, A, B, C, 1, 12, 1)
    FF(C, D, A, B, 2, 17, 2)
    FF(B, C, D, A, 3, 22, 3)
    FF(A, B, C, D, 4, 7, 4)
    FF(D, A, B, C, 5, 12, 5)
    FF(C, D, A, B, 6, 17, 6)
    FF(B, C, D, A, 7, 22, 7)
    FF(A, B, C, D, 8, 7, 8)
    FF(D, A, B, C, 9, 12, 9)
    FF(C, D, A, B, 10, 17, 10)
    FF(B, C, D, A, 11, 22, 11)
    FF(A, B, C, D, 12, 7, 12)
    FF(D, A, B, C, 13, 12, 13)
    FF(C, D, A, B, 14, 17, 14)
    FF(B, C, D, A, 15, 22, 15)
    
    /* Ronde 2 */
    GG(A, B, C, D, 1, 5, 16)
    GG(D, A, B, C, 6, 9, 17)
    GG(C, D, A, B, 11, 14, 18)
    GG(B, C, D, A, 0, 20, 19)
    GG(A, B, C, D, 5, 5, 20)
    GG(D, A, B, C, 10, 9, 21)
    GG(C, D, A, B, 15, 14, 22)
    GG(B, C, D, A, 4, 20, 23)
    GG(A, B, C, D, 9, 5, 24)
    GG(D, A, B, C, 14, 9, 25)
    GG(C, D, A, B, 3, 14, 26)
    GG(B, C, D, A, 8, 20, 27)
    GG(A, B, C, D, 13, 5, 28)
    GG(D, A, B, C, 2, 9, 29)
    GG(C, D, A, B, 7, 14, 30)
    GG(B, C, D, A, 12, 20, 31)
    
    /* Ronde 3 */
    HH(A, B, C, D, 5, 4, 32)
    HH(D, A, B, C, 8, 11, 33)
    HH(C, D, A, B, 11, 16, 34)
    HH(B, C, D, A, 14, 23, 35)
    HH(A, B, C, D, 1, 4, 36)
    HH(D, A, B, C, 4, 11, 37)
    HH(C, D, A, B, 7, 16, 38)
    HH(B, C, D, A, 10, 23, 39)
    HH(A, B, C, D, 13, 4, 40)
    HH(D, A, B, C, 0, 11, 41)
    HH(C, D, A, B, 3, 16, 42)
    HH(B, C, D, A, 6, 23, 43)
    HH(A, B, C, D, 9, 4, 44)
    HH(D, A, B, C, 12, 11, 45)
    HH(C, D, A, B, 15, 16, 46)
    HH(B, C, D, A, 2, 23, 47)
    
    /* Ronde 4 */
    II(A, B, C, D, 0, 6, 48)
    II(D, A, B, C, 7, 10, 49)
    II(C, D, A, B, 14, 15, 50)
    II(B, C, D, A, 5, 21, 51)
    II(A, B, C, D, 12, 6, 52)
    II(D, A, B, C, 3, 10, 53)
    II(C, D, A, B, 10, 15, 54)
    II(B, C, D, A, 1, 21, 55)
    II(A, B, C, D, 8, 6, 56)
    II(D, A, B, C, 15, 10, 57)
    II(C, D, A, B, 6, 15, 58)
    II(B, C, D, A, 13, 21, 59)
    II(A, B, C, D, 4, 6, 60)
    II(D, A, B, C, 11, 10, 61)
    II(C, D, A, B, 2, 15, 62)
    II(B, C, D, A, 9, 21, 63)
    
    A = A + AA
    B = B + BB
    C = C + CC
    D = D + DD
  FinBoucle i

Résultats

Le résultat correspond aux registres A, B, C, D concaténés de l'octet de poids faible de A à l'octet de poids fort de D.

C'est-à-dire :
(Digest est une chaîne de 16 caractères, Digest[n-1] est le n-ième caractère, le 1er octet est l'octet de poids faible, ..., le 4e est l'octet de poids fort)

Digest[0] = 1er octet de A
Digest[1] = 2e octet de A
Digest[2] = 3e octet de A
Digest[3] = 4e octet de A
Digest[4] = 1er octet de B
Digest[5] = 2e octet de B
Digest[6] = 3e octet de B
Digest[7] = 4e octet de B
Digest[8] = 1er octet de C
Digest[9] = 2e octet de C
Digest[10] = 3e octet de C
Digest[11] = 4e octet de C
Digest[12] = 1er octet de D
Digest[13] = 2e octet de D
Digest[14] = 3e octet de D
Digest[15] = 4e octet de D

L'empreinte de M est Digest.

Conclusion

MD5 est donc un algorithme rapide et simple à implémenter, mais il ne faut pas oublier que des failles ont été trouvées et qu'il n'est plus recommandé de l'utiliser. Toutefois, si une attaque par le paradoxe des anniversaires n'est pas envisageable (comme par exemple lorsqu'on utilise le MD5 pour prendre l'empreinte d'un mot de passe), le MD5 est « quasiment sûr ». En 2005, il requiert en effet, si le mot de passe dont on a prit l'empreinte est bien choisi, une puissance de calcul bien trop grande pour être attaqué en temps utile.

Annexe - La norme little endian

Pour comprendre ce qu'est la norme little endian, voyons un exemple avec ce petit code assembleur :

mov ax,1234h
mov es:[di],ax
mov al,es:[di]

La 1re ligne place le nombre 0x1234 dans le registre AX (2 octets).
La seconde enregistre ensuite ce nombre en mémoire.
La dernière lit 1 seul octet depuis la mémoire.
AL contient alors ... 0x34 !

Et oui, par souci de performance, les processeurs Intel inversent les octets lorqu'ils passent de la mémoire au processeur et vice versa. Ainsi, le registre AX contient 0x1234 mais place en mémoire 0x3412 donc la dernière instruction place 0x34 dans AL.

Pour cela, les processeurs Intel sont dits little endian.

On peut résumer cette norme comme suit :
Le 1er octet est l'octet de poids faible, le second, celui de poids fort.

De même, 0x11223344 en little endian correspond à 0x44332211.

Voir Little endian

Annexe - Implémentation de MD5

Voici une implémentation de MD5 que vous êtes libres d'utiliser comme bon vous semble.

Utilisation

#include <md5.h>

typedef unsigned long md5_size;
Ce type est utilisé pour les tailles des messages.
Le type unsigned long est l'un des défauts de cette implémentation (cf. plus bas).

md5_size md5_needed(char *M, md5_size len);
Cette fonction reçoit en paramètre le message M de taille len.
Elle calcule puis renvoie la taille de M après padding et ajout de la taille.

En effet, c'est au programmeur de contrôler que la mémoire allouée est suffisamment grande pour ces opérations.

char *md5(char *M, md5_size len, char *Digest);
Cette fonction calcule l'empreinte de M, un message de longueur len. Cette empreinte est stockée dans Digest.
La fonction renvoie le pointeur Digest.
Digest doit pointer vers une zone d'au moins 16 octets.

Allocation mémoire

C'est au programmeur que revient la tâche d'allouer la mémoire nécessaire car les opérations de padding et d'ajout de la taille sont réalisées directement à l'adresse indiquée par le pointeur recu en argument. De plus, la chaîne envoyée est alors modifiée.

Taille des messages

Normalement, MD5 peut fonctionner avec des messages dont la taille en bits tient sur 64 bits (voire plus). Or, ici, le type utilisée pour la taille en octets est unsigned long (soit 32 bits). La taille en bits tient donc sur 35 bits au maximum.

Lorsque md5_size équivaut à unsigned long, la compilation produit 3 warnings lignes 67, 68 et 69. C'est tout à fait normal.

Plate-forme

Ces fonctions n'ont été écrites que pour des machines à la norme little endian.

Fichiers


Image manquante
Key-crypto-sideways.png


Portail Cryptologie - Accédez d'un seul coup d’œil à toute la série des articles « Cryptologie » de Wikipédia.

See also: MD5, Algorithme, En 2005, File Transfer Protocol, Fonction de hachage