MD2

MD2
一般いっぱん
設計せっけい者しゃ	ロナルド・リベスト
初版しょはん発行はっこう日び	1989年ねん8月がつ
シリーズ	MD2, MD4, MD5, MD6
詳細しょうさい
ダイジェスト長ちょう	128 bits
ラウンド数すう	18

MD2（Message Digest Algorithm 2）とは、1989年ねんにロナルド・リベストが開発かいはつした暗号あんごう学がく的てきハッシュ関数かんすう^[1]^[2]。このアルゴリズムは8ビットコンピュータ向むけに最適さいてき化かされている。MD2 の仕様しようは RFC 1319 で示しめされている。MD2は既すでに安全あんぜんでないことが示しめされているが、 2014年ねん現在げんざいもRSA暗号あんごうと共ともに公開こうかい鍵かぎ証明しょうめい書しょを発行はっこうする公開こうかい鍵かぎ基盤きばんとして使つかわれ続つづけている。

概要がいよう

任意にんいのメッセージのハッシュ値ちが、コンピュータ上じょうのブロック長ちょう（128ビット/16バイト）の倍数ばいすうになるようパディングされ、16バイトのチェックサムを追加ついかした状態じょうたいで計算けいさんされる。実際じっさいの計算けいさんでは、48バイトの補助ほじょブロックと円周えんしゅう率りつの小数しょうすう部分ぶぶんの数列すうれつから間接かんせつ的てきに生成せいせいされた256バイトのSテーブルを使用しようする。そのアルゴリズムは、処理しょりされる16個この入力にゅうりょくバイトそれぞれについて、補助ほじょブロックの各かくバイトを18回かい並ならべ替かえるループを使用しようする。パディングされたメッセージの全ぜんブロックの処理しょりが終おわると、補助ほじょブロックの最初さいしょの不完全ふかんぜんブロックがそのメッセージのハッシュ値ちになる。

Sテーブルの値ねを16進数しんすうで表あらわすと次つぎのようになる。

0x29, 0x2E, 0x43, 0xC9, 0xA2, 0xD8, 0x7C, 0x01, 0x3D, 0x36, 0x54, 0xA1, 0xEC, 0xF0, 0x06, 0x13, 
0x62, 0xA7, 0x05, 0xF3, 0xC0, 0xC7, 0x73, 0x8C, 0x98, 0x93, 0x2B, 0xD9, 0xBC, 0x4C, 0x82, 0xCA, 
0x1E, 0x9B, 0x57, 0x3C, 0xFD, 0xD4, 0xE0, 0x16, 0x67, 0x42, 0x6F, 0x18, 0x8A, 0x17, 0xE5, 0x12, 
0xBE, 0x4E, 0xC4, 0xD6, 0xDA, 0x9E, 0xDE, 0x49, 0xA0, 0xFB, 0xF5, 0x8E, 0xBB, 0x2F, 0xEE, 0x7A, 
0xA9, 0x68, 0x79, 0x91, 0x15, 0xB2, 0x07, 0x3F, 0x94, 0xC2, 0x10, 0x89, 0x0B, 0x22, 0x5F, 0x21,
0x80, 0x7F, 0x5D, 0x9A, 0x5A, 0x90, 0x32, 0x27, 0x35, 0x3E, 0xCC, 0xE7, 0xBF, 0xF7, 0x97, 0x03, 
0xFF, 0x19, 0x30, 0xB3, 0x48, 0xA5, 0xB5, 0xD1, 0xD7, 0x5E, 0x92, 0x2A, 0xAC, 0x56, 0xAA, 0xC6, 
0x4F, 0xB8, 0x38, 0xD2, 0x96, 0xA4, 0x7D, 0xB6, 0x76, 0xFC, 0x6B, 0xE2, 0x9C, 0x74, 0x04, 0xF1, 
0x45, 0x9D, 0x70, 0x59, 0x64, 0x71, 0x87, 0x20, 0x86, 0x5B, 0xCF, 0x65, 0xE6, 0x2D, 0xA8, 0x02, 
0x1B, 0x60, 0x25, 0xAD, 0xAE, 0xB0, 0xB9, 0xF6, 0x1C, 0x46, 0x61, 0x69, 0x34, 0x40, 0x7E, 0x0F, 
0x55, 0x47, 0xA3, 0x23, 0xDD, 0x51, 0xAF, 0x3A, 0xC3, 0x5C, 0xF9, 0xCE, 0xBA, 0xC5, 0xEA, 0x26, 
0x2C, 0x53, 0x0D, 0x6E, 0x85, 0x28, 0x84, 0x09, 0xD3, 0xDF, 0xCD, 0xF4, 0x41, 0x81, 0x4D, 0x52, 
0x6A, 0xDC, 0x37, 0xC8, 0x6C, 0xC1, 0xAB, 0xFA, 0x24, 0xE1, 0x7B, 0x08, 0x0C, 0xBD, 0xB1, 0x4A, 
0x78, 0x88, 0x95, 0x8B, 0xE3, 0x63, 0xE8, 0x6D, 0xE9, 0xCB, 0xD5, 0xFE, 0x3B, 0x00, 0x1D, 0x39, 
0xF2, 0xEF, 0xB7, 0x0E, 0x66, 0x58, 0xD0, 0xE4, 0xA6, 0x77, 0x72, 0xF8, 0xEB, 0x75, 0x4B, 0x0A, 
0x31, 0x44, 0x50, 0xB4, 0x8F, 0xED, 0x1F, 0x1A, 0xDB, 0x99, 0x8D, 0x33, 0x9F, 0x11, 0x83, 0x14

