情報処理安全確保支援士試験 令和5年春期午前Ⅱ 衝突発見困難性
出典：令和5年春期 午前Ⅱ 問4
分野：セキュリティ ／ 情報セキュリティ
ハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち，適切なものはどれか。
- ア：SHA-256の衝突発見困難性を示す，ハッシュ値が一致する二つの元のメッセージの発見に要する最大の計算量は，256の2乗である。
- イ：SHA-256の衝突発見困難性を示す，ハッシュ値の元のメッセージの発見に要する最大の計算量は，2の256乗である。
- ウ：衝突発見困難性とは，ハッシュ値が与えられたときに，元のメッセージの発見に要する計算量が大きいことによる，発見の困難性のことである。
- エ：衝突発見困難性とは，ハッシュ値が一致する二つの元のメッセージの発見に要する計算量が大きいことによる，発見の困難性のことである。
TSUNAGARU-ADVICE
まず押さえたいこと
衝突発見困難性とは、同じハッシュ値になる二つの異なるメッセージを見つけることが難しいという性質です。
迷ったときの判断軸
ハッシュ値から元のメッセージを見つけにくい性質は、原像計算困難性です。一方、衝突発見困難性では、特定のハッシュ値から元を戻すのではなく、ハッシュ値が一致する二つの元メッセージを探す点に注目します。
科目Bにつなげるために
科目Bでは、ハッシュ関数の性質を、改ざん検知やデジタル署名の文脈で読み取ることがあります。衝突が簡単に見つかると、別のメッセージを同じハッシュ値に見せかけられるため、完全性の確認や署名の信頼性に影響すると理解しておきましょう。
ハッシュ関数は、入力データから固定長のハッシュ値を作る関数です。安全なハッシュ関数には、攻撃を防ぐために主に次の3つの性質が必要です。
衝突発見困難性は、「同じハッシュ値になる別々のデータの組合せ」を探し出すことが難しいという性質です。たとえば、異なるメッセージM1とM2について、hash（M1）＝hash（M2）となる組合せを見つけにくいことを指します。
第二原像計算困難性は、すでにあるメッセージM1が与えられているときに、それと同じハッシュ値になる別のメッセージM2を見つけることが難しいという性質です。
原像計算困難性は、ハッシュ値だけを見ても、元のメッセージMを逆算できないという性質です。
つまり、ハッシュ関数には「同じハッシュ値になる別データを見つけにくいこと」と「ハッシュ値から元データを戻しにくいこと」が求められます。
❌他選択肢が誤りの理由ア：SHA-256の衝突発見困難性を示す，ハッシュ値が一致する二つの元のメッセージの発見に要する最大の計算量は，256の2乗である。
⇒計算量の説明が誤りです。SHA-256の衝突発見は、誕生日攻撃を考えるとおおよそ
2^128程度の計算量が必要とされます。イ：SHA-256の衝突発見困難性を示す，ハッシュ値の元のメッセージの発見に要する最大の計算量は，2の256乗である。
⇒これはハッシュ値から元のメッセージを見つける「原像計算困難性」の説明です。衝突発見困難性ではありません。
ウ：衝突発見困難性とは，ハッシュ値が与えられたときに，元のメッセージの発見に要する計算量が大きいことによる，発見の困難性のことである。
⇒ハッシュ値から元のメッセージを見つける困難性なので、原像計算困難性の説明です。衝突発見困難性ではありません。