衝突発見困難性｜情報処理安全確保支援士 平成29年 秋期午前Ⅱ試験 問4
出典：平成29年秋期 午前Ⅱ 問4
分野：セキュリティ ／ 情報セキュリティ
ハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち，適切なものはどれか。
- ア：SHA-256の衝突発見困難性を示す，ハッシュ値が一致する二つのメッセージの探索に要する最大の計算量は，256の2乗である。
- イ：SHA-256の衝突発見困難性を示す，ハッシュ値の元のメッセージの探索に要する最大の計算量は，2の256乗である。
- ウ：衝突発見困難性とは，ハッシュ値が与えられたときに，元のメッセージの探索に要する計算量が大きいことによる，探索の困難性のことである。
- エ：衝突発見困難性とは，ハッシュ値が一致する二つのメッセージの探索に要する計算量が大きいことによる，探索の困難性のことである。
TSUNAGARU-ADVICE
まず押さえたいこと
ハッシュ関数の衝突発見困難性とは、同じハッシュ値になる二つの異なるメッセージを見つけることが難しいという性質です。つまり、あるハッシュ値から元のメッセージを探す話ではなく、ハッシュ値が一致する別々のメッセージの組を探しにくいという意味です。
迷ったときの判断軸
ハッシュ値から元のメッセージを見つけにくい性質は、原像計算困難性です。また、特定のメッセージと同じハッシュ値になる別メッセージを見つけにくい性質は、第2原像計算困難性として整理されます。衝突発見困難性は、二つの異なるメッセージが同じハッシュ値になる組合せを見つけにくい性質と判断しましょう。
科目Bにつなげるために
科目Bでは、ハッシュ関数・デジタル署名・改ざん検知・パスワード保管・証明書・ブロックチェーンなどと絡めて問われることがあります。ハッシュ関数の性質は似た表現が多いため、元データを探す話なのか、同じハッシュ値になる別データを探す話なのかを切り分けましょう。
ハッシュ関数は、入力データから固定長のハッシュ値を作る仕組みです。改ざん検知や電子署名などで使われるため、「簡単に逆算できないこと」や「同じハッシュ値になる別データを見つけにくいこと」が重要です。
衝突発見困難性は、攻撃者が自由に2つのデータを探して、同じハッシュ値になる組合せを見つけにくいことです。
第二原像計算困難性は、すでに特定のデータM1がある状態で、それと同じハッシュ値になる別データM2を見つけにくいことです。たとえば、正しい契約書と同じハッシュ値になる偽の契約書を作りにくい、というイメージです。
原像計算困難性は、ハッシュ値だけから元データを逆算しにくいことです。ハッシュ関数は一方向の変換であり、ハッシュ値から元の入力を簡単に戻せてはいけません。
つまり、ハッシュ関数の安全性は、「同じハッシュ値になる別データを見つけにくいこと」と「ハッシュ値から元データを戻しにくいこと」で支えられています。
したがって、エが適切です。
❌他選択肢が誤りの理由ア：SHA-256の衝突発見困難性を示す，ハッシュ値が一致する二つのメッセージの発見に要する最大の計算量は，256の2乗である。
⇒SHA-256のハッシュ値は256ビットであり、誕生日攻撃を考慮すると、衝突の発見に必要な計算量の目安は約2の128乗です。256の2乗ではありません。
イ：SHA-256の衝突発見困難性を示す，ハッシュ値の元のメッセージの発見に要する最大の計算量は，2の256乗である。
⇒ハッシュ値から元のメッセージを見つける困難性は、原像計算困難性の説明です。衝突発見困難性は、同じハッシュ値をもつ異なる二つのメッセージを見つける困難性を指します。
ウ：衝突発見困難性とは，ハッシュ値が与えられたときに，元のメッセージの発見に要する計算量が大きいことによる，発見の困難性のことである。
⇒原像計算困難性の説明です。与えられたハッシュ値から元のメッセージを求めることが困難である性質を表しており、二つの異なるメッセージのハッシュ値が一致する組合せを探す衝突発見困難性とは異なります。