情報処理安全確保支援士(情報セキュリティスペシャリスト) 試験情報＆徹底解説

報処理安全確保支援士平成29年秋期 午前Ⅱ 問4について教えてください。

選択肢イの以下解説文で「同じハッシュ値を出力する入力値は1つ以上ある」
というのがわかりません。
私はハッシュ関数は入力値が少しでも異なれば
全然異なる出力値になると理解しています。
aとbを入力すると同じ出力値のcが生成されるということですよね。
ごくまれに、異なる入力値から同じ出力値が生成されることもあるのでしょうか？

イ.解説文
SHA-256の衝突発見困難性を示す，ハッシュ値の元のメッセージの探索に要する最大の計算量は，2の256乗である。
nビットのハッシュ関数に対する原像攻撃では、攻撃が成功するまでの試行回数は2nに比例します。ただし、同じハッシュ値を出力する入力値は1つ以上あるので2256回の試行で必ず元のメッセージを探索できるわけではありません。

> ごくまれに、異なる入力値から同じ出力値が生成されることもあるのでしょうか？

その通りです。
ハッシュ関数には出力値が一意であるという保証はありません（もしそうであれば、理論上は既知の出力値を元にして入力値を復元できてしまいます）。
なお、ハッシュ関数において、異なる入力値から同一の出力値が出力されることを、衝突（コリジョン）と呼びます。

>ごくまれに、異なる入力値から同じ出力値が生成されることもあるのでしょうか？
はい。そうです。
しかしその「ごくまれ」が途方もなく大きな数ということになります。

話を簡単にするために概要で説明します。
256ビットのハッシュ値のパターンは2の256乗になります。これは十進数で
約10の78乗です。
参考として、宇宙のすべての原子の数が約10の80乗といわれています。
2の256乗とはそれほど巨大な数であり、この回数くらい試せば、同じ出力値が
生成されるかもしれないということです。

自称みなし合格士様、pix様
ご回答ありがとうございます。

たとえ2の256乗通り出力値があっても
2の256乗+1の値を入力すれば、2の256乗通りの
出力値のどれかと同じ出力値になるのですね。
理解しました。

論理的にはもっと単純です。

数Mバイトデータから算出された値がユニークになるには最低でも数Mバイトのデータサイズが必要で、数Gバイトデータから算出された値がユニークになるには最低でも数Gバイトのデータサイズが必要になります。
従って、数Tバイトデータから算出されたわずか数Kバイトのハッシュ値がユニークになるはずはありません。

時間がある今のうちにハッシュ関数やハッシュ値の性質や利用方法など基礎を理解しておきましょう。