誕生日攻撃

誕生日攻撃は、確率論における誕生日問題の背景にある数学を利用するブルートフォース衝突攻撃である。この攻撃は、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] $1-{\frac {365!}{(365-n)!\cdot 365^{n}}}$

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

誕生日攻撃では、攻撃者は良性と悪性の契約の様々なバリエーションを用意し、それぞれにデジタル署名が付与されます。そして、同じ署名を持つ良性と悪性の契約のペアを探します。この架空の例では、文字列のデジタル署名がSHA-256ハッシュの最初のバイトであると仮定します。見つかったペアは緑色で示されます。良性の契約のペア（青色）や悪性の契約のペア（赤色）を見つけても意味がありません。被害者が良性の契約を承認すると、攻撃者はそれを悪性の契約に置き換え、デジタル署名によって証明された被害者が署名したと主張します。

ボールをビンに入れる問題との関係

誕生日攻撃は、ボールをビンに入れる問題の一種としてモデル化できます。この問題では、ボール（ハッシュ関数の入力）がランダムにビン（ハッシュ関数の出力）に配置されます。ハッシュ衝突は、少なくとも2つのボールが同じビンに入れられた場合に発生します。

数学

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

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

p(n;H)\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^{2}/(2H)}

^[7]

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

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

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

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

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

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

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

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

