衝突攻撃

暗号学において、暗号ハッシュに対する衝突攻撃は、同じハッシュ値を生成する2つの入力、すなわちハッシュ衝突を見つけようとする攻撃です。これは、特定のハッシュ値を指定する 原像攻撃とは対照的です。

衝突攻撃には、大きく分けて 2 つの種類があります。

古典的な衝突攻撃

hash ( _{m1 )} = hash ( m2 )となる2_つの異なるメッセージm1とm2_を見つけます。

より一般的には：

選択プレフィックス衝突攻撃

2 つの異なるプレフィックスp ₁とp ₂が与えられた場合、hash ( p ₁ ∥ s ₁ ) = hash ( p ₂ ∥ s ₂ )となる2 つのサフィックスs ₁とs ₂を見つけます。ここで、 ∥ は連結演算を示します。

古典的な衝突攻撃

対称鍵暗号がブルートフォース攻撃に対して脆弱であるのと同様に、あらゆる暗号ハッシュ関数は本質的にバースデー攻撃による衝突に対して脆弱です。バースデー問題により、これらの攻撃はブルートフォース攻撃よりもはるかに高速です。nビットのハッシュは、^{2 n} / ²回のステップ（ハッシュ関数の評価） で解読できます。

数学的に言えば、衝突攻撃は、2つの異なるメッセージ⁠ ⁠${\displaystyle m_{1}}$ と⁠ ⁠${\displaystyle m_{2}}$ を見つけます。従来の衝突攻撃では、攻撃者はどちらのメッセージの内容も制御できず、アルゴリズムによって任意に選択されます。 ${\displaystyle ハッシュ(m_{1})=ハッシュ(m_{2})}$

特定のハッシュ関数に暗号解析を適用することで、より効率的な攻撃が可能になります。衝突攻撃が発見され、誕生日攻撃よりも高速であることが判明すると、ハッシュ関数はしばしば「壊れている」と非難されます。NISTハッシュ関数競争は、 MD5 ^{[ 1 ]}とSHA-1という2つの非常に一般的に使用されているハッシュ関数に対する衝突攻撃の公開によって主に引き起こされました。MD5に対する衝突攻撃は大幅に改良され、2007年現在では一般的なコンピュータでわずか数秒で実行可能です^{[ 2 ]} 。このようにして生成されたハッシュ衝突は通常、一定長で大部分が非構造化であるため、広く普及している文書形式やプロトコルへの攻撃に直接適用することはできません。

しかし、多くのフォーマットに存在する動的な構造を悪用することで、回避策を講じることが可能です。この方法では、ハッシュ値が一致するように、可能な限り類似した2つの文書が作成されます。一方の文書を認証機関に提示して署名を依頼し、その署名をもう一方のファイルにコピーします。このような悪意のある文書は、同じ文書内に2つの異なるメッセージを含みますが、ファイルに微妙な変更を加えることで、条件に応じてどちらか一方を表示します。

• PostScriptなどの一部のドキュメント形式やMicrosoft Wordのマクロには条件構文があります。^{[ 3 ] [ 4 ]} (if-then-else)を使用すると、ファイル内の特定の場所に特定の値があるかどうかをテストして、表示内容を制御できます。
• TIFFファイルには切り取られた画像を含めることができ、ハッシュ値に影響を与えずに画像の別の部分が表示されます。^{[ 4 ]}
• PDFファイルは、色の値を使った衝突攻撃に対して脆弱であり（例えば、一方のメッセージのテキストは背景に溶け込む白色で表示され、もう一方のメッセージのテキストは暗い色で表示される）、これを変更することで署名された文書の内容が変更される可能性があります。^{[ 4 ]}

選択プレフィックス衝突攻撃

