ハッシュ衝突確率の計算
入力
| ハッシュサイズ | 128 |
|---|---|
| アイテム数 | 1,000,000 |
ハッシュ衝突確率の計算
ハッシュ関数の出力ビット数とハッシュ対象のアイテム数から衝突確率を求め、50%衝突確率に達するアイテム数も算出します。
入力
ハッシュパラメータ
結果
値を入力すると計算結果が表示されます。
衝突確率
ハッシュ衝突確率の概要
ハッシュ関数は任意の長さの入力を、ダイジェストと呼ばれる固定長の出力に変換します。理想的には、異なる2つの入力が同じダイジェストを生成することはありません。この性質を衝突耐性といいます。しかし出力空間は有限であるため、衝突は必ず存在します。問題は、衝突が起きやすくなるまでにいくつの入力をハッシュ化する必要があるかという点です。この計算では、誕生日近似（誕生日のパラドックスにちなんだ名称）を用いてその確率を定量化します。
誕生日のパラドックス
365日の年から無作為に選ばれた23人のグループにおいて、2人が同じ誕生日を持つ確率はすでに50%を超えています。この確率が直感よりもはるかに高い理由は、特定の相手との一致ではなく、グループ内の任意のペアの一致を数えているからです。同じ非対称性がハッシュ衝突にも当てはまります。同じハッシュを持つ2つの入力を見つける（衝突）ことは、特定のターゲットハッシュを生成する入力を見つける（原像）よりもはるかに容易です。
計算式
ビットの出力を持つハッシュ関数では、探索空間は 個の等確率な値を持ちます。 個のランダムにハッシュ化されたアイテムが与えられたとき、衝突確率の正確な値は、 個すべての出力が異なる確率の補数として求められます。
p=1−k=0∏n−1(1−2bk)が十分に大きく が中程度の場合、誕生日近似により簡単な閉じた式が得られます。
p≈1−e−n2/(2⋅2b)確率が50%に達するアイテム数を解くと、次の式が得られます。
n50%=2⋅2b⋅ln2計算例
32ビットハッシュ（チェックサムに使われるCRC32など）の場合：
n50%=2×232×ln2=2×4,294,967,296×0.6931≈5,954,124,768≈77,163リポジトリに77,163個のファイルが存在するだけで、2つのファイルが同じ32ビットCRCを持つ確率は約50%に達します。近似式で確認すると次のとおりです。
p=1−e−771632/(2×232)≈1−e−0.693≈0.50これがCRC32が、小さなデータストリームの誤り検出コードとしては優れているにもかかわらず、大規模なコレクションにおける一意な識別子として不適切な理由です。
セキュリティへの含意
誕生日境界により、 ビットのハッシュ関数が提供する衝突耐性は ビットに過ぎないことがわかります。攻撃者は衝突を見つけるために 回ではなく、約 回のハッシュ評価しか必要としません。このため、暗号ハッシュ関数は目標とするセキュリティレベルよりも大きな出力ビット数で設計されます。
| ハッシュ関数 | 出力 | 衝突耐性 |
|---|---|---|
| MD5 | 128 ビット | ~（実用上破られている） |
| SHA-1 | 160 ビット | ~（実用上破られている） |
| SHA-256 | 256 ビット | ~（現行標準） |
| SHA-3-512 | 512 ビット | ~（高セキュリティ） |
MD5とSHA-1が「破られている」とされるのは、誕生日境界だけが理由ではありません。研究者が 回の演算よりもはるかに高速に衝突を生成するアルゴリズム的な弱点を発見したためです。MD5の衝突は、公開済みの手法を用いて一般的なハードウェアで数分以内に計算できます。
パスワードの探索空間に関する関連分析については、パスワードのエントロピー を参照してください。
よくある質問 (FAQ)
暗号における誕生日のパラドックスとは何ですか？
誕生日のパラドックスとは、23人のグループがいれば、365通りの誕生日があるにもかかわらず、2人が同じ誕生日を持つ確率が既に50%を超えるという直感に反した結果です。
同じ数学がハッシュ関数にも当てはまります。攻撃者は、同じ出力を持つ2つのアイテムを見つける確率が50%に達するために、おおよそ √(2^b) = 2^(b/2) 個のハッシュ済みアイテムしか必要としません。これが誕生日攻撃です。MD5のような128ビットハッシュでは、そのしきい値は約 2^64 ≈ 1.8 × 10¹⁹ 個となり、原像攻撃が必要とする 2^128 通りの組み合わせよりもはるかに少ない数です。
誕生日攻撃がビット数の半分しか必要としないのはなぜですか？
原像攻撃は特定のハッシュ出力を見つける必要があるため、2^b 全体の空間を探索しなければなりません。一方、誕生日攻撃は任意の2つの入力が衝突すればよく、誕生日境界によってそのようなペアが見つかる確率は約 2^(b/2) サンプル後に50%を超えます。このため、暗号ハッシュ関数は通常、目標とするセキュリティレベルの2倍の出力ビット数で設計されます。256ビットのハッシュは128ビットの衝突耐性を提供します。
MD5とSHA-1がなぜ安全でないとされているのですか？
MD5（128ビット）とSHA-1（160ビット）は、確率的な誕生日境界攻撃だけでなく、誕生日境界が予測するよりもはるかに効率的に衝突を見つけるアルゴリズム的な弱点によって破られています。2004年に研究者らがMD5の衝突を実証し、2017年にはGoogleのSHAtteredプロジェクトが最初の公開されたSHA-1衝突を生成しました。
これらの関数はチェックサムやコンテンツアドレッシングなど非暗号的な用途では引き続き安全ですが、デジタル署名や認証局のような衝突耐性が重要な場面では使用すべきではありません。
衝突と原像の違いは何ですか？
衝突とは、hash(x) = hash(y) となる異なる2つの入力 x と y を見つけることです。原像とは、特定のターゲット値 h にハッシュされる入力 x を見つけることで、両方の入力を自由に選べないため、衝突よりも困難です。第2原像とは、既知の x と同じハッシュを持つ別の入力 y を見つけることです。
これらは難易度の低い順に並んでいます。衝突耐性が最も弱い性質で、第2原像耐性が最も強い性質です。デジタル署名に使用されるハッシュ関数は第2原像攻撃に耐える必要があり、ハッシュテーブルやBloomフィルタに使用されるものは弱い衝突耐性だけが必要です。