ビット	可能な出力（H）	ランダム衝突の望ましい確率（2 sf）（p）
ビット	可能な出力（H）	10 ⁻¹⁸	10 ⁻¹⁵	10 ⁻¹²	10 ⁻⁹	10 ⁻⁶	0.1%	1%	25%	50%	75%
16	2 ¹⁶ (~6.5 x 10 ⁴ )	<2	<2	<2	<2	<2	11	36	190	300	430
32	2 ³² (~4.3 × 10 ⁹）	<2	<2	<2	3	93	2900	9300	5万	7万7000	11万
64	2 ⁶⁴ (~1.8 × 10 ¹⁹）	6	190	6100	19万	610万	1.9 × 10 ⁸	6.1 × 10 ⁸	3.3 × 10 ⁹	5.1 × 10 ⁹	7.2 × 10 ⁹
96	2 ⁹⁶ (~7.9 × 10 ²⁸）	4.0 × 10 ⁵	1.3 × 10 ⁷	4.0 × 10 ⁸	1.3 × 10 ¹⁰	4.0 × 10 ¹¹	1.3 × 10 ¹³	4.0 × 10 ¹³	2.1 × 10 ¹⁴	3.3 × 10 ¹⁴	4.7 × 10 ¹⁴
128	2 ¹²⁸ (~3.4 × 10 ³⁸）	2.6 × 10 ¹⁰	8.2 × 10 ¹¹	2.6 × 10 ¹³	8.2 × 10 ¹⁴	2.6 × 10 ¹⁶	8.3 × 10 ¹⁷	2.6 × 10 ¹⁸	1.4 × 10 ¹⁹	2.2 × 10 ¹⁹	3.1 × 10 ¹⁹
192	2 ¹⁹² (~6.3 × 10 ⁵⁷）	1.1 × 10 ²⁰	3.7 × 10 ²¹	1.1 × 10 ²³	3.5 × 10 ²⁴	1.1 × 10 ²⁶	3.5 × 10 ²⁷	1.1 × 10 ²⁸	6.0 × 10 ²⁸	9.3 × 10 ²⁸	1.3 × 10 ²⁹
256	2 ²⁵⁶ (~1.2 × 10 ⁷⁷）	4.8 × 10 ²⁹	1.5 × 10 ³¹	4.8 × 10 ³²	1.5 × 10 ³⁴	4.8 × 10 ³⁵	1.5 × 10 ³⁷	4.8 × 10 ³⁷	2.6 × 10 ³⁸	4.0 × 10 ³⁸	5.7 × 10 ³⁸
384	2 ³⁸⁴ (~3.9 × 10 ¹¹⁵）	8.9 × 10 ⁴⁸	2.8 × 10 ⁵⁰	8.9 × 10 ⁵¹	2.8 × 10 ⁵³	8.9 × 10 ⁵⁴	2.8 × 10 ⁵⁶	8.9 × 10 ⁵⁶	4.8 × 10 ⁵⁷	7.4 × 10 ⁵⁷	1.0 × 10 ⁵⁸
512	2 ⁵¹² (~1.3 × 10 ¹⁵⁴）	1.6 × 10 ⁶⁸	5.2 × 10 ⁶⁹	1.6 × 10 ⁷¹	5.2 × 10 ⁷²	1.6 × 10 ⁷⁴	5.2 × 10 ⁷⁵	1.6 × 10 ⁷⁶	8.8 × 10 ⁷⁶	1.4 × 10 ⁷⁷	1.9 × 10 ⁷⁷

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

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

単純な近似

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

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

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

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

。

または

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

。

これは、確率が 0.5 以下の場合に適しています。

この近似法は、指数を扱う際に特に使いやすいです。例えば、32ビットハッシュ（）を構築し、衝突の確率を100万分の1（）以下にしたいとします。この場合、最大でいくつの文書を扱えるでしょうか？ $H=2^{32}$ $p\approx 2^{-20}$

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に近いです。

デジタル署名の脆弱性

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

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

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

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

署名者 (ボブ) は、より大きなビット長を使用するほかに、署名する前に文書にランダムで無害な変更をいくつか加え、署名した契約書のコピーを自分で保管して、少なくとも法廷で自分の署名が不正な契約書ではなくその契約書と一致していることを証明できるようにすることで、自分自身を保護することができます。

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

逆攻撃

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

参照

注記

^ 「衝突の回避、暗号ハッシュ関数」（PDF）。ウェルズリー大学コンピュータサイエンス学部、暗号の基礎。
^ ab Dang, QH (2012). 承認されたハッシュアルゴリズムを使用するアプリケーションに対する推奨事項（レポート）. メリーランド州ゲイサーズバーグ: 米国国立標準技術研究所. doi : 10.6028/nist.sp.800-107r1 .
^ Daniel J. Bernstein. 「ハッシュ衝突のコスト分析：量子コンピューターはSHARCSを時代遅れにするのか？」(PDF) Cr.yp.to . 2017年10月29日閲覧。
^ Brassard, Gilles; HØyer, Peter; Tapp, Alain (1998年4月20日). 「ハッシュ関数とクローフリー関数の量子暗号解析」. LATIN'98: Theoretical Informatics . Lecture Notes in Computer Science. Vol. 1380. Springer, Berlin, Heidelberg. pp. 163– 169. arXiv : quant-ph/9705002 . doi :10.1007/BFb0054319. ISBN 978-3-540-64275-6. S2CID 118940551。
^ R. Shirey (2007年8月). インターネットセキュリティ用語集バージョン2. ネットワークワーキンググループ. doi : 10.17487/RFC4949 . RFC 4949. 情報提供。
^ 「誕生日の問題」. Brilliant.org . Brilliant_(ウェブサイト) . 2023年7月28日閲覧。
^ Bellare, Mihir; Rogaway, Phillip (2005). 「誕生日問題」. 現代暗号入門(PDF) . pp. 273– 274. 2023年3月31日閲覧。
^ フィリップ・フラジョレット;オドリズコ、アンドリュー M. (1990)。「ランダムマッピング統計」。キスカエにて、ジャン・ジャック。ヴァンデウォール、ジョース (編)。暗号学の進歩 — EUROCRYPT '89。コンピューターサイエンスの講義ノート。 Vol. 434. ベルリン、ハイデルベルク：シュプリンガー。 pp. 329–354。土井:10.1007/3-540-46885-4_34。ISBN 978-3-540-46885-1。
^ 上限と下限を参照してください。
^ Jacques Patarin, Audrey Montreuil (2005). 「Benes and Butterfly schemes revisited」（PostScript、PDF） . Université de Versailles . 2007年3月15日閲覧。 {{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
^ Gray, Jim; van Ingen, Catharine (2007年1月25日). 「ディスク故障率とエラー率の実証的測定」arXiv : cs/0701166 .
^ “CiteSeerX”. 2008年2月23日時点のオリジナルよりアーカイブ。2006年5月2日閲覧。
^ 「小さなxの値に対してlog(1+x)を正確に計算する」Mathworks.com . 2017年10月29日閲覧。

参考文献

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

外部リンク

RSA Securityの暗号に関するFAQより、「デジタル署名と認証とは何ですか?」
「誕生日攻撃」X5ネットワークス暗号に関するFAQ

[1] 「衝突の回避、暗号ハッシュ関数」（PDF）。ウェルズリー大学コンピュータサイエンス学部、暗号の基礎。

[:0-2] Dang, QH (2012). 承認されたハッシュアルゴリズムを使用するアプリケーションに対する推奨事項（レポート）. メリーランド州ゲイサーズバーグ: 米国国立標準技術研究所. doi : 10.6028/nist.sp.800-107r1 .

[3] Daniel J. Bernstein. 「ハッシュ衝突のコスト分析：量子コンピューターはSHARCSを時代遅れにするのか？」(PDF) Cr.yp.to . 2017年10月29日閲覧。

[4] Brassard, Gilles; HØyer, Peter; Tapp, Alain (1998年4月20日). 「ハッシュ関数とクローフリー関数の量子暗号解析」. LATIN'98: Theoretical Informatics . Lecture Notes in Computer Science. Vol. 1380. Springer, Berlin, Heidelberg. pp. 163– 169. arXiv : quant-ph/9705002 . doi :10.1007/BFb0054319. ISBN 978-3-540-64275-6. S2CID 118940551。

[rfc4949-5] R. Shirey (2007年8月). インターネットセキュリティ用語集バージョン2. ネットワークワーキンググループ. doi : 10.17487/RFC4949 . RFC 4949. 情報提供。

[6] 「誕生日の問題」. Brilliant.org . Brilliant_(ウェブサイト) . 2023年7月28日閲覧。

[7] Bellare, Mihir; Rogaway, Phillip (2005). 「誕生日問題」. 現代暗号入門(PDF) . pp. 273– 274. 2023年3月31日閲覧。

[8] フィリップ・フラジョレット;オドリズコ、アンドリュー M. (1990)。「ランダムマッピング統計」。キスカエにて、ジャン・ジャック。ヴァンデウォール、ジョース (編)。暗号学の進歩 — EUROCRYPT '89。コンピューターサイエンスの講義ノート。 Vol. 434. ベルリン、ハイデルベルク：シュプリンガー。 pp. 329–354。土井:10.1007/3-540-46885-4_34。ISBN 978-3-540-46885-1。

[9] 上限と下限を参照してください。

[10] Jacques Patarin, Audrey Montreuil (2005). 「Benes and Butterfly schemes revisited」（PostScript、PDF） . Université de Versailles . 2007年3月15日閲覧。 {{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です

[11] Gray, Jim; van Ingen, Catharine (2007年1月25日). 「ディスク故障率とエラー率の実証的測定」arXiv : cs/0701166 .

[12] “CiteSeerX”. 2008年2月23日時点のオリジナルよりアーカイブ。2006年5月2日閲覧。

[13] 「小さなxの値に対してlog(1+x)を正確に計算する」Mathworks.com . 2017年10月29日閲覧。