Implementation MD5 en C

Version imprimable

(Désoler si ce message n'est pas dans la bonne catégorie, je n'arivais pas à trouver une catégorie C "générale")

Bonjour, je souhaiterait implémenter l'algorithme MD5 moi même, histoire de voir comment on hash un message. Le problème c'est que ma tentative d'implémentation donne un peut n'importe quoi ^^'
J'ai pourtant tenter de trouver les erreurs avec ce document : http://www.faqs.org/rfcs/rfc1321.html mais je n'ai pas tout a fait procéder de la même façon sur certains points (utilisation de fonction inline et non de macro, remplissage avec une autre méthode)
Donc, d'après ce que j'ai put tester avec gdb : le remplissage marche. Le hachage de marche pas ^^' Des chaînes trop longue en entrée font plenter la fonction sans que je comprenne exactement où :/

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
#include "md5.h"
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
 
 
//! Rotate (<<) table : Tell the s value for v << s
char rotate[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};
 
//! MD5 Constants (get from sinus)
char sinconst[64];
 
void md5_init()
{
	//Feel sinconst
	int i=0;
	while(i < 64)
	{
		//4294967296 = 2^32
		sinconst[i] = (char)floor(fabs(sin(i+1)) * 4294967296.0e+0);
		i++;
	}
}
 
char* md5_hash(const char* str, const unsigned int len)
{
	//We start with a constant default block
	struct md5_hash_buffer res_block =
		{0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476};
 
	//Loop iteraotr i
	int i;
	int j;
 
	// -------------------------------------
	// Make the str length as a 512*n length
	// -------------------------------------
 
	//Size of the str
	int size = len*8;
	//Add the 1 bite, added
	size += 1;
	//The new size must be n*512+448
	if(size%512 > 448)
		size += 64;
	size += 448 - size%512;
	//Size of the final str wich will be use
	int f_size = size+64;
	//Alocate the buffer
	unsigned char* buff = (unsigned char*)malloc(f_size/8);
	//Copy str in buff
	sprintf(buff, "%s", str);
	//Copy 10000000 in buff
	buff[len] = 0x80;
	//Feel the str with 0
	int s_pos = (f_size-64)/8;
	for(i = 0; i < s_pos; i++)
		buff[len+i+1] = 0x00;
	//Add the len at end
	int_64* ptr = (int_64*)(buff + s_pos);
	*ptr = (int_64)f_size;
 
	//Loop on each 512 block
	for(i = 0; i < f_size/512; i++)
	{
		//Work block
		struct md5_hash_buffer work_block = res_block;
 
		//Temp res values
		int f, k;
 
 
		//Loop
		for(j = 0; j < 64; j++)
		{
			if(j < 16)
			{
				f = md5_f(work_block.b, work_block.c, work_block.d);
				k = j;
			}
			else if(j < 32)
			{
				f = md5_g(work_block.b, work_block.c, work_block.d);
				k = (5*j+1)%16;
			}
			else if(j < 48)
			{
				f = md5_h(work_block.b, work_block.c, work_block.d);
				k = (3*j+5)%16;
			}
			else
			{
				f = md5_i(work_block.b, work_block.c, work_block.d);
				k = (7*j)%16;
			}
 
			//Calc the new block
			work_block.a = md5_leftrotate((work_block.a + f + sinconst[i] + buff[k+i*512/8]), rotate[j]) + work_block.b;
 
			//Rotate elms
			int_32 d = work_block.d;
			work_block.d = work_block.c;
			work_block.c = work_block.b;
			work_block.b = work_block.a;
			work_block.a = d;
		}
 
		res_block.a += work_block.a;
		res_block.b += work_block.b;
		res_block.c += work_block.c;
		res_block.d += work_block.d;
	}
 
	//Create the return string and add value
	char* res = (char*)malloc(32+1);
	char* res_b = (char*)&res_block;
	for(i = 0; i < 32; i+=2)
		sprintf(res+i, "%02x", *(res_b+i));
	//Printf add a '0' at the end, so we don't need that
	//res[32] = 0;
 
	return res;
}

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
#ifndef _MD5_H_
#define _MD5_H_
 
 
//! int_32 is a 32 bits low endian integer
typedef unsigned long long int int_64;
typedef unsigned long int int_32;
 
