情報処理安全確保支援士試験 情報セキュリティスペシャリスト試験 平成28年度春期 午前Ⅱ 問5: ハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち，適切なものはどれか。

問題本文

ハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち，適切なものはどれか。

選択肢

• ア.SHA-256 の衝突発見困難性を示す，ハッシュ値が一致する二つのメッセージの探索に要する最大の計算量は，256 の 2 乗である。
• イ.SHA-256 の衝突発見困難性を示す，ハッシュ値の元のメッセージの探索に要する最大の計算量は，2 の 256 乗である。
• ウ.衝突発見困難性とは，ハッシュ値が与えられたときに，元のメッセージの探索に要する計算量の大きさによる，探索の困難性のことである。
• エ.衝突発見困難性とは，ハッシュ値が一致する二つのメッセージの探索に要する計算量の大きさによる，探索の困難性のことである。

正解

エ. 衝突発見困難性とは，ハッシュ値が一致する二つのメッセージの探索に要する計算量の大きさによる，探索の困難性のことである。

解説

衝突発見困難性とは、同じハッシュ値になる異なる二つのメッセージの組を見つけることが計算量的に困難である性質を指す。これに対し、ハッシュ値から元を求める困難性は原像計算困難性であり別概念。SHA-256では誕生日攻撃により衝突探索の計算量は約2の128乗で、原像探索の約2の256乗より小さい。実務では署名の偽造や改ざんを防ぐ要件として、衝突困難性の確保された関数を選ぶ必要がある。

選択肢ごとの解説

• ア.衝突探索量は256の2乗ではなく約2の128乗(誕生日攻撃)であり、値も概念も誤り。
• イ.2の256乗は原像探索の計算量で、衝突発見困難性の説明としては概念が誤り。
• ウ.ハッシュ値から元を探す困難性は原像計算困難性であり、衝突発見困難性ではないため誤り。
• エ.ハッシュ値が一致する二つのメッセージ探索の困難性という衝突発見困難性の定義どおりで正しい。