MDC-2

L'algorithme de Meyer-Schelling, aussi connu sous le nom MDC-2, est une fonction de hachage cryptographique inventée par Bruno Brachtl et collaborateurs en 1987, mieux connu au travers de sa présentation par Carl Meyer et Michael Schilling en 1988. Cet algorithme a été standardisé sous le numéro ISO/IEC 10118-2 en 1994. MDC-2 s'appuie sur le chiffrement par bloc DES comme fonction à sens unique, et la longueur de la sortie de MDC-2 est celle de deux blocs DES, c'est-à-dire au total 128 bits.

En 2007, une preuve de sécurité de la résistance aux collisions dans le modèle du chiffre idéal a été proposée. Mais en 2009, Knudsen et collaborateurs proposent une cryptanalyse permettant de trouver des collisions et des préimages plus efficacement qu'en attaquant DES. En matière de performances comme de sécurité, MDC-2 est considéré comme obsolète en regard d'alternatives modernes telles que SHA-3.

L'algorithme MDC-2 fut couvert par un brevet IBM de 1990 à 2002 ce qui a causé son retrait de la librairie OpenSSL et de nombreuses librairies cryptographiques, une exception notable étant la librairie GPG.

Mécanisme

Soit un message découpé en blocs $M_{1},\dotsc ,M_{m}$ de 64 bits chacun (correspondant à la largeur d'un bloc DES). L'algorithme MDC-2 consiste à effectuer les opérations suivantes :

• for $i=1$ to $m$:
  • $V_{i}=M_{i}\oplus E(M_{i},A_{i})$
  • $W_{i}=M_{i}\oplus E(M_{i},B_{i})$
  • $V_{i}^{L}||V_{i}^{R}=V_{i}$
  • $W_{i}^{L}||W_{i}^{R}=W_{i}$
  • $A_{i+1}=V_{i}^{R}||W_{i}^{L}$
  • $B_{i+1}=W_{i}^{R}||V_{i}^{L}$
• return $A_{m+1}||B_{m+1}$

où $E(m,k)$ désigne le chiffrement DES du message $m$ par la clé $k$, le symbole $\oplus$ désigne le ou exclusif, le symbole $||$ désigne la concaténation, et les exposants $L,R$ correspondent aux parties haute et basse respectivement d'un mot de 128 bits. Les constantes $A_{1}$ et $B_{1}$sont fixées une fois pour toutes. Souvent, les constantes 0x5252525252525252 et 0x2525252525252525 sont utilisées

Exemple

Dans l'exemple suivant on utilise DES et MDC-2 sur une chaîne de 43 caractères représentés en ASCII :

 MDC2("The quick brown fox jumps over the lazy dog") 
  = 000ed54e093d61679aefbeae05bfe33a

L'effet d'avalanche est illustré par l'effet d'une modification même mineure et localisée, ici le remplacement d'un d par un c :

 MDC2("The quick brown fox jumps over the lazy cog") 
  = 775f59f8e51aec29c57ac6ab850d58e8

La chaîne vide a pour haché la séquence suivante :

 MDC2("") 
  = 52525252525252522525252525252525