Collision Resistance

কলিশন রেজিস্ট্যান্স

দুইটা ভিন্ন input যেন একই hash output না দেয় তা খুঁজে বের করা computationally infeasible — birthday paradox-এর কারণে এই resistance digest size-এর অর্ধেক বিটেই সীমাবদ্ধ।

also: collision resistant, hash collision resistance, collision resistance property

find m1 != m2 such that H(m1) == H(m2)     (attacker উভয়ই স্বাধীনভাবে বাছে)

naive খরচ:  2^(n/2)   — preimage-এর 2^n থেকে অনেক কম

SHA-256-এ n=256, কিন্তু collision resistance মাত্র 2^128 — birthday bound-এর কারণ
MD5 (২০০৪) আর SHA-1 (SHAttered, ২০১৭) — দুইটারই collision resistance practically ভেঙেছে
Preimage/second-preimage resistance-এর সাথে সরাসরি সম্পর্ক নেই — স্বাধীন গ্যারান্টি
Digest size বাছার নিয়ম: কাঙ্ক্ষিত collision-security-এর দ্বিগুণ বিট output লাগবে