平成26年度秋期 情報処理安全確保支援士 午前Ⅱ 問2

午前II 問02：ハッシュ関数の“衝突”って何？

ハッシュ関数の衝突発見困難性とは、別々のメッセージなのに、同じハッシュ値になる組み合わせを見つけるのがとても難しい、という性質のことだよ。たとえるなら、違う荷物なのに同じ伝票番号になってしまう組み合わせを探すのが、現実的にはほぼ無理なくらい大変、というイメージだね。

この問題で問われていること

この問題では、“ハッシュ値から元のメッセージを逆算するのが難しい”という原像計算困難性と、“同じハッシュ値になる別々のメッセージのペアを見つけるのが難しい”という衝突発見困難性を、きちんと区別できるかがポイントだよ。

衝突発見困難性

与えられたハッシュ値から元メッセージを探す困難性ではなく、同じハッシュ値を持つ別々のメッセージ 2 つを見つける困難性が衝突発見困難性です。

2つの異なるメッセージ\n-> 同じハッシュ値\nこれを見つけるのが困難

確認ポイント

• 元メッセージ探索は原像計算困難性です。
• 衝突は「2 つのメッセージ」で考える。
• 一致する二つのメッセージ探索の困難性を選ぶ。

正解

エ

出典

問題文と解答は IPA 公開の過去問題冊子・解答例を基にしています。

選択肢ア

これは間違いだよ。SHA-256のハッシュ値は256ビットなので、探索の規模は「256を2回かける」みたいな話ではなく「2を何回かけるか」で考えるんだ。合鍵探しでいうと、鍵番号が256種類しかないわけじゃなく、2の256乗通りある感じだよ。衝突を探す場合も256の2乗ではなく、誕生日のパラドックスの考え方でおよそ2の128乗回くらいが目安になるよ。

選択肢イ

これは間違いだよ。2の256乗という大きさは、SHA-256で「あるハッシュ値に対応する元のメッセージを探す」原像探索の目安だよ。衝突発見困難性は、同じハッシュ値になる2つのメッセージを探す話なので、誕生日のパラドックスにより目安はおよそ2の128乗回になるんだ。別の宝箱2つが同じ鍵番号になる組合せを探す話と、鍵番号から元の宝箱を1つ当てる話は別物だよ。

選択肢ウ

これは間違いだよ。これは「ハッシュ値から元のメッセージを探すのが難しい」という説明で、衝突発見困難性ではなく原像計算困難性の話なんだ。たとえるなら、レシート番号だけを見て元の買い物内容を当てる難しさのことだよ。衝突発見困難性は、同じレシート番号になる別々の買い物内容を2つ見つける難しさなんだ。

選択肢エ（正解）

これは正解の説明だよ。衝突発見困難性は、違うメッセージなのに同じハッシュ値になる組合せを見つけにくい性質のことなんだ。たとえるなら、別々の人なのに同じ整理券番号を持つ2人を探すのがとても難しい、というイメージだよ。