Skip to content
←

필사 모드: 誕生日のパラドックスとハッシュ衝突 — なぜ23人で半分が一致するのか

日本語
0%
정확도 0%
💡 왼쪽 원문을 읽으면서 오른쪽에 따라 써보세요. Tab 키로 힌트를 받을 수 있습니다.

はじめに — パーティーから始まる確率の話

部屋に23人が集まっているとしましょう。このうち2人の誕生日が同じである確率はどれくらいでしょうか。多くの人は「365日のうち23人なら……6%くらい?」と答えます。実際の答えは**50.7%**です。半分を超えます。

この結果があまりに直感に反するので「誕生日のパラドックス」という名前がつきました。実際にはパラドックスというより、私たちの直感が間違った問いに答えているために生じる錯覚です。そしてこの錯覚をきちんと理解すると、一見まったく無関係に見える問題が一本に貫かれます。UUIDはなぜ衝突しないのか、ハッシュは何ビットあれば安全か、ハッシュテーブルはいつ大きくなるべきか、gitはなぜSHA-1を捨てたのか。

この記事はパーティーの確率問題から出発し、その数学がどこまで伸びていくかを追います。実際にハッシュを作りながら感覚をつかみたいなら、このサイトのハッシュジェネレーターを一緒に開いておくとよいでしょう。

なぜ23人で50%なのか

肝心なのは、私たちが何を数えているかです。直感が思い浮かべる問いはこうです。「自分と誕生日が同じ人がいるか?」ところが実際の問いは違います。「どれか2人の誕生日が同じか?」

23人から作れる人のペアは何通りでしょうか。組み合わせです。

ペアの数 = C(23, 2) = 23 × 22 / 2 = 253通り

253ペアです。各ペアが互いに誕生日が同じである確率は1/365なので、253ペアもあれば、そのうちの1つが一致する余地は思ったより大きいのです。人数が増えるとき、人数は線形に(23, 24, 25……)増えますが、ペアの数はほぼ2乗で(およそn²/2で)増えます。私たちの直感は人数しか見ず、本当に重要なペアの数を見落とします。

正確な確率は余事象で計算します。「一致するペアが1つもない」確率を求めてから1から引くのです。

P(全員バラバラ) = 365/365 × 364/365 × 363/365 × ... × 343/365
P(少なくとも1組一致) = 1 − P(全員バラバラ)

n人のときこの値を計算すると次のようになります。

人数少なくとも1組が一致する確率
10約11.7%
20約41.1%
23約50.7%
30約70.6%
50約97.0%
70約99.9%

23人ですでに半分を超え、70人ならほぼ確実です。Pythonで直接確かめることもできます。

def birthday_prob(n, days=365):
    p_all_different = 1.0
    for i in range(n):
        p_all_different *= (days - i) / days
    return 1 - p_all_different

for n in (10, 20, 23, 30, 50, 70):
    print(n, round(birthday_prob(n) * 100, 1))

√Nの直感 — この記事の本当の主役

誕生日問題の具体的な数字よりもはるかに重要なのは、その裏に隠れた規則です。N個の可能な値からランダムに取り出すとき、おおよそ√N個ほど取り出すと衝突(同じ値が2つ)が現れ始める。

誕生日はN = 365で、√365 ≈ 19.1です。実際に50%を超える地点である23人が、この√Nの近くにあります。偶然ではありません。

なぜ√Nなのかをおおまかに見るとこうです。n個を取り出すとペアは約n²/2個でき、各ペアが衝突する確率は1/Nです。衝突ペアの期待個数は約n²/(2N)で、この値がおよそ1になる地点、つまり「もう衝突が1つくらい出てもおかしくない」地点がn ≈ √Nです。50%の確率を基準にもう少し正確に書くと次のようになります。

50%の衝突に必要な標本数 n ≈ 1.1774 × √N

この1つの近似が、この記事の残りすべてを支配します。覚えるべきはただ1つです。衝突はNではなく√Nで始まる。 空間が大きいからと安心してはならず、その平方根がいくつかを見なければなりません。

UUIDとハッシュへ

さてパーティーを離れてコンピュータへ行きます。ソフトウェアでは、私たちは常に「一意でなければならない識別子」を作ります。UUID、ハッシュ値、トークン。これらは事実上、とても大きな箱からランダムに値を取り出すのと同じです。だから誕生日問題の数学がそのまま当てはまります。

UUID version 4は122ビットのランダムなビットを持ちます(128ビットのうち数ビットをバージョンとバリアント表示に使うためです)。可能な値の数NはN = 2¹²²で、これはおよそ5.3 × 10³⁶です。これほど大きな空間で衝突が現実的に心配になるには、√N個、つまり約2.3 × 10¹⁸個のUUIDを生成する必要があります。

