誕生日攻撃

バースデー攻撃は、確率論におけるバースデー問題の背後にある数学を利用するブルートフォース衝突攻撃である。この攻撃は、2 つ以上のパーティ間の通信を悪用するために使用できる。この攻撃は、ランダムな攻撃試行と固定された程度の順列 (ピジョンホール) の間に見られる衝突の可能性が高いことに依存する。をハッシュ関数の可能な値の数とし、 とする。バースデー攻撃では、の確率でハッシュ関数の衝突を見つけることができます。 ここで、はハッシュ出力のビット長であり、^{[1] [2]} であり、 は同じ確率で古典的な原像抵抗セキュリティです。 ^[2]量子コンピューターはバースデー攻撃を実行でき、衝突抵抗を で破ることができるという一般的な結果があります (ただし異論もあります^[3] ) 。^[4]${\textstyle H}$${\textstyle H=2^{l}}$${\textstyle 50\%}$${\textstyle {\sqrt {2^{l}}}=2^{l/2},}$${\textstyle l}$${\textstyle 2^{l-1}}$${\textstyle {\sqrt[{3}]{2^{l}}}=2^{l/3}}$

誕生日攻撃にはデジタル署名の脆弱性がいくつかあるが、ブルートフォース攻撃よりも速く暗号化方式を破ることはできない。^{[5] : 36}

例として、30 人の生徒 (n = 30) のクラスを担当する教師が、全員の誕生日を尋ね (簡単にするために、うるう年は無視します)、2 人の生徒が同じ誕生日であるかどうかを判断するシナリオを考えてみましょう (後述するハッシュ衝突に対応します)。直感的には、この確率は小さいように思えるかもしれません。直感に反して、どの日でも少なくとも 1 人の生徒が他の生徒と同じ誕生日である確率は、式 から約 70% (n = 30 の場合) です。^[6]${\displaystyle 1-{\frac {365!}{(365-n)!\cdot 365^{n}}}}$

教師が特定の日（たとえば、9 月 16 日）を選択した場合、少なくとも 1 人の生徒がその特定の日に生まれる確率は約 7.9% になります。 ${\displaystyle 1-(364/365)^{30}}$

バースデー攻撃では、攻撃者は良性の契約と悪性の契約のさまざまなバリエーションを準備し、それぞれにデジタル署名を付けます。同じ署名を持つ良性の契約と悪性の契約のペアが求められます。この架空の例では、文字列のデジタル署名がSHA-256ハッシュの最初のバイトであるとします。見つかったペアは緑色で示されます。良性の契約のペア (青) や悪性の契約のペア (赤) を見つけても無駄であることに注意してください。被害者が良性の契約を承諾すると、攻撃者はそれを悪性の契約に置き換え、デジタル署名によって証明された被害者が署名したと主張します。

誕生日攻撃の文脈では、重要な変数は確率論におけるよく知られたボールとビンの問題に次のように関連しています。

変数n は、入力 (または試行) の数を表します。ボールとビンの問題のアナロジーでは、n はH 個のビンにランダムに投げ込まれるボールの数を指します。各入力は、ビンの 1 つ (ハッシュ値) にボールを投げ込むことに対応します。

変数H は、ハッシュ関数の可能な出力の総数を表します。これは、ボールが入る可能性のある一意の「ビン」の数です。ハッシュ出力の総数は、多くの場合、 と表現されます。ここで、l はハッシュ出力のビット長です。ボールとビンのアナロジーでは、H はビンの数を表し、各ビンは一意のハッシュ値に対応します。 ${\displaystyle H=2^{l}}$

変数l はハッシュ関数の出力のビット長を表します。ビット長lのハッシュ関数は一意の出力を生成できるため、可能なハッシュ値 (またはビン) の数は です。 ${\displaystyle 2^{l}}$${\displaystyle H=2^{l}}$

変数p は衝突が発生する確率、つまり 2 つ以上の入力 (ボール) に同じ出力 (ビン) が割り当てられる確率を表します。バースデー アタックでは、衝突の確率を 50% にするために必要な入力数を見積もるために 、 pは 0.5 (50%) に設定されることが多いです。

誕生日攻撃は、ボールとビンの問題のバリエーションとしてモデル化できます。この問題では、

• ボールはハッシュ関数への入力を表します。
• ビンはハッシュ関数の可能な出力 (ハッシュ値) を表します。
• 衝突は、2 つ以上のボールが同じビンに着地したときに発生します (つまり、2 つの入力が同じハッシュ出力を生成します)。

