Hash MD5 en C

Version imprimable

Hash MD5 en C

Bonjour à tous,

j'ai un problème avec un code sensé calculer le hash MD5 d'une chaîne de caractères que j'ai trouvé sur Internet.

J'ai trouvé sur un autre site l'implémentation d'un algo pour calculer le hash MD5 d'une chaîne de caractères. Le code comportait des erreurs, et l'utilisateurs suivant l'a aidé à le corriger. Mais en appliquant les corrections, le code ne fonctionne pas chez moi ! Voilà le code, avec mes corrections (j'ai parfois mis des commentaires sur ce que j'ai corrigé) :

main.c

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
#include <stdlib.h>
#include "md5.h"
 
int main(void)
{
	char buffer[33];
	md5Digest("tototiti", 8, buffer);
	printf("MD5:%s\n", buffer);
 
	system("pause");
	return 0;
}

md5.c

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include "md5var.h"
#include "md5.h"
 
//Apparemment, pour faire fonctionner htonl()
#include <winsock.h>
#ifdef _MSC_VER
#pragma comment(lib, "ws2_32.lib")
#endif
 
void md5Init()
{
  int i;
  for(i = 0; i < 64; i++)
    y[i] = llabs((unsigned long long)(sin(i + 1.0) * powl(2.0, 32.0)));
  initialised = 1;
}
 
int md5Digest(char* src, unsigned long long size, char* dst)	// Size is expressed in bits
{
 
  unsigned char* paddedBuffer = NULL;
  unsigned long long paddedBufferSize = 0;
  unsigned long long paddingSize = 0;
  unsigned char* MD5 = (unsigned char*)dst;
  unsigned int tmpBuffer[16];
  unsigned int i = 0, j = 0;
  unsigned int 	A = 0, B = 0, C = 0, D = 0, t = 0, 
		H1 = 0, H2 = 0, H3 = 0, H4 = 0, 
		h1 = 0, h2 = 0, h3 = 0, h4 = 0, 
		m = 0;
 
  //Initialisation décalée après la déclaration des variables
  if(!initialised)
  {
    md5Init();
  }
 
 
  // Padding
 
  paddedBufferSize = ((size % 512) < 448) ? (size + 448 - (size % 512)) : (size + 960 - (size % 512));
  //Cast pour éviter l'erreur [Impossible d'assigner une valeur de type "void *" à une entité de type "unsigned char *]
  paddedBuffer = (unsigned char *)malloc((paddedBufferSize + 64) >> 3);
  memcpy(paddedBuffer, src, ((size % 8) ? (size >> 3) : (size >> 3) + 1));
  paddedBuffer[(size >> 3)] &= (0xFF << (8 - (size % 8)));
  paddedBuffer[(size >> 3)] |= (0x80 >> (size % 8));
 
  for(i = (size >> 3) + 1; i < (paddedBufferSize + 64) / 8; i++)
    paddedBuffer[i] = 0;
 
  paddedBuffer[(paddedBufferSize >> 3)] = size & 0x00000000000000FFULL;
  paddedBuffer[(paddedBufferSize >> 3) + 1] = (size & 0x000000000000FF00ULL) >> 8;
  paddedBuffer[(paddedBufferSize >> 3) + 2] = (size & 0x0000000000FF0000ULL) >> 16;
  paddedBuffer[(paddedBufferSize >> 3) + 3] = (size & 0x00000000FF000000ULL) >> 24;
  paddedBuffer[(paddedBufferSize >> 3) + 4] = (size & 0x000000FF00000000ULL) >> 32;
  paddedBuffer[(paddedBufferSize >> 3) + 5] = (size & 0x0000FF0000000000ULL) >> 40;
  paddedBuffer[(paddedBufferSize >> 3) + 6] = (size & 0x00FF000000000000ULL) >> 48;
  paddedBuffer[(paddedBufferSize >> 3) + 7] = (size & 0xFF00000000000000ULL) >> 56;
 
  // Initialisation
 
  h1 = 0x67452301;
  h2 = 0xefcdab89;
  h3 = 0x98badcfe;
  h4 = 0x10325476;
  H1 = h1;
  H2 = h2;
  H3 = h3;
  H4 = h4;
  A = h1;
  B = h2;
  C = h3;
  D = h4;
  m = (paddedBufferSize + 64) >> 9;
 
  // MD5 Calculation
 
  for(i = 0; i < m; i++)
  {    
    for(j = 0; j < 16; j++)
    {
      tmpBuffer[j] = ((unsigned int*)paddedBuffer)[16 * i + j];
    }
 
    for(j = 0; j < 16; j++)
    {
      t = (A + F(B, C, D) + tmpBuffer[z[j]] + y[j]);
      A = D;
      t = B + ROTL(t, s[j]);
      D = C;
      C = B;
      B = t;
    }
 
    for(j = 16; j < 32; j++)
    {
      t = (A + G(B, C, D) + tmpBuffer[z[j]] + y[j]);
      A = D;
      t = B + ROTL(t, s[j]);
      D = C;
      C = B;
      B = t;
    }
 
    for(j = 32; j < 48; j++)
    {
      t = (A + H(B, C, D) + tmpBuffer[z[j]] + y[j]);
      A = D;
      t = B + ROTL(t, s[j]);
      D = C;
      C = B;
      B = t;
    }
 
    for(j = 48; j < 64; j++)
    {
      t = (A + I(B, C, D) + tmpBuffer[z[j]] + y[j]);
      A = D;
      t = B + ROTL(t, s[j]);
      D = C;
      C = B;
      B = t;
    }
    H1 += A; H2 += B; H3 += C; H4 += D;
  }
  sprintf(dst, "%08x%08x%08x%08x\0", htonl(H1), htonl(H2), htonl(H3), htonl(H4));
  free(paddedBuffer);
  return 0;
}

