Discussion :

[TreizeSegments]

Bonjour,

est-il possible de gérer le codage MD5 sur 16 octets et non 32 comme on le trouve le plus souvent ?

Je pense, qu'il y a forcément une limite de la chaine à encoder pour ne pas avoir de doublons dans le codage résultat ?
En clair, voici ce que je récupère comme résultat à partir de l'algo d'encodage Javascript :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

return rhex(a) + rhex(b) ; //+ rhex(c) + rhex(d);

A moins qu'il ne faille plutot récupérer les 16 derniers ?

[alveric]

est-il possible de gérer le codage MD5 sur 16 octets et non 32 comme on le trouve le plus souvent ?

MD5 est defini comme etant un hash sur 128 bits, je n'ai pas trouve de docs donnant une variante 64 bits... Il faudrait chercher un autre algorithme, ou continuer a fouiller internet...

Je pense, qu'il y a forcément une limite de la chaine à encoder pour ne pas avoir de doublons dans le codage résultat ?

Si tu veux parler de collisions, du style

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

MD5(ma_premiere_chaine)=MD5(une_autre_chaine)

, alors oui ca existe, et c'est inevitable. On en parle dans un topic juste a cote... http://www.developpez.net/forums/viewtopic.php?t=353258

En clair, voici ce que je récupère comme résultat à partir de l'algo d'encodage Javascript :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

return rhex(a) + rhex(b) ; //+ rhex(c) + rhex(d);

Il est toujours possible de tronquer le resultat mais alors je ne garantis absolument plus rien sur l'efficacite du hachage, ou sa securite... Tu augmentes surement de maniere ENORME les probabilites de collisions, mais ne connaissant pas les details de l'algorithme MD5, je ne sais pas de combien...

Pour quelle raison veux-tu avoir un hash sur 64 bits ?

[TreizeSegments]

En fait, j'ai une appli qui génère automatiquement un code unique que l'utilisateur doit noter manuellement sur une étiquette pour des analyses. Le code est une concaténation de 4 identifiant numérique mis en chaine (donc de 1 à x caractères) suivi de la date et heure (JJ/MM/AA HH:MM:SS).

Par soucis de facilité, je voulais encoder cette chaine de manière à la faire tenir sur moins de caractères afin d'en faciliter la recopie.
j'avais déjà utilisé le MD5 un fois, je pensais le reprendre mais 32 car. ca fait beaucoup. 16 c'était un peu mieux .

[Mac LAK]

Je ne connais pas de fonctions de hachage réputée et renvoyant ses données directement sur 64 bits : à ma connaissance, ça passe directement de 32 à 128 bits. Faudra donc "truander" quelque part.

De toutes façons, il reste possible d'avoir des collisions : il faudra donc impérativement mémoriser toutes les empreintes calculées de manière à éviter, justement, une interversion accidentelle.

Par soucis de facilité, je voulais encoder cette chaine de manière à la faire tenir sur moins de caractères afin d'en faciliter la recopie.
j'avais déjà utilisé le MD5 un fois, je pensais le reprendre mais 32 car. ca fait beaucoup. 16 c'était un peu mieux .

S'il n'y a que ça pour te faire plaisir... J'ai une solution à 22 caractères, gérant les collisions.

Réfléchis 5 secondes : un caractère hexa, ça permet de coder un nombre entre 0 et 15 [4 bits], OK ? Mais ça n'utilise pas tout l'alphabet...
Si tu utilises tout l'alphabet (majuscules et minuscules), les chiffres et 2 caractères en plus (mettons "#" et "$"), on arrive à 26+26+10+2=64 caractères différentes, donc 64 possibilités... Soit 6 bits utiles.
Tu sais comment créer un tel encodage, ou pas ? Si non, demande au prochain post.

