情報セキュリティの基礎
出力が256ビットの理想的なハッシュ関数に対して、総当たりで攻撃するときに必要な計算の回数の目安として、「与えられたハッシュ値になる入力を見つける(原像攻撃)」場合と、「同じハッシュ値になる異なる2つの入力を、どれでもよいので見つける(衝突攻撃)」場合の組み合わせとして正しいものはどれか。
- A原像攻撃は約2^256回、衝突攻撃は約2^128回
- B原像攻撃は約2^128回、衝突攻撃は約2^256回
- C原像攻撃も衝突攻撃も約2^256回
答えと解説を見る
正解：A. 原像攻撃は約2^256回、衝突攻撃は約2^128回
出力がnビットの理想的なハッシュ関数では、ハッシュ値は 2^n 通りあり、入力を1つ試すごとに、決められたハッシュ値に一致する確率は 1/2^n です。そのため原像攻撃には、およそ 2^n 回、n = 256 なら約2^256回の計算が必要です。一方、衝突攻撃では、どの2つが一致してもよいので、k個の入力を試すと、比べられる組は約 k^2/2 通りに増えます。k^2/2 が 2^n に近づく、k が 2^(n/2) 程度で衝突が見つかる見込みが高くなり、n = 256 なら約2^128回です。これは「23人いれば、誕生日が同じ2人がいる確率が50%を超える」という誕生日のパラドックスと同じ考え方で、誕生日攻撃と呼ばれます。このため、ハッシュ関数の衝突に対する強さは出力のビット数の半分と見積もられ、128ビット相当の強さを求めるなら256ビットの出力が必要になります。
- A. 正しい。原像攻撃は約2^256回、衝突攻撃は誕生日攻撃により約2^128回です。
- B. 2つを逆にしています。どの2つが一致してもよい衝突攻撃のほうが少ない回数で済みます。
- C. 衝突攻撃では、試した入力どうしのどの組が一致してもよいので、約2^128回と原像攻撃よりずっと少なく済みます。