MD5

L' algorithme de hachage MD5 est une fonction de hachage largement utilisée qui produit une valeur de hachage de 128 bits . MD5 a été conçu par Ronald Rivest en 1991 pour remplacer une fonction de hachage antérieure MD4 , et a été spécifié en 1992 dans la RFC 1321.

MD5 peut être utilisé comme somme de contrôle pour vérifier l'intégrité des données contre toute corruption involontaire. Historiquement, il a été largement utilisé comme fonction de hachage cryptographique ; cependant, il s'est avéré souffrir de nombreuses vulnérabilités. Il reste adapté à d'autres fins non cryptographiques, par exemple pour déterminer la partition d'une clé particulière dans une base de données partitionnée , et peut être préféré en raison des exigences de calcul inférieures aux algorithmes de hachage sécurisé plus récents .

MD5 fait partie d'une série d' algorithmes de synthèse de messages conçus par le professeur Ronald Rivest du MIT (Rivest, 1992). Lorsque des travaux d'analyse ont indiqué que le prédécesseur de MD5, MD4, était susceptible d'être peu sûr, Rivest a conçu MD5 en 1991 comme un remplacement sécurisé. ( Hans Dobbertin a effectivement trouvé plus tard des faiblesses dans MD4.)

En 1993, Den Boer et Bosselaers ont donné un résultat précoce, bien que limité, en trouvant une « pseudo-collision » de la fonction de compression MD5 ; c'est-à-dire deux vecteurs d'initialisation différents qui produisent un condensé identique.

En 1996, Dobbertin a annoncé une collision de la fonction de compression de MD5 (Dobbertin, 1996). Bien qu'il ne s'agisse pas d'une attaque contre la fonction de hachage MD5 complète, elle était suffisamment proche pour que les cryptographes recommandent de passer à un remplacement, tel que SHA-1 (également compromis depuis) ​​ou RIPEMD-160 .

La taille de la valeur de hachage (128 bits) est suffisamment petite pour envisager une attaque d'anniversaire . MD5CRK était un projet distribué lancé en mars 2004 pour démontrer que MD5 est pratiquement non sécurisé en trouvant une collision à l'aide d'une attaque d'anniversaire.

MD5CRK a pris fin peu après le 17 août 2004, lorsque des collisions pour le MD5 complet ont été annoncées par Xiaoyun Wang , Dengguo Feng, Xuejia Lai et Hongbo Yu. Leur attaque analytique n'aurait pris qu'une heure sur un cluster IBM p690 .

Le 1er mars 2005, Arjen Lenstra , Xiaoyun Wang et Benne de Weger ont démontré la construction de deux certificats X.509 avec des clés publiques différentes et la même valeur de hachage MD5, une collision démontrable. La construction comprenait des clés privées pour les deux clés publiques. Quelques jours plus tard, Vlastimil Klima a décrit un algorithme amélioré, capable de construire des collisions MD5 en quelques heures sur un seul ordinateur portable. Le 18 mars 2006, Klima a publié un algorithme capable de trouver une collision en une minute sur un seul ordinateur portable, en utilisant une méthode qu'il appelle tunneling.

Plusieurs errata RFC liés à MD5 ont été publiés. En 2009, le Cyber ​​Command des États-Unis a utilisé une valeur de hachage MD5 de sa déclaration de mission comme partie de son emblème officiel.

Le 24 décembre 2010, Tao Xie et Dengguo Feng ont annoncé la première collision MD5 publiée en bloc unique (512 bits). (Les précédentes découvertes de collisions reposaient sur des attaques multiblocs.) Pour des « raisons de sécurité », Xie et Feng n'ont pas révélé la nouvelle méthode d'attaque. Ils ont lancé un défi à la communauté cryptographique, offrant une récompense de 10 000 $ US au premier découvreur d'une collision différente de 64 octets avant le 1er janvier 2013. Marc Stevens a répondu au défi et a publié des messages de collision en bloc unique ainsi que l'algorithme de construction et les sources.

En 2011, une RFC 6151 informative a été approuvée pour mettre à jour les considérations de sécurité dans MD5 et HMAC-MD5.

