Algorithme MD2 de résumé de message

Statut de ce mémoire

Le présent mémoore fournit des informations pour la communauté de l'Internet. Il ne spécifie aucune norme de l'Internet. La distribution du présent mémoire n'est soumise à aucune restriction.

Remerciements

La description de MD2 se fonde sur des matériaux préparés par John Linn et Ron Rivest. Leur permission d'incorporer ces matériaux est grandement appréciée.

Table des matières

1.   Introduction

2.   Terminologie et notation

3.   Description de l'algorithme MD2

3.1   Étape 1. Ajout d'octets de bourrage

3.2   Étape 2. Ajout de la somme de contrôle

3.3   Étape 3. Initialiser la mémoire tampon MD

3.4   Étape 4. Traiter le message en blocs de 16 octets

3.5   Étape 5. Sortie

4.   Résumé

Appendice A – Mise en œuvre de référence

A.1   global.h

A.2   md2.h

A.3   md2c.c

A.4   mddriver.c

A.5   Suite d'essai

 

1.   Introduction

La licence d'utilisation de MD2 est accordée pour la messagerie Internet non commericale à confidentialité améliorée [1-3].

Le présent document est une mise à jour de la RFC 1115 [3] d'août 1989, qui donne aussi une mise en œuvre de référence de MD2. Les principales différences sont qu'une description textuelle de MD2 est incluse, et que la mise en œuvre de référence de MD2 est plus portable.

Pour les applications fondées sur OSI, l'identifiant d'objet de MD2 est md2 OBJECT IDENTIFIER ::= iso(1) member-body(2) US(840) rsadsi(113549) digestAlgorithm(2) 2}

Dans le type X.509 AlgorithmIdentifier [4], les paramètres pour MD2 devraient avoir le type NULL.

2.   Terminologie et notation

Dans le présent document, un "octet" est une quantité de huit bits.

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 noter l'exposant, de sorte que x^i note x à la puissance i.

Soit X xor Y qui note la composition par opérateur OUX au bit près de X et Y.

3.   Description de l'algorithme MD2

On commence par supposer qu'on a un message de b octets en entrée, et qu'on souhaite trouver son résumé de message. Ici, b est un entier non négatif arbitraire ; b peut être zéro, et il peut être d'une longueur arbitraire. On imagine que les octets 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 d'octets de bourrage

Le message est "bourré" (étendu) de telle sorte que sa longueur (en octets) soit congruente à 0, modulo 16. C'est-à-dire que le message est étendu de telle façon que sa longueur soit un multiple de 16 octets. Le bourrage est toujours effectué, même si la longueur du message est déjà congruente à 0, modulo 16.

À ce point, le message résultant (après bourrage avec des octets) a une longueur qui est un exact multiple de 16 octets. Soit M[0 ... N-1] qui note les octets du message résultant, où N est un multiple de 16.

3.2   Étape 2. Ajout de la somme de contrôle

Une somme de contrôle du message de 16 octets est ajoutée au résultat de l'étape précédente.

Cette étape utilise une permutation "aléatoire" de 256 octets construite à partir des chiffres de pi. Soit S[i] qui note le i ème élément de ce tableau. Le tableau est donné en appendice.

Faire ce qui suit :

/* Résoudre la somme de contrôle. */

Pour i = 0 à 15 faire :

Régler C[i] à 0.

fin /* de la boucle sur i */

Régler L à 0.