Donc, par rapport à ton MD5 sur 128 bits, ça te permet de le coder en 22 caractères (21.33 en fait, mais on doit arrondir au plus haut) plutôt que 32. Au prix d'une manipulation des bits relativement complexe, mais largement faisable.
Il te reste même 4 bits "en trop" qui peuvent te servir à gérer les collisions, même si ce cas est improbable : ça autorise quand même jusqu'à 16 collisions par empreinte (numéro incrémental), c'est assez énorme ! Ca ne te fait pas arriver aux 16 que tu voulais, mais c'est déjà 33% de longueur en moins : c'est pas trop mal pour une simple manipulation de bits, non ?

Pour tomber à 16 caractères, il faudrait utiliser 256 caractères différents : or, c'est impossible, car non seulement le clavier ne permet pas de les entrer, mais en plus, sur la table ASCII standard, plusieurs de ces caractères ne sont pas affichables. Idem pour "monter" à 128 caractères, et "tomber" à 19 caractères pour ton code : tu ne pourrais pas les entrer au clavier.

Ca te convient ?



Une autre solution peut être d'utiliser 2 checksums 32 bits "collés" ensemble, par exemple un CRC32 couplé à un Adler32 : ça fait 64 bits, et donc 16 caractères hexa... Mais le risque de collision est beaucoup plus élevé.

[TreizeSegments]

Si tu utilises tout l'alphabet (majuscules et minuscules), les chiffres et 2 caractères en plus (mettons "#" et "$"), on arrive à 26+26+10+2=64 caractères différentes, donc 64 possibilités... Soit 6 bits utiles.
Arrow Tu sais comment créer un tel encodage, ou pas ? Si non, demande au prochain post.

Hélas, je ne suis point un professionnel de l'encodage !!!
En fait, dans mon cas je n'ai que des chiffres (je peux enlever le / et : de l'horodatage). Par contre la longueur de ma chaine d'origine est variable.
Alors effectivement, si tu as un petit code à me fournir

[alveric]

Mac Lak, pour ton codage sur 64 bits, je suis d'accord... Tu viens de meme de (re)inventer une variante de uuencode ou base64

Il te reste même 4 bits "en trop" qui peuvent te servir à gérer les collisions

Par contre, la, je ne vois pas comment tu fais ca...?

Pour tomber à 16 caractères, il faudrait utiliser 256 caractères différents : or, c'est impossible, car non seulement le clavier ne permet pas de les entrer, mais en plus, sur la table ASCII standard, plusieurs de ces caractères ne sont pas affichables. Idem pour "monter" à 128 caractères, et "tomber" à 19 caractères pour ton code : tu ne pourrais pas les entrer au clavier.

C'est un peu hors-sujet, car peu pratique dans notre cas, mais Unicode, ca existe, et aux dernieres nouvelles il y avait plus de 95000 caracteres definis (source Wikipedia)...

[Mac LAK]

Alors effectivement, si tu as un petit code à me fournir

Honnêtement, les manipulations binaires en algo, c'est pas facile à décrire : vaudrait mieux aller direct dans le langage final, je pense... Tu bosses avec quel langage, exactement ?

Mac Lak, pour ton codage sur 64 bits, je suis d'accord... Tu viens de meme de (re)inventer une variante de uuencode ou base64

Non, tu crois ?

Par contre, la, je ne vois pas comment tu fais ca...?

Bon, on est d'accord sur le fait qu'il reste bien 4 bits en utilisant 22 caractères "pleins" codant chacun 6 bits, OK ?
Donc, une fois le flux "reformé" à partir de ces 22 caractères, on obtient un nombre à 132 bits (et non pas 128). Par défaut, les 4 bits de poids fort sont à zéro.
Mais en cas de collision du MD5 (vérifié par présence dudit code dans la base), il faut et il suffit d'incrémenter ce nombre de 4 bits pour générer une "nouvelle" empreinte, différente de la première. En cas de collision de nouveau, on réincrémente, etc... On peut donc avoir jusqu'à 16 collisions par empreinte MD5, ce qui devrait normalement amplement suffire : c'est même à la limite de la sur-qualité...
Bien sûr, il faut stocker en base le MD5 (128 bits) plus ce numéro incrémental (défaut : 0), et provoquer une erreur s'il arrive à 16 (=> nombre maximum de collisions atteint).
C'est OK pour toi ?

