【IPA対策】弱衝突耐性と強衝突耐性

弱衝突耐性と強衝突耐性

弱衝突耐性と強衝突耐性の定義は，下記の通りです。

• 弱衝突耐性：あるメッセージm1と同一のハッシュ値をもつメッセージm2を見つけることが困難であること
• 強衝突耐性：同一のハッシュ値をもつメッセージm1とm2を見つけることが事実上不可能であること

誕生日が自分と同じ人が見つかる確率が0.5となる人数は自分を含めて254人であるのに対し，日付は指定せずに誕生日が同じ人が見つかる確率が0.5となる人数は23人となります。前者は弱衝突耐性を突破しようとする試行，後者は強衝突耐性を突破しようとする試行です。

覚え方

弱衝突耐性と強衝突耐性を覚えようとするとき，なぜ弱衝突耐性は「弱く」て衝突耐性は「強い」のか理解に苦しむことがあると思います。上で説明した誕生日の例でも分かる通り，強衝突耐性を突破する方が弱衝突耐性を突破するよりも簡単です。これは強衝突耐性が「強い」という言葉のイメージを矛盾します。割り切って覚えられる方はよいのですが，管理人のように暗記が苦手な方は少し回り道をして覚えましょう。ここからの説明は数学的に厳密ではないため，あくまでも暗記のための手段だと捉えてください。

定義より「弱衝突耐性を有していれば強衝突耐性も有している」ことが成り立つことに注目します。衝突に対する耐性の「保証」を表すベン図を考えると，弱衝突耐性が強衝突耐性を包含することになります。なぜなら，強衝突耐性では保証できないが，弱衝突耐性では保証できる領域（=自分以外の誕生日）が存在するからです。一般に，ベン図が小さいほど「（条件が）強い」と表現するため，弱衝突耐性は「弱く」て強衝突耐性は「強い」とされているものと考えられます。

補足1

弱衝突耐性よりも「弱い」衝突耐性として「現像耐性」があります。これは，あるハッシュ値をもつメッセージを見つけることが困難であること，と定義されます。

補足2

弱衝突耐性は第二現像計算耐性とも呼ばれ，強衝突耐性は単に衝突耐性とも呼ばれます。

• 現像耐性：ハッシュ値を固定
• 第二現像耐性：片方のメッセージを固定（逆関数は求めなくてよい）
• 衝突耐性：二つのメッセージは任意

つまり，現像耐性を破るのが一番困難で，次に第二現像攻撃を破るのが困難で，衝突耐性を破るのが一番容易であるという関係になります。これを理解すれば，ハッシュの攻撃として

• 現像攻撃：衝突耐性を破ろうとする攻撃。逆関数解読のイメージ。
• 第二現像攻撃：弱衝突耐性を破ろうとする攻撃。自分と同じ誕生日の人を見つける試行のイメージ。
• 衝突攻撃：強衝突耐性を破ろうとする攻撃。誰でもいいから同じ誕生日のペアを見つける試行のイメージ。

を理解できるようになるはずです。