読み方：しょうとつはっけんこんなんせい

衝突発見困難性【強衝突耐性】strong collision resistance

概要

衝突発見困難性とは、ハッシュ関数において、異なる二つの入力から同じハッシュ値が得られる組み合わせを現実的な計算時間で見つけることが極めて難しいという性質。暗号学的ハッシュ関数に求められる基本的な安全性要件の一つである。

ハッシュ関数とは、任意の長さのデータを受け取り、固定長の「ハッシュ値」に変換する関数である。同じ入力からは必ず同じ出力が得られる一方、出力の長さは有限であるため、理論上は異なる入力が同じハッシュ値を持つケース、すなわち「衝突」が必ず存在する。衝突発見困難性とは、この衝突を引き起こす入力の組を実際に発見することが現実的な計算能力では不可能に近いという性質を表している。

衝突発見困難性は「強衝突耐性」とも呼ばれ、「弱衝突耐性」（第二原像計算困難性）と区別される。弱衝突耐性が「ある特定の入力と同じハッシュ値を持つ別の入力を見つけられない」という性質であるのに対し、強衝突耐性はより厳しい条件である。攻撃者はどのような2つの入力の組み合わせでもよく、同じハッシュ値を持つペアを1組でも見つければ攻撃が成立するため、弱衝突耐性より破られやすい。

衝突発見困難性を破る攻撃手法として有力なのが「誕生日攻撃」である。これは確率論の「誕生日のパラドックス」に着想を得た総当たり攻撃で、ハッシュ値のビット長をnとすると、約2^n/2乗回の試行で衝突を発見できる。たとえばハッシュ値が128ビットであれば、2の64乗回程度の計算で衝突が見つかる可能性があることになる。

衝突発見困難性が破られた場合、デジタル署名やSSL/TLS証明書の偽造など、深刻なセキュリティ上のリスクが生じる。実際、MD5やSHA-1はこの性質が破られたことが実証されており、現在は暗号用途への使用が非推奨とされている。現代の暗号用途では、ビット数が半分になっても総当たりが困難な256ビット以上のハッシュ長を持つSHA-256やSHA-3などが推奨されている。