衝突攻撃の拡張として、マークル・ダムゴールハッシュ関数に特有の選択プレフィックス衝突攻撃があります。この場合、攻撃者は任意の異なる2つの文書を選択し、異なる計算値を付加することで、文書全体のハッシュ値が等しくなるようにすることができます。この攻撃は通常より困難で、nビットのハッシュは2 ^(n/2)+1ステップで解読可能ですが、従来の衝突攻撃よりもはるかに強力です。

数学的に言えば、2 つの異なるプレフィックスp ₁、p ₂が与えられた場合、攻撃はhash ( p ₁ s ₁ ) = hash ( p 2 s ₂ )となる2 つのサフィックスs ₁とs _{2を見つけ}ます(ここで は連結演算です)。

特定のハッシュ関数に暗号解析を適用することで、より効率的な攻撃も可能になります。2007年には、MD5に対する選択プレフィックス衝突攻撃が発見されました。この攻撃では、MD5関数を約2.50回評価する必要がありました。この論文では、異なるドメイン名に対してハッシュ値が衝突する2つのX.509証明書も示されています^。これは、あるドメインの証明書に署名を依頼し、その証明書（特に署名）を用いて別のドメインになりすますための新たな不正証明書を作成できることを意味します。^{[ 5 ]}

2008年12月、セキュリティ研究者のグループが偽造されたX.509署名証明書を公開し、MD5ハッシュ関数に対するプレフィックス衝突攻撃を利用して証明機関を偽装できるという現実世界の衝突攻撃が発表されました。これは、攻撃者が中間者となり、 SSLで保護された任意のウェブサイトを偽装し、電子商取引を保護するためにすべてのウェブブラウザに組み込まれている証明書検証を破ることができることを意味します。不正な証明書は、実際の証明機関によって取り消すことができない可能性があり、有効期限を任意に偽造することもできます。MD5は2004年には非常に脆弱であることがわかっていましたが、^{[ 1 ]}証明機関は2008年12月にもMD5検証済みの証明書に署名する用意があり、^{[ 6 ]}少なくとも1つのMicrosoftコード署名証明書は2012年5月にもMD5を使用していました。

Flameマルウェアは、選択されたプレフィックス衝突攻撃の新しいバリエーションをうまく利用して、侵害されたMD5アルゴリズムをまだ使用しているMicrosoftルート証明書によるコンポーネントのコード署名を偽装しました。 ^{[ 7 ] [ 8 ]}

2019年に研究者らは、計算複雑度が2の^66.9乗から2の^69.4乗で、コストが10万ドル未満であるSHA-1に対する選択プレフィックス衝突攻撃を発見した。 ^{[ 9 ] [ 10 ] 2020年に研究者らは、SHA-1に対する選択プレフィックス衝突攻撃の計算複雑度を2の63.4}乗にまで削減した。^{[ 11 ]}

攻撃シナリオ

暗号ハッシュ関数の多くの応用は衝突耐性に依存していないため、衝突攻撃はセキュリティに影響を与えません。例えば、HMACは脆弱ではありません。^{[ 12 ]}この攻撃が有効になるためには、攻撃者はハッシュ関数への入力を制御できなければなりません。

デジタル署名

デジタル署名アルゴリズムは大量のデータに効率的に署名できないため、ほとんどの実装ではハッシュ関数を用いて、署名するデータ量を一定サイズに縮小（「圧縮」）します。デジタル署名方式は、基礎となるハッシュ関数が実質的に破られると、ハッシュ衝突に対して脆弱になることがよくあります。ランダム化（ソルト化）ハッシュ法などの手法は、より困難な原像攻撃を必要とすることで、署名に要する時間を稼ぐことができます。^{[ 13 ]}

通常の攻撃シナリオは次のようになります。

1. マロリーは、ハッシュ値が同一（衝突）である2つの異なる文書AとBを作成します。マロリーは、ボブを騙して文書Bをアリスからのものとして受け入れさせようとします。
2. マロリーは文書 A をアリスに送信し、アリスは文書の内容に同意し、そのハッシュに署名して、その署名をマロリーに送信します。
3. マロリーは文書 A の署名を文書 B に添付します。
4. 次に、マロリーは署名と文書 B をボブに送信し、アリスが B に署名したと主張します。デジタル署名が文書 B のハッシュと一致するため、ボブのソフトウェアは置換を検出できません。

