Message Digest 4

Algorithme utilisé par Up ! Security Manager

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

/****************************************************************/
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