La somme de contrôle de 16 octets C[0 ... 15] est ajoutée au message. Soit M[0 (avec somme de contrôle), où N' = N + 16.

3.3   Étape 3. Initialiser la mémoire tampon MD

Une mémoire tampon de 48 octets X est utilisée pour calculer le résumé de message. La mémoire tampon est initialisée à zéro.

3.4   Étape 4. Traiter le message en blocs de 16 octets

Cette étape utilise la même permutation S à 256 octets que l'étape 2.

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[16+j] à M[i*16+j].

Régler X[32+j] à (X[16+j] xor X[j]).

fin /* de la boucle sur j */

Régler t à 0.

/* Faire 18 tours. */

Pour j = 0 à 17 faire

/* Tour j. */

Pour k = 0 à 47 faire

Régler t et X[k] à (X[k] xor S[t]).

fin /* de la boucle sur k */

Régler t à (t+j) modulo 256.

fin /* de la boucle sur j */

fin /* de la boucle sur i */

3.5   Étape 5. Sortie

Le résumé de message produit en sortie est X[0 ... 15]. C'est-à-dire que nous commençons avec X[0], et terminons avec X[15].

Cela termine la description de MD2. Une mise en œuvre de référence en C est donnée dans l'appendice.

4.   Résumé

Références

[1]   J. Linn, "Amélioration de la confidentialité pour la messagerie électronique : Partie 1 : Procédures de chiffrement de message et d'authentification", RFC1113, août 1989. (rendue obsolète par la RFC 1421)

[2]   S. Kent et J. Linn, "Amélioration de la confidentialité pour la messagerie électronique : Partie 2 : Gestion de clé à base de certificats", RFC1114, août 1989. (rendue obsolète par la RFC 1422)

[3]   J. Linn, "Amélioration de la confidentialité pour la messagerie électronique : Partie 3 : Algorithmes, modes et identifiants", RFC1115, août 1989. (rendue obsolète par la RFC 1423)

[4]   Recommandation UIT-T X.509 (1988), "L'annuaire – Cadre d'authentification".

APPENDICE A – Mise en œuvre de référence

Le présent appendice contient les fichiers suivants tirés de RSAREF : Trousse à outils cryptographiques pour une messagerie à confidentialité améliorée.

global.h – fichier d'en-tête global

md2.h – fichier d'en-tête pour MD2

md2c.c – code source pour MD2

Pour plus d'informations sur RSAREF, envoyer un message à <rsaref@rsa.com>.

L'appendice comporte aussi le fichier suivant :

mddriver.c – pilote d'essai 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 du compilateur C comme étant 2 ou 4.

A.1   global.h

/* GLOBAL.H - RSAREF types and constants */

/* PROTOTYPES devrait être réglé à un si et seulement si le compilateur prend en charge la constitution de prototypes d'argument de fonction. Ce qui suit fait revenir PROTOTYPES par défaut à 0 si il n'a pas été déjà défini avec les 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 en fonction de la façon dont PROTOTYPES est défini plus haut. Si on utilise PROTOTYPES, alors PROTO_LIST retourne la liste, autrement, il retourne une liste vide. */

#if PROTOTYPES

#define PROTO_LIST(list) list

#else

#define PROTO_LIST(list) ()

#endif

A.2   md2.h

/* MD2.H – fichier d'en-tête pour MD2C.C */

/* Copyright (C) 1990-2, RSA Data Security, Inc. Créée en 1990. Tous droits réservés.

Licence de copier et utiliser le présent logiciel est accordée pour la messagerie Internet non-commerciale à confidentialité améliorée à condition que soit identifié l'algorithme de résumé de message MD2 de RSA Data Security, Inc. dans tous les documents mentionnant ou faisant référence à ce logiciel ou à sa fonction.

RSA Data Security, Inc. n'offre aucune garantie de la possibilité de commercialiser le présent logiciel ni de l'adéquation du présent logiciel à aucun objet particulier. Il est fourni "en l'état" sans aucune garantie expresse ou implicite de quelque sorte que ce soit.

Ces remarques doivent être conservées dans toute copie d'une partie de la présente documentation et/ou logiciel. */

typedef struct {

unsigned char state[16]; /* état */

unsigned char checksum[16]; /* somme de contrôle */

unsigned int count; /* nombre d'octets, modulo 16 */

unsigned char buffer[16]; /* mémoire tampon d'entrée */

} MD2_CTX;

void MD2Init PROTO_LIST ((MD2_CTX *));

void MD2Update PROTO_LIST ((MD2_CTX *, unsigned char *, unsigned int));

void MD2Final PROTO_LIST ((unsigned char [16], MD2_CTX *));

A.3   md2c.c

/* MD2C.C - RSA Data Security, Inc., algorithme MD2 de résumé de message */

/* Copyright (C) 1990-2, RSA Data Security, Inc. Créée en 1990. Tous droits réservés.

Licence de copier et utiliser le présent logiciel est accordée pour la messagerie Internet non-commerciale à confidentialité améliorée à condition que soit identifié l'algorithme de résumé de message MD2 de RSA Data Security, Inc. dans tous les documents mentionnant ou faisant référence à ce logiciel ou à sa fonction.

RSA Data Security, Inc. n'offre aucune garantie de la possibilité de commercialiser le présent logiciel ni de l'adéquation du présent logiciel à aucun objet particulier. Il est fourni "en l'état" sans aucune garantie expresse ou implicite de quelque sorte que ce soit.

Ces remarques doivent être conservées dans toute copie d'une partie de la présente documentation et/ou logiciel. */

#include "global.h"

#include "md2.h"

static void MD2Transform PROTO_LIST

((unsigned char [16], unsigned char [16], unsigned char [16]));

static void MD2_memcpy PROTO_LIST ((POINTER, POINTER, unsigned int));

static void MD2_memset PROTO_LIST ((POINTER, int, unsigned int));

/* Permutation de 0..255 construite à partir des chiffres de pi. Cela donne une opération de substitution d'octets non linéaire "aléatoire". */

static unsigned char *PADDING[] = {

(unsigned char *)"",

(unsigned char *)"\001",

(unsigned char *)"\002\002",

(unsigned char *)"\003\003\003",

(unsigned char *)"\004\004\004\004",

(unsigned char *)"\005\005\005\005\005",

(unsigned char *)"\006\006\006\006\006\006",

(unsigned char *)"\007\007\007\007\007\007\007",

(unsigned char *)"\010\010\010\010\010\010\010\010",

(unsigned char *)"\011\011\011\011\011\011\011\011\011",

(unsigned char *)"\012\012\012\012\012\012\012\012\012\012",

(unsigned char *)"\013\013\013\013\013\013\013\013\013\013\013",

(unsigned char *)"\014\014\014\014\014\014\014\014\014\014\014\014",

(unsigned char *)"\015\015\015\015\015\015\015\015\015\015\015\015\015",

(unsigned char *)"\016\016\016\016\016\016\016\016\016\016\016\016\016\016",

(unsigned char *)"\017\017\017\017\017\017\017\017\017\017\017\017\017\017\017",

(unsigned char *)"\020\020\020\020\020\020\020\020\020\020\020\020\020\020\020\020"

};

/* Initialisation MD2. Commence une opération MD2, écrit un nouveau contexte. */

void MD2Init (context)

MD2_CTX *context; /* contexte */

{

context->count = 0;

MD2_memset ((POINTER)context->state, 0, sizeof (context->state));

MD2_memset

((POINTER)context->checksum, 0, sizeof (context->checksum));

}

/* Opération de mise à jour de bloc MD2. Continue une opération de résumé de message MD2, traite un autre bloc de message, et met à jour le contexte. */

void MD2Update (context, input, inputLen)

MD2_CTX *context; /* contexte */

unsigned char *input; /* bloc d'entrée */

unsigned int inputLen; /* longueur du bloc d'entrée */

{

unsigned int i, index, partLen;

/* Met à jour le nombre d'octets modulo 16. */

index = context->count;

context->count = (index + inputLen) & 0xf;

partLen = 16 - index;

/* Transforme autant de fois que possible. */

if (inputLen >= partLen) {

MD2_memcpy

((POINTER)&context->buffer[index], (POINTER)input, partLen);

MD2Transform (context->state, context->checksum, context->buffer);

for (i = partLen; i + 15 < inputLen; i += 16)

MD2Transform (context->state, context->checksum, &input[i]);

index = 0;

}

else

i = 0;

/* Met en mémoire tampon le reste de l'entrée. */

MD2_memcpy

((POINTER)&context->buffer[index], (POINTER)&input[i],

inputLen-i);

}

/* Finalisation MD2. Termine l'opération de résumé de message MD2, écrit le résumé de message et met à zéro le contexte.

*/

void MD2Final (digest, context)

unsigned char digest[16]; /* message digest */

MD2_CTX *context; /* context */

{

unsigned int index, padLen;

/* Bourre jusqu'à former un multiple de 16. */

index = context->count;

padLen = 16 - index;

MD2Update (context, PADDING[padLen], padLen);

/* Étend avec la somme de contrôle. */

MD2Update (context, context->checksum, 16);

/* Mémorise l'état dans le résumé. */

MD2_memcpy ((POINTER)digest, (POINTER)context->state, 16);

/* Met à zéro les informations sensibles. */

MD2_memset ((POINTER)context, 0, sizeof (*context));

}

/* Transformation MD2 de base. Transforme l'état et met à jour la somme de contrôle sur la base du bloc.*/

static void MD2Transform (state, checksum, block)

unsigned char state[16];

unsigned char checksum[16];

unsigned char block[16];

{

unsigned int i, j, t;

unsigned char x[48];

/* Forme le bloc de chiffrement à partir de l'état, bloc, bloc ^ état. */

MD2_memcpy ((POINTER)x, (POINTER)state, 16);

MD2_memcpy ((POINTER)x+16, (POINTER)block, 16);

for (i = 0; i < 16; i++)

x[i+32] = state[i] ^ block[i];

/* Chiffrement du bloc (18 tours). */

t = 0;

for (i = 0; i < 18; i++) {

for (j = 0; j < 48; j++)

t = x[j] ^= PI_SUBST[t];

t = (t + i) & 0xff;

}

/* Sauvegarde le nouvel état */

MD2_memcpy ((POINTER)state, (POINTER)x, 16);

/* Mise à jour de la somme de contrôle. */

t = checksum[15];

for (i = 0; i < 16; i++)

t = checksum[i] ^= PI_SUBST[block[i] ^ t];

/* Met à zéro les informations sensibles. */

MD2_memset ((POINTER)x, 0, sizeof (x));

}

/* Note: Remplacer "for loop" par standard memcpy si possible. */

static void MD2_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 standard memset si possible. */

static void MD2_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;

}

