実際には、衝突は MD5 と SHA-1 の両方に記載されているものよりも簡単です。MD5 衝突は、 2 26.5操作に相当する時間で検出できます(ここで、1 つの「操作」は、短いメッセージでの MD5 の計算です)。攻撃の詳細と実装については、このページを参照してください(コードは私が書きました。64 ビット モードの 2.4 GHz Core2 x86 で平均 14 秒以内に衝突を検出します)。
同様に、SHA-1 に対する最もよく知られている攻撃は、2 69操作ではなく、約2 61操作です。これはまだ理論的なものですが (実際の衝突はまだ発生していません)、実現可能な範囲内です。
セキュリティへの影響については、通常、ハッシュ関数には次の 3 つのプロパティがあると言われています。
- 前像なし: y が与えられた場合、 h(x) = yとなるようなxを見つけることは現実的ではないはずです。
- 2 番目のプリイメージはありません: x 1が与えられた場合、h(x 1 ) = h(x 2 )となるようなx 2 ( x 1とは異なる)を見つけることは現実的ではありません。
- 衝突なし: h(x 1 ) = h(x 2 )となるようなx 1とx 2 (互いに異なる)を見つけることは不可能です。
nビット出力のハッシュ関数の場合、最初の 2 つのプロパティの 2 n 操作と、3 番目のプロパティの 2 n/2 操作で、一般的な攻撃 (ハッシュ関数の詳細に関係なく機能します)があります。与えられたハッシュ関数に対して、ハッシュ関数がどのように動作するかの特別な詳細を悪用することによって、対応する一般的な攻撃よりも速くプリイメージ、2 番目のプリイメージ、または衝突を見つける攻撃が見つかった場合、ハッシュ関数は次のようになります。壊れる"。
ただし、ハッシュ関数のすべての使用法が 3 つのプロパティすべてに依存しているわけではありません。たとえば、デジタル署名は、署名するデータをハッシュすることから始まり、ハッシュ値はアルゴリズムの残りの部分で使用されます。これはプリイメージとセカンド プリイメージに対する耐性に依存しますが、デジタル署名自体は衝突の影響を受けません。攻撃者が被害者によって署名されるデータを選択できる特定の署名シナリオでは、衝突が問題になる可能性があります (基本的に、攻撃者は衝突を計算し、被害者によって署名された 1 つのメッセージを持ち、署名が有効になります他のメッセージも同様です)。これは、署名を計算する前に、署名されたメッセージにいくつかのランダムなバイトを追加することによって打ち消すことができます (X.509 証明書のコンテキストで示された攻撃と解決策)。
HMAC セキュリティは、ハッシュ関数が満たさなければならない別の特性に依存しています。つまり、「圧縮関数」（ハッシュ関数が構築される基本ブリック）が疑似ランダム関数（PRF）として機能することです。PRF とは何かについての詳細は非常に専門的ですが、大まかに言えば、PRF はランダム オラクルと区別がつかないはずです。. ランダム オラクルは、ノーム、いくつかのサイコロ、大きな本を含むブラック ボックスとしてモデル化されています。いくつかの入力データで、gnome は (サイコロを使用して) ランダムな出力を選択し、入力メッセージとランダムに選択された出力を本に書き留めます。gnome は本を使用して、同じ入力メッセージをすでに見たかどうかをチェックします。もしそうなら、gnome は以前と同じ出力を返します。構造上、特定のメッセージに対するランダムなオラクルの出力については、試してみるまで何もわかりません。
ランダム オラクル モデルにより、PRF の呼び出しで HMAC セキュリティ証明を定量化できます。基本的に、この証明では、PRF を何度も呼び出さない限り HMAC を破ることはできないと述べています。「巨大」とは、計算上実行不可能であることを意味します。
残念ながら、ランダム オラクルがないため、実際にはハッシュ関数を使用する必要があります。PRF プロパティを持つハッシュ関数が実際に存在するという証拠はありません。現時点では、候補、つまり圧縮関数が PRF ではないことを (まだ) 証明できない関数しかありません。
圧縮関数が PRF の場合、ハッシュ関数は衝突に対して自動的に耐性があります。それが PRF の魔法の一部です。したがって、ハッシュ関数の衝突を見つけることができれば、内部圧縮関数が PRF ではないことがわかります。これは衝突を HMAC への攻撃に変えません。自由に衝突を生成できることは、HMAC の破壊には役立ちません。ただし、これらの衝突は、HMAC に関連付けられているセキュリティ証明が適用されないことを示しています。保証は無効です。それはラップトップ コンピューターとまったく同じです。ケースを開けても、必ずしもマシンが壊れるわけではありませんが、その後は自分でできます。
Kim-Biryukov-Preneel-Hong の記事では、HMAC に対するいくつかの攻撃、特に HMAC-MD4 に対する偽造攻撃が紹介されています。この攻撃は、MD4 の欠点 (その「弱点」) を悪用して、PRF ではないものにしています。MD4 で衝突を生成するために、同じ弱点の亜種が使用されました (MD4 は完全に壊れています。一部の攻撃は、ハッシュ関数自体の計算よりも速く衝突を生成します!)。したがって、衝突は HMAC 攻撃を意味するものではありませんが、両方の攻撃が同じソースを利用しています。ただし、偽造攻撃のコストは2 58であり、これは非常に高く (実際の偽造は行われず、結果はまだ理論上のものです)、HMAC から予想される耐性レベルよりも大幅に低いことに注意してください ( n-ビット出力、HMAC は最大2 n作業係数に耐える必要があります。n = MD4 の場合は 128)。
したがって、衝突自体が HMAC の弱点を意味するわけではありませんが、悪いニュースです。実際には、衝突が問題になるセットアップはほとんどありません。しかし、衝突がハッシュ関数の特定の使用法に影響を与えるかどうかを知ることは非常に難しいため、衝突が実証されたハッシュ関数を使い続けることは非常に賢明ではありません。
SHA-1 の場合、攻撃はまだ理論的なものであり、SHA-1 は広く展開されています。状況は次のように説明されています。
この主題に関する詳細については、まず、Menezes、van Oorschot、および Vanstone によるHandbook of Applied Cryptographyの第 9 章を読んでください。 、これはよく書かれた紹介ですが、「ハンドブック」ほど完全ではありません)。