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