MD4

MD4
一般的な
デザイナー	ロナルド・リベスト
初版	1990年10月
シリーズ	MD2、MD4、MD5、MD6
暗号の詳細
ダイジェストサイズ	128ビット
ブロックサイズ	512 ビット
ラウンド	3
最高の公開暗号解読
	2007年に公開された衝突攻撃では、2回のハッシュ操作未満で完全なMD4の衝突を見つけることができます。

MD4メッセージダイジェストアルゴリズムは、 1990 年にロナルド・リベストによって開発された暗号ハッシュ関数です^{。[3]ダイジェストの長さは 128 ビットです。このアルゴリズムは、}MD5、SHA-1、RIPEMDアルゴリズムなどの後の設計に影響を与えました。頭文字の「MD」は「Message Digest」の略です。

1 つの MD4 操作。MD4 は 48 の操作で構成され、16 の操作の 3 ラウンドにグループ化されています。Fは非線形関数です。各ラウンドで 1 つの関数が使用されます。M *_{i は}メッセージ*入力の 32 ビットブロックを示し、*K _{i は}*各ラウンドで異なる 32 ビット定数を示します。

MD4 のセキュリティは深刻に侵害されています。MD4 に対する最初の完全な衝突攻撃は1995 年に公開され、それ以降、いくつかの新しい攻撃が公開されています。2007 年現在、攻撃は 2 回未満の MD4 ハッシュ操作で衝突を生成できます。^[2]理論的な原像攻撃も存在します。

MD4 のバリアントは、ed2k URI スキームで使用され、一般的な eDonkey2000 / eMule P2P ネットワーク内のファイルに一意の識別子を提供します。MD4 は、 rsyncプロトコル (バージョン 3.0.0 より前)でも使用されていました。

MD4は、Microsoft Windows NT、XP、Vista、7、8、10、11でNTLMパスワード派生キーダイジェストを計算するために使用されます。 ^[4]

安全

MD4 の弱点は、1991 年に発表された論文で Den Boer と Bosselaers によって実証されました。^[5]最初のフルラウンド MD4衝突攻撃は、1995 年にHans Dobbertinによって発見されましたが、当時は実行に数秒しかかかりませんでした。^[6] 2004 年 8 月、Wangらは、MD4/MD5/SHA-1/RIPEMD ファミリーの後のハッシュ関数設計に対する攻撃と並んで、非常に効率的な衝突攻撃を発見しました。この結果は後に Sasaki らによって改善され、衝突を生成することは、それを検証するのと同じくらい安価になりました (数マイクロ秒)。^[2]

2008年には、 MD4の原像計算耐性もガエタン・ルランによって2 ¹⁰²攻撃で破られた。^[7] 2010年には、Guoらが2 ^99.7攻撃を発表した。^[8]

2011 年、RFC 6150 では、RFC 1320 (MD4) は歴史的(廃止) であると宣言されました。

MD4ハッシュ

128 ビット (16 バイト) の MD4 ハッシュ (メッセージダイジェストとも呼ばれる) は、通常、32 桁の16 進数で表されます。以下は、43 バイトのASCII入力とそれに対応する MD4 ハッシュを示しています。

MD4(「素早い茶色のキツネが怠け者の犬を飛び越える」 )
= 1bee69a46ba811185c194762abaeae90

メッセージに小さな変更を加えるだけでも（圧倒的な確率で）完全に異なるハッシュが生成されます。たとえば、次dのように変更されます。c

MD4(「素早い茶色のキツネは怠け者の歯車を飛び越える」 )
= b86e130ce7028da59e672d56ad0113df

長さゼロの文字列のハッシュは次のとおりです。

MD4("") = 31d6cfe0d16ae931b73c59d7e0c089c0

MD4 テストベクトル

以下のテストベクトルは、RFC 1320 (MD4 メッセージダイジェストアルゴリズム) で定義されています。

MD4 ("") = 31d6cfe0d16ae931b73c59d7e0c089c0
MD4 ("a") = bde52cb31de33e46245e05fbdbd6fb24
MD4 ("abc") = a448017aaf21d8525fc10ae87aa6729d
MD4 (「メッセージダイジェスト」) = d9130a8164549fe818874806e1c7014b
MD4 ("abcdefghijklmnopqrstuvwxyz") = d79e1c308aa5bbcdeea8ed63df412da9
MD4 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = 043f8582f241db351ce627e153e7f0e4
MD4 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = e33b4ddc9c38f2199c3e7b164fcc0536

MD4衝突の例

させて：

k1 = 839c7a4d7a92cb 5 678a5d5 b 9eea5a7573c8a74deb366c3dc20a083b69f5d2a3bb3719dc69891e9f95e809fd7e8b23ba6318ed d 45e51fe39708bf9427e9c3e 8b9
 k2 = 839c7a4d7a92cb d 678a5d5 2 9eea5a7573c8a74deb366c3dc20a083b69f5d2a3bb3719dc69891e9f95e809fd7e8b23ba6318ed c 45e51fe39708bf9427e9c3e 8b9

MD4(k1) = MD4(k2) = 4d7e6a1defa93d2dde05b45d864c429b

k1 と k2 の 2 つの 16 進数字は、長さが 64 バイトの入力文字列の 1 バイトを定義することに注意してください。

参照

参考文献