L'une des exigences de base de toute fonction de hachage cryptographique est qu'il soit impossible de trouver deux messages distincts hachés avec la même valeur. MD5 échoue de manière catastrophique à cette exigence. Le 31 décembre 2008, le CMU Software Engineering Institute a conclu que MD5 était essentiellement « cryptographiquement cassé et impropre à une utilisation ultérieure ». Les faiblesses de MD5 ont été exploitées sur le terrain, notamment par le malware Flame en 2012. En 2019 , MD5 continue d'être largement utilisé, malgré ses faiblesses bien documentées et son désapprobation par les experts en sécurité.

Il existe une attaque par collision qui peut détecter des collisions en quelques secondes sur un ordinateur équipé d'un processeur Pentium 4 à 2,6 GHz (complexité de 2,24,1 ⁾ . De plus, il existe également une attaque par collision à préfixe choisi qui peut produire une collision pour deux entrées avec des préfixes spécifiés en quelques secondes, en utilisant du matériel informatique standard (complexité de 2,39 ⁾ . GPU standard . Sur un processeur graphique NVIDIA GeForce 8400GS, 16 à 18 millions de hachages par seconde peuvent être calculés. Une NVIDIA GeForce 8800 Ultra peut calculer plus de 200 millions de hachages par seconde.

Ces attaques par hachage et collision ont été démontrées en public dans diverses situations, notamment la collision de fichiers de documents et de certificats numériques . En 2015, il a été démontré que MD5 était encore assez largement utilisé, notamment par les sociétés de recherche en sécurité et d'antivirus.

En 2019, un quart des systèmes de gestion de contenu largement utilisés utiliseraient encore MD5 pour le hachage des mots de passe .

En 1996, une faille a été découverte dans la conception de MD5. Bien que cela n'ait pas été considéré comme une faiblesse fatale à l'époque, les cryptographes ont commencé à recommander l'utilisation d'autres algorithmes, tels que SHA-1 , qui s'est depuis avéré également vulnérable. En 2004, il a été démontré que MD5 n'est pas résistant aux collisions . En tant que tel, MD5 n'est pas adapté aux applications telles que les certificats SSL ou les signatures numériques qui s'appuient sur cette propriété pour la sécurité numérique. Les chercheurs ont également découvert des failles plus graves dans MD5 et décrit une attaque par collision réalisable - une méthode pour créer une paire d'entrées pour laquelle MD5 produit des sommes de contrôle identiques . D'autres progrès ont été réalisés dans le cassage de MD5 en 2005, 2006 et 2007. En décembre 2008, un groupe de chercheurs a utilisé cette technique pour falsifier la validité d'un certificat SSL .

En 2010, le CMU Software Engineering Institute considère que MD5 est « cryptographiquement cassé et impropre à une utilisation ultérieure » et la plupart des applications du gouvernement américain nécessitent désormais la famille de fonctions de hachage SHA-2 . En 2012, le malware Flame a exploité les faiblesses de MD5 pour falsifier une signature numérique Microsoft .

En 1996, des collisions ont été découvertes dans la fonction de compression de MD5, et Hans Dobbertin a écrit dans la newsletter technique de RSA Laboratories : « L'attaque présentée ne menace pas encore les applications pratiques de MD5, mais elle s'en rapproche plutôt... à l'avenir, MD5 ne devrait plus être implémenté... là où une fonction de hachage résistante aux collisions est requise. »

En 2005, les chercheurs ont pu créer des paires de documents PostScript et de certificats X.509 avec le même hachage. Plus tard cette année-là, le concepteur de MD5, Ron Rivest, a écrit que « md5 et sha1 sont tous deux clairement cassés (en termes de résistance aux collisions) ».

