Fonctions de hachage à sens unique

Caspar Fall, IPA-DP-EPFL, Lausanne, Février 1998

MD4 est une fonction de hachage, inventée par Ron Rivest, l'auteur également du protocole à clé publique RSA. Il s'agit de la quatrième version du "Message Digest". Cette fonction est à sens unique: il est très difficile de déterminer deux messages qui donnent le même condensé. Il faut que les condensés soient complètement aléatoires et uniformément répartis sur l'espace de tous les condensés possibles. De plus, deux messages à l'entrée doivent donner des condensés complètement non-corrélés, même si les messages initiaux sont très proches.

MD4 procède en découpant le message à digérer en blocs de 512 bits. On complète tout d'abord le message par un bit 1, concaténé à une suite de zéros, puis à la longueur du texte initial, de manière à obtenir un message d'entrée de longueur multiple de 512 bits. Ensuite on initialise le condensé de 128 bits et on parcourt chaque bloc du message 3 fois. A chaque passage, on effectue sur les mots de 32 bits du condensé des opérations logiques non-linéaires qui combinent par des fonctions OU, ET, OU-EXCLUSIF, SOMME et ROTATION le condensé déjà obtenu et le texte à digérer.

La variante MD5 est très proche de celle présentée ici. On effectue à chaque fois 4 passages, avec des fonctions logiques légèrement différentes. L'efficacité est un peu réduite, mais la sécurité est accrue.

Cet algorithme a été conçu pour des machines 32 bits. L'interface Mathematica étant indépendant de la précision, on ne peut pas exploiter cette caractéristique dans l'implementation. Il en résulte donc un exercice plutôt académique, présenté ici à titre éducatif, dont l'efficacité finale est très pauvre.

Initialisations

Définition de diverses opérations élémentaires sur les bits

Fonctions auxiliaires non linéaires de MD4

Définition de MD4

Constantes de MD4

Définition de la routine principale de MD4

MD4[NbMessage_]:=Do[
         (* convert numerical input to binary and add padding *)
         DataIn=IntegerDigits[NbMessage,2];
         UnpaddedLength=Length[DataIn];
         NZeros=512-Mod[UnpaddedLength,512]-65;
         If[NZeros<0,NZeros=NZeros+512];
         DataIn=Flatten[
          Append[DataIn,{{1},Table[0,{NZeros}],PaddedDigits[UnpaddedLength,64]}]];
         DataIn=Partition[DataIn,32];
         NbBlocks=Length[DataIn]/16;
         If[NbBlocks>1,DataIn=Partition[DataIn,16],DataIn={DataIn}];
         
         (* define initial hash *)
         DH=InitHash[];

         (* repeat over total number of 512-byte blocks *)
         Do[(* pass 1 *)
            Do[DH[[Ind1[[j]]]]=RotateLeft[BitSum3[DH[[Ind1[[j]]]],
                F[DH[[Ind2[[j]]]],DH[[Ind3[[j]]]],DH[[Ind4[[j]]]]],
                DataIn[[k]][[j]]],S1[[j]]];,
            {j,16}];
         (* pass 2 *)
            Do[DH[[Ind1[[j]]]]=RotateLeft[BitSum4[DH[[Ind1[[j]]]],
                G[DH[[Ind2[[j]]]],DH[[Ind3[[j]]]],DH[[Ind4[[j]]]]],Cst1,
                DataIn[[k]][[X[[j]]]]],S2[[j]]];,
            {j,16}];
         (* pass 3 *)
            Do[DH[[Ind1[[j]]]]=RotateLeft[BitSum4[DH[[Ind1[[j]]]],
                H[DH[[Ind2[[j]]]],DH[[Ind3[[j]]]],DH[[Ind4[[j]]]]],Cst2,
                DataIn[[k]][[R[[j]]]]],S3[[j]]];,
            {j,16}];
         ,{k,NbBlocks}];
         DH=FromDigits[Flatten[DH],2];
       Return[DH]];

Utilisation de MD4

On peut maintenant faire un test de hachage

Mesure de la distribution du texte haché

Le hachage de messages consécutifs ne montre aucune corrélation d'un point au suivant:
[Graphics:hashgr2.gif]

La distribution des condensés de messages aléatoire est plate, comme requis:

Différence entre deux messages consécutifs

On calcule les condensés de deux messages consécutifs, pp et qq. DIGITDIFFER donne le nombre de bits qui diffèrent dans l'expansion binaire. On voit que même si pp et qq ne diffèrent que d'un bit, les messages hachés diffèrent beaucoup (en moyenne de 64 bits, ce qui équivaut à la moitié de la longueur du haché).