Message Digest 4

Algorithme utilisé par Up ! Security Manager

L'algorithme Message Digest 4 (MD4) de l'Internet Engineering Task Force (IETF) a pour principe de calculer une signature sur 16 octets d'un flux binaire ou texte.

Cette signature permet par exemple d'attester l'intégrité du contenu d'un fichier, d'un enregistrement d'une base de données, d'un message échangé, etc. parce qu'il est pratiquement impossible que deux contenus distincts produisent la même signature.

Ainsi :

Si les signatures sont différentes alors les contenus sont différents.
Si les contenus sont identiques alors les signatures sont identiques.
Si les contenus sont différents alors les signatures sont très certainement différentes.

Le principe est de calculer la valeur de quatre registres A, B, C, D dont les valeurs changent par application d'opérations paramétrées par leurs valeurs précédentes et le contenu du flux.

Voici l'algorithme Md4 :

Initialisation.
A=0x67452301; B=0xefcdab89; C=0x98badcfe; D=0x10325476;
Pour chaque tranche de 64 octets du flux à signer :
- Conservation des registres.
  AA=A; BB=B; CC=C; DD=D;
- Opération 1.
  Application de l'opération Operation1 présentée ci-après :
  A=Operation1(A,B,C,D, 0, 3); D=Operation1(D,A,B,C, 1, 7); C=Operation1(C,D,A,B, 2, 11); B=Operation1(B,C,D,A, 3, 19); A=Operation1(A,B,C,D, 4, 3); D=Operation1(D,A,B,C, 5, 7); C=Operation1(C,D,A,B, 6, 11); B=Operation1(B,C,D,A, 7, 19); A=Operation1(A,B,C,D, 8, 3); D=Operation1(D,A,B,C, 9, 7); C=Operation1(C,D,A,B, 10, 11); B=Operation1(B,C,D,A, 11, 19); A=Operation1(A,B,C,D, 12, 3); D=Operation1(D,A,B,C, 13, 7); C=Operation1(C,D,A,B, 14, 11); B=Operation1(B,C,D,A, 15, 19);
- Opération 2.
  Application de l'opération Operation2 présentée ci-après :
  A=Operation2(A,B,C,D, 0, 3); D=Operation2(D,A,B,C, 4, 5); C=Operation2(C,D,A,B, 8, 9); B=Operation2(B,C,D,A, 12, 13); A=Operation2(A,B,C,D, 1, 3); D=Operation2(D,A,B,C, 5, 5); C=Operation2(C,D,A,B, 9, 9); B=Operation2(B,C,D,A, 13, 13); A=Operation2(A,B,C,D, 2, 3); D=Operation2(D,A,B,C, 6, 5); C=Operation2(C,D,A,B, 10, 9); B=Operation2(B,C,D,A, 14, 13); A=Operation2(A,B,C,D, 3, 3); D=Operation2(D,A,B,C, 7, 5); C=Operation2(C,D,A,B, 11, 9); B=Operation2(B,C,D,A, 15, 13);
- Opération 3.
  Application de l'opération Operation3 présentée ci-après :
  A=Operation3(A,B,C,D, 0, 3); D=Operation3(D,A,B,C, 8, 9); C=Operation3(C,D,A,B, 4, 11); B=Operation3(B,C,D,A, 12, 15); A=Operation3(A,B,C,D, 2, 3); D=Operation3(D,A,B,C, 10, 9); C=Operation3(C,D,A,B, 6, 11); B=Operation3(B,C,D,A, 14, 15); A=Operation3(A,B,C,D, 1, 3); D=Operation3(D,A,B,C, 9, 9); C=Operation3(C,D,A,B, 5, 11); B=Operation3(B,C,D,A, 13, 15); A=Operation3(A,B,C,D, 3, 3); D=Operation3(D,A,B,C, 11, 9); C=Operation3(C,D,A,B, 7, 11); B=Operation3(B,C,D,A, 15, 15);
- Incrémentation des registres.
  A+=AA; B+=BB; C+=CC; D+=DD;
Terminaison.
La signature est composée des octets de A, B, C, D.

Le flux est toujours prolongé de la sorte que sa taille soit toujours un multiple de 64 octets :

Le premier octet de la prologation est toujours 0x80.
Les suivants sont 0x00.
Les 8 derniers sont toujours la taille initiale du flux en nombre de bits, dans l'ordre poids faible puis poids fort.
Si un bloc n'est pas suffisant pour ajouter à la fois l'octet 0x80 et la taille, un nouveau est ajouté.

Les registres A, B, C, D sont encodés obligatoirement dans l'ordre poids faible puis poids fort.

Opérations

La variable Buffer contient la tranche des 16 octets du contenu à signer.

/****************************************************************/ Fonction F(X:Entier, Y:Entier, Z:Entier) Retourner Entier /* Objet : Transformation F(X,Y,Z) = XY v not(X) Z. */ /****************************************************************/ Debut Retourner (X&Y)|((~X)&Z); Fin Fonction /****************************************************************/ Fonction G(X:Entier, Y:Entier, Z:Entier) Retourner Entier /* Objet : Transformation G(X,Y,Z) = XZ v Y not(Z). */ /****************************************************************/ Debut Retourner (X&Z)|(Y&(~Z)); Fin Fonction /****************************************************************/ Fonction H(X:Entier, Y:Entier, Z:Entier) Retourner Entier /* Objet : Transformation H(X,Y,Z) = X xor Y xor Z. */ /****************************************************************/ Debut Retourner X^Y^Z; Fin Fonction /****************************************************************/ Fonction Rotation(X:Entier, N:Entier) Retourner Entier /* Objet : X <<< N. */ /****************************************************************/ Debut Retourner (X<<N)|(X>>(32-N)); Fin Fonction /****************************************************************/ Fonction Operation1(a:Entier, b:Entier, c:Entier, d:Entier, k:Entier, s:Entier) Retourner Entier /* Objet : a = (a + F(b,c,d) + X[k]) <<< s. */ /****************************************************************/ Debut Retourner Rotation((a + F(b,c,d) + Buffer[k]), s); Fin Fonction /****************************************************************/ Fonction Operation2(a:Entier, b:Entier, c:Entier, d:Entier, k:Entier, s:Entier) Retourner Entier /* Objet : a = (a + G(b,c,d) + X[k] + 5A827999) <<< s. */ /****************************************************************/ Debut Retourner Rotation((a + G(b,c,d) + Buffer[k] + 0x5A827999), s); Fin Fonction /****************************************************************/ Fonction Operation3(a:Entier, b:Entier, c:Entier, d:Entier, k:Entier, s:Entier) Retourner Entier /* Objet : a = (a + H(b,c,d) + X[k] + 6ED9EBA1) <<< s. */ /****************************************************************/ Debut Retourner RotationMd4((a + H(b,c,d) + Buffer[k] + 0x6ED9EBA1), s); Fin Fonction

Exemple de signatures obtenues par l'algorithme MD4

Signature de ".
31d6cfe0d16ae931b73c59d7e0c089c0
Signature de abc".
a448017aaf21d8525fc10ae87aa6729d
Signature de ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789".
043f8582f241db351ce627e153e7f0e4
Signature de 12345678901234567890123456789012345678901234567890123456789012345678901234567890".
e33b4ddc9c38f2199c3e7b164fcc0536