ハッシュ関数の性質
暗号学的ハッシュ関数 h の性質のうち，第二原像計算困難性（弱衝突耐性）の説明はどれか。
- ア入力 x が与えられたとき，h(x) = h(x') となる，x とは異なる x' を見つけることが計算量的に困難である。
- イハッシュ値 y が与えられたとき，h(x) = y となる入力 x を見つけることが計算量的に困難である。
- ウh(x) = h(x') となる，互いに異なる二つの入力 x，x' の組を見つけることが計算量的に困難である。
- エ入力が 1 ビット変化すると，出力のビットのうち約半分が変化する。
正解と解説を見る
正解 ア
この問題の基礎知識
- 暗号学的ハッシュ関数に求められる性質には，原像計算困難性（一方向性），第二原像計算困難性（弱衝突耐性），衝突困難性（強衝突耐性）がある。
- 3 つの性質は攻撃者に与えられる条件で区別する。ハッシュ値だけが与えられる，特定の入力が与えられる，入力を自由に選べる，の違いである。
- 誕生日のパラドックスにより，n ビットのハッシュ値の衝突はおよそ 2 の n/2 乗回の試行で見つかる見込みがあり，原像や第二原像の探索（およそ 2 の n 乗回）より容易である。
ア入力 x が与えられたとき，h(x) = h(x') となる，x とは異なる x' を見つけることが計算量的に困難である。正解
特定の入力 x を固定した上で，同じハッシュ値をもつ別の入力 x' を見つけることが困難である性質が第二原像計算困難性である。改ざんした文書を元の署名と一致させる攻撃への耐性に関わる。
イハッシュ値 y が与えられたとき，h(x) = y となる入力 x を見つけることが計算量的に困難である。
ハッシュ値だけから対応する入力を求めることが困難である性質は，原像計算困難性（一方向性）である。パスワードのハッシュ値から元のパスワードを求められないことなどに関わる。
ウh(x) = h(x') となる，互いに異なる二つの入力 x，x' の組を見つけることが計算量的に困難である。
入力を自由に選んでよい条件で同じハッシュ値をもつ組を見つけることが困難である性質は，衝突困難性（強衝突耐性）である。誕生日攻撃により，第二原像よりも少ない計算量で探索され得る。
エ入力が 1 ビット変化すると，出力のビットのうち約半分が変化する。
入力の僅かな変化が出力全体に大きく波及する性質はアバランシェ効果（雪崩効果）と呼ばれる。ハッシュ関数に望ましい性質ではあるが，第二原像計算困難性の定義ではない。
検証用の出典出典照合済み
NIST SP 800-107 Rev. 1 Recommendation for Applications Using Approved Hash Algorithms ／ A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996照合の根拠（4 件）
- ア（正解）: 第二原像計算困難性の定義
Second preimage resistance: It is computationally infeasible to find a second input that has the same hash value as any other specified input. That is, given an input x, it is computationally infeasible to find a second input x’ that is different from x, such that hash(x) = hash(x’).
NIST SP 800-107 Rev. 1 · Section 4.1（新しいタブで開きます） - イ（誤り）: ハッシュ値から入力を求められない性質は原像計算困難性（一方向性）
Given a randomly chosen hash value, hash_value, it is computationally infeasible to find an x so that hash(x) = hash_value. This property is also called the one-way property.
NIST SP 800-107 Rev. 1 · Section 4.1（新しいタブで開きます） - ウ（誤り）: 任意の異なる 2 入力の衝突を見つけられない性質は衝突困難性
it is computationally infeasible to find two different inputs x and x’ for which hash(x) = hash(x’).
NIST SP 800-107 Rev. 1 · Section 4.1（新しいタブで開きます） - ウの解説: 衝突困難性の強度は第二原像（L ビット）の半分（L/2 ビット）。エ（アバランシェ効果）は上記 3 性質の定義に含まれず，第二原像計算困難性の定義から排除される
The expected collision-resistance strength of a hash function is half the length of the hash value produced by that hash function
NIST SP 800-107 Rev. 1 · Section 4.1（新しいタブで開きます）