| 一般的な | |
|---|---|
| デザイナー | ロナルド・リベスト |
| 初版 | 1992年4月 |
| シリーズ | MD2、MD4、MD5、MD6 |
| 暗号の詳細 | |
| ダイジェストサイズ | 128ビット |
| ブロックサイズ | 512ビット |
| 構造 | メルクル・ダムガルド建設 |
| ラウンド | 4 [ 1 ] |
| 最高の公開暗号解読 | |
| 2013年に謝濤、劉凡宝、馮登国による攻撃は、MD5の衝突耐性を2 18秒で破った。この攻撃は通常のコンピュータで1秒未満で実行される。[ 2 ] MD5は長さ拡張攻撃 を受けやすい。 | |
MD5メッセージダイジェストアルゴリズムは、 128ビットのハッシュ値を生成する広く使用されているハッシュ関数です。MD5は、以前のハッシュ関数MD4 [ 3 ]を置き換えるために1991年にロナルド・リベストによって設計され、1992年にRFC 1321として規定されました。
MD5は、意図しない破損に対するデータの完全性を検証するためのチェックサムとして使用できます。歴史的には、暗号化ハッシュ関数として広く使用されていましたが、多くの脆弱性があることが判明しています。パーティション化されたデータベース内の特定のキーのパーティションを決定するなど、暗号化以外の目的には適しており、より新しいセキュアハッシュアルゴリズムよりも計算要件が低いため、好まれる場合があります。[ 4 ]
MD5は、 MITのロナルド・リベスト教授が設計した一連のメッセージダイジェストアルゴリズムの一つである(Rivest、1992)。分析の結果、MD5の前身であるMD4は安全ではない可能性が高いことが示されたため、リベストは1991年に安全な代替アルゴリズムとしてMD5を設計した。(実際、後にハンス・ドバーティンがMD4の脆弱性を発見した。)
1993年、デン・ボーアとボッセラーズは、MD5圧縮関数の「擬似衝突」を発見するという、限定的ではあるものの初期の成果を発表した。これは、同一のダイジェストを生成する2つの異なる初期化ベクトルの存在を示すものである。
1996年、ドバティンはMD5の圧縮関数の衝突を発表した(ドバティン、1996)。これはMD5ハッシュ関数全体に対する攻撃ではなかったものの、暗号学者がSHA-1(これも後に脆弱性が発見された)やRIPEMD-160などの代替手段への切り替えを推奨するほど、それに近いものであった。
ハッシュ値のサイズ(128ビット)は、誕生日攻撃を想定できるほど小さい。MD5CRKは、誕生日攻撃を用いて衝突を見つけることで、MD5が実際には安全ではないことを実証するために、2004年3月に開始された分散プロジェクトである。
MD5CRKは、2004年8月17日にXiaoyun Wang、Dengguo Feng、Xuejia Lai、Hongbo Yuによって完全なMD5の衝突が発表された直後に終了した。 [ 5 ] [ 6 ]彼らの解析的攻撃はIBM p690クラスター上でわずか1時間で完了したと報告されている。[ 7 ]
2005 年 3 月 1 日、Arjen Lenstra、Xiaoyun Wang、および Benne de Weger は、異なる公開鍵と同一の MD5 ハッシュ値を持つ2 つのX.509証明書の構築を実証し、実証可能な実用的な衝突を示しました。 [ 8 ]この構築には、両方の公開鍵の秘密鍵が含まれていました。数日後、Vlastimil Klima は、単一のノートブック コンピュータで数時間で MD5 衝突を構築できる改良されたアルゴリズムについて説明しました。[ 9 ] 2006 年 3 月 18 日、Klima は、トンネリングと呼ばれる方法を使用して、単一のノートブック コンピュータで 1 分以内に衝突を見つけることができるアルゴリズムを発表しました。[ 10 ]
MD5関連のRFC正誤表が多数公開されている。2009年には、米国サイバー軍が任務声明のMD5ハッシュ値を公式エンブレムの一部として使用した。[ 11 ]
2010年12月24日、Tao XieとDengguo Fengは、初めて公開された単一ブロック(512ビット)MD5衝突を発表した。[ 12 ](それまでの衝突発見は、マルチブロック攻撃に依存していた。)XieとFengは「セキュリティ上の理由」から、新しい攻撃方法を公開しなかった。彼らは暗号コミュニティに挑戦状を叩きつけ、2013年1月1日までに別の64バイト衝突を最初に発見した者に1万ドルの報酬を提供すると申し出た。Marc Stevensはこの挑戦に応じ、衝突する単一ブロックメッセージと構築アルゴリズムおよびソースコードを公開した。[ 13 ]
2011年に、MD5 [ 15 ]とHMAC-MD5 [ 16 ]のセキュリティに関する考慮事項を更新するための情報RFC 6151 [ 14 ]が承認されました。
暗号学的ハッシュ関数の基本的な要件の1つは、同じハッシュ値になる2つの異なるメッセージを見つけることが計算上不可能であることです。MD5はこの要件を致命的に満たしていません。2008年12月31日、カーネギーメロン大学ソフトウェア工学研究所は、MD5は本質的に「暗号学的に破られており、これ以上使用するのに適さない」と結論付けました。[ 17 ] MD5の弱点は、2012年のFlameマルウェアで最も悪名高い例ですが、実際に悪用されています。2019年現在MD5は、セキュリティ専門家による弱点や非推奨が十分に文書化されているにもかかわらず、依然として広く使用されている。[ 18 ]
2.6 GHz Pentium 4 プロセッサを搭載したコンピュータで数秒以内に衝突を見つけることができる衝突攻撃が存在する(複雑度 2 24.1 )。[ 19 ]さらに、市販のコンピューティング ハードウェアを使用して、指定されたプレフィックスを持つ 2 つの入力に対して数秒以内に衝突を生成できる選択プレフィックス衝突攻撃も存在する (複雑度 2 39 )。[ 20 ] 市販のGPUの使用により、衝突を見つける能力が大幅に向上した。NVIDIA GeForce 8400GS グラフィックス プロセッサでは、毎秒 1600 万~ 1800 万ハッシュを計算できる。NVIDIA GeForce 8800 Ultra では、毎秒 2 億ハッシュ以上を計算できる。[ 21 ]
これらのハッシュ攻撃と衝突攻撃は、衝突する文書ファイル[ 22 ] [ 23 ]やデジタル証明書[ 24 ]など、さまざまな状況で公に実証されています。2015年の時点で、MD5はセキュリティ研究やアンチウイルス企業を中心に、依然としてかなり広く使用されていることが実証されています[ 25 ] 。
2019年の時点で、広く使用されているコンテンツ管理システムの4分の1が、パスワードハッシュにMD5を使用していると報告されている。[ 18 ]
1996 年、MD5 の設計に欠陥が見つかりました。当時は致命的な弱点とはみなされませんでしたが、暗号学者はSHA-1などの他のアルゴリズムの使用を推奨し始めましたが、その後 SHA-1 も脆弱であることが判明しました。[ 26 ] 2004 年に、MD5 は衝突耐性が ないことが示されました。[ 27 ]そのため、MD5 は、デジタル セキュリティのためにこの特性に依存するSSL証明書やデジタル署名などのアプリケーションには適していません。研究者はさらに、MD5 のより深刻な欠陥を発見し、実行可能な衝突攻撃、つまり MD5 が同一のチェックサムを生成する入力のペアを作成する方法を説明しました。[ 5 ] [ 28 ] 2005 年、2006 年、2007 年に MD5 の解読がさらに進展しました。[ 29 ] 2008 年 12 月、研究者グループがこの技術を使用してSSL 証明書の有効性を偽装しました。[ 24 ] [ 30 ]
2010年現在、CMUソフトウェアエンジニアリング研究所はMD5を「暗号学的に破綻しており、これ以上使用するのに適さない」と考えており[ 17 ]、現在ではほとんどの米国政府アプリケーションでSHA-2ファミリーのハッシュ関数が要求されている[ 31 ] 。 2012年には、FlameマルウェアがMD5の脆弱性を悪用してMicrosoftのデジタル署名を偽造した[ 32 ]。
1996年にMD5の圧縮関数に衝突が発見され、ハンス・ドバーティンはRSA研究所の技術ニュースレターで「提示された攻撃はまだMD5の実用的なアプリケーションを脅かすものではないが、かなり近い…将来、衝突耐性のあるハッシュ関数が必要とされる場所ではMD5は実装されるべきではない」と書いた。[ 33 ]
2005年、研究者たちは同じハッシュ値を持つPostScript文書[ 34 ]とX.509証明書[ 35 ]のペアを作成することができた。同年後半、MD5の設計者であるロン・リベストは「md5とsha1はどちらも(衝突耐性の観点から)明らかに破られている」と書いた[ 36 ] 。
2008 年 12 月 30 日、研究者グループは第 25 回カオス通信会議で、MD5 衝突を利用して、MD5 ハッシュでチェックすると正当に見える中間認証局証明書を作成した方法を発表しました。[ 24 ]研究者らは、スイスのローザンヌにあるEPFLのPS3 クラスター[ 37 ]を使用して、 RapidSSLが発行した通常の SSL 証明書をその発行者の有効なCA 証明書に変更し、それを使用して、RapidSSL が発行した正当に見える他の証明書を作成することができました。RapidSSL証明書の発行者であるVerisign は、脆弱性が発表された後、RapidSSL のチェックサム アルゴリズムとして MD5 を使用する新しい証明書の発行を停止したと述べています。[ 38 ] Verisign は MD5 を使用して署名された既存の証明書の失効を拒否しましたが、エクスプロイトの著者 ( Alexander Sotirov、Marc Stevens、Jacob Appelbaum、Arjen Lenstra、 David Molnar 、 Dag Arne Osvik 、 Benne de Weger ) は Verisign の対応は適切であると考えました。[ 24 ] Bruce Schneier は、この攻撃について「MD5 が欠陥のあるハッシュ関数であることは既に分かっていた」とし、「MD5 はもう誰も使用すべきではない」と述べています。[ 39 ] SSL の研究者らは、「我々が望む影響は、認証局が新しい証明書の発行に MD5 を使用するのをやめることです。また、他のアプリケーションでの MD5 の使用も再検討されることを期待しています」と述べています。[ 24 ]
マイクロソフトによると、2012年にFlameマルウェアの作者はMD5衝突を利用してWindowsコード署名証明書を偽造した。[ 32 ]
MD5はMerkle–Damgård構造を使用しているため、同じハッシュ値を持つ2つのプレフィックスを作成できる場合、両方に共通のサフィックスを追加することで、衝突がアプリケーションによって有効なデータとして受け入れられる可能性が高くなります。さらに、現在の衝突検出技術では任意のプレフィックスを指定できます。攻撃者は、同じ内容で始まる2つの衝突ファイルを作成できます。2つの衝突ファイルを生成するために攻撃者が必要とするのは、64バイト境界にアラインされた128バイトのデータブロックを持つテンプレートファイルだけで、これは衝突検出アルゴリズムによって自由に変更できます。2つのメッセージが6バイト異なるMD5衝突の例は次のとおりです。
d131dd02c5e6eec4 693d9a0698aff95c 2fcab5 8 712467eab 4004583eb8fb7f89 55ad340609f4b302 83e4888325 7 1415a 085125e8f7cdc99f d91dbd f 280373c5b d8823e3156348f5b ae6dacd436c919c6 dd53e2 b 487da03fd 02396306d248cda0 e99f33420f577ee8 ce54b67080 a 80d1e c69821bcb6a88393 96f965 2 b6ff72a70
d131dd02c5e6eec4 693d9a0698aff95c 2fcab5 0 712467eab 4004583eb8fb7f89 55ad340609f4b302 83e4888325 f 1415a 085125e8f7cdc99f d91dbd 7 280373c5b d8823e3156348f5b ae6dacd436c919c6 dd53e2 3 487da03fd 02396306d248cda0 e99f33420f577ee8 ce54b67080 2 80d1e c69821bcb6a88393 96f965 a b6ff72a70
どちらもMD5ハッシュを生成します79054025255fb1a26e4bc422aef54eb4。[ 40 ] 2つのサンプルの違いは、各ニブルの先頭ビットが反転されていることです。たとえば、上のサンプル0x87の20番目のバイト(オフセット0x13)は、バイナリで10000111です。バイトの先頭ビット(最初のニブルの先頭ビットでもある)が反転され、下のサンプルに示すように00000111、つまり0x07になります。
その後、別々に選択されたプレフィックスを持つ 2 つのファイル間で衝突を構築できることも判明しました。この技術は、2008 年に不正な CA 証明書の作成に使用されました。2014年に Anton Kuznetsov は、 MPIを使用した並列衝突検索の新しいバリアントを提案し、これにより計算クラスタ上で 11 時間で衝突を見つけることができました。[ 41 ]
2009年4月、MD5の原像耐性を破るMD5に対する攻撃が発表された。この攻撃は理論上のものに過ぎず、完全な原像に対する計算複雑度は2 123.4である。[ 42 ] [ 43 ]
MD5ダイジェストは、転送されたファイルが破損なく到着したことをある程度保証するために、ソフトウェアの世界で広く使用されています。たとえば、ファイルサーバーは、ダウンロードしたファイルのチェックサムとユーザーが比較できるように、ファイルの事前計算されたMD5( md5sumとして知られています)チェックサムを提供することがよくあります。ほとんどのUnixベースのオペレーティングシステムには、配布パッケージにMD5サムユーティリティが含まれています。Windowsユーザーは、付属のPowerShell関数「Get-FileHash」、付属のコマンドライン関数「certutil -hashfile <filename> md5」[ 44 ] [ 45 ] 、 Microsoftユーティリティのインストール[ 46 ] [ 47 ]、またはサードパーティアプリケーションを使用できます。Android ROMもこのタイプのチェックサムを使用します。

