ハッシュ衝突の理解

ハッシュ衝突とは、2つの異なる入力が同じハッシュ出力を生成することです。ハッシュ関数は無限の入力空間を有限の出力空間にマッピングするため、衝突は数学的に必ず存在します。セキュリティの問題は、攻撃者がそれを効率的に見つけられるかどうかです。

誕生日のパラドックス:

誕生日のパラドックスは、わずか23人のグループで2人が同じ誕生日を共有する確率が50%であると述べます。ハッシュに適用すると、nビットハッシュ関数では約2^(n/2)個の入力を試すと50%の確率で衝突が見つかります。MD5（128ビット）では2^64回の操作、SHA-256（256ビット）では2^128回の操作です。2^64（実行可能）と2^128（実行不可能）の差は莫大です。

衝突攻撃の種類:

古典的な衝突攻撃はhash(x) = hash(y)となる任意の2入力xとyを見つけます。原像攻撃は特定のターゲット値hにハッシュされる入力xを見つけます。第二原像攻撃は与えられた入力xと同じハッシュを持つ別の入力yを見つけます。衝突攻撃が最も容易で、原像攻撃が最も困難です。MD5では衝突攻撃は簡単ですが、原像攻撃はまだ非現実的です。この区別はHMACなど原像耐性のみを必要とするアプリケーションで重要です。

現実の衝突攻撃:

最も影響の大きいMD5衝突攻撃は、2008年のCWI Amsterdamの研究者による不正CA証明書の作成です。正規のエンドエンティティ証明書（署名のためにCAに提出）と悪意のあるCA証明書という、同じMD5ハッシュを持つ2つのX.509証明書を作成しました。

現行アルゴリズムの衝突耐性:

MD5：2004年以降破られており、数秒で衝突生成可能。SHA-1：2017年（SHAttered）以降実質的に破られている。SHA-256：既知の弱点なし。最善の攻撃は2^128操作の汎用誕生日攻撃。SHA-3：既知の弱点なし。異なる内部構造（スポンジ構造）がSHA-2固有の攻撃に対する多層防御を提供。