衝突攻撃

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

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

古典的な衝突攻撃

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

より一般的に言えば：

選択された接頭辞の衝突攻撃

2つの異なる接頭辞p ₁とp ₂が与えられたとき、ハッシュ( p ₁ ∥ s ₁ ) =ハッシュ( p ₂ ∥ s ₂ )となるような2つの接尾辞s ₁とs ₂を見つけます。ここで、∥ は連結演算を表します。

対称鍵暗号が総当たり攻撃に弱いのと同様に、すべての暗号学的ハッシュ関数は、誕生日攻撃による衝突に対して本質的に脆弱です。誕生日問題のため、これらの攻撃は総当たり攻撃よりもはるかに高速です。n ビットのハッシュは、 2 n ^{/2 回の時間}ステップ (ハッシュ関数の評価)で解読できます。

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

特定のハッシュ関数に対して暗号解読を用いることで、より効率的な攻撃が可能になる。衝突攻撃が発見され、誕生日攻撃よりも高速であることが判明すると、ハッシュ関数はしばしば「破られている」と非難される。NISTハッシュ関数コンペティションは、MD5 ^{[ 1 ]}とSHA-1という 2 つの非常に一般的なハッシュ関数に対する衝突攻撃の発表が主なきっかけとなった。MD5 に対する衝突攻撃は非常に進歩しており、2007 年時点では、通常のコンピュータでわずか数秒で実行できる。^{[ 2 ]}このように作成されたハッシュ衝突は通常、長さが一定で、構造化されていないため、広く普及しているドキュメント形式やプロトコルへの攻撃に直接適用することはできない。

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

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

衝突攻撃の拡張として、選択プレフィックス衝突攻撃があります。これは、 Merkle–Damgårdハッシュ関数に特有の攻撃手法です。この攻撃では、攻撃者は任意の異なる2つの文書を選択し、計算された異なる値を付加することで、文書全体のハッシュ値を同じにすることができます。この攻撃は通常、より困難で、nビットのハッシュは2 ^(n/2)+1ステップで破られる可能性がありますが、古典的な衝突攻撃よりもはるかに強力です。

数学的に言うと、2つの異なる接頭辞p ₁、p ₂が与えられた場合、攻撃はhash ( p ₁ ∥ s ₁ ) = hash ( p ₂ ∥ s ₂ )となるような2つの接尾辞s ₁とs _{2 を}見つけます(ここで ∥ は連結演算です)。

特定のハッシュ関数に対して暗号解読を用いることで、より効率的な攻撃も可能になります。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年、研究者らはSHA-1に対する選択プレフィックス衝突攻撃を発見した。その計算複雑度は2 ^66.9から2 ^69.4の間で、コストは10万米ドル未満であった。^{[ 9 ] [ 10 ]} 2020年、研究者らはSHA-1に対する選択プレフィックス衝突攻撃の複雑度を2 ^63.4に削減した。^{[ 11 ]}

暗号学的ハッシュ関数の多くのアプリケーションは衝突耐性に依存していないため、衝突攻撃はそれらのセキュリティに影響を与えません。たとえば、HMAC は脆弱ではありません。^{[ 12 ]}攻撃が有効であるためには、攻撃者はハッシュ関数への入力を制御できる必要があります。

• パズルの親しみやすさ

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