関数 が与えられた場合、攻撃の目的はとなる2 つの異なる入力を見つけることです。このようなペアは衝突と呼ばれます。衝突を見つけるために使用される方法は、同じ結果が複数回見つかるまで、ランダムまたは疑似ランダムに選択される可能性のある異なる入力値に対して関数を評価することです。誕生日問題のため、この方法はかなり効率的です。具体的には、関数がのいずれかの異なる出力を等しい確率で生成し、十分に大きい場合、平均して約 の異なる引数に対して関数を評価した後、異なる引数のペアとを取得することが期待されます。 ${\displaystyle f}$${\displaystyle x_{1},x_{2}}$${\displaystyle f(x_{1})=f(x_{2})}$${\displaystyle x_{1},x_{2}}$${\displaystyle f}$ ${\displaystyle f(x)}$${\displaystyle H}$${\displaystyle H}$${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle f(x_{1})=f(x_{2})}$${\displaystyle 1.25{\sqrt {H}}}$

次の実験を考えてみましょう。H個の値のセットからn個の値を一様にランダムに選択し、繰り返しを可能にします。p ( n ;  H )を、この実験中に少なくとも 1 つの値が複数回選択される確率とします。この確率は次のように近似できます。

${\displaystyle p(n;H)\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^{2}/(2H)}}$^[7]

ここで、 は選択された値 (入力) の数であり、 は可能な結果 (可能なハッシュ出力) の数です。 ${\displaystyle n}$${\displaystyle H}$

衝突が見つかる確率が少なくとも pになるように選択しなければならない値の最小数をn ( p ;  H )とする。この式を逆にすると、次の近似値が得られる。

${\displaystyle n(p;H)\approx {\sqrt {2H\ln {\frac {1}{1-p}}}}}$

衝突の確率を0.5とすると、

${\displaystyle n(0.5;H)\approx 1.1774{\sqrt {H}}}$

Q ( H ) を最初の衝突を見つけるまでに選択しなければならない値の期待値の数とする。この数は次のように近似できる。

${\displaystyle Q(H)\approx {\sqrt {{\frac {\pi }{2}}H}}}$

例えば、64ビットハッシュを使用する場合、およそ1.8 × 10 ¹⁹通りの出力があります。これらがすべて同じ確率で発生する場合（最良のケース）、試行回数は「わずか」約 50 億回です（5.38 × 10 ⁹）でブルートフォースを使用して衝突を生成することができます。^[8]この値は誕生日境界と呼ばれ^{[9] 、} lビットコードの場合は2 ^{l /2}と近似できます^[10]その他の例は次のとおりです。

表は、すべてのハッシュが等しく起こりうると仮定して、与えられた成功確率を達成するために必要なハッシュ数n ( p )を示しています。比較のために、10 ⁻¹⁸から10 ⁻¹⁵は、一般的なハードディスクの訂正不可能なビットエラー率です。^[11]理論的には、MD5ハッシュまたはUUIDは約128ビットであり、出力がさらに多くなる可能性があるとしても、約8200億の文書まではその範囲内にとどまるはずです。

関数の出力が不均等に分散されていれば、衝突がさらに速く発見できることは容易に分かる。ハッシュ関数の「バランス」という概念は、関数のバースデー攻撃（不均等なキー配布を悪用する）に対する耐性を定量化する。しかし、ハッシュ関数のバランスを決定するには通常、すべての可能な入力を計算する必要があるため、MDやSHAファミリーなどの一般的なハッシュ関数では実行不可能である。^{[12] の}式の サブ式は、一般的なプログラミング言語に直接翻訳した場合、有意性が失われるため、小さい場合には正確に計算されない。 が使用可能な場合（たとえばC99の場合のように）、代わりに同等の式を使用する必要があります。^[13] これを行わないと、上記の表の最初の列はゼロとして計算され、2番目の列のいくつかの項目には正しい有効数字が1つもありません。 ${\displaystyle \ln {\frac {1}{1-p}}}$${\displaystyle n(p;H)}$${\displaystyle p}$log(1/(1-p))log1p-log1p(-p)

暗算に使える良い経験則は、次の関係である。

${\displaystyle p(n)\approx {n^{2} \over 2H}}$

これは次のようにも書ける。

${\displaystyle H\approx {n^{2} \over 2p(n)}}$。

または

${\displaystyle n\approx {\sqrt {2H\times p(n)}}}$。

