Birthday Attack
বার্থডে অ্যাটাক
Birthday paradox কাজে লাগিয়ে hash collision খোঁজার কৌশল — n-bit hash-এ targeted preimage লাগে 2^n কাজ, কিন্তু যেকোনো collision পাওয়া যায় মাত্র ~2^(n/2) হ্যাশেই।
also: birthday paradox attack, birthday bound, birthday paradox
k ≈ 1.1774 * sqrt(2^n) — এত hash-এই 50% সম্ভাবনায় কোনো collision মেলে- ২৩ জনেই ৫০% জন্মদিন-মিল সম্ভাবনা (বছরে ৩৬৫ দিন) — কারণ জোড়ার সংখ্যা
k(k-1)/2, বর্গের হারে বাড়ে - Targeted নয় — attacker একটা নির্দিষ্ট hash-এর সাথে মেলাচ্ছে না, যেকোনো দুইটা input-এর মিলই যথেষ্ট
- SHA-1-এর SHAttered (২০১৭) আক্রমণ birthday bound (
2^80) থেকেও সস্তা হয়েছিল — structural weakness কাজে লাগিয়ে~2^63.1-এ - এই বাউন্ডের কারণেই digest size কাঙ্ক্ষিত security level-এর দ্বিগুণ বাছা হয়