ハッシュ衝突攻撃の系譜（MD5・SHA-1 はなぜ破られたか）

ハッシュが「破られた」とは何が壊れたのか

暗号学的ハッシュ関数には3つの安全性要件があります。MD5 や SHA-1 が「破られた」と言うとき、実際に壊れたのはそのうちのどれなのかを最初に切り分けておくと、なぜ署名は危険でパスワード保存の文脈では事情が違うのか、までが正確に理解できます。要件の定義は 暗号の基礎 でも触れた通りですが、ここでは攻撃の難易度差まで踏み込みます。

ここで決定的なのは、衝突耐性だけが、攻撃者が両方のメッセージを自由に選べる点です。原像・第二原像は標的のハッシュ値やメッセージが先に固定されますが、衝突は攻撃者が2つとも作り込めるため、誕生日のパラドックスが効いて計算量が一気に下がります。

誕生日攻撃：なぜ n ビットが n/2 ビットになるのか

「23人いれば誕生日が一致する確率が50%を超える」という誕生日のパラドックスが、衝突探索の数理そのものです。出力が n ビットなら取り得る値は 2^n 通りですが、ランダムに約 2^(n/2) 個のメッセージをハッシュした時点で、その中のどこかに同じ値の対が現れる確率が約 50% に達します。

出力空間のサイズ N = 2^n
k 個ハッシュしたとき、全て相異なる確率 ≈ exp( -k(k-1) / (2N) )
衝突が出る確率が 1/2 になる k ≈ 1.1774 * sqrt(N) ≈ 2^(n/2)

直感的には、k 個の要素からは k(k-1)/2 通りの対が作れ、各対が衝突する確率が 1/N。期待衝突数が 1 を超えるのは k ≈ sqrt(N) のときです。つまり総当たりの平方根まで落ちる。

注意すべきは、2^64 や 2^80 はあくまで汎用の誕生日攻撃の上限だという点です。MD5 や SHA-1 が現実に破られたのは、ここからさらに内部構造を突く差分解読で計算量を削ったからです。

差分解読：構造を突いて誕生日限界を割り込む

MD5・SHA-1 はどちらも Merkle–Damgård 構造 で、固定長の圧縮関数を反復します。**差分解読（differential cryptanalysis）**は、入力に特定の差分（XOR 差）を与えたとき、それが圧縮関数の各ラウンドをどう伝播するかを追い、**最終的に差分が打ち消し合って出力差がゼロになる差分経路（differential path）**を構築する手法です。

