|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 誕生 ： [たんじょう] 1. (n,vs) birth 2. creation 3. formation ・ 誕生日 ： [たんじょうび] 【名詞】 1. birthday ・ 生 ： [せい, なま] 1. (adj-na,n,adj-no) (1) draft (beer) 2. draught 3. (2) raw 4. unprocessed ・ 日 ： [にち, ひ] 1. (n-adv,n-t) sun 2. sunshine 3. day ・ 攻撃 ： [こうげき] 1. (n,vs) attack 2. strike 3. offensive 4. criticism 5. censure
誕生日攻撃（たんじょうびこうげき、）は、暗号理論における暗号攻撃方法の1つ。確率論における誕生日問題の背後にある数学的理論を利用することからこの名称になっている。関数 ''f'' があるとき、この攻撃の目的は となるような2つの異なる入力 を求めることである。この のような組合せを衝突と呼ぶため、衝突攻撃ともいう。 衝突を見つける方法は、無作為または擬似乱数的に生成した異なる複数の入力を関数 ''f'' に与えて評価し、複数回同じ値となるまで続けるだけである。前述した誕生日問題から、この方法は思ったより効率的である。特に関数 が 個の異なる出力をそれぞれ同じ確率で生成し が非常に大きい場合、 となるような異なる入力 と を得るまでに ''f'' を評価する回数の平均は約 回である。 == 数値的解説 == 次のような実験を考える。 個の値の集合から 個の値を一様かつ無作為に選ぶ（重複もありうる）。この実験で少なくとも1つの値が2回以上選ばれる確率を とする。この確率は次のように概算できる。 : 衝突を発見する確率を 以上とするとき、行わなければならない試行回数の下限を とする。すると、上の式から次のような近似が得られる。 : 衝突発生確率を0.5とすると、次のようになる。 : 最初の衝突が発生するまでに行わなければならない試行回数を とする。この近似は次のようになる。 : 例えば、64ビットの暗号学的ハッシュ関数を使っている場合、約 1.8 × 1019 個の異なる出力がありうる。これらが全て同じ確率で発生する場合（最良ケース）、約 5.1 × 109 回の試行で衝突を発生させることができる。この値を birthday bound と呼び、n-ビットの符号についての birthday bound は となる〔 〕。他の例は次のようになる。 : : この表は、指定した確率で衝突を発生させるのに必要な試行回数を示している（各ハッシュ値の発生確率は等しいと仮定）。ちなみに 10−18 から 10−15 は一般的なハードディスクで訂正できないビット誤りが発生する確率である〔Empirical Measurements of Disk Failure Rates and Error Rates 〕。したがって、128ビットのMD5を文書のチェックサムとして使用する場合、8200億個の文書までならハードディスクでの誤り発生確率の範囲内に収まると言える（実際にはもっと多数のハッシュ値を生成できる）。 関数の出力が一様に分布しない場合、衝突をもっと早く見つけられることは容易に想像がつく。ハッシュ関数の「バランス」の観念は、誕生日攻撃への関数の耐性を定量化し、MDやSHAなどのよく知られたハッシュの脆弱性を見積もることを可能にする〔Hash Function Balance and its Impact on Birthday Attacks Bellare and Kohno, 2002〕。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「誕生日攻撃」の詳細全文を読む スポンサード リンク
|