これは、確率が 0.5 以下の場合に有効です。

この近似方式は、指数を扱うときに特に使いやすいです。たとえば、32 ビットのハッシュ ( ) を構築していて、衝突の可能性を最大で 100 万分の 1 ( ) にしたい場合、最大でいくつのドキュメントを持つことができますか? ${\displaystyle H=2^{32}}$${\displaystyle p\approx 2^{-20}}$

${\displaystyle n\approx {\sqrt {2\times 2^{32}\times 2^{-20}}}={\sqrt {2^{1+32-20}}}={\sqrt {2^{13}}}=2^{6.5}\approx 90.5}$

これは正解の93に近いです。

バースデー攻撃は、ハッシュ関数の衝突の数学を利用する方法です。以下では、ボールとビンの問題の類推に基づいて、衝突の確率の上限と下限を示し、重要な方程式を導出します。

バースデー攻撃は、n 個のボール (入力) をH個のビン (ハッシュ出力の可能性) に投げ込むというモデル化が可能です。衝突の確率は次の式で制限されます。

${\displaystyle p\leq {\frac {n^{2}}{2H}}}$

この式は、少なくとも 1 回の衝突が発生する確率の上限を与える結合境界から得られます。i 番目のボールが前のボールの 1 つと衝突するイベントを と表します。i 番目のボールの衝突確率は次のとおりです。 ${\displaystyle C_{i}}$

${\displaystyle \Pr[C_{i}]\leq {\frac {i-1}{H}}}$

したがって、 n個のボールをすべて投げた後に衝突する確率の合計は次のように制限されます。

${\displaystyle p=\Pr[C_{1}\cup C_{2}\cup \cdots \cup C_{n}]\leq {\frac {0}{H}}+{\frac {1}{H}}+\cdots +{\frac {n-1}{H}}={\frac {n(n-1)}{2H}}}$

これはハッシュ関数における衝突の確率の上限を示します。

衝突の確率の下限は、すべて異なるビンを占めるi個のボールを投げた後に衝突がないと仮定することで導き出すことができます。(i+1) 番目のボールを投げた後に衝突がない確率は次のとおりです。

${\displaystyle \Pr[D_{i+1}|D_{i}]={\frac {H-i}{H}}=1-{\frac {i}{H}}}$

n 個のボールをすべて投げた後に衝突しない確率の合計は、次の項の積です。

${\displaystyle \Pr[D_{n}]=\prod _{i=1}^{n-1}\left(1-{\frac {i}{H}}\right)}$

不等式を使用すると、これを次のように近似できます。 ${\displaystyle 1-x\leq e^{-x}}$

${\displaystyle \Pr[D_{n}]\leq \prod _{i=1}^{n-1}e^{-{\frac {i}{H}}}=e^{-{\frac {n(n-1)}{2H}}}}$

したがって、少なくとも 1 回の衝突が発生する確率は以下のように制限されます。

${\displaystyle p\geq 1-e^{-{\frac {n(n-1)}{2H}}}}$

これにより、衝突の確率の下限が示されます。

上記の議論から、少なくとも 1 回の衝突の確率は次の範囲に制限されることがわかります。

${\displaystyle {\frac {n(n-1)}{4H}}\leq p\leq {\frac {n^{2}}{2H}}}$

とすると、試行回数nが次のように与えられる場合、ほぼ確実に衝突が発生します。 ${\displaystyle p\approx 1}$

${\displaystyle n=\Theta ({\sqrt {H}})=\Theta (2^{l/2})}$

これは、ハッシュ出力のビット長の関数として、衝突に必要な入力数がどのように増加するかを示しています。

デジタル署名は、バースデー攻撃、より正確には選択プレフィックス衝突攻撃の影響を受ける可能性があります。メッセージは通常、最初に （ここで、 は暗号化ハッシュ関数）を計算し、次に何らかの秘密鍵を使用して に署名することによって署名されます。マロリーがボブを騙して不正な契約に署名させようとしているとします。マロリーは公正な契約と不正な契約を準備します。次に、カンマの挿入、空行、文の後のスペース 1 つまたは 2 つ、同義語の置き換えなど、意味を変えずに を変更できる位置をいくつか見つけます。これらの変更を組み合わせることで、公正な契約である膨大な数のバリエーションを作成できます。 ${\displaystyle m}$${\displaystyle f(m)}$${\displaystyle f}$${\displaystyle f(m)}$${\displaystyle m}$${\displaystyle m'}$${\displaystyle m}$${\displaystyle m}$

同様に、マロリーは不正な契約の膨大な数のバリエーションも作成します。次に、ハッシュ関数をこれらすべてのバリエーションに適用し、同じハッシュ値を持つ公正な契約のバージョンと不正な契約のバージョンを見つけます。彼女は公正なバージョンをボブに提示して署名を求めます。ボブが署名した後、マロリーは署名を受け取り、不正な契約に添付します。この署名は、ボブが不正な契約に署名したことを「証明」します。 ${\displaystyle m'}$${\displaystyle f(m)=f(m')}$

