Voir la source de MD6

L'algorithme '''MD6''', pour '''[[Message Digest]] 6''', est une [[fonction de hachage cryptographique]] qui permet d'obtenir l'empreinte numérique d'un fichier (on parle souvent de ''message'').  MD6 a été développée par un groupe<ref>Liste des auteurs: Benjamin Agre, Dan Bailey, Sarah Cheng, Christopher Crutchfield, Yevgeniy Dodis, Kermin Fleming, Asif Khan, Jayant Krishnamurthy, Yuncheng Lin, Leo Reyzin, Ron Rivest, Emily Shen, Jim Sukha, Eran Tromer, Yiqun Lisa Yin</ref> mené par [[Ronald L. Rivest]], cryptologue américain qui inventa [[MD5]] et participa au développement de [[Rivest Shamir Adleman|RSA]], avec [[Adi Shamir|Shamir]] et [[Len Adleman|Adleman]].

MD6 a été proposée pour participer à la [[NIST hash function competition|compétition de fonction de hachage du NIST]] en 2008 mais ne fut pas retenue lors de la deuxième étape de sélection.

==Principe==
MD6 prend en entrée un message de taille au plus <math>2^{64}</math> bits, pour lequel il
calcule une empreinte de ''d'' bits, où 0 < ''d'' ≤ 512 bits.

De même, un certain nombre de paramètres, possédant des valeurs par défaut,
peuvent être modifiés :
*''Clé K'': nulle par défaut (et donc de taille 0). Peut être utilisée pour du [[Salage (cryptographie)|salage]].
*''Hauteur de l'arbre L''. En effet, comme décrit plus loin, MD6 utilise un [[arbre de Merkle]] quaternaire. Sa hauteur peut donc être spécifié. Si L vaut 0, la compression se fait selon un schéma séquentiel (de type [[Merkle-Damgård]]) permettant d'obtenir le même résultat. Si L est inférieur à 64, la compression peut être hybride, car commençant pour un [[parcours d'arbre]] pour finir pour un parcours séquentiel.
*''Nombre de tour r'': par défaut, <math>\scriptstyle r=40+ \lfloor d/4 \rfloor</math>, donc avec la valeur par défaut de ''d'' (256), r=104.
*''Les autres paramètres'': les constantes utilisées par la [[fonction de compression]] (''Q''), ou les indices des valeurs hachés à réutiliser pour le hachage du tour de boucle suivant(''t1, t2, t3, t4, t5'') peuvent aussi être modifié, sous certaines conditions. Par exemple, les valeurs des ''ti'' ne peuvent excéder 89.

==Mode d'opération==
[[Image:Md6ParMode.png|thumb|L'arbre de Merkle de MD6|right|upright=2.5]]
Le mode d'opération par défaut repose sur un [[arbre de Merkle]] quaternaire.

L'unité de mesure est le ''mot'', qui vaut {{Unité|8|octets}}, ou 64 bits.

Les feuilles de l'arbre proviennent du fichier à hacher. Elles sont éventuellement complétées par des 0 pour obtenir des feuilles de taille 16 mots, soit {{Unité|128|octets}} ou 1024 bits.
De plus, chaque nœud ayant 4 fils, des feuilles/nœuds supplémentaires composés de 0 sont ajoutés pour obtenir le bon nombre de feuilles/nœuds.
Chaque bloc, composé de quatre nœuds, est compressé (avec la fonction de compression détaillée dans la partie suivante) pour obtenir en sortie un nœud de taille 16 mots.

Ainsi, on remonte dans l'arbre jusqu'à n'avoir plus qu'un seul nœud : la racine.

L'empreinte de la fonction de hachage est calculée en tronquant les ''d'' derniers bits de la racine de l'arbre (256 par défaut).

==Fonction de compression==
[[Image:Md6InternalState.png|thumb|Données en entrée de la fonction de compression|right|upright=2.5]]

La fonction de compression prend en entrée un vecteur de 89 mots, composé des éléments suivants :
*''Q'' un vecteur de 15 mots, égal à la [[partie fractionnaire]] de <math>\scriptstyle  \sqrt{6}</math>
*''K'' les 8 mots de la clé (ou 0 s'il n'y a pas de clé)
*''U'' 1 mot, indiquant la position du bloc, dont le contenu est détaillé sur la figure ci-contre
*''V'' 1 mot, composé de ''r'' (le nombre de tour), ''L'' (la hauteur maximale de l'arbre), ''z'' (vaut 1 lors de la dernière compression, celle qui permet d'obtenir la racine, 0 sinon), ''p''  (le nombre de 0 ajouté (padding)), ''keylen'' la taille de la clé et ''d'' la taille de l'empreinte à générer
*''B'' 1 bloc de 64 mots de données, correspondant à 4 nœuds de 16 mots

La fonction de compression, effectue ensuite ''r'' tours (par défaut 104), composé chacun de 16 boucles indépendantes.
Chacune de ses 16 boucles effectue une quinzaine d'opérations logiques ou de décalage de bits (les opérations logiques sont préférées aux opérations arithmétiques et aux opérations dépendant de branchement afin d'empêcher les attaques par canaux auxiliaires).

Chaque tour calcule 89 mots, à partir des 89 mots calculés précédemment (les 89 premières valeurs sont le vecteur de 89 mots passé en entrée de la fonction de compression).

Les 64 derniers mots calculés sont la sortie de la fonction de compression.

==Notes et références==
{{références}}

==Liens externes==
* {{en}} {{Lien web|url=http://people.csail.mit.edu/rivest/md6_report.pdf|titre=Papier de référence}}
* {{en}} {{Lien web|url=http://groups.csail.mit.edu/cis/md6/docs/2008-06-crutchfield_ms_thesis.pdf|titre=Preuve de sécurité du mode d'opération de MD6}}
* {{fr}} {{Lien web|url=http://moais.imag.fr/membres/jean-louis.roch/perso_html/transfert/2009-06-19-IntensiveProjects-M1-SCCI-Reports/BiennerDequidt_fr.pdf|titre=Article sur les implémentations parallèles de MD6}}

{{Palette|Fonctions de hachage cryptographiques}}
{{Portail|Cryptologie}}

[[Catégorie:Algorithme de hachage]]