衝突攻撃

暗号化において、暗号化ハッシュに対する衝突攻撃は、同じハッシュ値を生成する 2 つの入力、つまりハッシュ衝突を見つけようとします。これは、特定のターゲット ハッシュ値が指定される原像攻撃とは対照的です。

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

古典的な衝突攻撃

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

より一般的には:

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

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

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

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

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

ただし、多くの形式に存在する動的構造を悪用することで回避策が可能です。この方法では、同じハッシュ値を持つように、可能な限り類似した 2 つのドキュメントが作成されます。1 つのドキュメントを署名のために機関に提示し、その後、署名を他のファイルにコピーできます。このような悪意のあるドキュメントには、同じドキュメント内に 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 ₂ ‖ s ₂ )となる2 つのサフィックスs ₁とs ₂を見つけます(ここで、 ‖ は連結演算です)。

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

2008 年 12 月、セキュリティ研究者のグループが、MD5 ハッシュ関数に対するプレフィックス衝突攻撃を利用して証明機関になりすますために使用できる偽造X.509署名証明書を公開し、現実世界の衝突攻撃が発表されました。これは、攻撃者が中間者としてSSLで保護された任意の Web サイトになりすまし、電子商取引を保護するためにすべてのWeb ブラウザーに組み込まれている証明書検証を破壊できることを意味しました。不正な証明書は、実際の機関によって取り消すことができない可能性があり、有効期限を任意に偽造することもできます。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ハッシュを持つ2番目のバージョンには、任意の他の証明書を発行するための正当な機関としてそれを受け入れるようにWebブラウザに通知するフラグが含まれていた。^[14]

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

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

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

• パズルの親しみやすさ

• 「意味のある衝突」、暗号ハッシュ衝突を悪用する攻撃シナリオ
• 高速 MD5 および MD4 衝突ジェネレータ - Bishop Fox (旧 Stach & Liu)。Xiaoyun Wang が最初に開発した技術を改良した画期的な新しいコードを使用して、MD4 および MD5 ハッシュ衝突を作成します。1.6 GHz Pentium 4 を使用すると、MD5 衝突は平均 45 分で生成でき、MD4 衝突は平均 5 秒で生成できます。2006 年 6 月 22 日に最初にリリースされました。