Discussion :

[deltabweb]

Bonjour,

Je souhaite programmer un algorithme me retournant le md5 d'un texte.
Après de longues heures de travail je suis parvenu à obtenir un algorithme qui fonctionne mais je n'obtiens pas les mêmes empreintes qu'avec le md5 "officiel" (celui décrit par le RFC 1321).

J'obtiens actuellement 7A64D72B5402ED028CF9C8F2627D2B0A pour un message vide au lieu de d41d8cd98f00b204e9800998ecf8427e. Je pense donc que le problème viens des constantes.

Pour rappel le pseudo code du md5 est :

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
//Note: Toutes les variables sont sur 32 bits

//Définir r comme suit : 
var int[64] r, k
r[ 0..15] := {7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22}
r[16..31] := {5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20}
r[32..47] := {4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23}
r[48..63] := {6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21}

//MD5 utilise des sinus d'entiers pour ses constantes:
pour i de 0 à 63 faire
    k[i] := floor(abs(sin(i + 1)) × 2^32)
fin pour

//Préparation des variables:
var int h0 := 0x67452301
var int h1 := 0xEFCDAB89
var int h2 := 0x98BADCFE
var int h3 := 0x10325476

//Préparation du message (padding) :
ajouter "1" bit au message
ajouter "0" bits jusqu'à ce que la taille du message en bits soit égale à 448 (mod 512)
ajouter la taille du message codée en 64-bit little-endian au message

//Découpage en blocs de 512 bits:
pour chaque bloc de 512 bits du message
    subdiviser en 16 mots de 32 bits en little-endian w[i], 0 ≤ i ≤ 15

    //initialiser les valeurs de hachage:
    var int a := h0
    var int b := h1
    var int c := h2
    var int d := h3

    //pour principale:
    pour i de 0 à 63 faire
        si 0 ≤ i ≤ 15 alors
            f := (b et c) ou ((non b) et d)
            g := i
        sinon si 16 ≤ i ≤ 31 alors
                  f := (d et b) ou ((non d) et c)
                  g := (5×i + 1) mod 16
              sinon si 32 ≤ i ≤ 47 alors
                        f := b xor c xor d
                        g := (3×i + 5) mod 16
                    sinon si 48 ≤ i ≤ 63 alors
                              f := c xor (b ou (non d))
                              g := (7×i) mod 16
                          fin si
                    fin si
              fin si
        fin si

        var int temp := d
        d := c
        c := b
        b := ((a + f + k[i] + w[g]) leftrotate r[i]) + b
        a := temp
    fin pour

    //ajouter le résultat au bloc précédent:
    h0 := h0 + a
    h1 := h1 + b 
    h2 := h2 + c
    h3 := h3 + d
fin pour

var int empreinte := h0 concaténer h1 concaténer h2 concaténer h3 //(en little-endian)

Mon programme travaille en binaire et d'après ce que j'ai lu il faut coder le tout en little endian (bit le moins important en premier).

• Première question : Certains sites donnent h0=0x01234567 comme première variable et ainsi de suite au lieu de ce qui est spécifié plus haut ... Si j'ai bien compris cela dépend de quels octets on met en premier. Quelle écriture dois-je utiliser ?
• Deuxième question : Pour coder les variables hexadecimales je prends celles du pseudocode les convertit d'abord en binaire puis j'inverse le sens d'écriture pour obtenir du little-endian. Est-ce la bonne procédure ?
• J'obtiens 10000000110001001010001011100110 pour h0 est-ce le bon résultat ?
• De même j'obtiens 00011110001001010101011011101011 pour k[0] est-ce le bon résultat ?

PS: J'utilise caml comme language de programmation mais je ne pense pas que ça ait une importance pour ce problème.

[sloshy]

Bonjour,
Cela est plus de la prog d'algo que de la prog windows non?

[deltabweb]

En effet désolé pour l'erreur ... Si un modérateur veut bien déplacer le topic.
Sinon personne n'a déjà programmé du md5 et peux m'aider ?

[Piano]

J'ai déjà "programmé du md5" mais avec l'implémentation C déjà faite.
Pourquoi tu ne vérifies pas sur celle-là ?
Va sur wikipédia, cherche MD5 puis prends les liens en bas ;-)

[sloshy]

Rebonjour ;-)
Est l'impémentation qui est importante ou bien le résultat?
A savoir, il existe des APIs permettant de calculer des hash MD5 et elles sont très bien faites. (après, si c'est un exercice par exemple, ça n'a aucun interet).

Il me semble qu'un code d'implémentation en C est présent dans la RFC non?

[deltabweb]

Premièrement, merci pour votre soutient.
Il y a effectivement une implémentation en C dans la RFC mais vu que je n'ai jamais programmé dans ce language je n'ai quasiment rien compris.
Ensuite c'est bien l'implémentation qui m'intéresse puisque je compte ensuite fabriquer des algorithmes permettant des attaques par bruteforce, dictionnaire et table en arc-en-ciel. Le problème étant que je ne peux pas à ma connaissance utiliser d'API avec Caml, il faut donc que je l'implémente moi même.
Etant donné que je ne comprends rien au C, ce serait vraiment sympa si tu pouvais vérifer pour moi pianopariss ou n'importe qui d'autre qui sait comment faire

[droggo]

Woe,

Premièrement, merci pour votre soutient.
Il y a effectivement une implémentation en C dans la RFC mais vu que je n'ai jamais programmé dans ce language je n'ai quasiment rien compris.
Ensuite c'est bien l'implémentation qui m'intéresse puisque je compte ensuite fabriquer des algorithmes permettant des attaques par bruteforce, dictionnaire et table en arc-en-ciel. Le problème étant que je ne peux pas à ma connaissance utiliser d'API avec Caml, il faut donc que je l'implémente moi même.
Etant donné que je ne comprends rien au C, ce serait vraiment sympa si tu pouvais vérifer pour moi pianopariss ou n'importe qui d'autre qui sait comment faire

