Network Working Group B. Kaliski Request for Comments: 1319 RSA Laboratories Updates: RFC 1115 April 1992 MD2 メッセージダイジェストアルゴリズム このメモの位置付け このメモは、インターネット・コミュニティに対し情報を提供するものである。 インターネット標準を規定するものではない。このメモの配布は無制限である。 謝辞 MD2は、John LinnとRon Rivestにより準備された資料に基づく。その資料の 組み込みを許可していただいたことに大いに感謝する。 目次 1. 要約 1 2. 用語と記法 2 3. MD2 アルゴリズム 2 4. まとめ 4 参考文献 5 付録 A - 参考実装 5 セキュリティに関する考察 17 著者のアドレス 17 1. 要約 このドキュメントでは、MD2メッセージダイジェストアルゴリズムを記述する。 アルゴリズムは、任意の長さのメッセージを受け取り、128ビットの「指紋」、 すなわち入力の「メッセージダイジェスト」を出力する。同じメッセージダイ ジェストとなる2つのメッセージを作成すること、またはあらかじめ指定された メッセージダイジェストとなるメッセージを作成することは、計算上実行不可能 であると推測される。 MD2アルゴリズムは、電子署名アプリケーションでの使用 が意図されている。この場合、大きなサイズのファイルは、RSAなどの公開鍵暗号 方式における私有鍵で暗号化される前に、安全な方法で「圧縮」されなければ ならない。 非商用目的のInternet Privacy Enhanced Mail [1-3] においては、MD2を使用 するためのライセンスが認められる。 このドキュメントは、MD2の参考実装を掲載している1989年8月の RFC 1115 [3] を置きかえるものである。主な違いは、MD2を文章により記述したことと、MD2の 参考実装がよりポータブルになったことである。 OSIベースのアプリケーションでは、MD2のオブジェクト識別子は次のようなもの である。 md2 OBJECT IDENTIFIER ::= iso(1) member-body(2) US(840) rsadsi(113549) digestAlgorithm(2) 2} X.509の AlgorithmIdentifier型 [4]では、MD2での parameters は、NULL型で あるべきである。 2. 用語と記法 このドキュメントでは、1「バイト」は8ビットである。 x_iは、"添え字i付きのx"を意味する。添え字が式であるときには、x_{i+1}の ように、それを括弧でくくる。同様に、^は上付き（指数）を表す。そのため、 x^iは、xのi乗を意味する。 X xor Yは、ビットに関するXとYのXORを意味する。 3. MD2 アルゴリズム まず、入力としてbビットのメッセージがあり、そのメッセージダイジェストを 見つけることを考える。ここで、bは任意の非負の整数である。bはゼロになって もよく、任意の大きさをもつ。メッセージにおけるそれぞれのビットを、次の ように示す。 m_0 m_1 ... m_{b-1} 以下の5つのステップが、メッセージのメッセージダイジェストを計算するため に実行される。 3.1 ステップ 1. パディングバイトの付加 メッセージは「パディングされ」(拡張され)て、その長さ(バイト)は16を法とし たときの0とされる。すなわち、メッセージは拡張されることにより、16バイト の整数倍にされる。このパディングは常に実行される。メッセージの長さが、 既に16を法としたときの0に一致していても実行される。 パディングは次のように実行される。”i”の値を持つiバイトをメッセージに 付加し、パディングされたメッセージのバイト長が、16を法としたときの0にな るようにする。最小で1バイト、最大で16バイトが付加される。 ここで、(バイトをパディングした後に)結果的に生成されるメッセージは、16 バイトの倍数の長さとなる。ここで、M[0 ... N-1]は、結果として生成される メッセージのバイトを表すものとする。Nは16の倍数である。 3.2 Step 2. チェックサムの適用 メッセージの16バイトのチェックサムが、前ステップの結果に付加される。 このステップでは、PIの値の数列から構成された、256バイトの”ランダムな” 順列を使用する。ここで S[i]は、このテーブルのi番目の要素を表す。テーブル は付録で与えられている。 そして以下を実行する。 /* チェックサムのクリア */ For i = 0 to 15 do: Set C[i] to 0. end /* i のループの終了 */ Set L to 0. /* それぞれの16ワードブロックを処理する */ For i = 0 to N/16-1 do /* ブロックiのチェックサム */ For j = 0 to 15 do Set c to M[i*16+j]. Set C[j] to S[c xor L]. Set L to C[j]. end /* j のループの終了 */ end /* i のループの終了 */ 16バイトのチェックサム C[0 ... 15] は、メッセージに付加される。 3.3 ステップ 3. MDバッファの初期化 48バイトのバッファXが、メッセージダイジェストを計算するのに使用される。 バッファはゼロに初期化される。 3.4 ステップ 4. 16ワードブロックごとのメッセージ処理 このステップでは、ステップ2で使用したのと同じ256バイトの順列Sを使用 する。 そして以下を実行する。 /* それぞれの16ワードブロックを処理する */ For i = 0 to N'/16-1 do /* ブロックiをXにコピーする */ For j = 0 to 15 do Set X[16+j] to M[i*16+j]. Set X[32+j] to (X[16+j] xor X[j]). end /* j のループの終了 */ Set t to 0. /* 18回のラウンド実行 */ For j = 0 to 17 do /* Round j */ For k = 0 to 47 do Set t and X[k] to (X[k] xor S[t]). end /* k のループの終了 */ Set t to (t+j) modulo 256. end /* j のループの終了 */ end /* i のループの終了 */ 3.5 ステップ 5. 出力 出力として生成されるメッセージダイジェストは X[0 ... 15] である。すなわ ち、X[0]から始まり、X[15]で終わる。 これでMD2の表記を終了する。C言語を使用した参考実装が付録に記されている。 4. まとめ MD2メッセージダイジェストアルゴリズムは、実装するのが簡単であり、任意の 長さを持つメッセージに対する「指紋」、すなわちメッセージダイジェストを 提供する。同じメッセージダイジェストを持つ2つのメッセージを作成することが 困難であるのは、2^64オーダーの演算のためであり、またあらかじめ指定された メッセージダイジェストを持つメッセージを作成することが困難なのは、2^128 オーダーの演算のためであると推測される。MD2アルゴリズムは、その弱点が慎重 に精査されている。しかしながら、この種類の新しい提案が常にそうであるように、 比較的新しいアルゴリズムと一層のセキュリティ分析により、このアルゴリズム の正当性が評価される。 参考文献 [1] Linn, J., "Privacy Enhancement for Internet Electronic Mail: Part I -- Message Encipherment and Authentication Procedures", RFC 1113, DEC, IAB Privacy Task Force, August 1989. [2] Kent, S., and J. Linn, "Privacy Enhancement for Internet Electronic Mail: Part II -- Certificate-Based Key Management", RFC 1114, BBNCC, DEC, IAB Privacy Task Force, August 1989. [3] Linn, J., "Privacy Enhancement for Internet Electronic Mail: Part III -- Algorithms, Modes, and Identifiers", RFC 1115 DEC, IAB Privacy Task Force, August 1989. [4] CCITT Recommendation X.509 (1988), "The Directory - Authentication Framework". 付録 A - 参考実装 この付録には、RSAREFとA Cryptographic Toolkit for Privacy-Enhanced Mail から引用された以下のファイルが含まれている。 global.h -- グローバルヘッダファイル md2.h -- MD2のヘッダファイル md2c.c -- MD2のソースコード RSAREFに関する詳細については、へメールのこと。 付録ではまた、以下のファイルが含まれている。 mddriver.c -- MD2、MD4、MD5用テストドライバ ドライバは、デフォルトでMD5のコンパイルを行うが、シンボルMDをCコンパイ ラコマンドライン上で2または4と定義すれば、MD2またはMD4のコンパイルを行う ことができる。 A.1 global.h /* GLOBAL.H - RSAREF types and constants */ /* PROTOTYPES should be set to one if and only if the compiler supports function argument prototyping. The following makes PROTOTYPES default to 0 if it has not already been defined with C compiler flags. */ #ifndef PROTOTYPES #define PROTOTYPES 0 #endif /* POINTER defines a generic pointer type */ typedef unsigned char *POINTER; /* UINT2 defines a two byte word */ typedef unsigned short int UINT2; /* UINT4 defines a four byte word */ typedef unsigned long int UINT4; /* PROTO_LIST is defined depending on how PROTOTYPES is defined above. If using PROTOTYPES, then PROTO_LIST returns the list, otherwise it returns an empty list. */ #if PROTOTYPES #define PROTO_LIST(list) list #else #define PROTO_LIST(list) () #endif A.2 md2.h /* MD2.H - header file for MD2C.C */ /* Copyright (C) 1990-2, RSA Data Security, Inc. Created 1990. All rights reserved. License to copy and use this software is granted for non-commercial Internet Privacy-Enhanced Mail provided that it is identified as the "RSA Data Security, Inc. MD2 Message Digest Algorithm" in all material mentioning or referencing this software or this function. RSA Data Security, Inc. makes no representations concerning either the merchantability of this software or the suitability of this software for any particular purpose. It is provided "as is" without express or implied warranty of any kind. These notices must be retained in any copies of any part of this documentation and/or software. */ typedef struct { unsigned char state[16]; /* state */ unsigned char checksum[16]; /* checksum */ unsigned int count; /* number of bytes, modulo 16 */ unsigned char buffer[16]; /* input buffer */ } 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., MD2 message-digest algorithm */ /* Copyright (C) 1990-2, RSA Data Security, Inc. Created 1990. All rights reserved. License to copy and use this software is granted for non-commercial Internet Privacy-Enhanced Mail provided that it is identified as the "RSA Data Security, Inc. MD2 Message Digest Algorithm" in all material mentioning or referencing this software or this function. RSA Data Security, Inc. makes no representations concerning either the merchantability of this software or the suitability of this software for any particular purpose. It is provided "as is" without express or implied warranty of any kind. These notices must be retained in any copies of any part of this documentation and/or software. */ #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 of 0..255 constructed from the digits of pi. It gives a "random" nonlinear byte substitution operation. */ static unsigned char PI_SUBST[256] = { 41, 46, 67, 201, 162, 216, 124, 1, 61, 54, 84, 161, 236, 240, 6, 19, 98, 167, 5, 243, 192, 199, 115, 140, 152, 147, 43, 217, 188, 76, 130, 202, 30, 155, 87, 60, 253, 212, 224, 22, 103, 66, 111, 24, 138, 23, 229, 18, 190, 78, 196, 214, 218, 158, 222, 73, 160, 251, 245, 142, 187, 47, 238, 122, 169, 104, 121, 145, 21, 178, 7, 63, 148, 194, 16, 137, 11, 34, 95, 33, 128, 127, 93, 154, 90, 144, 50, 39, 53, 62, 204, 231, 191, 247, 151, 3, 255, 25, 48, 179, 72, 165, 181, 209, 215, 94, 146, 42, 172, 86, 170, 198, 79, 184, 56, 210, 150, 164, 125, 182, 118, 252, 107, 226, 156, 116, 4, 241, 69, 157, 112, 89, 100, 113, 135, 32, 134, 91, 207, 101, 230, 45, 168, 2, 27, 96, 37, 173, 174, 176, 185, 246, 28, 70, 97, 105, 52, 64, 126, 15, 85, 71, 163, 35, 221, 81, 175, 58, 195, 92, 249, 206, 186, 197, 234, 38, 44, 83, 13, 110, 133, 40, 132, 9, 211, 223, 205, 244, 65, 129, 77, 82, 106, 220, 55, 200, 108, 193, 171, 250, 36, 225, 123, 8, 12, 189, 177, 74, 120, 136, 149, 139, 227, 99, 232, 109, 233, 203, 213, 254, 59, 0, 29, 57, 242, 239, 183, 14, 102, 88, 208, 228, 166, 119, 114, 248, 235, 117, 75, 10, 49, 68, 80, 180, 143, 237, 31, 26, 219, 153, 141, 51, 159, 17, 131, 20 }; 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" }; /* MD2 initialization. Begins an MD2 operation, writing a new context. */ void MD2Init (context) MD2_CTX *context; /* context */ { context->count = 0; MD2_memset ((POINTER)context->state, 0, sizeof (context->state)); MD2_memset ((POINTER)context->checksum, 0, sizeof (context->checksum)); } /* MD2 block update operation. Continues an MD2 message-digest operation, processing another message block, and updating the context. */ void MD2Update (context, input, inputLen) MD2_CTX *context; /* context */ unsigned char *input; /* input block */ unsigned int inputLen; /* length of input block */ { unsigned int i, index, partLen; /* Update number of bytes mod 16 */ index = context->count; context->count = (index + inputLen) & 0xf; partLen = 16 - index; /* Transform as many times as 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; /* Buffer remaining input */ MD2_memcpy ((POINTER)&context->buffer[index], (POINTER)&input[i], inputLen-i); } /* MD2 finalization. Ends an MD2 message-digest operation, writing the message digest and zeroizing the context. */ void MD2Final (digest, context) unsigned char digest[16]; /* message digest */ MD2_CTX *context; /* context */ { unsigned int index, padLen; /* Pad out to multiple of 16. */ index = context->count; padLen = 16 - index; MD2Update (context, PADDING[padLen], padLen); /* Extend with checksum */ MD2Update (context, context->checksum, 16); /* Store state in digest */ MD2_memcpy ((POINTER)digest, (POINTER)context->state, 16); /* Zeroize sensitive information. */ MD2_memset ((POINTER)context, 0, sizeof (*context)); } /* MD2 basic transformation. Transforms state and updates checksum based on block. */ 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]; /* Form encryption block from state, block, state ^ block. */ 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]; /* Encrypt block (18 rounds). */ t = 0; for (i = 0; i < 18; i++) { for (j = 0; j < 48; j++) t = x[j] ^= PI_SUBST[t]; t = (t + i) & 0xff; } /* Save new state */ MD2_memcpy ((POINTER)state, (POINTER)x, 16); /* Update checksum. */ t = checksum[15]; for (i = 0; i < 16; i++) t = checksum[i] ^= PI_SUBST[block[i] ^ t]; /* Zeroize sensitive information. */ MD2_memset ((POINTER)x, 0, sizeof (x)); } /* Note: Replace "for loop" with standard memcpy if 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: Replace "for loop" with standard memset if 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 - test driver for MD2, MD4 and MD5 */ /* Copyright (C) 1990-2, RSA Data Security, Inc. Created 1990. All rights reserved. RSA Data Security, Inc. makes no representations concerning either the merchantability of this software or the suitability of this software for any particular purpose. It is provided "as is" without express or implied warranty of any kind. These notices must be retained in any copies of any part of this documentation and/or software. */ /* The following makes MD default to MD5 if it has not already been defined with C compiler flags. */ #ifndef MD #define MD MD5 #endif #include #include #include #include "global.h" #if MD == 2 #include "md2.h" #endif #if MD == 4 #include "md4.h" #endif #if MD == 5 #include "md5.h" #endif /* Length of test block, number of test blocks. */ #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 /* Main driver. Arguments (may be any combination): -sstring - digests string -t - runs time trial -x - runs test script filename - digests file (none) - digests standard input */ 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); } /* Digests a string and prints the result. */ 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"); } /* Measures the time to digest TEST_BLOCK_COUNT TEST_BLOCK_LEN-byte blocks. */ 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); /* Initialize block */ 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)); } /* Digests a reference suite of strings and prints the results. */ 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"); } /* Digests a file and prints the result. */ 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"); } } /* Digests the standard input and prints the result. */ 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"); } /* Prints a message digest in hexadecimal. */ static void MDPrint (digest) unsigned char digest[16]; { unsigned int i; for (i = 0; i < 16; i++) printf ("%02x", digest[i]); } A.5 テストスイート MD2のテストスイート(ドライバオプション“-x")は、以下の結果を出力する はずである。 MD2 test suite: MD2 ("") = 8350e5a3e24c153df2275c9f80692773 MD2 ("a") = 32ec01ec4a6dac72c0ab96fb34c0b5d1 MD2 ("abc") = da853b0d3f88d99b30283a69e6ded6bb MD2 ("message digest") = ab4f496bfb2a530b219ff33031fe06b0 MD2 ("abcdefghijklmnopqrstuvwxyz") = 4e8ddff3650292ab5a4108c3aa47940b MD2 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = da33def2a42df13975352846c30338cd MD2 ("123456789012345678901234567890123456789012345678901234567890123456 78901234567890") = d5976f79d83d3a0dc9806c3c66f3efd8 セキュリティに関する考察 このメモで議論されているセキュリティのレベルは、MD2と公開鍵暗号方式に 基づく、非常に高いセキュリティをもつハイブリッド電子署名の実装に十分 であると考えられる。 著者のアドレス Burton S. Kaliski Jr. RSA Laboratories (a division of RSA Data Security, Inc.) 10 Twin Dolphin Drive Redwood City, CA 94065 Phone: (415) 595-8782 FAX: (415) 595-4126 EMail: burt@rsa.com 日本語訳 西原 啓輔 2001年5月 訳者は、訳出した文書を利用することにより発生したいかなる損害に対しても 責任を負いません。 本文書には、技術的あるいは翻訳上の誤りがある可能性があります。技術的に 正しい知識を獲得しなければならない場合は、InterNIC/IETFから発行されて いる原文を参照してください。