MD5の衝突は容易に発生させることができるため、ファイルを作成した人物が同じチェックサムを持つ別のファイルを作成することが可能です。そのため、この手法では悪意のある改ざんを防ぐことはできません。場合によっては、チェックサムが信頼できないこともあります(例えば、ダウンロードしたファイルと同じチャネルで取得された場合など)。その場合、MD5はエラーチェック機能しか提供できません。つまり、破損または不完全なダウンロードを検出しますが、これは大きなファイルをダウンロードする際に起こりやすくなります。
歴史的に、MD5 はパスワードの一方向ハッシュを保存するために使用されてきましたが、多くの場合、キー ストレッチングが使用されていました。[ 48 ] [ 49 ] NIST は、パスワード保存に推奨されるハッシュのリストに MD5 を含めていません。[ 50 ]
MD5は、電子証拠開示の分野でも使用されており、法的証拠開示手続き中に交換される各文書に固有の識別子を付与するために用いられます。この方法は、紙文書の交換において数十年にわたり使用されてきたベイツスタンプ番号システムに代わるものとして利用できます。しかし、前述のとおり、衝突攻撃を受けやすいため、この使用方法は推奨されません。

MD5 は可変長メッセージを 128 ビットの固定長出力に処理します。入力メッセージは 512 ビットのブロック (32 ビットのワードが 16 個) に分割されます。メッセージは、元の長さが 512 で割り切れる場合でも常にパディングされます(RFC 1321、セクション 3.1 を参照)。パディングは次のように機能します。まず、メッセージの末尾に 1 ビットが追加されます。次に、メッセージの長さが 512 の倍数より 64 ビット少なくなるように必要な数のゼロが追加されます。残りのビットは、2 64を法とする元のメッセージの長さを表す 64 ビットで埋められます。
MD5アルゴリズムのメイン部分は、128ビットの状態を4つの32ビットワード(A、B、C、Dと表記)に分割して処理します。これらのワードは、特定の固定定数で初期化されます。メインアルゴリズムは、512ビットのメッセージブロックを順番に使用して状態を変更します。メッセージブロックの処理は、ラウンドと呼ばれる4つの類似したステージで構成されます。各ラウンドは、非線形関数F、モジュラー加算、および左回転に基づく16の類似した操作で構成されます。図1は、ラウンド内の1つの操作を示しています。使用可能な関数は4つあり、各ラウンドで異なる関数が使用されます。
MD5ハッシュはこのアルゴリズムに従って計算されます。[ 51 ]すべての値はリトルエンディアンです。
// : すべての変数は符号なし 32 ビットであり、計算時に 2^32 でラップされます。 var int s[64]、K[64] var int i // s はラウンドごとのシフト量を指定します s[ 0..15] := { 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22 } s[16..31] := { 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20 } s[32..47] := { 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23 } s[48..63] := { 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21 } //整数の正弦(ラジアン)のバイナリ整数部分を定数として使用します。 for i from 0 to 63 do K[i] := floor(2 32 × abs(sin(i + 1))) end for // (または、以下の事前計算済みテーブルを使用するだけです) K[ 0.. 3] := { 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee } K[ 4.. 7] := { 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501 } K[ 8..11] := { 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be } K[12..15] := { 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821 } K[16..19] := { 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa } K[20..23] := { 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8 } K[24..27] := { 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed } K[28..31] := { 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a } K[32..35] := { 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c } K[36..39] := { 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70 } K[40..43] := { 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05 } K[44..47] := { 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665 } K[48..51] := { 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039 } K[52..55] := { 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1 } K[56..59] := { 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1 } K[60..63] := { 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 } //変数の初期化: var int a0 := 0x67452301 // A var int b0 := 0xefcdab89 // B var int c0 := 0x98badcfe // C var int d0 := 0x10325476 // D//前処理: 1 ビットを 1 つ追加してメッセージに"1" ビットを追加します< // 注意: 入力バイトはビット列として扱われます。 // ここで、最初のビットはバイトの最上位ビットです。[ 52 ]//前処理: ゼロによるパディング メッセージ長がビット単位で ≡ 448 (mod 512) になるまで「0」ビットを追加します// 注意: 上記の 2 つのパディング手順は、よりシンプルな方法で実装されています // 完全なバイト列のみを扱う実装の場合: 0x80 を追加する // メッセージの長さがバイト単位で ≡ 56 (mod 64) になるように 0x00 バイトでパディングします。元の長さをビット単位で追加し、それを2 64で割った余りをメッセージに追加します。//メッセージを連続する 512 ビットのチャンクで処理します。 パディングされたメッセージの512 ビットのチャンクごとに、 チャンクを16個の32ビットワードM[j]に分割する(0 ≤ j ≤ 15)。 //このチャンクのハッシュ値を初期化します: var int A := a0 var int B := b0 var int C := c0 var int D := d0 //メインループ: for i from 0 to 63 do var int F, g if 0 ≤ i ≤ 15 then F := (B and C) or (( not B) and D) g := i そうでなければ、 16 ≤ i ≤ 31の場合、 F := (DかつB)または(( D以外)かつC) g := (5×i + 1) mod 16 そうでなければ、 32 ≤ i ≤ 47ならば F := B xor C xor D g := (3×i + 5) mod 16 そうでなければ、 48 ≤ i ≤ 63の場合、 F := C xor (Bまたは( D以外)) g := (7×i) mod 16 //以下の a,b,c,d の定義に注意してください F := F + A + K[i] + M[g] // M[g] は 32 ビットのブロックである必要があります A := D D := C C := B B := B + leftrotate (F, s[i]) end for //このチャンクのハッシュをこれまでの結果に追加します。 a0 := a0 + A b0 := b0 + B c0 := c0 + C d0 := d0 + D 終了var char digest[16] := a0 append b0 append c0 append d0 // (出力はリトルエンディアンです)
元のRFC 1321に示されている定式化の代わりに、効率を向上させるために次の式を使用できます(アセンブリ言語を使用している場合に便利です。そうでない場合は、コンパイラが通常上記のコードを最適化します。これらの定式化では各計算が他の計算に依存しているため、nand/andを並列化できる上記の方法よりも遅くなることがよくあります)。
( 0 ≤ i ≤ 15): F := D xor (Bかつ(C xor D)) (16 ≤ i ≤ 31): F := C xor (Dかつ(B xor C))
128ビット(16バイト)のMD5ハッシュ(メッセージダイジェストとも呼ばれる)は、通常、32桁の16進数で表されます。以下に、43バイトのASCII入力とそれに対応するMD5ハッシュを示します。
MD5("素早い茶色のキツネが怠惰な犬を飛び越える") = 9e107d9d372bb6826bd81d3542a419d6メッセージのわずかな変更でも、(圧倒的な確率で)雪崩効果により、ハッシュ値はほぼ完全に異なるものになります。例えば、文末にピリオドを追加すると次のようになります。
MD5("素早い茶色のキツネが怠惰な犬を飛び越える。 ") = e4d909c290d0fb1ca068ffaddf22cbd0長さゼロの文字列のハッシュ値は次のとおりです。
MD5("") = d41d8cd98f00b204e9800998ecf8427eMD5アルゴリズムは、任意のビット数で構成されるメッセージに対して規定されており、8ビット(オクテット、バイト)の倍数に限定されません。md5sumなどの一部のMD5実装はオクテットに制限されている場合や、初期長が未定のメッセージのストリーミングをサポートしていない場合があります。
以下は、MD5をサポートする暗号化ライブラリの一覧です。
提示された攻撃はまだ MD5 の実用性を脅かすものではないが、かなり近い。…
[
原文ママ
]
将来、
衝突耐性のあるハッシュ関数が必要とされる場所では、 MD5 はもはや実装されるべきではない…
[
原文ママ
] 。
(文書を表示するには、ヘルプ:FTPを参照してください)