C'est un peu hors-sujet, car peu pratique dans notre cas, mais Unicode, ca existe, et aux dernieres nouvelles il y avait plus de 95000 caracteres definis (source Wikipedia)...

Je suis d'accord avec toi, mais faut pouvoir les saisir, ces caractères : perso, j'ai jamais touché un IME de ma vie, je n'en ai même pas un seul qui soit installé !!

[alveric]

Mais en cas de collision du MD5 (vérifié par présence dudit code dans la base), il faut et il suffit d'incrémenter ce nombre de 4 bits pour générer une "nouvelle" empreinte, différente de la première. En cas de collision de nouveau, on réincrémente, etc...

Ok, je n'avais pas compris que tu gardais tous les md5 dans une base... Dans ce cas, je suis d'accord.

[Mac LAK]

Ok, je n'avais pas compris que tu gardais tous les md5 dans une base... Dans ce cas, je suis d'accord.

J'avais écrit ça :

De toutes façons, il reste possible d'avoir des collisions : il faudra donc impérativement mémoriser toutes les empreintes calculées de manière à éviter, justement, une interversion accidentelle.

[TreizeSegments]

Le langage est du VB !!

[Mac LAK]

Le langage est du VB !!

Arf... Et m.....

Ca m'arrangerait que tu me donnes les éléments de VB permettant de faire des AND binaires, ainsi que des décalages binaires (Shift, Shr, Shl)... Cherches dans l'aide de VB, moi je n'ai même pas ce compilateur.

Bon, le principe :
1) Commence par "compléter" tes 32 caractères du MD5 par les bits nécessaires : un chiffre hexa, en début de chaîne, contenant le numéro incrémental dont je t'ai parlé précédemment. "0" par défaut, donc. La chaîne va donc faire 33 caractères de longueur.
2) Un chiffre hexa = 4 bits, un chiffre "compacté" = 6 bits. Donc, 3 chiffres hexa => 2 chiffres "compactés".
3) Initialiser la chaîne résultat (chaîne vide).
4) Faire une boucle, de 1 à 11 :
- Lire 3 caractères de la chaîne MD5 étendue,
- Convertir en 2 caractères compactés,
- Ajouter ces caractères compactés à la chaîne finale.
5) Fin, renvoyer la chaîne finale (22 caractères).

L'algo inverse de "décompactage" n'est pas plus difficile, il faut juste faire attention à "ajouter" ou "retirer" les caractères du bon côté des chaînes de caractères pour ne pas "inverser" le MD5 au bilan final.

La condition suivante doit toujours être réalisée :
Decompactage(Compactage(MD5_Etendu))=MD5_Etendu

Tout le "coeur" du problème consiste à écrire les fonctions suivantes :
- 3 caractères hexa -> 2 caractères compactés,
- 2 caractères compactés -> 3 caractères hexa,
- Une valeur 6 bits -> 1 caractère compacté,
- Un caractère compacté -> Une valeur 6 bits,
- Une valeur 4 bits -> 1 caractère hexa,
- Un caractère hexa -> Une valeur 4 bits.

A partir de ces fonctions "primitives", tu sauras réaliser les fonctions générales de compactage/décompactage ?

Donnes-moi, stp, tous les éléments de Visual Basic qui pourraient accélérer tout ça (notamment les conversions hexa <-> numérique), et quelles sont les fonctions que tu saurais réaliser toi-même...

