Cryptographie!

Etude d'une fonction de hachage : le MD5

  Rappelons qu'une fonction de hachage calcule le résumé d'un texte, et que ce résumé doit être très sensible au texte initial (une petite modification du texte doit provoquer une grande modification du résumé). Une des fonctions de hachage les plus utilisées (du moins jusqu'en 2005) fut MD5 (pour Message Digest 5). Elle n'est plus considérée comme sûre pour un usage en cryptographie car durant l'été 2004, des chercheurs chinois ont montré comment réaliser des collisions avec MD5, c'est-à-dire comment produire deux messages ayant la même empreinte (le même résumé) en appliquant l'algorithme MD5. Cela dit, le MD5 est encore utilisé pour des usages non sensibles, par exemple pour vérifier l'intégrité d'un fichier téléchargé. De plus, le MD5 est une sorte de "mythe" pour certains geeks. Par exemple, quelques heures avant le lancement de Free Mobile, en 2012, la page officielle consacrée au lancement affichait cette suite un peu étrange : "efb7929e6a5b7dcc6ebb79aa3c45af13". Ceci constitue l'empreinte, après application de MD5, de la phrase "jesaispas".

  Voyons maintenant comment fonctionne le MD5.
  • Etape 1 : Complétion
      Le message est constitué de b bits m1...mb. On complète le message par un 1, et suffisamment de 0 pour que le message étendu ait une longueur congruente à 448, modulo 512. Puis on ajoute à ce message la valeur de b, codée en binaire sur 64 bits (on a donc b qui peut valoir jusque 264... ce qui est énorme). On obtient donc un message dont la longueur totale est un multiple de 512 bits. On va travailler itérativement sur chacun des blocs de 512 bits.
  • Etape 2 : Initialisation
      On définit 4 buffers de 32 bits A,B,C et D, initialisés ainsi (les chiffres sont hexadécimaux, ie a=10, b=11...).
    A=01234567
    B=89abcdef
    C=fedcba98
    D=76543210
    On définit aussi 4 fonctions F,G,H et I, qui prennent des arguments codés sur 32 bits, et renvoie une valeur sur 32 bits, les opérations se faisant bit à bit.
    F(X,Y,Z) = (X AND Y) OR (not(X) AND Z)
    G(X,Y,Z) = (X AND Z) OR (Y AND not(Z))
    H(X,Y,Z) = X xor Y xor Z
    I(X,Y,Z) = Y xor (X OR not(Z))
    Ce qu'il y a d'important avec ces 4 fonctions et que si les bits de leurs arguments X,Y et Z sont indépendants, les bits du résultat le sont aussi.
  • Etape 3 : Calcul itératif
      Pour chaque bloc de 512 bits du texte, on fait les opérations suivantes :
    1. on sauvegarde les valeurs des registres dans AA,BB,CC,DD.
    2. on calcule de nouvelles valeurs pour A,B,C,D à partir de leurs anciennes valeurs, à partir des bits du bloc qu'on étudie, et à partir des 4 fonctions F,G,H,I.
    3. on fait A=AA+A, B=BB+B, C=CC+C, D=DD+D.
    Le détail des calculs se trouve en annexe.
  • Etape 4 : Ecriture du résumé
      Le résumé sur 128 bits est obtenu en mettant bout à bout les 4 buffers A,B,C,D de 32 bits.

  Le programme JavaScript suivant permet de calculer le résumé MD5 d'un texte.
Message
       
Résumé
Consulter aussi