Doux rêveur.

Et j'ai un problème de compréhension : tu n'arrives pas à l'implémenter et tu veux implémenter de quoi le casser ?
Tu peux toujurs essayer, mais bien d'autres s'y sont essayés.

[deltabweb]

J'ai réussi à l'implémenter et j'ai déjà commencé à créer des algorithmes pour le casser.
Le seul problème est que pour un texte donné je n'obtiens pas la même signature qu'avec un programme conforme à la RFC.
Ce n'est pas un problème pour la suite puisque les propriétés du MD5 sont conservés avec mon implémentation : Empreinte constante pour un texte donné, Collisions difficiles à trouver, etc ...
Mais j'aimerais tout de même obtenir les mêmes résultats par souci d'utilisation de mes résultats avec d'autres programmes et de présentation.

[sloshy]

Bonjour,
Si c'est le résultat qui compte et non le fait que face ton implémentation toi même -> http://caml.inria.fr/pub/docs/manual...ef/Digest.html
Dans le même style, si tu veux utiliser l'API win32 -> http://www.speakeasy.org/~hchomsky/ocaml-win32.html
Tu ne réussira pas créer un algorithme permettant de partir d'un hash MD5 et d'arriver à la chaine initiale.
Des équipes de mathématicien diplomé s'y sont essayé avant toi.

La seule possibilitée se base sur une recherche par dictionnaire.
Là tu arrives à devoir faire un compromis temps/mémoire et tu devra implémenter le concepte des rainbows tables qui sont déjà mise en application dans bien des cas.

Bon apprentissage quand même, j'espère que le but de tes démarches est bien ça et rien d'autre ...

[deltabweb]

Merci pour ces liens malheureusement j'utilise caml light et non ocaml, de plus je préfèrerais quand même faire l'implémentation moi même.

Le but de mes démarches est de faire une présentation sur les attaques possibles sur le md5 comme TIPE (épreuve que l'on passe en classe préparatoire pendant les concours d'entrée à une école d'ingénieur).

Par contre, je pense que tu m'as mal compris (ou bien que tu n'as pas bien lu ce que je disais ) j'entendais par casser utiliser des méthodes tel que le bruteforce (Test de toutes les possibilités jusqu'à arriver au même MD5); l'attaque par dictionnaire et les rainbow table (que j'ai appelé table en arc-en-ciel) comme tu le précisais.
J'ai en effet déjà implémenté la méthode de brute force et de rainbow table.

[deltabweb]

Quelqu'un peut m'aider ?
Je demande juste comment le buffer h0 du md5 est vu en binaire, je me débrouillerais pour le reste.
Ceci n'est apparemment pas difficile à obtenir si on connait le C++ (ce qui n'est pas mon cas)

Merci par avance (Eh oui jsuis optimiste )

[Neitsa]

Bonjour,

3.3 Step 3. Initialize MD Buffer

A four-word buffer (A,B,C,D) is used to compute the message digest.
Here each of A, B, C, D is a 32-bit register. These registers are
initialized to the following values in hexadecimal, low-order bytes
first):

word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10

La phrase "low order byte first" signifie qu'ils sont écrits ici en little-endian, comprendre : l'octet de poids faible vient en premier (on va du poids le plus faible au poids le plus fort).

En C on écrirait donc [en supposant que Buffer soit un pointeur sur une structure ayant 4 double-mots (32 bits donc) nommés A, B, C, D] :

Code C :

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

1
2
3
4
5
 
  Buffer->A = 0x67452301;
  Buffer->B = 0xefcdab89;
  Buffer->C = 0x98badcfe;
  Buffer->D = 0x10325476;

[deltabweb]

Merci pour la réponse mais c'est surtout la version binaire de ceci qui m'intéresse.
Par exemple si je convertis 0x67452301 avec la calculatrice windows en binaire, j'obtiens 1100111010001010010001100000001 or si j'ai bien compris il faudrais que j'inverse le sens pour obtenir du little endian soit 1000000011000100101000101110011 ...
Or avec ce procédé j'obtiens des signatures md5 qui ne correspondent pas à celle que l'on aurait selon la RFC1321

Je reformule donc ma question : que donne le 0x67452301 en binaire ?

[Médinoc]

Ça fait
0110 0111 1000 0101 0010 0011 0000 0001

[Médinoc]

Attention, l'endianness est rarement un problème d'ordre des bits. C'est plus souvent un problème d'ordre des octets:

Ce qui donne 0x67452301 = 67 45 23 01 en big-endian, 01 23 45 67 en little-endian.

Donc, en big-endian: 01100111 10000101 00100011 00000001
En little-endian: 00000001 00100011 10000101 01100111

[Neitsa]

Je ne comprends pas très bien pourquoi tu t'obstines à vouloir une représentation en binaire... Tu te crées un faux problème tout seul.

L'endianess n'est pas une inversion de sens des bits. C'est prendre des paquets de 8 bits (octets) et mettre les octets de poids faible au début et mettre les octets de poids fort à la fin.

Là, dans ton problème tu n'as pas à te soucier de l'endianess du système sous-jacent, c'est ton compilo pour le système cible qui s'en charge. Ecrit tes nombres comme tu le ferais naturellement, c-a-d en big endian (cf. bout de code en C).

A ma connaissance, il n'existe pas de langage de programmation actuel et répandu ou les nombres doivent explicitement être écrit en little-endian dans le code source (en plus c'est contre intuitif).