IT用語集 2024/11/21

誕生日攻撃とは？ 10分でわかりやすく解説

コラム

誕生日攻撃（Birthday attack）は、ハッシュ関数で衝突を見つける計算量が直感より小さくなる性質を利用する攻撃です。主に問題になるのは、電子署名、証明書、改ざん検知のように衝突耐性へ依存する用途です。逆に、パスワード保存で中心になるのは総当たりや辞書攻撃への耐性であり、誕生日攻撃と同じ軸では整理しません。

誕生日攻撃とは何か

誕生日攻撃とは、暗号学で使うハッシュ関数に対して、同じハッシュ値を持つ異なる入力を見つける攻撃手法です。狙いは衝突であり、ハッシュ値から元データを求める原像探索や、ある入力と同じハッシュ値を持つ別入力を探す第二原像探索とは別に扱います。

なぜ成立しやすく見えるのか

名称は誕生日のパラドックスに由来します。23人集まると同じ誕生日の組が生じる確率が50％を超える、という性質と同じ発想で、ハッシュ値も試行回数が増えるほど一致が起きやすくなります。nビットのハッシュ値では、衝突探索の計算量は概ね 2^(n/2) 回規模で見積もられます。

ハッシュ関数で区別しておきたい3つの性質

ハッシュ関数は、任意長のデータを固定長の値へ変換します。用途を誤らないためには、次の性質を分けて理解しておく必要があります。

衝突耐性（collision resistance）：異なる2つの入力から同じハッシュ値を見つけにくい性質
原像困難性（preimage resistance）：与えられたハッシュ値から元の入力を見つけにくい性質
第二原像困難性（second-preimage resistance）：ある入力と同じハッシュ値を持つ別入力を見つけにくい性質

誕生日攻撃が直接削るのは、主に衝突耐性です。

攻撃の流れ

攻撃者が多数の入力候補を用意する
各入力のハッシュ値を計算する
同じハッシュ値になった組を探す
衝突が見つかるまで試行を続ける

どこで問題になり、どこでは主題になりにくいか

問題になりやすい用途：電子署名、証明書署名、ファイル配布時の改ざん検知、衝突耐性を前提にした識別処理
主題になりにくい用途：パスワード保存、総当たり耐性の設計、ソルトやKDFの選定

つまり、同じ「ハッシュを使う処理」でも、何を守りたいかで見るべき性質が変わります。

誕生日攻撃が問題になる場面

電子署名

署名は文書そのものではなく、文書から計算したハッシュ値を対象に行う実装が一般的です。そのため、攻撃者が衝突する2つの文書を用意できると、正当な文書に対する署名を別文書へ流用できる余地が生じます。

証明書や署名基盤

証明書発行や署名基盤でも、衝突耐性が弱いハッシュを前提にすると、真正性の前提が崩れます。証明書そのものだけでなく、証明書署名に使うワークフロー全体で、どのハッシュを前提にしているかを確認する必要があります。

改ざん検知と整合性確認

ファイルやメッセージの整合性確認で、同じハッシュ値なら同じ内容とみなす運用をしている場合、衝突が実用域に入ると検知をすり抜けられる可能性があります。特に、古いハッシュ関数を互換性だけを理由に残している環境は見直し対象になります。

ハッシュ値を短く切り詰める設計

ハッシュ値を独自仕様で短く切り詰めると、衝突耐性もその長さに応じて下がります。たとえば96ビットまで切り詰めたダイジェストでは、衝突耐性は概ね48ビット相当として見積もる必要があります。識別子を短くしたいという都合だけでダイジェスト長を削ると、誕生日攻撃に対する余裕まで削ることになります。

パスワード保存と誕生日攻撃を切り分ける

パスワード保存で中心になるリスクは、衝突よりもオフラインでの総当たりです。攻撃者が狙うのは「同じハッシュ値の別入力」ではなく、「本人のパスワードそのもの」や、それと同等に通る候補です。

このため、パスワード保存の対策は、衝突耐性の議論だけでは足りません。ソルトを付け、適切な一方向の鍵導出関数を使い、1回ごとの推測コストを上げる設計が軸になります。誕生日攻撃を説明する記事で、パスワード保存まで同じ論理でまとめると論点がずれます。

誕生日攻撃への対策

衝突耐性が必要な用途で古いハッシュへ依存しない

電子署名、証明書、改ざん検知のように衝突耐性が前提になる用途では、MD5のような古いハッシュを使い続けない方針へ切り替えます。SHA-1も、少なくとも新規の署名生成に依存しない設計へ移し、SHA-256やSHA-3系を候補に据えて整理するのが安全です。

出力長を削りすぎない

誕生日攻撃の計算量は出力長に左右されます。短いダイジェストや、用途に対して余裕のない切り詰めは避け、必要な衝突耐性から逆算して長さを決めます。

パスワード保存の対策を別軸で設計する

パスワード保存では、ソルトと適切なKDFを用いてオフライン攻撃のコストを引き上げます。ここでの論点は「衝突を防ぐこと」ではなく、「推測を高コストにすること」です。

棚卸しと移行計画を先に作る

どのシステムで、どのハッシュ関数を、何の目的で使っているかを一覧化する
署名、証明書、改ざん検知など、衝突耐性が前提の用途から優先して見直す
互換性の都合で残す箇所は、残置理由と廃止時期を明文化する

まとめ

誕生日攻撃は、ハッシュ関数の衝突探索が 2^(n/2) 回規模で現実味を帯びるという性質を利用する攻撃です。確認すべき点は3つです。第一に、対象の用途が衝突耐性へ依存しているか。第二に、古いハッシュや短いダイジェストを残していないか。第三に、パスワード保存のような別問題を同じ説明で混同していないか。署名、証明書、改ざん検知でハッシュを使っている環境では、この3点を基準に棚卸しすると論点を外しにくくなります。