A.4   mddriver.c

/* MDDRIVER.C – pilote d'essai pour MD2, MD4 et MD5*/

/* Copyright (C) 1990-2, RSA Data Security, Inc. Créé en 1990. Tous droits réservés.

RSA Data Security, Inc. n'offre aucune garantie de la possibilité de commercialiser le présent logiciel ni de l'adéquation du présent logiciel à aucun objet particulier. Il est fourni "en l'état" sans aucune garantie expresse ou implicite de quelque sorte que ce soit.

Ces remarques doivent être conservées dans toute copie d'une partie de la présente documentation et/ou logiciel. */

/* Ce qui suit ramène par défaut MD à MD5 si il n'a pas déjà été 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'essai, nombre de 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 toute combinaison) :

   -sstring   - chaînes de résumés

   -t   - fait courir le temps d'essai

   -x   - fait courrir le script d'essai

   filename   - résum e le fichier

   (ancune)   - résume l'entrée standard */

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);

/* Initialise le bloc */

for (i = 0; i < TEST_BLOCK_LEN; i++)

block[i] = (unsigned char)(i & 0xff);

/* Start timer */

time (&startTime);

/* Digest blocks */

MDInit (&context);

for (i = 0; i < TEST_BLOCK_COUNT; i++)

MDUpdate (&context, block, TEST_BLOCK_LEN);

