誕生日攻撃 例

ウィキペディア

誕生日攻撃

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/06/01 18:30 UTC 版)

例

デジタル署名への攻撃

デジタル署名は誕生日攻撃の影響を受ける場合がある。多くのデジタル署名では、暗号学的ハッシュ関数 $f$ を使ってメッセージ $m$ のハッシュ値 $f(m)$ を計算し、そのハッシュ値に対して秘密鍵を適用して署名を得る。ここでアリスがボブを騙し、ニセの契約書に署名させる場合を考える。アリスはまず正しい契約書 $m$ とニセの契約書 $m'$ を用意する。次に $m$ の意味を変えずに字面を変えた書面をコンマを挿入したり、空行を挿入したり、文の後の空白を増やしたり、同義語で置換したりしていくつも作成する。このようにすることで、正しい契約書 $m$ の膨大なバリエーションを作成できる。

同様の手法でアリスはニセの契約書 $m'$ についても多数のバリエーションを作成する。次にアリスは、それらの正しい契約書とニセの契約書の全バリエーションについてハッシュ関数を適用し、同じハッシュ値 $f(m)=f(m')$ となるものを探す。そして、衝突した正しい方の契約書をボブに提示し署名を求める。ボブが署名したら、アリスはその署名を切り出し、ニセの（衝突した）契約書に添付する。この署名はボブがニセの契約書に署名したことを証明している。

なお，本来の誕生日問題とは若干異なり、正しい契約書間同士のペアやニセの契約書間同士のペアで衝突が見つかってもアリスには何の利益も生じない。アリスが詐欺を成功させるには、正しい契約書とニセの契約書の組み合わせのペアで衝突が発生する文面を見つける必要がある。つまり、上の説明での $n$ は正しい契約書とニセの契約書のペアの個数に相当するため、アリスは実際には $2n$ 回ハッシュ値生成を試行しなければならない。

このような攻撃を防ぐため、署名で使用するハッシュ関数の出力長は誕生日攻撃が事実上不可能な程度にまで十分長くなければならない。つまり、通常の総当り攻撃を防ぐのに必要なビット数の2倍を必要とする。

ポラード・ロー素因数分解法の離散対数への応用（en）は、離散対数の計算に誕生日攻撃を応用した例である。

DNSキャッシュポイズニング

BINDの実装上の問題などによる、誕生日攻撃を利用したDNSのDNSキャッシュポイズニングの可能性が議論されている。