確率は元の誕生日問題とは少し異なります。同じハッシュを持つ 2 つの公正な契約または 2 つの不正な契約を見つけても、マロリーは何も得ません。マロリーの戦略は、公正な契約と不正な契約のペアを生成することです。与えられたハッシュ関数では、可能なハッシュの数です。ここで、はハッシュ出力のビット長です。誕生日問題の方程式は、ここでは正確には当てはまりません。衝突の確率が 50% の場合、マロリーは約 個のハッシュを生成する必要があり、これは古典的な誕生日問題での単純な衝突に必要な数の 2 倍です。 ${\displaystyle 2^{l}}$${\displaystyle l}$${\displaystyle 2^{(l/2)+1}}$

この攻撃を回避するには、署名方式に使用されるハッシュ関数の出力長を、誕生日攻撃が計算上実行不可能になるくらい十分に大きく、つまり通常のブルートフォース攻撃を防ぐために必要なビット数の約 2 倍に選択することができます。

署名者 (ボブ) は、より大きなビット長を使用する以外にも、署名する前に文書に無作為に無害な変更を加えたり、署名した契約書のコピーを自分の手元に保管したりすることで、自分自身を守ることができます。そうすれば、少なくとも法廷で、自分の署名が不正な契約書ではなく、その契約書と一致していることを証明することができます。

対数に対するポラードのローアルゴリズムは、離散対数の計算に誕生日攻撃を使用するアルゴリズムの例です。

署名者がボブではなくマロリーである場合も、同じ詐欺が可能です。ボブはマロリーに署名用の契約を提案できます。マロリーは、詐欺的な契約と同じ署名を持つ、この公正な契約の無害な修正版を見つけることができ、マロリーは修正された公正な契約と署名をボブに提供できます。後で、マロリーは詐欺的なコピーを提出できます。ボブが無害な修正版の契約を持っていない場合 (おそらく元の提案しか見つけていない場合)、マロリーの詐欺は完璧です。ボブがそれを持っている場合、マロリーは少なくともボブが詐欺師であると主張することができます。

追加の詳細は次のとおりです:

1. 当初の契約提案: ボブはマロリーに公正な契約を提案し、彼女が署名することを期待します。

2. マロリーの改変された詐欺的な契約: ボブの契約書に直接署名する代わりに、マロリーは2つのバージョンの契約書を作成します。

• 1 つは、ボブの契約書をわずかに修正したもので、ボブにとって無害または「不快感を与えない」ものと思われます。

• もう 1 つは、マロリーに利益をもたらす不正な契約ですが、重要なことに、修正版と同じデジタル署名が付いています。

3. マロリーが修正した契約書を提供する: マロリーは修正版に署名し、ボブに渡します。このバージョンの署名は、不正な契約書に記載されるものと同じです。

4. ボブのリスク: ボブがマロリーが署名した修正版のコピーを保管せず、元の提案書だけを保管した場合、ボブはマロリーが同意した内容の証拠を持ちません。後になって、マロリーは偽造契約書 (署名が同じ) を提示し、署名したのはその契約書であると主張することができます。

5. 成果:

• ボブが修正版を持っていない場合、マロリーの不正な契約は署名された文書と区別がつかなくなり、完全な詐欺が可能になります。
• ボブが修正版を保管している場合、マロリーはボブが契約をすり替えたと主張する可能性があり、詐欺の責任者が誰なのかという疑問が生じます。

• 衝突攻撃
• 中間者攻撃
• BHTアルゴリズム

• ミヒル・ベラーレ、河野忠義：「ハッシュ関数のバランスと誕生日攻撃への影響」EUROCRYPT 2004: pp401–418
• 応用暗号学、第 2 版、ブルース・シュナイアー著

• RSA Securityの暗号化に関するFAQから、「デジタル署名と認証とは何ですか?」
• 「バースデーアタック」X5ネットワークス暗号に関するFAQ