MDFinal (digest, &context);

/* Stop timer */

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 référence de chaînes et imprime les résultats. */

static void MDTestSuite ()

{

printf ("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 l'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]);

}

A.5   Suite d'essai

La suite d'essai MD2 (option de pilote "-x") devrait imprimer les résultats suivants :

MD2 test suite:

MD2 ("") = 8350e5a3e24c153df2275c9f80692773

MD2 ("a") = 32ec01ec4a6dac72c0ab96fb34c0b5d1

MD2 ("abc") = da853b0d3f88d99b30283a69e6ded6bb

MD2 ("message digest") = ab4f496bfb2a530b219ff33031fe06b0

MD2 ("abcdefghijklmnopqrstuvwxyz") = 4e8ddff3650292ab5a4108c3aa47940b

MD2 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = da33def2a42df13975352846c30338cd

MD2 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = d5976f79d83d3a0dc9806c3c66f3efd8

Considérations pour la sécurité

Le niveau de sécurité exposé dans le présent mémoire est considéré comme suffisant pour la mise en œuvre de schémas de signature numérique hybrides de très haute sécurité fondés sur MD2 et un système de chiffrement à clé publique.

Adresse de l'auteur

Burton S. Kaliski Jr.

RSA Laboratories (division de RSA Data Security, Inc.)

10 Twin Dolphin Drive

Redwood City, CA 94065

Téléphone : (415) 595-8782

Fax : (415) 595-4126

mél : burt@rsa.com