md5.h

Code:

1
2
3
4
5
6
7
#ifndef MD5_H
#define MD5_H
 
void md5Init();
int md5Digest(char* src, unsigned long long size, char* dst);
 
#endif

md5var.h

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#ifndef MD5VAR_H
#define MD5VAR_H
 
#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
#define H(x, y, z) ((x) ^ (y) ^ (z))
#define I(x, y, z) ((y) ^ ((x) | (~z)))
#define ROTL(number, shift) ((number << shift) | (number >> (32 - shift)))
#define ROTR(number, shift) ((number >> shift) | (number << (32 - shift)))
 
unsigned long long s[64] = {7,12,17,22,7,12,17,22,7,12,17,22,7,12,17,22,
			    5,9,14,20,5,9,14,20,5,9,14,20,5,9,14,20,
			    4,11,16,23,4,11,16,23,4,11,16,23,4,11,16,23,
			    6,10,15,21,6,10,15,21,6,10,15,21,6,10,15,21};
 
unsigned long long y[64];
 
unsigned long long z[64] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
			    1,6,11,0,5,10,15,4,9,14,3,8,13,2,7,12,
			    5,8,11,14,1,4,7,10,13,0,3,6,9,12,15,2,
			    0,7,14,5,12,3,10,1,8,15,6,13,4,11,2,9};
 
int initialised = 0;
 
#endif

Problème actuel : le hash MD5 est bien généré, sauf que... ce n'est pas le bon ! Par exemple, lorsque je tape un mot de passe comme "toto1234", il ne trouve pas le même hash qu'un site comme md5.fr. Par contre, pas de problème pour une chaîne vide, le bon hash est généré. De plus, les hash de "toto" et "titi" sont identiques.

Merci à tous pour votre aide, j'aimerais vraiment comprendre ce qui ne va pas :ccool:

PS : pour ceux qui me conseilleraient la "légendaire" RFC 1321, je n'arrive pas à la faire fonctionner. Je copie-colle le contenu exactement comme suggéré, dans les 4 fichiers (global.h...), mais il y a un nombre important d'erreurs à la compilation, et cette librairie semble de toutes façons trop compliquée à comprendre et à mettre en oeuvre pour mes besoins, comparée à celle que j'ai trouvée.

21/06/2012, 00h34
Obsidian

Hello,

Je n'ai que survolé ton post mais il appelle déjà deux petites remarques :

— Vérifie que tu n'inclus pas le retour à la ligne dans le calcul de ton hash MD5. C'est un cas classique ;
— Pourquoi utiliser powl(2.0,32.0) pour calculer 2³² ? Utilise plutôt directement (1 << 32) ou carrément 0x100000000.
21/06/2012, 01h03
benji1000

