Message Digest 5

Vue générale de MD5

L'algorithme MD5, pour Message Digest 5, est une fonction de hachage cryptographique qui permet d'obtenir l'empreinte numérique d'un fichier (on parle souvent de message). Il a été inventé par Ronald Rivest.

Origine

MD5 (Message Digest 5) est une fonction de hachage cryptographique qui calcule, à partir d'un fichier numérique, son empreinte numérique (en l'occurrence une séquence de 128 bits ou 32 caractères en notation hexadécimale) avec une probabilité très forte que deux fichiers différents donnent deux empreintes différentes.

En 1991, Ronald Rivest améliore l'architecture de MD4 pour contrer des attaques potentielles qui seront confirmées plus tard par les travaux de Hans Dobbertin.

Cinq ans plus tard, en 1996, une faille qualifiée de grave (possibilité de créer des collisions à la demande) est découverte et indique que MD5 devrait être mis de côté au profit de fonctions plus robustes comme SHA-1.

En 2004, une équipe chinoise découvre des collisions complètes. MD5 n'est donc plus considéré comme sûr au sens cryptographique. On suggère maintenant d'utiliser plutôt des algorithmes tels que SHA-256, RIPEMD-160 ou Whirlpool.

Cependant, la fonction MD5 reste encore largement utilisée comme outil de vérification lors des téléchargements et l'utilisateur peut valider l'intégrité de la version téléchargée grâce à l'empreinte. Ceci peut se faire avec un programme comme md5sum pour MD5 et sha1sum pour SHA-1.

MD5 peut aussi être utilisé pour calculer l'empreinte d'un mot de passe ; c'est le système employé dans GNU/Linux avec la présence d'un sel compliquant le décryptage. Ainsi, plutôt que de stocker les mots de passe dans un fichier, ce sont leurs empreintes MD5 qui sont enregistrées, de sorte que quelqu'un qui lirait ce fichier ne pourra pas découvrir les mots de passe.

Le programme John the ripper permet de casser les MD5 triviaux par force brute. Des serveurs de « tables inverses » (à accès direct, et qui font parfois plusieurs gigaoctets) permettent de les craquer souvent en moins d'une seconde – cf. les Rainbow attacks.

Exemple

Voici l'empreinte (appelée abusivement signature) obtenue sur une phrase :

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

En modifiant un caractère, cette empreinte change radicalement :

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

Très concrètement, la vérification de l'empreinte ou somme de contrôle MD5 peut-être réalisée de la façon suivante: lors du téléchargement d'un programme, on note la série de caractères indiquée sur la page de téléchargement. Quand ce téléchargement est terminé, on lance un utilitaire de calcul MD5, comme par exemple HashCalc ou md5sums, qui indique entre autres la somme de contrôle correspondant au fichier. Si les deux valeurs correspondent, on peut alors raisonnablement considérer que le fichier n'a pas été corrompu (volontairement ou non d'ailleurs). On constate plusieurs fragilités dans ce processus : la page d'origine a pu être modifiée, et l'utilitaire de calcul peut être adapté pour fournir la signature attendue. C'est pourquoi il faut impérativement utiliser un utilitaire provenant d'une source de confiance. On peut aussi utiliser une extension pour le navigateur Firefox comme MD Hash tool^[1] afin d'automatiser ce contrôle.

Cryptanalyse

À ses débuts, la fonction MD5 était considérée comme sûre, mais au cours du temps, des failles potentielles ont été découvertes dans son fonctionnement et durant l'été 2004, il a été cassé par des chercheurs chinois, Xiaoyun Wang, Dengguo Feng, Xuejia Lai (co-inventeur du célèbre algorithme de chiffrement IDEA) et Hongbo Yu. Leur attaque a permis de découvrir une collision complète (deux messages différents qui produisent la même empreinte) sans passer par une méthode de type recherche exhaustive^[2],[3].

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 ces trois chercheurs concerne des collisions quelconques et ne permet pas de réaliser une collision sur une empreinte spécifique, c'est-à-dire réaliser un deuxième message, à partir de l'empreinte d'un premier message, qui produirait la même empreinte. 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 sait maintenant générer des collisions MD5 en moins d'une minute lorsque les deux blocs en collisions sont « libres ». On peut aussi générer une infinité de collisions avec un texte T à partir de deux messages M1 et M2 de même longueur qui sont en collision. Il suffit de concaténer M1 et M2 avec T, tel que T1 = M1 + T et T2 = M2 + T, afin d'obtenir une collision complète entre T1 et T2. On ne peut toutefois pas générer une signature particulière et la falsification de documents reste un exercice difficile.

Dès 2006, il est par exemple possible de créer des pages HTML aux contenus très différents et ayant pourtant le même MD5. La présence de métacodes de « bourrage » placés en commentaires, visibles seulement dans la source de la page web, trahit toutefois les pages modifiées pour usurper le MD5 d'une autre. La supercherie peut donc être levée si on examine la source de la page en question.

En 2008, le logiciel BarWF^[4] utilise les ressources des instructions SSE2 et des processeurs massivement parallèles d'une carte graphique (CUDA) pour casser du MD5 en force brute à la vitesse annoncée de 350 millions de clés par seconde.

Algorithme

Une opération de MD5. MD5 comprend 64 blocs de ce type, groupés en quatre tours de 16 opérations. F est une fonction non-linéaire, qui varie selon le tour. M_i symbolise un bloc de 32 bits provenant du message à hacher et K_i est une constante de 32 bits, différentes pour chaque opération.

Notation

