Fonction de hachage, exemple de md5

Une fonction de hachage prend des données, de taille variable, en entrée, et produit une image numérique de taille fixe en sortie. L'image est parfois appelée empreinte ou condensat.

On attend deux propriétés de cette fonction :

• qu'il soit impossible de calculer l'antécédent en ne connaissant que l'image,
• que deux images très proches aient des empreintes très différentes.

Ainsi, s'il arrivait par hasard que deux antécédents A et B aient la même empreinte, il serait impossible de deviner A à partir de B.

On pourra noter $z = h(A)$ l'empreinte de $A$.

• Sur mon site web, je met $A$, un fichier de quelques centaine de Mo, et je donne son empreinte, simple chaîne de caractères assez courte.
  Quand le client a fini de télécharger le fichier, il a obtenu $A'$. Normalement $A = A'$ mais s'il y a eu des erreurs, on peut avoir $A \neq A'$.
  Si on a $h(A) = h(A')$ on est quasiment certain que $A = A'$.
• L'utilisateur U a un mot de passe pour se connecter sur mon serveur S. Mais je ne veux pas écrire le mot de passe en clair dans ma base de donnée. Je ne veux même pas connaître le mot de passe de U.
  Dans ma base de donnés, quand U s'inscrit, je n'enregistre pas $mdp_U$. J'enregistre à la place $h(mdp_U)$.
  Chaque fois que U se connecte, il me donne $mdp_U$, je calcule $h(mdp_U)$ et je compare avec ce qui est en base de données.
  Ainsi je n'ai jamais stocké $mdp_U$.
• Signature numérique.

Il en existe plusieurs. Actuellement, les plus à jours sont celles de la série SHA-2 – SHA = Secure Hash Algorithm – notamment SHA 256.

On va plutôt étudier ici MD5 – Message Digest 5 – qui est maintenant dépassée dans les contextes de sécurité, mais qui permet de comprendre les principes.

Les fonctions SHA suivent le même principe mais avec des calculs plus compliqués.

MD5 a été inventée par Ronald Rivest en 1991, le même Rivest que pour le chiffrement RSA.

MD5 produit une empreinte de 128 bits soit 32 caractères quand on l'écrit en hexadécimal. Exemple :

MD5("Vers l'infini et au-delà !") = "b8c268a321a016a98707de3a245f6b8d"

• $\wedge$ : ET bitwise
• $\vee$ : OU bitwise
• $\neg$ : inversion bitwise
• $\oplus$ : OU Exclusif bitwise
• $+$ : toutes les additions sont à modulo $2^{32}$, où 0x100000000
• $\lll_n$ : rotation de $n$ bits à gauche
  Exemple pour un mot de 32 bits : 01100100010110101110111000000000, l'opération $\lll_3$ produit 00100010110101110111000000000011.

Le message en entrée est de taille variable mais doit être découpé en blocs de 512 bits. Quand ce n'est pas le cas, on bourre de la façon suivante :

• Le message $M$ compte $n$ bits,
• on place un 1 à la suite,
• on prévoit $n_{LE}$ l'écriture de $n$ en binaire 64 bits.

• on bourre en écrivant $M 1 0 \cdots 0 n_{64}$, c'est à dire le message, suivi de 1, suivi d'un certain nombre de 0, suivi de $n$ écrit en binaire 64 bits.
  On choisit le nombre de 0 de sorte que la taille du résultat soit aussi petite que possible et multiple de 512.

On fait cela même si le message de départ a une taille multiple de 512 !

MD5 utilise 64 constantes $K_i$ qui s'obtiennent :

$$K_i = \left\lfloor\left|2^{32} \times \sin(i+1)\right|\right\rfloor\quad 0 \leqslant i < 64$$

Les valeurs sont données dans ce tableau :

K = [0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501, 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be, 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821, 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa, 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8, 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed, 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a, 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c, 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70, 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05, 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665, 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1, 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1, 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391]

On utilise également 4 constantes d'initialisation :

H = [0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476]

L'algorithme s'exécute sur des mots de 128 bits eux-mêmes découpés en 4 mots A, B, C, D de 32 bits chacun.

A, B, C et D sont initialisés avec les constantes H puis l'algorithme utilise des blocs issus du message à hacher pour poursuivre.

Les opérations sur chaque bloc de 128 bits se déroulent en 4 étapes elles-mêmes découpées en 16 opérations.

On dispose de 4 fonctions de base :

• $F_{0 \leqslant i < 16}(B, C, D) = (B \wedge C) \vee (\neg B \wedge D)$
• $F_{16 \leqslant i < 32}(B, C, D) = (B \wedge D) \vee (C \wedge \neg D)$
• $F_{32 \leqslant i < 48}(B, C, D) = B \oplus C \oplus D$
• $F_{48 \leqslant i < 64}(B, C, D) = C \oplus (B\vee \neg D)$

On effectue des rotations selon les étapes :

• $R_{0 \leqslant i < 16} = [7, 12, 17, 22]$
• $R_{16 \leqslant i < 32} = [5, 9, 14, 20]$
• $R_{32 \leqslant i < 48} = [4, 11, 16, 23]$
• $R_{48 \leqslant i < 64} = [6, 10, 15, 21]$

Le message préparé est découpé en bloc de 512 bits = 64 octets.

Quand on traite un bloc, on le découpe en 16 sous-blocs de 4 octets.

On pourra ainsi créer un tableau w contenant les mots de 4 octets. Comme il y a 16 de ces mots, on ira de w[0] à w[15].

Considérons le bloc. Il compte 64 octets, donc :

• w[0] représente bloc[0:4],
• w[1] représente bloc[4:8],
• …
• w[15] représente bloc[60:64],

Puisque les sous-blocs sont des blocs de 4 octets, on peut les stocker dans des int. Il s'agit donc de prendre un bloc de 4 bytes pour en faire un int.

w[0] = int.from_bytes(bloc[0:4], byteorder='little')

À chaque itération on sélectionne un sous-bloc du message. Les blocs de 512 bits sont découpés en 16 blocs $w$ de 32 bits. On a besoin de connaître $g$ tel que $0 \leqslant g < 16$ pour pouvoir sélectionner $w[g]$.

• $G_{0 \leqslant i < 16}: i \mapsto i$
• $G_{16 \leqslant i < 32}: i \mapsto 5 \cdot i + 1 \mod 16$
• $G_{32 \leqslant i < 48}: i \mapsto 3 \cdot i + 4 \mod 16$
• $G_{48 \leqslant i < 67}: i \mapsto 7 \cdot i \mod 16$

MP = Message préparé
initialiser les H[i]

POUR CHAQUE bloc de 512 bits
    découpage du bloc en 16 mots w, little indian (w[0] = poids faible)
    a, b, c, d initialisé à H[0], ... H[3]
    POUR i ALLANT DE 0 À 63 FAIRE
        soit f = F_i(b, c, d)
        soit r = R_i[i modulo 4]
        soit g = G_i[i modulo 16]
        soit T = <<<r(a + f + K[i] + w[g]) + b
        a, b, c, d = d, T, b, c
    H[0] à H[3] augmentés respectivement de a, b, c, d
RENVOIE concaténation de H[0], ... H[3] transformés en octets

h[0].to_bytes(4, byteorder='little')

Implémentez une fonction de hachage md5(message:bytes)→bytes qui réalise le hachage décrit ici.

# test
message = "Vers l'infini et au-delà !"
h = md5(message.encode('utf8'))
# h est une suite d'octets que l'on veut convertir en une écriture hexadécimale
h_hex = "".join(f"{octet:02x}" for octet in h)
assert h_hex == "b8c268a321a016a98707de3a245f6b8d"