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

UnsplashのLidya Nadaが撮影した写真      

誕生日攻撃（Birthday attack）は、ハッシュ関数で「衝突（collision）」を見つける計算量が、直感よりも小さくなる性質（誕生日のパラドックス）を利用する攻撃です。衝突耐性が弱いハッシュ関数を、電子署名や証明書、改ざん検知に使い続けると、偽造やなりすましのリスクにつながります。この記事では、誕生日攻撃の仕組みと、どこで問題になるのか、そして現実的な対策を整理します。

誕生日攻撃とは何か

誕生日攻撃とは、暗号学で使用されるハッシュ関数において、衝突（同じハッシュ値を持つ異なるデータ）を見つけるための攻撃手法の総称です。ここで重要なのは、誕生日攻撃が狙うのは「衝突」であり、ハッシュ値から元データを当てる「復元（preimage）」とは別の性質だという点です。

誕生日のパラドックスとの関連性

誕生日攻撃の名称は、「誕生日のパラドックス」に由来します。誕生日のパラドックスとは、ランダムに選ばれた23人のグループ内で誕生日が同じ人が少なくとも2人いる確率が50%を超える、という直感に反する現象です。この性質は、ハッシュ関数の衝突探索にも当てはまり、nビットのハッシュ値なら、概ね2^(n/2)回程度の試行で衝突が見つかり得る、という見積もりにつながります。

ハッシュ関数と衝突の概要

ハッシュ関数は、任意の長さのデータを固定長の値（ハッシュ値）に変換する関数です。代表的な用途には、改ざん検知（整合性確認）、電子署名、メッセージ認証、パスワード保存などがあります。ただし用途によって必要な性質が異なります。

• 衝突耐性（collision resistance）：異なる2つの入力で同じハッシュ値を作ることが困難
• 第二原像困難性（second-preimage resistance）：ある入力と同じハッシュ値を持つ別の入力を作ることが困難
• 原像困難性（preimage resistance）：ハッシュ値から元の入力を推測することが困難

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

誕生日攻撃の基本的な仕組み

誕生日攻撃は、ハッシュ関数の衝突を見つけるために、以下のような手順で行われます。

1. 攻撃者は、入力データを大量に生成する（ランダム、または工夫された生成）
2. 生成したデータに対してハッシュ値を計算する
3. ハッシュ値を比較し、同じ値（衝突）が出た組を探す
4. 衝突が発見されるまで繰り返す

誕生日攻撃では、出力がnビットのハッシュ関数なら、衝突探索の計算量が概ね2^(n/2)に下がる点がポイントです。これが短い出力長や古いアルゴリズムで問題になります。

攻撃が問題になる代表的な場面

誕生日攻撃（衝突探索）が現実のリスクになるのは、主に次のような場面です。

• 電子署名：衝突する2つの文書を用意し、署名の「使い回し」を狙う
• 証明書：ハッシュの衝突を利用して不正な証明書発行・なりすましを狙う議論につながる
• 改ざん検知：ファイル整合性確認に衝突耐性の弱いハッシュを使うと、改ざんを隠される恐れがある

一方で、パスワード保存の領域で重要なのは通常、衝突よりも総当たりや辞書攻撃に耐える設計（ソルト＋遅いKDF）です。誕生日攻撃を「パスワードが直接突破される」と結びつけて説明すると誤解が生まれるため、用途別に整理して理解する必要があります。

誕生日攻撃の脅威と影響

ハッシュ関数の安全性を脅かす危険性

衝突耐性が破られると、ハッシュ値が「指紋」として機能しにくくなります。特に、署名や改ざん検知のように「同じハッシュ＝同じ内容」と見なす設計では、深刻な影響が出ます。

データの完全性と真正性への影響

送信者と受信者がハッシュ値を照合して改ざん検知を行う場合、衝突が実用的になると、攻撃者が別内容のデータでも同じハッシュ値を作り、検知をすり抜ける恐れがあります。電子署名でも同様に、署名対象のハッシュが衝突すると、真正性の前提が揺らぎます。

パスワードなど認証情報との関係（誤解しやすい点）

パスワード保存における主要リスクは、衝突よりも総当たり（ブルートフォース）や辞書攻撃です。衝突攻撃が直接「パスワードを当てる」わけではありません。したがって対策は、衝突耐性の確保というより、ソルト付きで遅いパスワードハッシュ（例：bcrypt、scrypt、Argon2など）を使い、推測コストを上げることが基本になります。

