MD5

1. Origine

MD5 (Message Digest version 5) est une fonction de hachage cryptographique qui permet d’obtenir pour chaque message une empreinte numérique (en l’occurrence une séquence de 128 bits) avec une probabilité très forte que, pour deux messages différents, leurs empreintes soient 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. En 1996, une faille est découverte et laissait entendre que MD5 devait ê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.

Toutefois, MD5 reste encore très utilisé comme outil de vérification 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, c'est le système employé dans GNU/Linux avec la présence d'un sel. En effet, il est plus sûr de stocker des empreintes MD5 plutôt que les mots de passe eux-mêmes, de sorte que si quelqu'un accède à cette liste, il ne puisse pas trouver les mots de passe, du moins ceux qui ne sont pas triviaux.

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

3. Cryptanalyse

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

4. Algorithme

Une opération de MD5. MD5 comprend 64 blocs de ce type, groupés en quatre tours de 16 opérations. ’F est 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érations

4.1. Notation

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

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

4.3. 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 and 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 stages, eux-mêmes subdivisés en 16 opérations similaires basées sur une fonction non-linéaire F qui varie selon le tour, une addition et une rotation vers la gauche. Les quatre fonctions non-linéaires disponibles sont :

F(X,Y,Z) = (XwedgeY)vee(egXwedgeZ)

G(X,Y,Z) = (XwedgeZ)vee(YwedgeegZ)

H(X,Y,Z) = XoplusYoplusZ

I(X,Y,Z) = Yoplus(XveeegZ)

5. 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:
 ajouter "1" bit au message
 ajouter "0" bits jusqu’à ce que la taille du message soit ≡ 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 principale:
     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
 
     //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)

6. Implémentations de MD5

Il existe un grand nombres d'implémentation 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 ou Java.

• LibTomCrypt (C/C++)
  • (C/C++)
    • Fast MD5 implementation (Java)
      • Implémentation de Fabien Pollet en C
        • Classe MessageDigest (Java)

          
          Important !
          Ce document contient des informations provenant à l'origine de l'encyclopédie collaborative Wikipédia. Même s'il a fait l'objet d'une validation rapide et s'il a pu être corrigé depuis, toutes les informations qu'il contient n'ont pu être vérifiées, aussi nous vous recommandons la consultation d'autres sources avant de l'utiliser.
          

          

          Ce document « MD5 » est publié en ligne sur le site Libre Savoir.

          
          Vous pouvez en consulter la dernière version à l’adresse https://libresavoir.org/index.php?title=MD5.
          Vous avez la permission de copier, distribuer et/ou modifier ce document selon les termes de la « Licence de documentation libre GNU », dans sa version 1.2 ou plus récente publiée par la Free Software Foundation ; sans sections inaltérables, sans texte de première page de couverture et sans texte de dernière page de couverture.

          Copyright (c) les auteurs sur Libre Savoir.

          
          Thème:Algorithme de hachage