struct md5_hash_buffer
{
	int_32 a;
	int_32 b;
	int_32 c;
	int_32 d;
};
 
/** No-linear function f
  * @param x block b from the md5_hash_buffer
  * @param y block c from the md5_hash_buffer
  * @param z block d from the md5_hash_buffer
  * @return x&y | (~y & z)
  */
static inline int_32 md5_f(const int_32 x, const int_32 y, const int_32 z)
{
	return (x&y) | (~y & z);
}
 
/** No-linear function g
  * @param x block b from the md5_hash_buffer
  * @param y block c from the md5_hash_buffer
  * @param z block d from the md5_hash_buffer
  * @return x&y | (y & ~z)
  */
static inline int_32 md5_g(const int_32 x, const int_32 y, const int_32 z)
{
	return (x&y) | (y & ~z);
}
 
/** No-linear function h
  * @param x block b from the md5_hash_buffer
  * @param y block c from the md5_hash_buffer
  * @param z block d from the md5_hash_buffer
  * @return x^y^z;
  */
static inline int_32 md5_h(const int_32 x, const int_32 y, const int_32 z)
{
	return x^y^z;
}
 
/** No-linear function
  * @param x block b from the md5_hash_buffer
  * @param y block c from the md5_hash_buffer
  * @param z block d from the md5_hash_buffer
  * @return y^(x|~z)
  */
static inline int_32 md5_i(const int_32 x, const int_32 y, const int_32 z)
{
	return y^(x|~z);
}
 
/** Make a binary rotation
  * @param x int_32 block
  * @param r rotate value
  * @return int_32 block after rotation
  */
static inline int_32 md5_leftrotate(const int_32 x, const int_32 r)
{
	return (x << r) | (r >> (32-r));
}
 
//! Initialise the md5 constants
void md5_init();
 
/** Hashe a string str with a length len
  * and return a dynamic char[32]
  * @param str A char* (binary) string
  * @param len The length of the string
  */
char* md5_hash(const char* str, const unsigned int len);
 
 
#endif

05/02/2008, 17h53
cmoibal
bonjour,

d'aprés ma petite experience, j'ai utiliser le même algorithme avec SHA1 et ça marche, mais une fonction de hashage n'a pas le même fonctionmenet que les algorithme MD5 et SHA1 : elle l'utilise.

pour une fonction de hashage simple, tu peut suivre les références , ils présentent un exemple d'implementation en C.

et pour les données de grande taille(un fichier par exemple), il fault les divizer sur plusieur segments, et faire le hashage sur c'est petit segments, et faire la termineson en finale step.

En générale il y a les troix fonctions suivant pour le hmac:

hmac_init()
hmac_update()
hmac_final();

pour un fichier tu auras un code comme :
Code:

1 2 3 4 5 6 7 hmac_init(); for(;EOF();) hmac_update(buffer); hmac_final();
une petite recherche tu sera d'une grande utilité

Citation:

Envoyé par SulphurEagle

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
#include "md5.h"
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
 
 
//! Rotate (<<) table : Tell the s value for v << s
char rotate[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};
 
//! MD5 Constants (get from sinus)
char sinconst[64];
 
void md5_init()
{
	//Feel sinconst
	int i=0;
	while(i < 64)
	{
		//4294967296 = 2^32
		sinconst[i] = (char)floor(fabs(sin(i+1)) * 4294967296.0e+0);
		i++;
	}
}
 