Stp, ne fais pas "l'assisté" sur ce coup : je ne connais vraiment pas Visual Basic, je ne peux donc presque pas t'aider sur la réalisation du code !! Il faut vraiment que tu cherches par toi-même le maximum d'infos possibles pour me filer un coup de main, OK ?

[alveric]

Le coup de prendre 3 caracteres de la chaine representant le code md5 en hexa en 2 caracteres, est-ce vraiment necessaire ? Il serait peut-etre plus simple de prendre directement 6 bits du md5 pour en faire un caractere ? (en les prenant par bloc de 4 octets si besoin)
Ainsi, il y a juste besoin de:
- 6 bits MD5 -> un caractere "base64"
- un caractere "base64" -> 6 bits du MD5
avec, peut-etre
-24 bits MD5 -> 4 caracteres
-et l'inverse.
Le tout sans oublier les 4 bits de collision.

Mais cela depend de l'interface fournie par VB, si on peut acceder directement au code md5, ou seulement a la chaine hexa...

[Mac LAK]

Le coup de prendre 3 caracteres de la chaine representant le code md5 en hexa en 2 caracteres, est-ce vraiment necessaire ?

Nécessaire, non. Souhaitable, oui : les conversions seront plus simples. C'est surtout lié au fait que l'on ne puisse pas stocker une empreinte MD5 en mémoire en tant qu'entier, tout simplement.

[TreizeSegments]

Merci Mac LAK.
E nce qui concerne les fonctions de manipulations binaires sous VB, effectivement c'est pas la joie.