Merci pour ta réponse.

Pour le retour à la ligne, c'est ce que j'ai pensé, au début. Mais c'est pour ça que du coup, avant d'envoyer une variable à la fonction md5Digest(), je lui ai envoyé une chaîne de caractères "en dur" (tototiti par ex). Rien n'y fait.

Par contre, je ne comprends pas ta deuxième remarque :\ en quoi ce que tu propose est égal à 2^32 ?
21/06/2012, 07h18
Neckara

Citation:

Envoyé par benji1000

Par contre, je ne comprends pas ta deuxième remarque :\ en quoi ce que tu propose est égal à 2^32 ?

<< va décaler tous les bits vers la gauches (= vers le bits de poids fort) ainsi 1 << 32 on a un seul bit tout à droite (bit de poids faible) et on le décale de 32 bits vers la gauche (poids fort). Le résultat est donc : 2^(0 + 32) où 0 est la position initiale du bit et 0 + 32 sa position finale.

0x100000000 est tout simplement l'écriture de 2^32 en hexadécimale.
21/06/2012, 09h42
benji1000

OK, merci pour l'astuce ! En fait, j'ai pas l'habitude de manier les nombres hexadécimaux ou les opérations bit à bit, mais ça peut toujours servir !

Malheureusement, cela ne fonctionne pas. Ni l'une ni l'autre solution. J'ai toujours un hash en retour, mais qui ne correspond pas exactement au "vrai" hash du mot recherché. Et les hash de "toto" et "titi" sont toujours identiques.

Une question également : je ne suis jamais sûr du deuxième paramètre. Le prototype indique que ce doit être un long, et qu'il doit correspondre à la taille de la chaîne de caractères. Donc si je lui envoie "toto" et 4, c'est bon ? Si je lui envoie toto="toto" et strlen(toto), c'est bon ?

Citation:

Envoyé par benji1000

OK, merci pour l'astuce ! En fait, j'ai pas l'habitude de manier les nombres hexadécimaux ou les opérations bit à bit, mais ça peut toujours servir !

Il vaudrait mieux en prendre vite l'habitude car, d'une part, quand tu utilises powl(), tu appelles une fonction qui va effectuer des calculs à l'exécution alors qu'il s'agit d'une constante. En fait, c'est exactement comme si tu écrivais « powl(10.0,6.0) » pour écrire un million, en décimal. Tu ne peux malheureusement pas les considérer comme de simples représentations mathématiques d'une même valeur. Il faut prendre la notion de coût en considération.

D'autre part, cette fonction va elle même faire des manipulations de bits pour mener ses calculs à bien.

Ensuite, tu fais encore beaucoup de mélanges de types, en t'appuyant d'emblée sur des long long voire des long double qui ne sont même pas pris en charge nativement par les architectures, même en 64 bits, alors que dans le cas de l'initialisation avec les sinus, par exemple, un simple float aurait déjà été plus qu'il n'en faut.

Citation:

Malheureusement, cela ne fonctionne pas. Ni l'une ni l'autre solution. J'ai toujours un hash en retour, mais qui ne correspond pas exactement au "vrai" hash du mot recherché. Et les hash de "toto" et "titi" sont toujours identiques.

Ok, j'ai fini par comprendre. Il y a un grand nombre de choses qui pourraient planter dans ton programme mais qui fonctionnent quand même, mais la seule chose qui fait échouer le tout, c'est le fait que tu transmets une taille en nombre de caractères à md5Digest() alors qu'elle attend une taille en nombre de bits, chose que tu as toi-même écrite dans les commentaires. Fais les modifs suivantes dans le programme principal :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include <stdio.h> #include <stdlib.h> #include <limits.h> #include "md5.h" int main(void) { char buffer[33]; md5Init(); md5Digest("tototiti", 8 * CHAR_BIT , buffer); printf("MD5:%s\n", buffer); system("pause"); return 0; }
… et tu devrais retomber sur les bonnes valeurs. Ça marche chez moi.

MàJ : ça marche oui, mais tant que tu restes sur un seul bloc, c'est-à-dire en dessous de 448 bits ou 56 caractères. Au delà, tu as d'autres bugs qu'il faudra corriger.

21/06/2012, 19h20
benji1000

Citation:

Envoyé par Obsidian