1. メッセージ対 (M, M') の差分 ΔM = M XOR M' を設計
2. 各ラウンドで内部状態の差分 ΔH がどう変化するかを追跡
3. ローテーション・加算・非線形関数で差分が「都合よく相殺」する
   経路を、確率を最大化しながら探索
4. その経路を満たす実際のメッセージ対を、条件を解いて構成
   → H(M) = H(M') を直接作れる（誕生日攻撃を経由しない）

王小雲（Wang Xiaoyun）らの 2004〜2005 年の成果が転換点でした。MD5 については 2^39 回程度（当時のPCで数時間〜数分）で衝突を生成し、SHA-1 についても 2^69（後に 2^63）と、誕生日限界の 2^80 を大きく下回る攻撃経路を示しました。理論限界より速いという事実こそが、これらの関数が「設計として壊れた」ことの証拠です。

chosen-prefix collision：任意の前半を選べる衝突

実害を決めたのは衝突の自由度です。2種類を区別します。

• identical-prefix collision（共通接頭辞衝突）：両メッセージが同じ接頭辞 P を共有し、攻撃者が作った衝突ブロックを続ける。形は P || C1 と P || C2。前半は同一でなければならない。
• chosen-prefix collision（選択接頭辞衝突）：攻撃者が任意に選んだ異なる2つの接頭辞 P1、P2 から出発し、それぞれに別の衝突ブロックを付けて全体のハッシュを一致させる。形は P1 || C1 と P2 || C2。

Merkle–Damgård の反復性が鍵です。P1 と P2 を処理し終えた時点の内部状態（chaining 値）は普通は異なりますが、その差分を打ち消す衝突ブロック対 (C1, C2) を差分解読で構成できれば、以降の処理は完全に一致し、最終ハッシュも一致します。P1・P2 を自由に選べるので、攻撃者は意味のある2つの文書（たとえば内容の異なる2枚の証明書）を衝突させられる。

state(P1) ──┐                          ┌── 同じ chaining 値
            ├ 差分 Δ を C1,C2 で吸収 →─┤  → 以降の追記が共通なら
state(P2) ──┘                          └── 最終ハッシュも一致

MD5 の chosen-prefix collision は 2007〜2009 年に Stevens・Lenstra・de Weger らが確立しました。これが、現実のインフラを揺るがす攻撃の弾になります。

系統と時系列：MD5 から SHA-1 崩壊まで

衝突攻撃の発展を年代・分岐で整理します。重要なのは「衝突生成の理論」と「現実の悪用」が交互に駆動した点です。

Flame（2012）：MD5 衝突が国家級攻撃に化けた瞬間

Flame は中東を標的にした高度なスパイ用マルウェアです。最も衝撃的だったのは、Windows Update の仕組みを悪用するために、Microsoft の正規 CA から発行された証明書を出発点に、MD5 の chosen-prefix collision で偽のコード署名証明書を捏造した点でした。当時 Microsoft の一部のライセンスサービスがまだ MD5 ベースの証明書を発行しており、攻撃者は正規証明書と同じ MD5 ハッシュを持つ偽証明書を作成。これにより、Microsoft が署名したかのように見える悪性コードを Windows に受け入れさせ、LAN 内で正規アップデートを装って感染を広げました。署名の信頼が PKI の連鎖に依存している以上、その根のハッシュが衝突可能なら連鎖全体が崩れる、という教訓です。

SHAttered（2017）：SHA-1 初の実衝突

Google と CWI が公開した SHAttered は、同じ SHA-1 ハッシュを持つ2つの異なる PDF ファイルを実際に生成して見せました。計算量は約 2^63.1 で、内訳は約 900 京回の SHA-1 計算。GPU 換算で膨大なコストですが「不可能」ではないことを証明しました。これは identical-prefix collision で、2つの PDF は共通接頭辞の後に衝突ブロックを仕込み、PDF の描画オブジェクト切り替えの仕掛けで「同じハッシュ・異なる表示内容」を実現していました。

衝突できても原像はできない：射程の限界

ここまでの攻撃はすべて衝突耐性に対するもので、原像耐性は別問題です。攻撃者は「同じハッシュを持つ2つを自分で作る」ことはできても、「世の中にある特定のハッシュ値から元データを逆算する」ことは依然 2^n に近い困難さを保ちます。MD5・SHA-1 に対する実用的な原像攻撃は今も存在しません。

この非対称性が用途別のリスクを分けます。

移行と防御の実務

対策は単純で、署名・証明書・改ざん検知の用途では MD5・SHA-1 を SHA-256 以上（または SHA-3）へ移行すること。誕生日攻撃の 2^(n/2) を踏まえれば、衝突耐性を 128 ビット以上確保するには最低 256 ビット出力が要ります。主要 CA は 2017 年までに SHA-1 証明書の発行を停止し、ブラウザも SHA-1 証明書を拒否済みです。

完全な置き換えがすぐにできない場合の中間策として、SHAttered の著者らは衝突ブロックの特徴を検知する sha1collisiondetection（counter-cryptanalysis）を公開しており、Git なども導入しています。ただしこれは延命策にすぎません。新規設計では SHA-256 を既定とし、将来の暗号アジリティを見据えるなら 暗号アルゴリズムの系統樹 で整理した世代交代の観点で選定するのが筋です。

ハッシュ衝突攻撃の系譜は、「理論上の弱点」が放置されれば必ず「現実の攻撃」に育つことの教科書例です。誕生日攻撃で半減した安全余裕を、差分解読がさらに削り、chosen-prefix が実害の扉を開けた――この連鎖を辿れると、なぜ暗号の世界が「破られる前に移行する」予防原則で動くのかが腑に落ちます。