Jusqu'à présent, j'ai recherché un réponse à mon problème de façon générale (par exemple j'ai testé le MD5 sur un source JS) ! Le portage VB risque de ne pas être facile.

Si tu as un bout de code dans un langage quelqu'il soit et que tu peux me le présenter je suis preneur (seul l'encodage m'intéresse finalement). Je me chargerais de (tenter) faire le portage en VB.

[jmv]

salut

Dans le temps j'avais fait une classe md5 en C++. Si ça peut t'aider :
http://perso.wanadoo.fr/jmv/info/crypto/cmd5.h
http://perso.wanadoo.fr/jmv/info/crypto/cmd5.cpp
http://perso.wanadoo.fr/jmv/info/crypto/testmd5.cpp

[Mac LAK]

Merci Mac LAK.
E nce qui concerne les fonctions de manipulations binaires sous VB, effectivement c'est pas la joie.

De rien. C'est bien ce qu'il me semblait, pour le binaire sous VB... Pas cool. T'as toujours la solution d'une fonction dans un langage (ex : C), mis dans une DLL et importé directement en VB : à mon avis, ce sera la meilleure solution, et surtout la plus rapide...

Si tu as un bout de code dans un langage quelqu'il soit et que tu peux me le présenter je suis preneur (seul l'encodage m'intéresse finalement). Je me chargerais de (tenter) faire le portage en VB.

Je peux te proposer du Delphi ou du C, suivant le langage que tu connais le mieux... J'écrirais le code ce soir, il me faudra la réponse d'ici là.

[TreizeSegments]

désolé, je n'ai pas eu le temps de vérifier les msg.

Ok pour le C.
Merci d'avance.

(PS : cela ne presse pas à la journée tu as tout ton temps)

[Mac LAK]

Le programme est compilable directement, les fonctions sont présentes.
Je n'ai pas écrit de code spécifique Windows, au cas où...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
#include <stdio.h>
#include <stdlib.h>
#include <mem.h>
#include <string.h>
 
// Table de conversion pour l'encodage.
char B64LUT[64] ;
 
// Conversion d'un entier en chiffre hexa.
#define nibble2hex(n) ((char)(((n)<10) ? ('0'+(n)) : ('A'+((n)-10))))
 
// Préparation de la LUT de conversion.
// A n'appeler qu'une seule fois dans le programme !
void CreateLUT64 ( char* LUT ) {
 
   int i ;
   // Remplissage simple
   for (i=0;i<10;i++)
      // Codes numériques.
      LUT[i]=(char)('0'+i);
   for (i=10;i<36;i++)
      // Codes alphabétiques : majuscules.
      LUT[i]=(char)('A'+(i-10));
   for (i=36;i<62;i++)
      // Codes alphabétiques : minuscules.
      LUT[i]=(char)('a'+(i-36));
   // Codes alphabétiques : autres codes.
   LUT[62]='#';
   LUT[63]='-';
}
 
// Fonction d'encodage unitaire : 3 chars "hexa" -> 2 chars "compactés".
void Encode64 ( char* HexaString, char* B64String ) {
 
   unsigned int value ;
   char tmp[4] ;
 
   // Recopie de la chaine hexa (3 caractères seulement).
   strncpy(tmp,HexaString,3);
   tmp[3]=0;
   // Conversion hexa->numérique.
   sscanf(tmp,"%x",&value);
   // Encodage : découpage des 2 codes 6 bits et conversion.
   *(B64String++)=B64LUT[((value>>6) & 0x3F)];
   *B64String=B64LUT[value & 0x3F];
}
 
// Compactage d'une empreinte MD5. Les buffers doivent être corrects et alloués.
// Retourne la chaîne compactée.
char* PackMD5 ( char* MD5, char* Packed, int CollisionIndex ) {
 
   char tmd5[34] ;
   char* tmp = tmd5 ;
   char* pck = Packed ;
 
   // Copie et complétion du MD5.
   memcpy(tmd5,MD5,32);
   // Calcul du chiffre hexa correspondant au numéro de collision.
   tmd5[32]=nibble2hex((CollisionIndex & 0x0F));
   tmd5[33]=0;
 
   // Encodage, par paquets de 3/2.
   for ( int i=0 ; i<22 ; i+=2, tmp+=3, pck+=2 )
     Encode64(tmp,pck);
   // Ajout du zéro terminal.
   Packed[22]=0;
 
   return Packed;
}
 
void main ( void ) {
 
   char md5[33] ;
   char packed[23] ;
   int i, j, v ;
 
   // Initialisation des buffers (pour zéro terminal notamment).
   memset(md5,0,sizeof(md5));
   memset(packed,0,sizeof(packed));
   // Création de la table d'encodage.
   CreateLUT64(B64LUT);
   // Initialisation générateur aléatoire.
   srand(time(NULL));
 
   // Conversions d'exemple : 10 conversions aléatoires.
   for (j=0;j<10;j++) {
      // Création d'un MD5 pour l'exemple.
      for (i=0;i<32;i++) {
         v = (rand() & 0x0F) ;
         md5[i]=nibble2hex(v); // Attention, c'est une macro !!
      }
      printf("\nOriginal MD5 checksum      : %s\n",md5);
      for (i=0;i<16;i+=15) {
         PackMD5(md5,packed,i);
         printf("Packed checksum (coll. %02d) : %s\n",i,packed);
      }
   }
}

Exemple de conversions :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
Original MD5 checksum      : 7ABD8590AA48D0D8DC346BE2B0F23E8A
Packed checksum (coll. 00) : Uhs5aAf8qDZSD6lYiF8#YW
Packed checksum (coll. 15) : Uhs5aAf8qDZSD6lYiF8#Yl
 
Original MD5 checksum      : 6886689E0ED94B613D489C5AB5843524
Packed checksum (coll. 00) : Q8PedWxPIs4zI9nQjOGr90
Packed checksum (coll. 15) : Q8PedWxPIs4zI9nQjOGr9F

Ca te va ?

[TreizeSegments]

Je te remercie.
Voilà une bonne base de travail, sympa

Y a plus qu'à...

[alveric]

Quitte a donner du code, autant qu'il soit valide, alors:

• main doit renvoyer un int, pas void, et
• il manque l'inclusion de time.h.

Comment ca, on n'est pas sur le forum C ?