2008年、研究者たちはこのシナリオを用いてMD5に対する選択プレフィックス衝突攻撃を仕掛け、不正な認証局証明書を作成しました。彼らは2つのバージョンのTLS公開鍵証明書を作成しました。1つは正当な証明書のように見え、RapidSSL認証局に署名のために提出されました。同じMD5ハッシュを持つもう1つのバージョンには、ウェブブラウザに任意の他の証明書を発行するための正当な認証局として受け入れるよう指示するフラグが含まれていました。^{[ 14 ]}

ハッシュフラッディング

ハッシュフラッディング（ HashDoS ^{[ 15 ]}とも呼ばれる）は、ハッシュ衝突を利用してハッシュテーブル検索の最悪ケース（線形プローブ）実行時間を悪用するサービス拒否攻撃である。 ^{[ 16 ]}これは、2003年にアルゴリズム複雑性攻撃の例として最初に説明された。^{[ 17 ]}このような攻撃を実行するために、攻撃者は同じ値にハッシュされる複数のデータをサーバーに送信し、サーバーに低速な検索を実行させようとする。ハッシュテーブルで使用されるハッシュ関数の主な焦点はセキュリティではなく速度であったため、ほとんどの主要なプログラミング言語が影響を受け、^{[ 17 ]}このクラスの新しい脆弱性は、最初の発表から10年経った今でも依然として出現している。^{[ 16 ]}

ハッシュ関数を過度に複雑にすることなくハッシュフラッディングを防止するため、新しい鍵付きハッシュ関数が導入されました。これらの関数は、鍵が不明な限り衝突を発見しにくいというセキュリティ上の目的を持っています。これらの関数は以前のハッシュよりも遅くなる可能性がありますが、それでも暗号ハッシュよりもはるかに計算が容易です。2021年現在、Jean-Philippe AumassonとDaniel J. BernsteinによるSipHash (2012) は、このクラスで最も広く使用されているハッシュ関数です。^{[ 18 ]}（鍵なしの「単純な」ハッシュは、アプリケーションのハッシュテーブルが外部から制御できない限り、安全に使用できます。）

（部分的な）プリイメージ攻撃を用いてブルームフィルタを埋める同様の攻撃を実行することが可能である。^{[ 19 ]}

参照

• パズルへの親しみやすさ

参考文献

