ハッシュの衝突発見困難性｜情報処理安全確保支援士 平成31年 春期午前Ⅱ試験 問4
出典：平成31年春期 午前Ⅱ 問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乗である。
⇒ハッシュ値から元のメッセージを見つける困難性は、原像計算困難性の説明です。衝突発見困難性は、同じハッシュ値をもつ異なる二つのメッセージを見つける困難性を指します。
ウ：衝突発見困難性とは，ハッシュ値が与えられたときに，元のメッセージの発見に要する計算量が大きいことによる，発見の困難性のことである。
⇒原像計算困難性の説明です。与えられたハッシュ値から元のメッセージを求めることが困難である性質を表しており、二つの異なるメッセージのハッシュ値が一致する組合せを探す衝突発見困難性とは異なります。