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[1], mieux connu au travers de sa présentation par Carl Meyer et Michael Schilling en 1988[2]. 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[3]. Mais en 2009, Knudsen et collaborateurs proposent une cryptanalyse permettant de trouver des collisions et des préimages[4] 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[1] 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 de 64 bits chacun (correspondant à la largeur d'un bloc DES). L'algorithme MDC-2 consiste à effectuer les opérations suivantes[5] :
- for to :
- return
où désigne le chiffrement DES du message par la clé , le symbole désigne le ou exclusif, le symbole désigne la concaténation, et les exposants correspondent aux parties haute et basse respectivement d'un mot de 128 bits. Les constantes et 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
Références
- Brevet américain 4,908,861, délivré le 12 mars 1990, déposé par IBM le 28 août 1987. Les inventeurs désignés sont Bruno O. Brachtl, Don Coppersmith, Myrna M. Hyden, Stephen M. Matyas Jr., Carl H. W. Meyer, Jonathan Oseas, Shaiy Pilpel et Michael Schilling .
- (en) C. H. Meyer and M. Schilling. Secure Program Load with Manipulation Detection Code. In SECURICOM 88, Proceedings, pages 111–130, 1988.
- (en) John P. Steinberger, « The Collision Intractability of MDC-2 in the Ideal-Cipher Model », dans Advances in Cryptology - EUROCRYPT 2007, Springer Berlin Heidelberg, (ISBN 9783540725398, DOI 10.1007/978-3-540-72540-4_3, lire en ligne), p. 34–51
- (en) Lars R. Knudsen, Florian Mendel, Christian Rechberger et Søren S. Thomsen, « Cryptanalysis of MDC-2 », dans Advances in Cryptology - EUROCRYPT 2009, Springer Berlin Heidelberg, (ISBN 9783642010002, DOI 10.1007/978-3-642-01001-9_6, lire en ligne), p. 106–120
- (en) Bart Preneel, « Cryptographic hash functions: an overview », COSIC, (lire en ligne)