暗号化通信の安全性に与える影響

ハッシュ関数は、電子署名、証明書、改ざん検知、メッセージ認証など幅広く使われます。衝突耐性の弱いハッシュを重要用途で使い続けると、偽造や改ざんの余地が広がります。運用上は、古いハッシュ（例：MD5、SHA-1）を「互換性のために残す」ことが、長期的に技術的負債になります。

誕生日攻撃への対策

誕生日攻撃への対策は、「何にハッシュを使っているか」で変わります。ここでは用途別に整理します。

衝突耐性の高いハッシュ関数へ移行する

衝突耐性が問題になる用途（署名、証明書、改ざん検知など）では、信頼性の高いハッシュアルゴリズムへ移行することが重要です。一般に、MD5やSHA-1のような古いアルゴリズムは避け、SHA-256やSHA-3などが選択肢になります。

出力長を十分に確保する

誕生日攻撃の計算量は出力長に依存するため、短いハッシュ値を安易に採用しないことが基本です。特に独自仕様でハッシュを切り詰める設計は、衝突探索を容易にします。

ソルトの位置づけを正しく理解する

ソルトはパスワード保存では非常に有効ですが、署名や改ざん検知の用途では「ソルトを付ければ衝突問題が解決する」という単純な話にはなりません。用途ごとに、必要な性質と対策を切り分けることが重要です。

パスワード保存は「衝突」ではなく「推測耐性」を上げる

パスワード保存では、強力なパスワード要件や多要素認証に加え、ソルト付きで遅いKDF（bcrypt、scrypt、Argon2など）を採用し、総当たりのコストを上げることが実務の基本です。「定期的な変更」は必ずしも安全性を上げるとは限らないため、組織の方針・脅威モデルに沿って設計します。

移行計画と棚卸し（運用面）

• どこでどのハッシュを使っているか（署名、整合性チェック、API、ログなど）を棚卸しする
• 互換性要件がある場合は、並行期間を設けて段階的に移行する
• 「古いハッシュが残る理由」を明文化し、期限を持って解消する

まとめ

誕生日攻撃は、ハッシュ関数の衝突探索が想像より少ない試行回数で成立し得る性質を利用する攻撃です。衝突耐性が弱いハッシュを署名や改ざん検知に使い続けると、偽造や改ざんのリスクが高まります。対策としては、衝突耐性の高いハッシュ関数への移行、十分な出力長の確保、用途別の設計（特にパスワード保存は推測耐性の向上）を組み合わせ、棚卸しと移行計画を含めて継続的に見直すことが重要です。

よくある質問（FAQ）

Q. 誕生日攻撃は「同じ誕生日の人が出る」話とどう関係しますか？

多数の試行をすると一致が起きやすいという性質が、ハッシュの衝突探索に当てはまるためです。

Q. 誕生日攻撃はハッシュ値から元のデータを復元する攻撃ですか？

いいえ。主に「衝突（別データで同じハッシュ値）」を見つける攻撃で、復元（原像探索）とは別です。

Q. なぜ2^(n/2)程度で衝突が見つかるのですか？

ハッシュの出力空間に対して試行回数が増えると、組み合わせの数が急増して一致が起きやすくなるためです。

Q. パスワード保存にも誕生日攻撃は効きますか？

一般に主要リスクは衝突ではなく総当たりです。対策はソルト付きで遅いKDFの採用が中心になります。

Q. MD5やSHA-1は使ってはいけませんか？

署名や改ざん検知など衝突耐性が重要な用途では避けるべきです。互換性があっても移行計画が必要です。

Q. SHA-256にすれば誕生日攻撃は完全に心配不要ですか？

衝突探索の計算量は大きくなりますが、運用や実装の問題が別に残ることがあります。用途に応じて設計します。

Q. ハッシュ値を短く切り詰めても大丈夫ですか？

推奨しません。出力長を短くすると誕生日攻撃の計算量が下がり、衝突が見つかりやすくなります。

Q. ソルトを付ければ衝突は防げますか？

パスワード保存には有効ですが、署名や改ざん検知の用途では「ソルトで解決」とは限りません。

Q. 電子署名で誕生日攻撃が問題になるのはなぜですか？

署名はハッシュ値に対して行われるため、衝突する2文書を用意されると署名の意味が崩れる恐れがあるためです。

Q. 企業で最初にやるべき対策は何ですか？

どこでどのハッシュを使っているかを棚卸しし、重要用途から安全なアルゴリズムへ移行計画を作ることです。