衝突困難性（Collision Resistance）

0 / 4

衝突困難性とは

衝突困難性は、ハッシュ値が同じ異なる2つの入力、つまり衝突を見つけられないという性質です。強衝突耐性とも呼ばれます。第二原像と違って攻撃者が2つの入力を両方選べるので、攻撃がより簡単で、その分守るのが難しい性質です。

オレンジの行は攻撃者が選んだ入力です。その下に、互いに比べた組の数を数えます。

1 / 4

2つの入力を両方選ぶ

攻撃者はvote yesとvote noのように、2つの入力を自由に選べます。この2つはハッシュ値が違います。決まったハッシュ値を当てる必要はなく、どんな2つでも同じになれば成功です。

2 / 4

入力が増えると組が急に増える

入力を4つ集めると、比べる組は6つになります。k個集めると組は約k²/2個なので、ハッシュ値が2^256通りでも約2^128個集めれば衝突が見つかる見込みです。23人集まるだけで誕生日が同じ2人がいる確率が半分を超える、誕生日のパラドックスと同じです。

3 / 4

衝突があれば差し替えられる

ハッシュ値が同じ契約書を2通作れれば、無害な方に署名をもらってから別の方に差し替えても、署名はそのまま通ります。衝突困難性を持つハッシュ関数は、第二原像計算困難性も併せ持ちます。

4 / 4

MD5とSHA-1は破られた

MD5は2004年、SHA-1は2017年に実際の衝突が見つかり、セキュリティ用途には使われません。今はSHA-256などのSHA-2やSHA-3を使います。