•  [<<<]_s est une rotation de s bits vers la gauche, s varie pour chaque opération.
•  [+] symbolise l'addition modulo 2³².
•   symbolisent respectivement les opérations booléennes XOR, AND, OR et NOT.

Préparation du message

MD5 travaille avec un message de taille variable et produit une empreinte de 128 bits. Le message est divisé en blocs de 512 bits, on applique un remplissage de manière à avoir un message dont la longueur est un multiple de 512. Le remplissage se présente comme suit :

• on ajoute un '1' à la fin du message
• on ajoute une séquence de '0' (le nombre de zéros dépend de la longueur du remplissage nécessaire)
• on écrit la taille du message, un entier codé sur 64 bits

Ce remplissage est toujours appliqué, même si la longueur du message peut être divisée par 512. Cette méthode de padding est semblable à celle utilisée dans la plupart des algorithmes de Message Digest des familles MD (comme MD5 ou RIPEMD) ou SHA (SHA-1 ou SHA-512) mais différente de celle de l'algorithme Tiger qui utilise une convention dite Little endian d'ordonnancement des bits dans chaque octet.

La taille du message est codée en Little endian. 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.

Boucle principale

L'algorithme principal travaille avec un état sur 128 bits. Il est lui-même divisé en 4 mots de 32 bits : A, B, C et D. Ils sont initialisés au début avec des constantes. L'algorithme utilise ensuite les blocs provenant du message à hacher, ces blocs vont modifier l'état interne. Les opérations sur un bloc se décomposent en quatre rondes (étapes), elles-mêmes subdivisées en 16 opérations similaires basées sur une fonction non-linéaire F qui varie selon la ronde, une addition et une rotation vers la gauche. Les quatre fonctions non-linéaires disponibles sont :

Pseudocode

MD5 peut s'écrire sous cette forme en pseudo-code.

//Note: Toutes les variables sont sur 32 bits

//Définir r comme suit : 
var int[64] r, k
r[ 0..15] := {7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22}
r[16..31] := {5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20}
r[32..47] := {4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23}
r[48..63] := {6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21}

//MD5 utilise des sinus d'entiers pour ses constantes:
pour i de 0 à 63 faire
    k[i] := floor(abs(sin(i + 1)) × 2^32)
fin pour

//Préparation des variables:
var int h0 := 0x67452301
var int h1 := 0xEFCDAB89
var int h2 := 0x98BADCFE
var int h3 := 0x10325476

//Préparation du message (padding) :
ajouter "1" bit au message
ajouter "0" bits jusqu'à ce que la taille du message en bits soit égale à 448 (mod 512)
ajouter la taille du message codée en 64-bit little-endian au message

//Découpage en blocs de 512 bits:
pour chaque bloc de 512 bits du message
    subdiviser en 16 mots de 32 bits en little-endian w[i], 0 ≤ i ≤ 15

    //initialiser les valeurs de hachage:
    var int a := h0
    var int b := h1
    var int c := h2
    var int d := h3

    //pour principal:
    pour i de 0 à 63 faire
        si 0 ≤ i ≤ 15 alors
            f := (b et c) ou ((non b) et d)
            g := i
        sinon si 16 ≤ i ≤ 31 alors
                  f := (d et b) ou ((non d) et c)
                  g := (5×i + 1) mod 16
              sinon si 32 ≤ i ≤ 47 alors
                        f := b xor c xor d
                        g := (3×i + 5) mod 16
                    sinon si 48 ≤ i ≤ 63 alors
                              f := c xor (b ou (non d))
                              g := (7×i) mod 16
                          fin si
                    fin si
              fin si
        fin si

        var int temp := d
        d := c
        c := b
        b := ((a + f + k[i] + w[g]) leftrotate r[i]) + b
        a := temp
    fin pour

    //ajouter le résultat au bloc précédent:
    h0 := h0 + a
    h1 := h1 + b 
    h2 := h2 + c
    h3 := h3 + d
fin pour

var int empreinte := h0 concaténer h1 concaténer h2 concaténer h3 //(en little-endian)

Voir aussi

• Ronald Rivest

Liens externes

Implémentations

le RFC 1321 qui détaille l'algorithme :

• (en) RFC 1321 en anglais

Il existe un grand nombre d'implémentations pour diverses architectures et langages, avec des sources libres ou non. MD5 est maintenant intégré d'office au sein des API de plusieurs langages comme Python, PHP ou Java.

• (en)Gnu Crypto (C/C++)
• Une implémentation simple en C
• (en)Fast MD5 implementation (Java)
• (en)Classe MessageDigest (Java)
• (en)MD5 (Python Library)

Ci dessous, des logiciels de calcul MD5 pour une utilisation immédiate :

• MD5 (Conversion en ligne)
• WinMD5 de S!Ri (freeware Windows)
• mst MD5 de mst software (freeware Windows)
• MD5summer (Logiciel libre Windows)

Cryptanalyse

• (fr) L'algorithme MD5, utilisé par de nombreux sites, n'est pas fiable par Catherine Vincent
• (en) Cryptanalysis of MD5 Compress par Hans Dobbertin
• (en) New way of cryptanalyzing MD5 par Buddhi Madhav
• (en) Practical Attacks on Digital Signatures Using MD5 Message Digest par Ondrej Mikle
• (en) Finding MD5 collisions - A toy for notebook[pdf] de Vlastimil Klíma
• (en) Musings on the Wang et al. MD5 Collision[pdf] de P. Hawkes et al. (description précise et formelle de la recherche de collisions)

Références

• Portail de la cryptologie