char* md5_hash(const char* str, const unsigned int len)
{
	//We start with a constant default block
	struct md5_hash_buffer res_block =
		{0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476};
 
	//Loop iteraotr i
	int i;
	int j;
 
	// -------------------------------------
	// Make the str length as a 512*n length
	// -------------------------------------
 
	//Size of the str
	int size = len*8;
	//Add the 1 bite, added
	size += 1;
	//The new size must be n*512+448
	if(size%512 > 448)
		size += 64;
	size += 448 - size%512;
	//Size of the final str wich will be use
	int f_size = size+64;
	//Alocate the buffer
	unsigned char* buff = (unsigned char*)malloc(f_size/8);
	//Copy str in buff
	sprintf(buff, "%s", str);
	//Copy 10000000 in buff
	buff[len] = 0x80;
	//Feel the str with 0
	int s_pos = (f_size-64)/8;
	for(i = 0; i < s_pos; i++)
		buff[len+i+1] = 0x00;
	//Add the len at end
	int_64* ptr = (int_64*)(buff + s_pos);
	*ptr = (int_64)f_size;
 
	//Loop on each 512 block
	for(i = 0; i < f_size/512; i++)
	{
		//Work block
		struct md5_hash_buffer work_block = res_block;
 
		//Temp res values
		int f, k;
 
 
		//Loop
		for(j = 0; j < 64; j++)
		{
			if(j < 16)
			{
				f = md5_f(work_block.b, work_block.c, work_block.d);
				k = j;
			}
			else if(j < 32)
			{
				f = md5_g(work_block.b, work_block.c, work_block.d);
				k = (5*j+1)%16;
			}
			else if(j < 48)
			{
				f = md5_h(work_block.b, work_block.c, work_block.d);
				k = (3*j+5)%16;
			}
			else
			{
				f = md5_i(work_block.b, work_block.c, work_block.d);
				k = (7*j)%16;
			}
 
			//Calc the new block
			work_block.a = md5_leftrotate((work_block.a + f + sinconst[i] + buff[k+i*512/8]), rotate[j]) + work_block.b;
 
			//Rotate elms
			int_32 d = work_block.d;
			work_block.d = work_block.c;
			work_block.c = work_block.b;
			work_block.b = work_block.a;
			work_block.a = d;
		}
 
		res_block.a += work_block.a;
		res_block.b += work_block.b;
		res_block.c += work_block.c;
		res_block.d += work_block.d;
	}
 
	//Create the return string and add value
	char* res = (char*)malloc(32+1);
	char* res_b = (char*)&res_block;
	for(i = 0; i < 32; i+=2)
		sprintf(res+i, "%02x", *(res_b+i));
	//Printf add a '0' at the end, so we don't need that
	//res[32] = 0;
 
	return res;
}

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
#ifndef _MD5_H_
#define _MD5_H_
 
 
//! int_32 is a 32 bits low endian integer
typedef unsigned long long int int_64;
typedef unsigned long int int_32;
 
struct md5_hash_buffer
{
	int_32 a;
	int_32 b;
	int_32 c;
	int_32 d;
};
 
/** No-linear function f
  * @param x block b from the md5_hash_buffer
  * @param y block c from the md5_hash_buffer
  * @param z block d from the md5_hash_buffer
  * @return x&y | (~y & z)
  */
static inline int_32 md5_f(const int_32 x, const int_32 y, const int_32 z)
{
	return (x&y) | (~y & z);
}
 
/** No-linear function g
  * @param x block b from the md5_hash_buffer
  * @param y block c from the md5_hash_buffer
  * @param z block d from the md5_hash_buffer
  * @return x&y | (y & ~z)
  */
static inline int_32 md5_g(const int_32 x, const int_32 y, const int_32 z)
{
	return (x&y) | (y & ~z);
}
 
/** No-linear function h
  * @param x block b from the md5_hash_buffer
  * @param y block c from the md5_hash_buffer
  * @param z block d from the md5_hash_buffer
  * @return x^y^z;
  */