これがどれほど大きな数か感覚をつかみましょう。1秒に10億個(10⁹)のUUIDを休まず生成しても、50%の衝突確率に達するには数百年かかります。だから実務ではUUIDv4を「衝突しない」と安心して使います。厳密には衝突は可能ですが、確率が無視できるほど小さいのです。

ここで√Nの直感の威力が現れます。122ビット空間の安全性は122ビットではなく、その半分の61ビット分です。衝突耐性を考えるときは、常にビット数を半分に折って考えなければなりません。

ハッシュ衝突の確率を見積もる

暗号学的ハッシュ関数も同じ話です。ハッシュ関数は任意長の入力を固定長の出力に送ります。出力がbビットなら、可能なハッシュ値は2ᵇ個です。異なる入力が同じハッシュ値を持つのが衝突です。

誕生日近似をそのまま当てはめると、約2^(b/2)個の異なる入力をハッシュしたとき衝突確率が意味を持ち始めます。まとめるとこうです。

ハッシュ出力サイズ全空間 N衝突が心配になる地点 (約√N)
32ビット2³² ≈ 43億約2¹⁶ = 65,536個
64ビット2⁶⁴約2³² ≈ 43億個
128ビット2¹²⁸約2⁶⁴個
256ビット2²⁵⁶約2¹²⁸個

32ビットハッシュは、わずか6万5千個ほどの値で衝突が50%の確率で現れます。43億という空間の大きさに騙されてはいけない理由がこれです。実際の安全マージンはその平方根である6万5千に過ぎません。

とても小さい衝突確率を見積もる便利な公式もあります。Nが大きく、標本数nが√Nよりはるかに小さいとき、衝突確率はおおよそ次のようになります。

P(衝突) ≈ n² / (2N)

たとえば128ビットハッシュ(N = 2¹²⁸)に10億個(n = 10⁹ ≈ 2³⁰)の値を入れると、衝突確率は約(2³⁰)² / (2 × 2¹²⁸) = 2⁶⁰ / 2¹²⁹ = 2⁻⁶⁹です。事実上ゼロです。

なぜ128ビットで十分なのか

これで「なぜ128ビットなのか」に答えられます。128ビットのハッシュや識別子の衝突耐性は√N、つまり2⁶⁴回の試行の水準です。2⁶⁴はおよそ1.8 × 10¹⁹です。

この規模が物理的にどんな意味を持つか見ましょう。地球上でもっとも速いスーパーコンピュータを総動員して毎秒数兆回(約2⁴⁰)ハッシュを計算しても、2⁶⁴回に達するには数十万年かかります。ランダムな衝突に偶然出会う確率は実質的にゼロです。

ここで2種類の「衝突耐性」を区別しなければなりません。

  • 衝突耐性(collision resistance): 攻撃者が「どれか2つの入力」のハッシュが同じになるように探すこと。誕生日攻撃が当てはまり、難易度は2^(b/2)です。128ビットなら2⁶⁴。
  • 原像耐性(preimage resistance): 「与えられた特定のハッシュ値」に対応する入力を探すこと。ここは誕生日のトリックが効かず、難易度は2ᵇです。128ビットなら2¹²⁸。

つまり同じ128ビットでも「特定の値を破ること」は2¹²⁸ではるかに難しく、「どれでも衝突を見つけること」は2⁶⁴で相対的に易しいのです。だから強い衝突耐性が必要な場所では128ビットでは足りないと考え、256ビットを使います。SHA-256が256ビットを使うのは、まさにこの余裕(2¹²⁸の衝突耐性)を確保するためです。

ハッシュテーブル — 衝突をむしろ活用する場所

ここまで衝突は悪いことでした。しかしハッシュテーブルでは衝突は避けられない日常であり、むしろそれを前提に設計します。ここではハッシュ空間がわざと小さいからです。

ハッシュテーブルはキーをハッシュしたあと、その値をバケット数mで割った余りをインデックスに使います。

index = hash(key) % num_buckets

バケットがm個しかなければN = mで非常に小さいです。誕生日問題により、キーを√m個だけ入れても衝突が始まります。バケットが100個なら、わずか十数個のキーですでに衝突が普通になります。だからハッシュテーブルは衝突をなくそうとはせず、衝突が起きたときにうまく処理することに集中します。代表的なのは同じバケットに連結リストでぶら下げるチェイニング(chaining)、あるいは次の空きを探すオープンアドレス法(open addressing)です。

負荷率とリサイズ

ハッシュテーブルの性能を支配する値が**負荷率(load factor)**です。

負荷率 α = 格納された項目数 n / バケット数 m