Ensuite, tu fais encore beaucoup de mélanges de types, en t'appuyant d'emblée sur des long long voire des long double qui ne sont même pas pris en charge nativement par les architectures, même en 64 bits, alors que dans le cas de l'initialisation avec les sinus, par exemple, un simple float aurait déjà été plus qu'il n'en faut.

Pour ma défense en fait, comme je l'ai dit, j'ai trouvé le code sur un autre site. Mais bon, je sais que c'est pas vraiment une excuse, j'aurais dû mieux analyser et comprendre le code ! Je dois admettre que je me suis posé des questions concernant ces long ; quel est l'avantage d'utiliser des long, plutôt que des double ou des int (d'une part ici, et plus généralement, en programmation) ? Je n'ai pas de grandes connaissances en programmation, mais le peu qu'on nous a appris en cours, on ne nous a jamais parlé des long en fait (juste des double et des int). Ni même de l'avantage bit à bit (faudra que je me renseigne mieux sur le sujet), je croyais que ça s'utilisait que quand on faisait de la programmation de micro-contrôleurs, ou en tous cas, en électronique.

Citation:

Envoyé par Obsidian

Chose que tu as toi-même écrite dans les commentaires.

Idem, pas mes commentaires... :D

Bref, merci beaucoup, ça fonctionne effectivement. Si tu as le temps, j'aimerais beaucoup améliorer ce code afin de m'en faire une base solide, si jamais je dois l'utiliser dans d'autres projets. Peux-tu me donner une liste (ou deux trois pistes) des choses qui ne vont pas, que j'essaie de plancher dessus ?

EDIT : ah et aussi, intérêt d'utiliser des unsigned ?
21/06/2012, 20h10
Obsidian
Hello,

Pas de problème ! ;) Ce n'était pas une accusation, mais plutôt une façon de bien mettre en évidence les sections concernées.

Pour le reste, il faudrait que je me penche en détails sur ton programme entier et ça risque de prendre un peu de temps. Malgré cela :
- En fait, je ne sais pas si tu gères déjà les messages de longueur supérieure à 448 bits ou pas ;
- Lorsque tu initialises le tableau, tu utilises la formule « sin(1+i) × 2³² » pour i=0 à 64. Or, toutes ces valeurs sont des constantes. Tu peux donc les calculer une fois pour toutes et les déposer dans un tableau fixe, dont tu te serviras pour initialiser le buffer servant à calculer ta somme MD5 ;
- Dans l'algorithme présenté sur Wikipédia, il est indiqué que tous les entiers sont larges de 32 bits. Si tu utilises un format différent (plus court ou plus long), tu risques d'avoir des calculs faussés. Donc, exit les « long long » et compagnie. Utilise plutôt « #include <stdint.h> » et les types « int32_t » et « uint32_t » ;
- À noter que lorsque tu multiplies un nombre binaire par une puissance de 2, c'est exactement comme si tu multipliais un nombre décimal par une puissance de 10 : tu le décales vers la gauche, d'un nombre de rangs égal à la puissance. Quand tu multiplies par 2³², tu décales le résultat du sinus vers la gauche de 32 bits. L'idée est d'acquérir les n premières décimales de chaque sinus dans le registre correspondant. C'est un moyen « simple » d'obtenir dès le départ un motif très varié ;
- Les variables globales, c'est mal ;
- Les variables globales dans un fichier *.h, c'est très mal ! ;) D'une manière générale, tu ne devrais avoir que des déclarations dans un fichier *.h, mais jamais de code ou de variable instanciés depuis cet endroit.
21/06/2012, 21h06
benji1000

Merci pour ces conseils ! J'essaierai de me pencher dessus quand j'aurai un peu plus de temps :ccool: N'hésite pas si tu en as d'autres.

Pour répondre à certaines de tes remarques :

- les variables dans le fichier .h : il me semblait bien aussi que c'était mal ^^ je les ai déplacées dans le fichier .c, directement dans la fonction ;
- je n'ai pas besoin de gérer des messages de plus de 448 bits, j'en ai juste besoin pour des mots de passe (pas plus d'une dizaine de caractères, donc)
- pour la phase d'initialisation avec sin(1+i) × 2³², c'est pour gagner en temps d'exécution ? Comment devrais-je m'y prendre pour les calculer et les stocker "en dur" ?