Bonsoir,

Je recherche quelqu'un qui connaît bien l'algorithme MD4 ( et aussi le Caml si possible mais ce n'est pas le plus important) pour m'aider à comprendre plusieurs choses sur cet algorithme que je dois implémenter en Caml : je l'ai implémenté mais il ne renvoie pas la bonne empreinte. J'aimerais donc savoir si quelqu'un s'y connaît dans le coin ou si vous connaissez un site où je pourrai trouver du monde qui s'y connait là-dedans.

Merci d'avance.

Bonjour,

Je ne connais pas MD4 plus que ça, mais à défaut j'ai déjà pas mal codé en (O)caml. Je pourrais donc éventuellement t'aider si tu nous montres du code.

Merci ^^ , je t'ai répondu en message privé.

Sur les conseils de Chris_27 je vais poster ici plutôt qu'en message privé pour avoir plus de chances d'obtenir des réponses :

je mets du coup un petit récapitulatif de ce qu'on a dit en message privé pour ceux qui veulent suivre l'évolution du truc :D :

==================
==================

Maxchaos93 :

Bonsoir,
merci pour ta réponse, je peux t'envoyer un passage de la chose qui me bloque : je ne vois pas comment interpréter un passage dans la description de MD4 ( sur le site https://tools.ietf.org/html/rfc1186 ) : voilà l'extrait :

In this note a "word" is a 32-bit quantity and a byte is an 8-bit
quantity. A sequence of bits can be interpreted in a natural manner
as a sequence of bytes, where each consecutive group of 8 bits is
interpreted as a byte with the high-order (most significant) bit of
each byte listed first. Similarly, a sequence of bytes can be
interpreted as a sequence of 32-bit words, where each consecutive
group of 4 bytes is interpreted as a word with the low-order (least
significant) byte given first.

Je ne vois pas comment ça peut se traduire concrètement dans mon programme : j'utilise des vecteurs pour représenter les suites de chiffres binaires et j'ai représenté ça de façon classique : bit de poids fort à gauche vers bit de poids faible à droite mais j'ai l'impression que ce passage suppose autre chose que ce que j'ai fait et cela doit probablement contribuer à l'échec de mon programme.

Après il y a peut-être ( probablement :D ) des erreurs à traquer dans le programme, mais j'aimerais avant avoir une idée claire de ce passage afin d'être fixé là-dessus.

Une fois que j'aurai la vraie solution pour l'interprétation de ce morceau, si je n'ai toujours rien de bon, c'est qu'il y a une ou des erreurs ailleurs dans mon programme.

Chris_27 :

Bonsoir,

Là c'est plus de la technique pure et dure qu'autre chose. Ce qu'on te dit, c'est que tu as une sequence de bits.

Vu que tu codes en caml, toute structure autre qu'une liste (ou un stream si vraiment tu traites des données de plusieurs centaines de Mo) n'est pas envisageable. A partir de là, on t'explique comment transformer une liste de bits en une liste de bytes : lire par paquet de 8, bits de forts en tête de paquets.

Ainsi, [0;1;1;1;1;1;1;1; 1;0;0;0;0;0;0] va devenir [ 127; 128 ]. Ce passage peut s'obtenir facilement à l'aide d'une fonction récursive qui lit les 8 premiers éléments d'une liste, comme suit :

let rec f l = match l with
| [] -> []
| b1::b2::b3::b4::b5::b6::b7::b8::q -> (128*b1 + 64*b2 + 32*b3 + .... + 2*b7 + b8) :: f q
| _ -> assert false
;;

Pour le passage aux mots, c'est pareil sauf que c'est du bit de poids faible en tête. ça donne quelque chose comme :

let rec g l = match l with
| [] -> []
| o1::o2::o3::o4::q -> (o1 + 256*o2 + 256*256*o3 + 256*256*256*o4) :: g q
| _ -> assert false
;;

SAUF QUE ... si tu n'es pas sur un système 64 bits, avec un ocaml version 64 bits... le 256*256*256*o4 risque d'être plus grand que max_int, et donc tous tes calculs seront faux.

Donc, commence par vérifier combien vaut max_int (s'il a moins de 15 chiffres, tu vas être coincé).

==================
==================

Pour ce qui est de ta réponse, je crois avoir compris quelques petits choses mais je ne vois pas vraiment comment appliquer ça en pratique dans mon implémentation. Du coup, plutôt que de m'embrouiller dans un tas d'explications, je vais vous décrire comment j'interprète les choses dans l'algorithme. Pour ça je vais décrire comment j'ai compris les choses dans la rfc ( https://tools.ietf.org/html/rfc1186 ) du début de la partie partie 3 ) MD4 Algorithm Description à la fin de la "step 2" de cette même partie :

Tout d'abord je ne tiendrai pas compte des conventions que je ne comprends pas encore, du coup tous mes vecteurs binaires seront écrits des poids forts vers le poids faible.

Description : On prend un message que l'on traduit en binaire et on commence l'étape 1 ( "step 1" ) : on fait le "padding" c'est-à-dire que l'on rajoute un 1 puis que des zéros au bout de notre vecteur de façon à ce que sa taille soit congrue à 448 modulo 512. Une fois que c'est fait on attaque l'étape 2 : on reprend notre vecteur originel ( celui avant padding ) et on note sa taille dont on fait une représentation binaire en 64 bits. On concatène alors le tableau obtenu suite au padding et celui obtenu par la représentation 64 bits.

Exemple : voici comment fonctionne mon programme sur un exemple simple : on met en message d'entrée "bonjour" :

Oups, fausse manip ^^", je reprends où j'en étais :
"bonjour" en entrée :

1) Je traduis ça en binaire : je prends la table ascii pour chaque lettre et je traduis en binaire le décimal obtenu et je concatène le tout pour avoir mon message complet :

1. traduc_string_bin "bonjour";;

- : int vect =
[|0; 1; 1; 0; 0; 0; 1; 0; 0; 1; 1; 0; 1; 1; 1; 1; 0; 1; 1; 0; 1; 1; 1; 0; 0; 1; 1; 0; 1; 0; 1; 0; 0; 1; 1; 0; 1; 1; 1; 1; 0; 1; 1; 1; 0; 1; 0; 1; 0; 1; 1; 1; 0; 0; 1; 0|]

#

2 ) Ensuite j'effectue le padding : je rajoute mon 1 et mes 0 comme décrit précédemment :