MD2 ハッシュ値ち

128ビット（16バイト）の MD2 のハッシュ値ち（これを message digests とも呼よぶ）は、通常つうじょう32桁けたの16進数しんすうで表あらわされる。以下いかに 43バイトの ASCIIを入力にゅうりょくとして MD2 のハッシュ値ちを得える様子ようすを示しめす。

 MD2("The quick brown fox jumps over the lazy dog")
  = 03d85a0d629d2c442e987525319fc471

メッセージに微妙びみょうな修正しゅうせいを施ほどこした場合ばあいでも、完全かんぜんに異ことなるハッシュ値ちが生成せいせいされる。ここでは、dog が cog に修正しゅうせいされている。

 MD2("The quick brown fox jumps over the lazy cog")
  = 6b890c9292668cdbbfda00a4ebf31f05

長ながさ 0 のメッセージのハッシュ値ちは次つぎのようになる。

 MD2("") = 8350e5a3e24c153df2275c9f80692773

セキュリティ

Rogier と Chauvaud (1997年ねん) は MD2 の圧縮あっしゅく関数かんすうでのコリジョンを見出みいだした。ただし、彼かれらも MD2 全体ぜんたいへの攻撃こうげきには成功せいこうしなかった。

2004年ねん、2¹⁰⁴ の圧縮あっしゅく関数かんすう評価ひょうかと等価とうかな時間じかん複雑ふくざつ性せいの原はら像ぞう攻撃こうげきで MD2 の脆弱ぜいじゃく性せいが明あきらかとなった（Muller、2004年ねん）。「MD2 はもはや安全あんぜんな単たん方向ほうこうのハッシュ関数かんすうとは言いえない」

2008年ねん、2⁷³ の圧縮あっしゅく関数かんすう評価ひょうかと等価とうかな時間じかん複雑ふくざつ性せいおよび 2⁷³ のメッセージブロックのメモリ容量ようりょうによる原はら像ぞう攻撃こうげきが示しめされた^[3]。

2009年ねん、2^63.3 の圧縮あっしゅく関数かんすう評価ひょうかと等価とうかな時間じかん複雑ふくざつ性せいおよび 2⁵² のハッシュ値ちのメモリ容量ようりょうによる衝突しょうとつ攻撃こうげきで MD2 の脆弱ぜいじゃく性せいが示しめされた。これは2^65.5の圧縮あっしゅく関数かんすう評価ひょうかが必要ひつようと見積みつもられている誕生たんじょう日び攻撃こうげきよりも若干じゃっかんよい値ねである^[4]。

2009年ねん、OpenSSL、GnuTLS、Network Security Services においてMD2を使用しよう不可ふかにするセキュリティアップデートが発行はっこうされた^[5]。

参考さんこう文献ぶんけん

Burt Kaliski, RFC 1319 - MD2 Message Digest Algorithm, April 1992.
N. Rogier, Pascal Chauvaud, The compression function of MD2 is not collision free, Selected Areas in Cryptography - SAC'95 Ottawa, Canada, May 18–19, 1995 (workshop record).
N. Rogier, Pascal Chauvaud, MD2 is not Secure without the Checksum Byte, Designs, Codes and Cryptography, 12(3), pp245–251, 1997.
Frédéric Muller, The MD2 Hash Function is Not One-Way, ASIACRYPT 2004, pp214–229.
Lars R. Knudsen and John Erik Mathiassen, Preimage and Collision Attacks on MD2. FSE 2005.

脚注きゃくちゅう

^ ^a ^b John Linn, RFC 1115 - Privacy Enhancement for Internet Electronic Mail: Part III—Algorithms, Modes, and Identifiers, Section 4.2, August 1989, Source by Ron L. Rivest October, 1988.
^ “What are MD2, MD4, and MD5?”. Public-Key Cryptography Standards (PKCS): PKCS #7: Cryptographic Message Syntax Standard: 3.6 Other Cryptographic Techniques: 3.6.6 What are MD2, MD4, and MD5?. RSA Laboratories. 2011年ねん4月がつ29日にち閲覧えつらん。
^ Søren S. Thomsen (2008). An improved preimage attack on MD2. http://eprint.iacr.org/2008/089.pdf.
^ http://www.springerlink.com/content/qn746388035614r1/
^ CVE-2009-2409

外部がいぶリンク

RFC 1319, The MD2 Message-Digest Algorithm
RFC 6149, MD2 to Historic Status
Online MD2 Calculator over HTTPS
Serversniff.net 文字もじ列れつの MD2 などのハッシュ値ちを計算けいさんするオンラインツール
テキスト、16進しん、2進しん、Base64などの相互そうご変換へんかんと同時どうじにMD2その他たのハッシュ値ちを計算けいさんするオンラインツール [1]

[rfc1115-1] John Linn, RFC 1115 - Privacy Enhancement for Internet Electronic Mail: Part III—Algorithms, Modes, and Identifiers, Section 4.2, August 1989, Source by Ron L. Rivest October, 1988.

[2] “What are MD2, MD4, and MD5?”. Public-Key Cryptography Standards (PKCS): PKCS #7: Cryptographic Message Syntax Standard: 3.6 Other Cryptographic Techniques: 3.6.6 What are MD2, MD4, and MD5?. RSA Laboratories. 2011年ねん4月がつ29日にち閲覧えつらん。

[3] Søren S. Thomsen (2008). An improved preimage attack on MD2. http://eprint.iacr.org/2008/089.pdf.

[4] ttp://www.springerlink.com/content/qn746388035614r1/

[5] CVE-2009-2409

[1]

[2]

[3]

[4]

[5]