Le 30 décembre 2008, un groupe de chercheurs a annoncé au 25e Chaos Communication Congress comment ils avaient utilisé des collisions MD5 pour créer un certificat d'autorité de certification intermédiaire qui semblait légitime lorsqu'il était vérifié par son hachage MD5. Les chercheurs ont utilisé un cluster PS3 à l' EPFL à Lausanne , en Suisse pour changer un certificat SSL normal émis par RapidSSL en un certificat CA fonctionnel pour cet émetteur, qui pourrait ensuite être utilisé pour créer d'autres certificats qui sembleraient légitimes et émis par RapidSSL. VeriSign , l'émetteur des certificats RapidSSL, a déclaré qu'il avait cessé d'émettre de nouveaux certificats utilisant MD5 comme algorithme de somme de contrôle pour RapidSSL une fois la vulnérabilité annoncée. Bien que Verisign ait refusé de révoquer les certificats existants signés avec MD5, leur réponse a été considérée comme adéquate par les auteurs de l'exploit ( Alexander Sotirov , Marc Stevens , Jacob Appelbaum , Arjen Lenstra , David Molnar, Dag Arne Osvik et Benne de Weger). Bruce Schneier a écrit à propos de l'attaque que « nous savions déjà que MD5 était une fonction de hachage défectueuse » et que « personne ne devrait plus utiliser MD5 ». Les chercheurs SSL ont écrit : « Notre objectif est que les autorités de certification cessent d'utiliser MD5 pour émettre de nouveaux certificats. Nous espérons également que l'utilisation de MD5 dans d'autres applications sera également reconsidérée ».

En 2012, selon Microsoft , les auteurs du malware Flame ont utilisé une collision MD5 pour falsifier un certificat de signature de code Windows.

MD5 utilise la construction Merkle–Damgård , donc si deux préfixes avec le même hachage peuvent être construits, un suffixe commun peut être ajouté aux deux pour augmenter la probabilité que la collision soit acceptée comme donnée valide par l'application qui l'utilise. De plus, les techniques actuelles de recherche de collision permettent de spécifier un préfixe arbitraire : un attaquant peut créer deux fichiers en collision qui commencent tous deux par le même contenu. Tout ce dont l'attaquant a besoin pour générer deux fichiers en collision est un fichier modèle avec un bloc de données de 128 octets, aligné sur une limite de 64 octets, qui peut être modifié librement par l'algorithme de recherche de collision. Un exemple de collision MD5, avec les deux messages différant de 6 bits, est :

d131dd02c5e6eec4 693d9a0698aff95c 2fcab5 8 712467eab 4004583eb8fb7f89 55ad340609f4b302 83e4888325 7 1415a 085125e8f7cdc99f d91dbd f 280373c5b d8823e3156348f5b ae6dacd436c919c6 dd53e2 b 487da03fd 02396306d248cda0 e99f33420f577ee8 ce54b67080 a 80d1e c69821bcb6a88393 96f965 2 b6ff72a70 

d131dd02c5e6eec4 693d9a0698aff95c 2fcab5 0 712467eab 4004583eb8fb7f89 55ad340609f4b302 83e4888325 f 1415a 085125e8f7cdc99f d91dbd 7 280373c5b d8823e3156348f5b ae6dacd436c919c6 dd53e2 3 487da03fd 02396306d248cda0 e99f33420f577ee8 ce54b67080 2 80d1e c69821bcb6a88393 96f965 a b6ff72a70 

Les deux produisent le hachage MD5 79054025255fb1a26e4bc422aef54eb4. La différence entre les deux échantillons est que le bit de tête de chaque quartet a été inversé. Par exemple, le 20e octet (décalage 0x13) dans l'échantillon supérieur, 0x87, est 10000111 en binaire. Le bit de tête de l'octet (également le bit de tête du premier quartet) est inversé pour former 00000111, qui est 0x07, comme indiqué dans l'échantillon inférieur.

Plus tard, il a également été découvert qu'il était possible de construire des collisions entre deux fichiers avec des préfixes choisis séparément. Cette technique a été utilisée dans la création du certificat CA non autorisé en 2008. Une nouvelle variante de recherche de collision parallélisée utilisant MPI a été proposée par Anton Kuznetsov en 2014, qui a permis de trouver une collision en 11 heures sur un cluster de calcul.

En avril 2009, une attaque contre MD5 a été publiée, qui brise la résistance de la préimage de MD5 . Cette attaque n'est que théorique, avec une complexité de calcul de 2 ^123,4 pour la préimage complète.

