衝突攻撃 – ウィキペディア

Posted on by
before-content-x4

a 衝突 同一のハッシュ値に示されている2つの異なるドキュメントを見つけることを目的とした暗号学的ハッシュ関数への攻撃です。 Primage攻撃とは対照的に、両方のドキュメント（したがってハッシュ値）は自由に選択可能です。そのような衝突が見つかった場合、これは、とりわけ、暗号化アプリケーションのハッシュ関数（データ暗号化、デジタル署名手順）が適切ではないことを意味します。このような衝突は、暗号学的要件を満たすために開発されていないハッシュ機能で簡単に見つけることができます。これの例は、CRC 32テスト合計です。「バッケルー」と「プラムレス」という言葉は両方ともテスト値につながります 4DDB0C25 。

after-content-x4

キーレスハッシュ関数に対する一般的な攻撃は、成功の高い可能性を達成するために名を冠した誕生日パラドックスを使用する誕生日攻撃です。この攻撃はすべてのハッシュ関数で可能であり、実験の数を大幅に減らします（考えられるハッシュ値の平方根まで）。この攻撃は常に可能であるため、他の攻撃が測定される比較値を形成します。ハッシュ関数に対する攻撃の成功は、誕生日攻撃よりも効率的でなければなりません。これを行うには、ハッシュ関数の弱点を利用する必要があります。

最も明白なアプローチの1つは、ドキュメントを持つことです

バツ {displaystyle x}

これを選択するには、ハッシュ値

と = h （ バツ ）） {displaystyle y = h（x）}

計算してから2番目のドキュメントを計算します

バツ ‘ {displaystyle x ‘}

ハッシュ値も検索します

と {displaystyle y}

もっている。このアプローチは、プライマージ攻撃に対応しています。 

 ナイベコリジョン （h）
     ランダムドキュメントxを選択します
     y：= h（x） 繰り返す ランダムドキュメントx '！= xを選択します それまで h（x '）= y 戻る （x、x '）

これにより、平均期間が得られます

after-content-x4
m {displaystyle m}

、それによって

m {displaystyle m}

考えられるハッシュ値の数はです。

例：SHA-1には常にバイナリ160ビット出力、つまり2があります 160 考えられるハッシュ値。したがって、このアルゴリズムはSHA-1で平均2で2でなければなりません 159 彼が衝突を見つけるまで繰り返しを実行します。 1秒あたり10億テストを作成するコンピューターの場合、用語は4.6・10です 最初に30 年。

誕生日攻撃では、はるかに高い成功の確率を達成できます。ここでは、ランダムに選択します

Q {displaystyle q}

ドキュメント

バツ 1{displaystyle x_ {1}}

それまで

バツ q{displaystyle x_ {q}}

、それぞれを計算します

と 1= h （ バツ 1）） {displaystyle y_ {1} = h（x_ {1}）}

それまで

と q= h （ バツ q）） {displaystyle y_ {q} = h（x_ {q}）}

そして、下にいるかどうかをテストします

と i{displaystyle y_ {i}}

2つは同じです。 

 バースデーコール （h）
     ランダムドキュメントX_1 ... X_Qを選択します ために i = 1 に Q
        y_i：= h（x_i）を計算する
     i、jをwith i！= jとy_i = y_jを見つけます 戻る （x_i、x_j）

ここでは、誕生日のパラドックスに似ています

m {displaystyle m}

考えられるハッシュ値は成功の確率を評価します

形成と推定の後、それはその1つに続きます

Q = 初め 、 18 de m{displaystyle q = 1 {、} 18cdot {sqrt {m}}}

ドキュメントは、の成功の確率にパターン化する必要があります p =½を取得します。

SHA-1の例では、これは1.18・2を意味します 80 ½の確率で衝突を見つけるには実験が必要です。 1秒あたり10億テストを作成するコンピューターの場合、ここでの用語は4.5・10です。 7 年。

ほとんどの標準化されたハッシュ関数は、Merkle-Damgård構造に基づいています。それらの構造のため、衝突がさらに衝突を作成することがわかった場合、つまり、同じハッシュ値のニュースペアが発見された場合は簡単です。衝突は、メッセージの開始が自由に選択可能であるMD5アルゴリズムでも知られています。これは、攻撃者が異なるコンテンツを持つ2つのドキュメントを作成できることを意味します。たとえば、彼は同じハッシュ値を持つ2つの証明書を作成できます。そのうちの1つは意図しない証明書であり、2番目の証明書は他の証明書を発行する権利があります。彼は現在、認定機関によって最初の署名を持っています。ただし、デジタル署名を使用すると、メッセージ全体は通常署名されていませんが、ハッシュ値のみです。また、攻撃者は2番目の署名を持っており、任意のキーに対して有効な証明書を作成できるようになりました。 [初め]

  • Claudia Eckert： ITセキュリティ：Concepts-Procedure-Protocols 。 Oldenbourg、ISBN 978-3-486-58270-3、 S. 349 。
  1. ↑ アレクサンダー・ソティロフら： MD5は今日有害であると考えました 。 2008年12月30日。

after-content-x4