1. padding m;;

- : int vect =
[|0; 1; 1; 0; 0; 0; 1; 0; 0; 1; 1; 0; 1; 1; 1; 1; 0; 1; 1; 0; 1; 1; 1; 0; 0; 1; 1; 0; 1; 0; 1; 0; 0; 1; 1; 0; 1; 1; 1; 1; 0; 1; 1; 1; 0; 1; 0; 1; 0; 1; 1; 1; 0; 0; 1; 0; 1; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0;
...|]

#

Il n'y a que des 0 jusqu'à la fin ensuite d'où les ...|]

3 ) Ensuite je note la taille de mon message binaire "bonjour" ( je l'appelle n ) et j'en fais une représentation 64 bits :

n = 56

1. ecrire_binaire_64 56;;

- : int vect =
[|0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 1; 1; 1; 0; 0; 0|]

#

4 ) Je mets au bout du vecteur obtenu en étape 2 celui obtenu en étape 4 et j'obtiens :

1. ecrire_complet_vect ( preparation_MD4 "bonjour" );;

[|0; 1; 1; 0; 0; 0; 1; 0; 0; 1; 1; 0; 1; 1; 1; 1; 0; 1; 1; 0; 1; 1; 1; 0; 0; 1; 1; 0; 1; 0; 1; 0; 0; 1; 1; 0; 1; 1; 1; 1; 0; 1; 1; 1; 0; 1; 0; 1; 0; 1; 1; 1; 0; 0; 1; 0; 1; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 1; 1; 1; 0; 0; 0|]- : unit = ()

#

=========
=========

Voilà pour les explications, maintenant les questions :D :

1 ) Comment appliquer les conventions que tu m'as expliquées là-dedans ?

2 ) Y a t-il des erreurs dans ce que j'ai fait et si oui lesquelles ? (je pense notamment au fait que je ne suis pas très sur que ce soit bien comme ça qu'il faille passer de la chaîne de caractère à la représentation binaire par exemple ).

Si tu veux vraiment utiliser des vecteurs, ne code pas en caml, vraiment.

Sinon

1) je pense que ton ecrire_binaire ne met pas les bits dans le bon sens. Tel que je comprends la RFC, le poids le plus faible (donc les 1) devraient être en premier.

2) tu ne pourrais pas comparer ce que tu obtiens en sortie avec ce que donne une commande Unix ou un site web bien senti ?

• Pour ce qui est des vecteurs, j'ai déjà tout programmé avec jusqu'à maintenant et j'ai pas eu trop de soucis ( mais bon au pire si besoin est je peux faire un petit coup de list_of_vect ).

• Ensuite, je ne vois pas trop ce que tu veux dire par "le poids le plus faible (donc les 1) devraient être en premier." : cette histoire d'ordre n'est qu'un histoire liée aux puissances affectées à 2 quand on lit le vecteur non ?

poids faible ------------> poids fort
2^0 ------------> 2^n

poids fort ------------> poids faible
2^n ------------> 2^0

c'est pas comme ça que ça marche ? Ce que je veux dire c'est que je ne vois pas pourquoi ça changerait les 1 de place et je ne vois pas trop comment. Si on prend l'exemple ça devrait donner quoi selon toi ?

• Pour ce qui est de la dernière question, je n'ai pas trouvé de site qui proposent de donner les résultats intermédiaires du MD4 , ils balancent directement la signature. J'ai bien essayé d'utiliser l'implémentation en C fournie dans la rfc en demandant à un ami qui connait le C de compiler le programme mais apparemment ça ne marche pas car certaines commandes ou standards ne sont plus utilisés aujourd'hui par les compilateurs... Car si ça avait marché j'aurais essayé de voir comment faire renvoyer les résultats intermédiaires par le programme en C pour comparer.

fait gaffe quand tu fais des histoires de bit de poids fort et bit de poids faible. Ca depend souvent de l'architecture materielle. En C, travailler sur un tableau de unsigned char regle souvent le probleme.

Le truc que j'ai un peu de mal à voir c'est comment gérer cet ordre des bits car, je ne connais pas le C, mais j'ai l'impression que toutes ces histoires d'ordre sont traitées en arrière plan de façon autonome mais là en Caml, avec mes tableaux j'ai l'impression que c'est moi qui doit bien construire mes fonctions pour que l'ordre soit respecté, un peu comme si je devais créer la bonne structure à gérer. Je ne sais pas si vous voyez vraiment ce que je veux dire ( j'avoue que c'est pas très clair ce que je viens de raconter mais j'ai un peu de mal à bien comprendre tout ça aussi ^^" ) mais si quelqu'un voit, est-ce qu'il peut m'expliquer ça sur l'exemple que j'ai donné plus haut pour que je puisse mieux me rendre compte de ce que ça doit donner ?