Les condensés MD5 ont été largement utilisés dans le monde des logiciels pour fournir une certaine assurance qu'un fichier transféré est arrivé intact. Par exemple, les serveurs de fichiers fournissent souvent une somme de contrôle MD5 pré-calculée (appelée md5sum ) pour les fichiers, afin qu'un utilisateur puisse comparer la somme de contrôle du fichier téléchargé à celle-ci. La plupart des systèmes d'exploitation basés sur Unix incluent des utilitaires de somme MD5 dans leurs packages de distribution ; les utilisateurs Windows peuvent utiliser la fonction PowerShell incluse « Get-FileHash », la fonction de ligne de commande incluse « certutil -hashfile <filename> md5 », installer un utilitaire Microsoft, ou utiliser des applications tierces. Les ROM Android utilisent également ce type de somme de contrôle.

Comme il est facile de générer des collisions MD5, il est possible que la personne qui a créé le fichier crée un deuxième fichier avec la même somme de contrôle, de sorte que cette technique ne peut pas protéger contre certaines formes de falsification malveillante. Dans certains cas, la somme de contrôle n'est pas fiable (par exemple, si elle a été obtenue via le même canal que le fichier téléchargé), auquel cas MD5 ne peut fournir qu'une fonctionnalité de vérification des erreurs : il reconnaîtra un téléchargement corrompu ou incomplet, ce qui devient plus probable lors du téléchargement de fichiers plus volumineux.

Historiquement, MD5 a été utilisé pour stocker un hachage unidirectionnel d'un mot de passe , souvent avec un étirement de clé . Le NIST n'inclut pas MD5 dans sa liste de hachages recommandés pour le stockage de mots de passe.

Le MD5 est également utilisé dans le domaine de la découverte électronique , pour fournir un identifiant unique à chaque document échangé au cours du processus de découverte juridique. Cette méthode peut être utilisée pour remplacer le système de numérotation par tampon Bates qui est utilisé depuis des décennies lors de l'échange de documents papier. Comme ci-dessus, cette utilisation doit être découragée en raison de la facilité des attaques par collision.

MD5 transforme un message de longueur variable en une sortie de longueur fixe de 128 bits. Le message d'entrée est divisé en blocs de 512 bits (seize mots de 32 bits) ; le message est complété de manière à ce que sa longueur soit divisible par 512. Le remplissage fonctionne comme suit : tout d'abord, un seul bit, 1, est ajouté à la fin du message. Il est suivi d'autant de zéros que nécessaire pour amener la longueur du message à 64 bits de moins qu'un multiple de 512. Les bits restants sont complétés avec 64 bits représentant la longueur du message d'origine, modulo 2 ⁶⁴ .

L'algorithme MD5 principal fonctionne sur un état de 128 bits, divisé en quatre mots de 32 bits, notés A , B , C et D. Ceux-ci sont initialisés à certaines constantes fixes. L'algorithme principal utilise ensuite chaque bloc de message de 512 bits à tour de rôle pour modifier l'état. Le traitement d'un bloc de message se compose de quatre étapes similaires, appelées tours ; chaque tour est composé de 16 opérations similaires basées sur une fonction non linéaire F , une addition modulaire et une rotation à gauche. La figure 1 illustre une opération au sein d'un tour. Il existe quatre fonctions possibles ; une fonction différente est utilisée à chaque tour :

Le hachage MD5 est calculé selon cet algorithme. Toutes les valeurs sont en little-endian .

// : Toutes les variables sont non signées sur 32 bits et s'enroulent modulo 2^32 lors du calcul de
 var 
int s[64], K[64] var 
int i // s spécifie les montants de décalage par tour 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 } // Utilisez la partie entière binaire des sinus des entiers (Radians) comme constantes :
 pour i de 0 à 63 do K[i] := floor(2 32 × abs(sin(i + 1))) end for 
// (Ou utilisez simplement le tableau précalculé suivant) : K[ 0.. 3] := { 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee } K[ 4.. 7] := { 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501 } K[ 8..11] := { 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be } K[12..15] := { 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821 } K[16..19] := { 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa } K[20..23] := { 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8 } K[24..27] := { 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed } K[28..31] := { 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a } K[32..35] := { 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c } K[36..39] := { 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70 } K[40..43] := { 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05 } K[44..47] := { 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665 } K[48..51] := { 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039 } K[52..55] := { 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1 } K[56..59] := { 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1 } K[60..63] := { 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 } // Initialiser les variables :
 var 