1. Xiaoyun Wang、Dengguo Feng、Xuejia Lai、Hongbo Yu：「ハッシュ関数MD4、MD5、HAVAL-128、RIPEMDの衝突」、Cryptology ePrint Archive Report 2004/199、2004年8月16日、2004年8月17日に改訂。2008年7月27日閲覧。
2. Stevens, MMJ (2007年6月). MD5の衝突について(PDF) (修士). アイントホーフェン工科大学. [...] 推奨IHVでは、約2回の^24.1圧縮でMD5の衝突を検出でき、2.6GHz Pentium 4では約6秒かかります。
3. Magnus Daum; Stefan Lucks . 「ハッシュ衝突（毒メッセージ攻撃）」 . Eurocrypt 2005 rump session . 2010年3月27日時点のオリジナルよりアーカイブ。
4. マックス、ゲプハルト;イリース、ゲオルグ。 Schindler、Werner (2005 年 10 月 31 日)、A Note on the Practical Value of Single Hash Collisions for Special File Formats (PDF)、Bundesamt für Sicherheit in der Informationstechnik、2008 年 9 月 17 日のオリジナル(PDF)からアーカイブ
5. Marc Stevens、Arjen Lenstra、Benne de Weger (2007年11月30日). 「MD5の選択プレフィックス衝突と異なるIDのX.509証明書の衝突」 . Advances in Cryptology - EUROCRYPT 2007. Lecture Notes in Computer Science. Vol. 4515. p. 1. Bibcode : 2007LNCS.4515....1S . doi : 10.1007/978-3-540-72540-4_1 . ISBN 978-3-540-72539-8。
6. Alexander Sotirov; et al. (2008-12-30). 「不正なCA証明書の作成」 . 2012-04-18時点のオリジナルよりアーカイブ。2009-10-07閲覧。
7. 「Microsoft、セキュリティアドバイザリ2718704をリリース」。Microsoft 。 2012年6月3日。 2012年6月7日時点のオリジナルよりアーカイブ。 2012年6月4日閲覧。
8. Marc Stevens (2012年6月7日). 「CWI暗号解析者がFlame Spyマルウェアに新たな暗号攻撃の亜種を発見」 Centrum Wiskunde & Informatica . 2012年6月9日閲覧。
9. Catalin Cimpanu (2019年5月13日). 「SHA-1衝突攻撃は今や実際に実行可能であり、差し迫った危険となっている」 . ZDNet .
10. Gaëtan Leurent; Thomas Peyrin (2019年5月6日). 「衝突から選択プレフィックス衝突への応用：完全なSHA-1への応用」(PDF) .
11. Gaëtan Leurent、Thomas Peyrin (2020年1月5日). 「SHA-1は大混乱 - SHA-1における最初の選択プレフィックス衝突とPGP Web of Trustへの応用」(PDF) .
12. 「ハッシュ衝突Q&A」。Cryptography Research Inc. 2005年2月15日。2008年7月17日時点のオリジナルよりアーカイブ。HMAC構築におけるハッシュ関数の使用方法のため、これらの最近の攻撃で使用されている手法は適用されない。
13. Shai HaleviとHugo Krawczyk、「ランダムハッシュとデジタル署名」 、 2009年6月20日アーカイブ、 Wayback Machine
14. アレクサンダー・ソティロフ;マーク・スティーブンス;ジェイコブ・アッペルバウム。アリジェン・レンストラ。デビッド・モルナー;ダグ・アルネ・オスヴィク;ベン・デ・ウェガー (2008 年 12 月 30 日)。MD5 は今日では有害であると考えられています。カオスコミュニケーションコングレス2008。
15. Falkenberg, Andreas; Mainka, Christian; Somorovsky, Juraj; Schwenk, Jörg (2013). 「WebサービスにおけるDoS侵入テストへの新たなアプローチ」. 2013 IEEE 第20回国際Webサービス会議. pp.  491– 498. doi : 10.1109/ICWS.2013.72 . ISBN 978-0-7695-5025-1. S2CID  17805370 .
16. 「Node.js のハッシュフラッディング脆弱性について... · V8 」。v8.dev 。
17. Scott A. CrosbyとDan S. Wallach. 2003. 「アルゴリズム的複雑性攻撃によるサービス拒否」。第12回USENIXセキュリティシンポジウム会議録 - 第12巻 (SSYM'03)、第12巻。USENIX Association、カリフォルニア州バークレー、3-3ページ。
18. Jean-Philippe Aumasson & Daniel J. Bernstein (2012-09-18). 「SipHash: 高速なショートインプットPRF」(PDF) .
19. Gerbet, Thomas; Kumar, Amrit; Lauradoux, Cédric (2014年11月12日).ブルームフィルタにおける悪の選択の力（報告書）. INRIA Grenoble.

外部リンク

• 「意味のある衝突」、暗号ハッシュ衝突を悪用する攻撃シナリオ
• 高速MD5およびMD4衝突生成器- Bishop Fox（旧称Stach & Liu）。Xiaoyun Wang氏が開発した手法を改良した画期的な新コードを用いて、MD4およびMD5ハッシュ衝突を生成します。1.6GHzのPentium 4プロセッサを使用することで、MD5衝突は平均45分、MD4衝突は平均5秒で生成できます。初版は2006年6月22日です。