負荷率が低ければ衝突がまれで、検索が平均O(1)に近づきます。しかし負荷率が高くなるほどバケットごとに項目が積み重なり、衝突が頻繁になり、検索がその鎖をたどるので遅くなります。だからほとんどのハッシュテーブル実装は、負荷率がしきい値を超えるとバケット数を増やし、すべての項目を再配置します。これがリサイズ(resizing)またはリハッシュ(rehashing)です。

  • JavaのHashMapはデフォルトの負荷率しきい値が0.75です。項目数がバケット数の75%を超えるとバケットを2倍にします。
  • Pythonのdictはおおよそ2/3(約0.66)を超えると大きくなります。
  • Goのマップも同様のしきい値で成長します。

リサイズはすべての項目を新しいバケットに入れ直す必要があるのでO(n)のコストがかかります。高価に見えますが、バケットを2倍ずつ増やす戦略(amortized doubling)のおかげで、項目1つを追加する平均コストは依然O(1)に保たれます。動的配列が大きくなるとき2倍ずつ増やすのと同じ原理です。たまに1回大きく高価になりますが、そのコストをその間の安価な演算に分けて担わせれば、平均は定数時間です。

ここに面白い対比があります。暗号学では√Nで衝突が始まることが脅威なので、空間を大きくして衝突を避けました。ハッシュテーブルでは同じ√N現象を認め、空間は小さく保ちつつ、衝突処理とリサイズで性能を管理します。同じ数学、正反対の戦略です。

衝突が本当に重要になるとき — gitのSHA-1からSHA-256へ

衝突確率が理論ではなく実際の事件になった代表例がgitです。

gitはすべてのオブジェクト(コミット、ツリー、ブロブ)をその内容のハッシュで識別します。長らくこのハッシュはSHA-1で、SHA-1は160ビットを出力します。誕生日規則によれば、SHA-1の衝突耐性は2^(160/2) = 2⁸⁰回の試行です。長い間これで十分安全だと考えられていました。

問題は2つありました。1つ目、2⁸⁰は無限ではなく、計算能力が発展するにつれて次第に手の届く範囲に入ってきました。2つ目、より決定的に、SHA-1は純粋なランダム関数ではありませんでした。内部構造の弱点のため、総当たりの2⁸⁰よりはるかに少ない労力で衝突を作る方法が発見されたのです。

2017年、GoogleとCWIが実際に、異なる2つのPDFファイルが同じSHA-1ハッシュを持つように作ることに成功しました。この「SHAttered」攻撃は約2⁶³の計算で衝突を作り出しました。理論的な安全線である2⁸⁰よりずっと下でした。これはコンテンツアドレスストレージであるgitへの直接的な脅威でした。悪意を持って作った2つのオブジェクトが同じハッシュを持てば、一方をもう一方にこっそりすり替える余地が生じるからです。

そこでgitは2つの方向で対応しました。

  • 短期的防御: SHAttered型の衝突を検出する強化版SHA-1(collision detectionが付いた変種)を導入し、既知の攻撃パターンをふるい落とします。
  • 根本的解決: ハッシュ関数そのものをSHA-256へ移行する作業を進めました。SHA-256は256ビットを出力するので衝突耐性が2¹²⁸に跳ね上がり、予測可能な未来においてランダムな衝突はもちろん構造的攻撃も事実上不可能です。

gitの教訓は明確です。「今十分なビット数」が永遠に十分とは限りません。計算能力の発展とハッシュ関数自体の弱点の発見が重なると、昨日の安全線が今日の脆弱性になります。だからセキュリティシステムは常に十分な余裕(SHA-256の2¹²⁸のような)を持たせて設計します。

まとめ — 1つの数学、いくつもの顔

誕生日のパラドックスはパーティーの面白いトリックのように見えますが、実はコンピューティング全体を貫く根本原理です。

  • 核心の規則: N個の空間で衝突はNではなく√Nで始まる。
  • UUID・ハッシュ: だからbビットの衝突耐性は実質的にb/2ビット。128ビットが安全なのは2⁶⁴の壁が物理的に越えにくいから。
  • ハッシュテーブル: 同じ√N現象のため衝突は必然。だから負荷率を管理し、しきい値で2倍にリサイズする。
  • git: SHA-1の2⁸⁰の耐性がSHAtteredで破られると、SHA-256の2¹²⁸へ移った。昨日の十分さは明日の不足になりうる。

これらすべてが「ペアの数は人数の2乗で増える」という単純な観察から出てきます。次にUUIDを発行したりハッシュサイズを選んだりするとき、空間の大きさではなくその平方根を思い浮かべてみてください。本当の安全マージンは、いつもそこにあります。

いろいろなハッシュアルゴリズムの出力を実際に作り、サイズを比べてみたいならハッシュジェネレーターで実験してみてください。

参考資料

현재 단락 (1/87)

部屋に23人が集まっているとしましょう。このうち2人の誕生日が同じである確率はどれくらいでしょうか。多くの人は「365日のうち23人なら……6%くらい?」と答えます。実際の答えは**50.7%**です...

작성 글자: 0자원문 글자: 6,493자작성 단락: 0/87