int a0 := 0x67452301 // A 
var 
int b0 := 0xefcdab89 // B 
var 
int c0 := 0x98badcfe // C 
var 
int d0 := 0x10325476 // D
// Prétraitement : ajout d'un seul bit
 append "1" au message< // Remarque : les octets d'entrée sont considérés comme des chaînes de bits, // où le premier bit est le bit le plus significatif de l'octet. // Prétraitement : remplissage avec des zéros,
 ajout du bit « 0 » jusqu'à ce que la longueur du message en bits ≡ 448 (mod 512) // Remarque : les deux étapes de remplissage ci-dessus sont implémentées de manière plus simple // dans les implémentations qui fonctionnent uniquement avec des octets complets : ajouter 0x80 // et compléter avec 0x00 octets pour que la longueur du message en octets ≡ 56 (mod 64).
ajouter la longueur d'origine en bits mod 2 64 
au message // Traitez le message en blocs successifs de 512 bits :
 pour chaque bloc de 512 bits du message complété, effectuez diviser le fragment en seize mots de 32 bits M[j], 0 ≤ j ≤ 15  // Initialiser la valeur de hachage pour ce bloc :
 var 
int A := a0 var 
int B := b0 var 
int C := c0 var 
int D := d0  // Boucle principale :
 pour i de 0 à 63 faire 
var 
int F, g si 0 ≤ i ≤ 15 alors F := (B et C) ou (( pas B) et D) g := je sinon si 16 ≤ i ≤ 31 alors F := (D et B) ou (( pas 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 ( pas D)) g := (7×i) mod 16  // Méfiez-vous des définitions ci-dessous de a,b,c,d F := F + A + K[i] + M[g] // M[g] doit être un bloc de 32 bits A := D D := C C := B B := B + leftrotate (F, s[i]) end for 
 // Ajouter le hachage de ce morceau au résultat jusqu'à présent : a0 := a0 + A b0 := b0 + B c0 := c0 + C d0 := d0 + D fin pour
var 
char digest[16] := a0 append b0 append c0 append d0 // (La sortie est en little-endian)

Au lieu de la formulation de la RFC 1321 d'origine présentée, ce qui suit peut être utilisé pour une efficacité améliorée (utile si le langage assembleur est utilisé - sinon, le compilateur optimisera généralement le code ci-dessus. Étant donné que chaque calcul dépend d'un autre dans ces formulations, cela est souvent plus lent que la méthode ci-dessus où le nand/and peut être parallélisé) :

( 0 ≤ i ≤ 15) : F := D xor (B et (C xor D)) (16 ≤ i ≤ 31) : F := C xor (D et (B xor C)) 

Les hachages MD5 de 128 bits (16 octets) (également appelés résumés de messages ) sont généralement représentés sous la forme d'une séquence de 32 chiffres hexadécimaux . L'exemple suivant illustre une entrée ASCII de 43 octets et le hachage MD5 correspondant :

MD5(" Le renard brun rapide saute par-dessus le chien paresseux ") = 9e107d9d372bb6826bd81d3542a419d6 

Même un petit changement dans le message entraînera (avec une probabilité écrasante) un hachage essentiellement différent, en raison de l' effet d'avalanche . Par exemple, ajouter un point à la fin de la phrase :

MD5(" Le renard brun rapide saute par-dessus le chien paresseux . ") = e4d909c290d0fb1ca068ffaddf22cbd0 

Le hachage de la chaîne de longueur nulle est :

MD5("") = d41d8cd98f00b204e9800998ecf8427e 

L'algorithme MD5 est spécifié pour les messages constitués de n'importe quel nombre de bits ; il n'est pas limité aux multiples de huit bits ( octets , octets ). Certaines implémentations MD5 telles que md5sum peuvent être limitées aux octets ou ne pas prendre en charge la diffusion en continu pour les messages d'une longueur initialement indéterminée.

Vous trouverez ci-dessous une liste des bibliothèques de cryptographie qui prennent en charge MD5 :

• Botanique
• Château gonflable
• cryptlib
• Crypto++
• Libgcrypt
• Ortie
• OpenSSL
• loupSSL