衝突攻撃 (Collision attack)

ハッシュ関数が衝突耐性を持つとは、同じ出力になる2つの異なるメッセージを現実的な手間では見つけられないということだ。誕生日のパラドックスにより、衝突の探索コストは出力空間の平方根程度で済む。理論上、128ビットのハッシュなら約2^64回の計算で衝突しうる。長期の安全性に256ビット出力が推奨されるのはそのためだ。

実際の攻撃も現れた。MD5は1996年から段階的に破られ、2004年にXiaoyun Wangらが衝突を作り出した。SHA-1は2017年、CWIとGoogleが同じハッシュを持つ2つのPDFファイルを公開して陥落した。教訓は単純で、相手が内容を選べる状況では、ハッシュ一致を文書の同一性の証拠にはできない。