Groupe de travail Réseau |
R. Rivest |
Request for Comments : 1320 |
MIT Laboratory for Computer Science et RSA Data Security, Inc. |
RFC rendue obsolète : RFC 1186 |
|
Traduction Claude Brière de L'Isle |
avril 1992 |
Algorithme de résumé de message MD4
Statut du présent mémoire
Le présent mémoire donne des informations pour la communauté de l'Internet. Il ne spécifie pas une norme de l'Internet. La distribution du présent mémoire n'est soumise à aucune restriction.
Remerciements
Nous tenons à remercier Don Coppersmith, Burt Kaliski, Ralph Merkle et Noam Nisan pour leurs nombreux commentaires et suggestions utiles.
Table des Matières
3. Description de l'algorithme MD4
3.1 Étape 1. Ajout des bits de bourrage
3.2 Étape 2. Ajouter la longueur
3.3 Étape 3. Initialiser la mémoire tampon MD
3.4 Étape 4. Traiter le message par blocs de 16 mots
Appendice A – Mise en œuvre de référence
Le présent document décrit l'algorithme de résumé de message MD4 [1]. L'algorithme prend en entrée un message de longueur arbitraire et produit en sortie une "empreinte" ou "résumé de message" de 128 bits de l'entrée. On fait l'hypothèse qu'il est impossible de calculer deux messages ayant le même résumé de message, ou de produire un message ayant un résumé de message cible pré-spécifié. L'algorithme MD4 est destiné aux applications de signature numérique, où un grand fichier doit être "compressé" de façon sûre avant d'être chiffré avec une clé privée (secrète) dans un système de chiffrement à clé publique tel que RSA.
L'algorithme MD4 est conçu pour être assez rapide sur des machines à 32 bits. De plus, il n'exige pas de gros tableaux de substitution ; l'algorithme peut être codé de façon assez compacte.
L'algorithme MD4 a été mis dans le domaine publique pour révision et possible adoption comme norme.
Le présent document remplace la RFC 1186 [2] d'octobre 1990. La principale différence est que la mise en œuvre de référence de MD4 dans l'appendice est plus portable.
Pour les applications fondées sur OSI, l'identifiant d'objet de MD4 est
md4 OBJECT IDENTIFIER ::= {iso(1) member-body(2) US(840) rsadsi(113549) digestAlgorithm(2) 4}
Dans le type X.509 AlgorithmIdentifier [3], les paramètres pour MD4 devraient avoir le type NULL.
Dans le présent document un "mot" est une quantité de 32 bits et un "octet" est une quantité de huit bits. Une séquence de bits peut être interprétée de façon naturelle comme une séquence d'octets, où chaque groupe consécutif de huit bits est interprété comme un octet avec le bit de plus fort poids (d'ordre le plus élevé) de chaque octet donné en premier. De même, une séquence d'octets peut être interprétée comme une séquence de mots de 32 bits, où chaque groupe consécutif de quatre octets est interprété comme un mot avec l'octet de moindre poids (d'ordre inférieur) donné en premier.
Soit x_i qui note "x indice i". Si l'indice est une expression, on l'entoure d'accolades, comme dans x_{i+1}. De même, on utilise ^ pour exprimer l'exposant (puissance), de sorte que x^i note x à la puissance i.
Soit le symbole "+" qui note l'addition de mots (c'est-à-dire, l'addition modulo 2^32). Soit X <<< s qui note la valeur de 32 bits obtenue par rotation circulaire (permutation) de X à gauche de s positions de bits. Soit not(X) qui note le complément de X au bit près, et soit X v Y qui note la composition au bit près OU de X et Y. Soit X xor Y qui note la composition par opérateur OU au bit près OUX de X et de Y, et soit XY qui note l'ajout au bit près ET de X et Y.
3. Description de l'algorithme MD4
On commence par supposer qu'on a un message de b bits en entrée, et que nous souhaitons trouver son résumé de message. Ici, b est un entier arbitraire non négatif ; b peut être zéro, il n'est pas nécessaire qu'il soit un multiple de huit, et il peut être de longueur arbitraire. On imagine que les bits du message sont écrits comme suit :
m_0 m_1 ... m_{b-1}
Les cinq étapes suivantes sont effectuées pour calculer le résumé de message du message.
3.1 Étape 1. Ajout des bits de bourrage
Le message est "bourré" (étendu) de telle sorte que sa longueur (en bits) soit congruente à 448, modulo 512. C'est à dire que le message est étendu de façon à ce qu'il soit à 64 bits près un multiple d'une longueur de 512 bits. Le bourrage est toujours effectué, même si la longueur du message est déjà congruente à 448, modulo 512.
Le bourrage est effectué comme suit : un seul bit "1" est ajouté au message, puis des bits "0" sont ajoutés de telle sorte que la longueur en bits du message bourré devienne congruente à 448, modulo 512. En tout, au moins un bit un et au plus 512 bits sont ajoutés.
3.2 Étape 2. Ajouter la longueur
Une représentation de b sur 54 bits (la longueur du message avant l'ajout des bits de bourrage) est ajoutée au résultat de l'étape précédente. Dans le cas peu vraisemblable où b serait supérieur à 2^64, seuls les 64 bits de moindre poids de b sont alors utilisés. (Ces bits sont ajoutés sous la forme de deux mots de 32 bits et l'ajout est fait avec le mot de moindre poids en premier, conformément aux conventions précédentes.)
À ce moment, le message résultant (après le bourrage avec des bits et avec b) a une longueur qui est un exact multiple de 512 bits. De façon équivalente, ce message a une longueur qui est un exact multiple de 16 (32 bits) mots. Soit M[0 ... N-1] qui note les mots du message résultant, où N est un multiple de 16.
3.3 Étape 3. Initialiser la mémoire tampon MD
Une mémoire tampon de quatre mots (A,B,C,D) est utilisée pour calculer le résumé de message. Ici, A, B, C, D sont chacun un registre de 32 bits. Ces registres sont initialisés aux valeurs suivantes en hexadécimal, octets de moindre poids d'abord) :
mot A : 01 23 45 67
mot B : 89 ab cd ef
mot C : fe dc ba 98
mot D : 76 54 32 10
3.4 Étape 4. Traiter le message par blocs de 16 mots
On définit d'abord trois fonctions auxiliaires qui prennent chacune en entrée trois mots de 32 bits et produisent en sortie un mot de 32 bits.
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XY v XZ v YZ
H(X,Y,Z) = X xor Y xor Z
Chaque position binaire F agit comme un conditionnel : si X alors Y ou autrement Z. (La fonction F pourrait être définie en utilisant + au lieu de v car XY et not(X)Z n'auront jamais de bits "1" dans la même position binaire.) Chaque position binaire G agit comme une fonction de majorité : si au moins deux parmi X, Y, Z sont mis à 1, alors G a un bit "1" dans cette position binaire, autrement G a un bit "0". Il est intéressant de noter que si les bits de X, Y et Z sont indépendants et non biaisés, chacun des bits de f(X,Y,Z) sera indépendant et non biaisé, et de même chaque bit de g(X,Y,Z) sera indépendant et non biaisé. La fonction H est la fonction OUX au bit près ou fonction de "parité" ; elle a des propriétés similaires à celles de F et G.
Faire ce qui suit :
*/ Traiter chaque bloc de 16 mots. */
Pour i = 0 à N/16-1 faire
/* Copier le bloc i dans X. */
Pour j = 0 à 15 faire
Régler X[j] à M[i*16+j].
fin /* de la boucle sur j */
/* Sauvegarder A comme AA, B comme BB, C comme CC, et D comme DD. */
AA = A
BB = B
CC = C
DD = D
/* Tour 1. */
/* Soit [abcd k s] qui note l'opération a = (a + F(b,c,d) + X[k]) <<< s. */
/* Effectuer les 16 opérations suivantes. */
[ABCD 0 3] [DABC 1 7] [CDAB 2 11] [BCDA 3 19]
[ABCD 4 3] [DABC 5 7] [CDAB 6 11] [BCDA 7 19]
[ABCD 8 3] [DABC 9 7] [CDAB 10 11] [BCDA 11 19]
[ABCD 12 3] [DABC 13 7] [CDAB 14 11] [BCDA 15 19]
/* Tour 2. */
/* Soit [abcd k s] qui note l'opération a = (a + G(b,c,d) + X[k] + 5A827999) <<< s. */
/* Faire les 16 opérations suivantes. */
[ABCD 0 3] [DABC 4 5] [CDAB 8 9] [BCDA 12 13]
[ABCD 1 3] [DABC 5 5] [CDAB 9 9] [BCDA 13 13]
[ABCD 2 3] [DABC 6 5] [CDAB 10 9] [BCDA 14 13]
[ABCD 3 3] [DABC 7 5] [CDAB 11 9] [BCDA 15 13]
/* Tour 3. */
/* Soit [abcd k s] qui note l'opération a = (a + H(b,c,d) + X[k] + 6ED9EBA1) <<< s. */
/* Faire les 16 opérations suivantes. */
[ABCD 0 3] [DABC 8 9] [CDAB 4 11] [BCDA 12 15]
[ABCD 2 3] [DABC 10 9] [CDAB 6 11] [BCDA 14 15]
[ABCD 1 3] [DABC 9 9] [CDAB 5 11] [BCDA 13 15]
[ABCD 3 3] [DABC 11 9] [CDAB 7 11] [BCDA 15 15]
/* Puis effectuer les additions suivantes. (C'est à dire, incrémenter chacun des quatre registres de la valeur qu'il avait avant le début de ce bloc.) */
A = A + AA
B = B + BB
C = C + CC
D = D + DD
fin /* de la boucle sur i */
Note. La valeur 5A..99 est une constante hexadécimale de 32 bits, écrite avec le chiffre de plus fort poids en premier. Cette constant représente la racine carrée de 2. La valeur de cette constante en octal est 013240474631.
La valeur 6E..A1 est une constante hexadécimale de 32 bits, écrite avec le chiffre de plus fort poids en premier. Cette constant représente la racine carrée de 3. La valeur en octal de cette constante est 015666365641.
Voir Knuth, The Art of Programming, Volume 2 (Seminumerical Algorithms), Second Edition (1981), Addison-Wesley. Table 2, page 660.
Le résumé de message produit en sortie est A, B, C, D. C'est à dire que nous commençons par l'octet de moindre poids de A, et terminons par l'octet de plus fort poids de D.
Cela achève la description de MD4. Une mise en œuvre de référence en C est données dans l'appendice.
L'algorithme de résumé de message MD4 est simple à mettre en œuvre, et fournit une "empreinte" ou résumé de message d'un message de longueur arbitraire. On fait l'hypothèse que la difficulté d'arriver à deux messages ayant le même résumé de message est de l'ordre de 2^64 opérations, et que la difficulté d'arriver à tout message an ayant un résumé de message donné est de l'ordre de 2^128 opérations. L'algorithme MD4 a été analysé avec soin à la recherche de faiblesses. Il est, cependant, un algorithme relativement nouveau et des analyses de sécurité complémentaires sont bien sûr justifiées, comme c'est le cas avec toute nouvelle proposition de cette sorte.
[1] Rivest, R., "The MD4 message digest algorithm", in A.J. Menezes and S.A. Vanstone, editors, Advances in Cryptology - CRYPTO '90 Proceedings, pages 303-311, Springer-Verlag, 1991.
[2] R. Rivest, "Algorithme de résumé de message MD4", RFC 1186, MIT, octobre 1990.
[3] Recommandation UIT-T X.509 (1988), "L'annuaire – cadre d'authentification".
[4] R. Rivest, "Algorithme de résumé de message MD5", RFC 1321, MIT et RSA Data Security, Inc, avril 1992.
Appendice A – Mise en œuvre de référence
Cet appendice contient les fichiers suivants :
global.h – fichier d'en-tête global
md4.h – fichier d'en-tête pour MD4
md4c.c -- code source pour MD4
mddriver.c – pilote d'essais pour MD2, MD4 et MD5
Le pilote compile pour MD5 par défaut mais peut compiler pour MD2 ou MD4 si le symbole MD est défini sur la ligne de commande de compilateur C comme 2 ou 4.
La mise en œuvre est portable et devrait fonctionner sur de nombreuses plates-formes différentes. Cependant, il n'est pas difficile d'optimiser la mise en œuvre sur des plates-formes particulières, un exercice laissé à la discrétion du lecteur. Par exemple, sur les plates-formes "petit boutiennes" où le dernier octet traité dans un mot de 32 bits est celui de moindre poids et où il n'y a pas de restrictions d'alignement, l'invocation de Decode dans MD4Transform peut être remplacée par un typecast.
/* GLOBAL.H - types et constantes RSAREF */
/* PROTOTYPES devrait être réglé à un si et seulement si le compilateur prend en charge le prototypage d'argument de fonction. Ce qui suit fait que PROTOTYPES revient par défaut à 0 si il n'a pas été déjà défini avec des fanions de compilateur C. */
#ifndef PROTOTYPES
#define PROTOTYPES 0
#endif
/* POINTER définit un type de pointeur générique */
typedef unsigned char *POINTER;
/* UINT2 définit un mot de deux octets */
typedef unsigned short int UINT2;
/* UINT4 définit un mot de quatre octets */
typedef unsigned long int UINT4;
/* PROTO_LIST est défini selon la façon dont PROTOTYPES est défini auparavant. Si on utilisé PROTOTYPES, PROTO_LIST retourne alors la liste, autrement, il retourne une liste vide. */
#if PROTOTYPES
#define PROTO_LIST(list) list
#else
#define PROTO_LIST(list) ()
#endif
/* MD4.H – fichier d'en-tête pour MD4C.C */
/* Copyright (C) 1991-2, RSA Data Security, Inc. Créée en 1991. Tous droits réservés.
Licence de copier et utiliser le présent logiciel est accordé à condition qu'il soit identifié comme "algorithme de résumé de message MD4 de RSA Data Security, Inc." dans tout matériel mentionnant ou faisant référence à ce logiciel ou à sa fonction.
Licence est aussi accordée de faire et utiliser des travaux dérivés pourvu que de tels travaux soient identifiés comme "dérivés de l'algorithme de résumé de message MD4 de RSA Data Security, Inc." dans tout matériel mentionnant ou faisant référence à ces travaux dérivés.
RSA Data Security, Inc. ne donne aucune garantie concernant la possibilité de commercialiser ce logiciel ni son adéquation à aucun objet particulier. Il est fourni "en l'état" sans garantie expresse ou implicite d'aucune sorte.
Ces notices doivent être conservées dans toutes les copies de toute partie de cette documentation et/ou logiciel. */
/* contexte MD4. */
typedef struct {
UINT4 state[4]; /* état (ABCD) */
UINT4 count[2]; /* nombre de bits, modulo 2^64 (lsb en premier) */
unsigned char buffer[64]; /* mémoire tampon d'entrée */
} MD4_CTX;
void MD4Init PROTO_LIST ((MD4_CTX *));
void MD4Update PROTO_LIST
((MD4_CTX *, unsigned char *, unsigned int));
void MD4Final PROTO_LIST ((unsigned char [16], MD4_CTX *));
/* MD4C.C - algorithme de résumé de message MD4 de RSA Data Security, Inc. */
/* Copyright (C) 1990-2, RSA Data Security, Inc. Tous droits réservés.
Licence de copier et utiliser le présent logiciel est accordé à condition qu'il soit identifié comme "algorithme de résumé de message MD4 de RSA Data Security, Inc." dans tout matériel mentionnant ou faisant référence à ce logiciel ou à sa fonction.
Licence est aussi accordée de faire et utiliser des travaux dérivés pourvu que de tels travaux soient identifiés comme "dérivés de l'algorithme de résumé de message MD4 de RSA Data Security, Inc." dans tout matériel mentionnant ou faisant référence à ces travaux dérivés.
RSA Data Security, Inc. ne donne aucune garantie concernant la possibilité de commercialiser ce logiciel ni son adéquation à aucun objet particulier. Il est fourni "en l'état" sans garantie expresse ou implicite d'aucune sorte.
Ces notices doivent être conservées dans toutes les copies de toute partie de cette documentation et/ou logiciel. */
#include "global.h"
#include "md4.h"
/* Constantes pour le sous-programme MD4Transform. */
#define S11 3
#define S12 7
#define S13 11
#define S14 19
#define S21 3
#define S22 5
#define S23 9
#define S24 13
#define S31 3
#define S32 9
#define S33 11
#define S34 15
static void MD4Transform PROTO_LIST ((UINT4 [4], unsigned char [64]));
static void Encode PROTO_LIST ((unsigned char *, UINT4 *, unsigned int));
static void Decode PROTO_LIST ((UINT4 *, unsigned char *, unsigned int));
static void MD4_memcpy PROTO_LIST ((POINTER, POINTER, unsigned int));
static void MD4_memset PROTO_LIST ((POINTER, int, unsigned int));
static unsigned char PADDING[64] = { 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
/* F, G et H sont des fonctions MD4 de base. */
#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
#define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
#define H(x, y, z) ((x) ^ (y) ^ (z))
/* ROTATE_LEFT fait une rotation de x bits de n sur la gauche. */
#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
/* FF, GG et HH sont les transformations pour les tours 1, 2 et 3 */
/* La rotation est séparée de l'addition pour empêcher le recalcul. */
#define FF(a, b, c, d, x, s) { \
(a) += F ((b), (c), (d)) + (x); \
(a) = ROTATE_LEFT ((a), (s)); \
}
#define GG(a, b, c, d, x, s) { \
(a) += G ((b), (c), (d)) + (x) + (UINT4)0x5a827999; \
(a) = ROTATE_LEFT ((a), (s)); \
}
#define HH(a, b, c, d, x, s) { \
(a) += H ((b), (c), (d)) + (x) + (UINT4)0x6ed9eba1; \
(a) = ROTATE_LEFT ((a), (s)); \
}
/* Initialisation de MD4. Commence une opération MD4, en écrivant un nouveau contexte. */
void MD4Init (context)
MD4_CTX *context; /* contexte */
{
context->count[0] = context->count[1] = 0;
/* Charge les constantes magiques d'initialisation. */
context->state[0] = 0x67452301;
context->state[1] = 0xefcdab89;
context->state[2] = 0x98badcfe;
context->state[3] = 0x10325476;
}
/* Opération de mise à jour de bloc MD4. Continue une opération de résumé de message MD4, traite un autre bloc de message, et met à jour le contexte. */
void MD4Update (context, input, inputLen)
MD4_CTX *context; /* contexte */
unsigned char *input; /* bloc d'entrée */
unsigned int inputLen; /* longueur du bloc d'entrée */
{
unsigned int i, index, partLen;
/* Calcule le nombre d'octets modulo 64 */
index = (unsigned int)((context->count[0] >> 3) & 0x3F);
/* Met à jour le nombre de bits */
if ((context->count[0] += ((UINT4)inputLen << 3)) < ((UINT4)inputLen << 3)) context->count[1]++;
context->count[1] += ((UINT4)inputLen >> 29);
partLen = 64 - index;
/* Transforme autant de fois que possible. */
if (inputLen >= partLen) {
MD4_memcpy ((POINTER)&context->buffer[index], (POINTER)input, partLen);
MD4Transform (context->state, context->buffer);
for (i = partLen; i + 63 < inputLen; i += 64) MD4Transform (context->state, &input[i]);
index = 0;
else
i = 0;
/* Mettre en mémoire tampon le reste de l'entrée. */
MD4_memcpy
((POINTER)&context->buffer[index], (POINTER)&input[i], inputLen-i);
}
/* Finalisation de MD4. Termine une opération de résumé de message MD4 en écrivant le résumé de message et en mettant le contexte à zéro. */
void MD4Final (digest, context)
unsigned char digest[16]; /* résumé de message. */
MD4_CTX *context; /* contexte */
{
unsigned char bits[8];
unsigned int index, padLen;
/* Sauvegarder le nombre de bits */
Encode (bits, context->count, 8);
/* Bourrer à 56 modulo 64. */
index = (unsigned int)((context->count[0] >> 3) & 0x3f);
padLen = (index < 56) ? (56 - index) : (120 - index);
MD4Update (context, PADDING, padLen);
/* Ajouter la longueur (avant bourrage) */
MD4Update (context, bits, 8);
/* Mémoriser l'état dans le résumé. */
Encode (digest, context->state, 16);
/* Mettre à zéro les informations sensibles. */
MD4_memset ((POINTER)context, 0, sizeof (*context));
}
/* Transformation de base MD4. Transforme l'état sur la base du bloc. */
static void MD4Transform (state, block)
UINT4 state[4];
unsigned char block[64];
{
UINT4 a = state[0], b = state[1], c = state[2], d = state[3], x[16];
Decode (x, block, 64);
/* Tour 1 */
FF (a, b, c, d, x[ 0], S11); /* 1 */
FF (d, a, b, c, x[ 1], S12); /* 2 */
FF (c, d, a, b, x[ 2], S13); /* 3 */
FF (b, c, d, a, x[ 3], S14); /* 4 */
FF (a, b, c, d, x[ 4], S11); /* 5 */
FF (d, a, b, c, x[ 5], S12); /* 6 */
FF (c, d, a, b, x[ 6], S13); /* 7 */
FF (b, c, d, a, x[ 7], S14); /* 8 */
FF (a, b, c, d, x[ 8], S11); /* 9 */
FF (d, a, b, c, x[ 9], S12); /* 10 */
FF (c, d, a, b, x[10], S13); /* 11 */
FF (b, c, d, a, x[11], S14); /* 12 */
FF (a, b, c, d, x[12], S11); /* 13 */
FF (d, a, b, c, x[13], S12); /* 14 */
FF (c, d, a, b, x[14], S13); /* 15 */
FF (b, c, d, a, x[15], S14); /* 16 */
/* Tour 2 */
GG (a, b, c, d, x[ 0], S21); /* 17 */
GG (d, a, b, c, x[ 4], S22); /* 18 */
GG (c, d, a, b, x[ 8], S23); /* 19 */
GG (b, c, d, a, x[12], S24); /* 20 */
GG (a, b, c, d, x[ 1], S21); /* 21 */
GG (d, a, b, c, x[ 5], S22); /* 22 */
GG (c, d, a, b, x[ 9], S23); /* 23 */
GG (b, c, d, a, x[13], S24); /* 24 */
GG (a, b, c, d, x[ 2], S21); /* 25 */
GG (d, a, b, c, x[ 6], S22); /* 26 */
GG (c, d, a, b, x[10], S23); /* 27 */
GG (b, c, d, a, x[14], S24); /* 28 */
GG (a, b, c, d, x[ 3], S21); /* 29 */
GG (d, a, b, c, x[ 7], S22); /* 30 */
GG (c, d, a, b, x[11], S23); /* 31 */
GG (b, c, d, a, x[15], S24); /* 32 */
/* Tour 3 */
HH (a, b, c, d, x[ 0], S31); /* 33 */
HH (d, a, b, c, x[ 8], S32); /* 34 */
HH (c, d, a, b, x[ 4], S33); /* 35 */
HH (b, c, d, a, x[12], S34); /* 36 */
HH (a, b, c, d, x[ 2], S31); /* 37 */
HH (d, a, b, c, x[10], S32); /* 38 */
HH (c, d, a, b, x[ 6], S33); /* 39 */
HH (b, c, d, a, x[14], S34); /* 40 */
HH (a, b, c, d, x[ 1], S31); /* 41 */
HH (d, a, b, c, x[ 9], S32); /* 42 */
HH (c, d, a, b, x[ 5], S33); /* 43 */
HH (b, c, d, a, x[13], S34); /* 44 */
HH (a, b, c, d, x[ 3], S31); /* 45 */
HH (d, a, b, c, x[11], S32); /* 46 */
HH (c, d, a, b, x[ 7], S33); /* 47 */
HH (b, c, d, a, x[15], S34); /* 48 */
state[0] += a;
state[1] += b;
state[2] += c;
state[3] += d;
/* Mettre à zéro les informations sensibles. */
MD4_memset ((POINTER)x, 0, sizeof (x));
}
/* Coder l'entrée (UINT4) en sortie (unsigned char). On suppose que la longueur est un multiple de 4. */
static void Encode (output, input, len)
unsigned char *output;
UINT4 *input;
unsigned int len;
{
unsigned int i, j;
for (i = 0, j = 0; j < len; i++, j += 4) {
output[j] = (unsigned char)(input[i] & 0xff);
output[j+1] = (unsigned char)((input[i] >> 8) & 0xff);
output[j+2] = (unsigned char)((input[i] >> 16) & 0xff);
output[j+3] = (unsigned char)((input[i] >> 24) & 0xff);
}
}
/* Décoder le résultat (unsigned char) et sortie (UINT4). On suppose que la longueur est un multiple de 4. */
static void Decode (output, input, len)
UINT4 *output;
unsigned char *input;
unsigned int len;
{
unsigned int i, j;
for (i = 0, j = 0; j < len; i++, j += 4)
output[i] = ((UINT4)input[j]) | (((UINT4)input[j+1]) << 8) |
(((UINT4)input[j+2]) << 16) | (((UINT4)input[j+3]) << 24);
}
/* Note : Remplacer "for loop" par le memcpy standard si possible. */
static void MD4_memcpy (output, input, len)
POINTER output;
POINTER input;
unsigned int len;
{
unsigned int i;
for (i = 0; i < len; i++)
output[i] = input[i];
}
/* Note : Remplacer "for loop" par le memset standard si possible. */
static void MD4_memset (output, value, len)
POINTER output;
int value;
unsigned int len;
{
unsigned int i;
for (i = 0; i < len; i++)
((char *)output)[i] = (char)value;
}
/* MDDRIVER.C – pilote d'essais pour MD2, MD4 et MD5 */
/* Copyright (C) 1990-2, RSA Data Security, Inc. Créée en 1990. Tous droits réservés.
RSA Data Security, Inc. n'assure aucune responsabilité quant à la possibilité de commercialiser le présent logiciel ou quant à l'adéquation du présent logiciel pou quelque objet particulier que ce soit. Il est fourni "en l'état" sans garanties expresses ou implicites d'aucune sorte.
Ces notices doivent être conservées dans toutes copies de tout ou partie de la présentes documentation et/ou logiciel. */
/* Ce qui suit fait revenir MD par défaut à MD5 si il n'a pas été déjà défini avec des fanions de compilateur C. */
#ifndef MD
#define MD MD5
#endif
#include <stdio.h>
#include <time.h>
#include <string.h>
#include "global.h"
#if MD == 2
#include "md2.h"
#endif
#if MD == 4
#include "md4.h"
#endif
#if MD == 5
#include "md5.h"
#endif
/* Longueur du bloc d'essais, nombre des blocs d'essai. */
#define TEST_BLOCK_LEN 1000
#define TEST_BLOCK_COUNT 1000
static void MDString PROTO_LIST ((char *));
static void MDTimeTrial PROTO_LIST ((void));
static void MDTestSuite PROTO_LIST ((void));
static void MDFile PROTO_LIST ((char *));
static void MDFilter PROTO_LIST ((void));
static void MDPrint PROTO_LIST ((unsigned char [16]));
#if MD == 2
#define MD_CTX MD2_CTX
#define MDInit MD2Init
#define MDUpdate MD2Update
#define MDFinal MD2Final
#endif
#if MD == 4
#define MD_CTX MD4_CTX
#define MDInit MD4Init
#define MDUpdate MD4Update
#define MDFinal MD4Final
#endif
#if MD == 5
#define MD_CTX MD5_CTX
#define MDInit MD5Init
#define MDUpdate MD5Update
#define MDFinal MD5Final
#endif
/* Pilote principal.
Arguments (peut être n'importe quelle combinaison):
-sstring - chaîne de résumé
-t - lance l'essai de temps
-x - lance le script d'essai
filename - fichier des résumés
(none) - entrée standard de résumé */
int main (argc, argv)
int argc;
char *argv[];
{
int i;
if (argc > 1)
for (i = 1; i < argc; i++)
if (argv[i][0] == '-' && argv[i][1] == 's')
MDString (argv[i] + 2);
else if (strcmp (argv[i], "-t") == 0)
MDTimeTrial ();
else if (strcmp (argv[i], "-x") == 0)
MDTestSuite ();
else
MDFile (argv[i]);
else
MDFilter ();
return (0);
}
/* Résume une chaîne et imprime le résultat. */
static void MDString (string)
char *string;
{
MD_CTX context;
unsigned char digest[16];
unsigned int len = strlen (string);
MDInit (&context);
MDUpdate (&context, string, len);
MDFinal (digest, &context);
printf ("MD%d (\"%s\") = ", MD, string);
MDPrint (digest);
printf ("\n");
}
/* Mesure le temps pour résumer les blocs TEST_BLOCK_COUNT TEST_BLOCK_LEN-byte. */
static void MDTimeTrial ()
{
MD_CTX context;
time_t endTime, startTime;
unsigned char block[TEST_BLOCK_LEN], digest[16];
unsigned int i;
printf
("MD%d time trial. Digesting %d %d-byte blocks ...", MD, TEST_BLOCK_LEN, TEST_BLOCK_COUNT);
/* Initialiser le bloc */
for (i = 0; i < TEST_BLOCK_LEN; i++)
block[i] = (unsigned char)(i & 0xff);
/* Lancer le temporisateur */
time (&startTime);
/* Résumer les blocs */
MDInit (&context);
for (i = 0; i < TEST_BLOCK_COUNT; i++)
MDUpdate (&context, block, TEST_BLOCK_LEN);
MDFinal (digest, &context);
/* Arrêter le temporisateur */
time (&endTime);
printf (" done\n");
printf ("Digest = ");
MDPrint (digest);
printf ("\nTime = %ld seconds\n", (long)(endTime-startTime));
printf ("Speed = %ld bytes/second\n", (long)TEST_BLOCK_LEN * (long)TEST_BLOCK_COUNT/(endTime-startTime));
}
/* Résume une suite de chaînes de référence et imprime le résultat. */
static void MDTestSuite ()
{
rintf ("MD%d test suite:\n", MD);
MDString ("");
MDString ("a");
MDString ("abc");
MDString ("message digest");
MDString ("abcdefghijklmnopqrstuvwxyz");
MDString ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789");
MDString ("1234567890123456789012345678901234567890\1234567890123456789012345678901234567890");
}
/* Résume un fichier et imprime le résultat. */
static void MDFile (filename)
char *filename;
{
FILE *file;
MD_CTX context;
int len;
unsigned char buffer[1024], digest[16];
if ((file = fopen (filename, "rb")) == NULL) printf ("%s can't be opened\n", filename);
else {
MDInit (&context);
while (len = fread (buffer, 1, 1024, file)) MDUpdate (&context, buffer, len);
MDFinal (digest, &context);
fclose (file);
printf ("MD%d (%s) = ", MD, filename);
MDPrint (digest);
printf ("\n");
}
}
/* Résume d'entrée standard et imprime le résultat. */
static void MDFilter ()
{
MD_CTX context;
int len;
unsigned char buffer[16], digest[16];
MDInit (&context);
while (len = fread (buffer, 1, 16, stdin)) MDUpdate (&context, buffer, len);
MDFinal (digest, &context);
MDPrint (digest);
printf ("\n");
}
/* Imprime un résumé de message en hexadécimal. */
static void MDPrint (digest)
unsigned char digest[16];
{
unsigned int i;
for (i = 0; i < 16; i++)
printf ("%02x", digest[i]);
}
La suite d'essais MD4 (option de pilote "-x") devrait imprimer les résultats suivants :
MD4 test suite:
MD4 ("") = 31d6cfe0d16ae931b73c59d7e0c089c0
MD4 ("a") = bde52cb31de33e46245e05fbdbd6fb24
MD4 ("abc") = a448017aaf21d8525fc10ae87aa6729d
MD4 ("message digest") = d9130a8164549fe818874806e1c7014b
MD4 ("abcdefghijklmnopqrstuvwxyz") = d79e1c308aa5bbcdeea8ed63df412da9
MD4 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = 043f8582f241db351ce627e153e7f0e4
MD4 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = e33b4ddc9c38f2199c3e7b164fcc0536
Considérations pour la sécurité
Le niveau de sécurité discuté dans le présent mémoire est considéré comme suffisant pour mettre en œuvre des schémas de signature numérique hybrides de sécurité modérée sur la base de MD4 ete d'un système de chiffrement à clé publique. On ne voit aucune raisons pour que MD4 ne soit pas suffisant pour mettre en œuvre des schémas de signature numérique à très haute sécurité, mais comme MD4 a été conçu comme étant exceptionnellement rapide, il est "sur le fil" en termes de risque d'attaque cryptanalyque réussie. Après une révision critique plus approfondie, il pourrait être approprié de considérer MD4 pour des applications de très haute sécurité. Pour les applications de très haute sécurité, en attendant l'achèvement de cette révision, l'algorithme MD5 [4] est recommandé.
Ronald L. Rivest
Massachusetts Institute of Technology
Laboratory for Computer Science
NE43-324
545 Technology Square
Cambridge, MA 02139-1986
téléphone : (617) 253-5880
mél : rivest@theory.lcs.mit.edu