static inline int_32 md5_h(const int_32 x, const int_32 y, const int_32 z)
{
	return x^y^z;
}
 
/** No-linear function
  * @param x block b from the md5_hash_buffer
  * @param y block c from the md5_hash_buffer
  * @param z block d from the md5_hash_buffer
  * @return y^(x|~z)
  */
static inline int_32 md5_i(const int_32 x, const int_32 y, const int_32 z)
{
	return y^(x|~z);
}
 
/** Make a binary rotation
  * @param x int_32 block
  * @param r rotate value
  * @return int_32 block after rotation
  */
static inline int_32 md5_leftrotate(const int_32 x, const int_32 r)
{
	return (x << r) | (r >> (32-r));
}
 
//! Initialise the md5 constants
void md5_init();
 
/** Hashe a string str with a length len
  * and return a dynamic char[32]
  * @param str A char* (binary) string
  * @param len The length of the string
  */
char* md5_hash(const char* str, const unsigned int len);
 
 
#endif

Excuse-moi si je te parais un petit peu abrupt... mais tu t'amuses à refaire la libmd5 qui existe déjà et dont les sources sont dispo... et tu n'y arrives pas parce que t'as sûrement raté un truc idiot au moment où il ne fallait pas. Ben c'est pas grave. Reprends à nouveau le code source de la libmd5 et refais-le de nouveau. Ou mieux... reprend l'ensemble complet du code d'origine, teste-le. Si ça marche bien ben remplace la première fonction "officielle" par la tienne et reteste-le de nouveau. Et tant que tout va bien tu continues d'avancer dans les autres fonctions...

05/02/2008, 23h59
Zenol

Je ne remet pas en doute l'algorithme utiliser, mais mon implémentation, je ne parvient pas à obtenir un résultat qui ressemble de près ou de loin à un hash MD5, pourtant c'est l'algo que je tente d'implémenter. pour le découpage en block de 256bits, c'est automatique, le bourrage n'est rajouter qu'à la fin de ma chaîne et chacun des blocks est traiter l'un après l'autre. Mais j'obtiens un sigseg quand j'ai plus d'un block à traiter, et enfin le résultat est du grand n'importe quoi. Seulement tout ce que j'ai réussi à faire pour le moment c'est faire planter le déboguer en cherchant l'origine du sigseg :/

Donc si quelqu'un avais une petite idée de ce qui clochait dans mon implémentation, est-ce qu'il y aurait un problème au niveau de l'initialisation des variables? De la multiplication par 2^32? De la rotation de bit? Ou des itérations des boucles? De l'utilisation de l'opérateur d'addition? (Au niveau du little endian/big endian normalement c'est bon)
06/02/2008, 11h33
cmoibal

Est ce que t'utilises l'algorithme dans une machine 32 ?
07/02/2008, 19h48
Zenol

Citation:

Envoyé par Sve@r

Excuse-moi si je te parais un petit peu abrupt... mais tu t'amuses à refaire la libmd5 qui existe déjà et dont les sources sont dispo... et tu n'y arrives pas parce que t'as sûrement raté un truc idiot au moment où il ne fallait pas. Ben c'est pas grave. Reprends à nouveau le code source de la libmd5 et refais-le de nouveau. Ou mieux... reprend l'ensemble complet du code d'origine, teste-le. Si ça marche bien ben remplace la première fonction "officielle" par la tienne et reteste-le de nouveau. Et tant que tout va bien tu continues d'avancer dans les autres fonctions...

Ah merci de l'idée (je n'avais pas vue le message, page non actualisée...), j'essayerais ça quand j'aurai un moment(je ne connaissais pas l'implémentation libmd5). Parce que bon j'ai réussi à faire planter gdb la dernière fois :/

(Vivi, j'utilise bien un proc 32bits en little endian (x86) )