バート・デン・ブール、アントーン・ボッセラーズ：MD4 の最後の 2 ラウンドへの攻撃。Crypto 1991：194–203
ハンス・ドッベルティン: MD4 の暗号解析。高速ソフトウェア暗号化 1996: 53–69
ハンス・ドッベルティン、1998年。MD4の暗号解読。J.暗号学11(4):253–271
Xiaoyun Wang、Xuejia Lai、Denguo Feng、Hui Chen、Xiuyuan Yu: ハッシュ関数 MD4 および RIPEMD の暗号解析。ユーロクリプト 2005: 1–18
佐々木優、王磊、太田和夫、國弘昇: MD4 の新しいメッセージ差分。高速ソフトウェア暗号化 2007: 329–348

^ Rivest, Ronald L. (1990 年 10 月). 「MD4 メッセージダイジェストアルゴリズム」. ネットワークワーキンググループ. 2011 年 4 月 29 日閲覧。
^ abc Yu Sasaki; et al. (2007). 「MD4 の新しいメッセージの違い」(PDF)。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です
^ 「MD2、MD4、MD5 とは何ですか?」。公開鍵暗号化標準 (PKCS): PKCS #7: 暗号化メッセージ構文標準: 3.6 その他の暗号化技術: 3.6.6 MD2、MD4、MD5 とは何ですか? RSA ラボラトリーズ。2011 年 9 月 1 日のオリジナルからアーカイブ。2011年 4 月 29 日取得。
^ 「5.1 実装者のためのセキュリティに関する考慮事項」。2011-07-21取得。パスワードからキーを導出する方法は、[RFC1320] および [FIPS46-2] で指定されています。
^ Bert den Boer、Antoon Bosselaers (1991)。「MD4 の最後の 2 ラウンドに対する攻撃」(PDF) 。2003 年 5 月 23 日のオリジナル(PDF)からアーカイブ。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です
^ Hans Dobbertin (1995-10-23). 「MD4の暗号解析」. Journal of Cryptology . 11 (4): 253–271. doi : 10.1007/s001459900047 . S2CID 7462235.
^ Gaëtan Leurent (2008-02-10). 「MD4 は一方向ではない」(PDF) . FSE 2008. {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です
^ Guo, Jian; Ling, San; Rechberger, Christian; Wang, Huaxiong (2010)。「高度な Meet-in-the-Middle プリイメージ攻撃: Full Tiger での最初の結果と MD4 および SHA-2 での改善された結果」。Advances in Cryptology - ASIACRYPT 2010。Lecture Notes in Computer Science。Vol. 6477。pp. 56–75。doi : 10.1007/ 978-3-642-17373-8_4。hdl : 10356 / 94168。ISBN 978-3-642-17372-1。

外部リンク

RFC 1320 - Ron Rivest による MD4 の説明
RFC 6150 - MD4 の歴史的ステータス
Rivest, Ronald (1991)。「MD4 メッセージダイジェストアルゴリズム」。Advances in Cryptology-CRYPT0' 90 。Lecture Notes in Computer Science。Vol. 537。Springer Berlin / Heidelberg。pp. 303–311。doi :10.1007/3-540-38424-3_22。ISBN 978-3-540-54508-8。

衝突攻撃

MD4 の最後の 2 ラウンドへの攻撃
MD4 の衝突攻撃の改善

[1] Rivest, Ronald L. (1990 年 10 月). 「MD4 メッセージダイジェストアルゴリズム」. ネットワークワーキンググループ. 2011 年 4 月 29 日閲覧。

[sasaki-2007-2] Yu Sasaki; et al. (2007). 「MD4 の新しいメッセージの違い」(PDF)。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です

[drt-3] 「MD2、MD4、MD5 とは何ですか?」。公開鍵暗号化標準 (PKCS): PKCS #7: 暗号化メッセージ構文標準: 3.6 その他の暗号化技術: 3.6.6 MD2、MD4、MD5 とは何ですか? RSA ラボラトリーズ。2011 年 9 月 1 日のオリジナルからアーカイブ。2011年 4 月 29 日取得。

[ntlm-4] 「5.1 実装者のためのセキュリティに関する考慮事項」。2011-07-21取得。パスワードからキーを導出する方法は、[RFC1320] および [FIPS46-2] で指定されています。

[5] Bert den Boer、Antoon Bosselaers (1991)。「MD4 の最後の 2 ラウンドに対する攻撃」(PDF) 。2003 年 5 月 23 日のオリジナル(PDF)からアーカイブ。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です

[6] Hans Dobbertin (1995-10-23). 「MD4の暗号解析」. Journal of Cryptology . 11 (4): 253–271. doi : 10.1007/s001459900047 . S2CID 7462235.

[7] Gaëtan Leurent (2008-02-10). 「MD4 は一方向ではない」(PDF) . FSE 2008. {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です

[8] Guo, Jian; Ling, San; Rechberger, Christian; Wang, Huaxiong (2010)。「高度な Meet-in-the-Middle プリイメージ攻撃: Full Tiger での最初の結果と MD4 および SHA-2 での改善された結果」。Advances in Cryptology - ASIACRYPT 2010。Lecture Notes in Computer Science。Vol. 6477。pp. 56–75。doi : 10.1007/ 978-3-642-17373-8_4。hdl : 10356 / 94168。ISBN 978-3-642-17372-1。