حمله روز تولد
ریاضیات

یک تابع f مفروض است هدف از حمله پیدا کردن دو ورودی متفاوت  X1 , x2 می‌باشد به‌طوری‌ که  f(x_{1})=f(x_{2})  به هر زوج  x_{1},x_{2}  تصادم گویند. روش مورد استفاده جهت پیدا کردن تصادم ساده‌ است به‌طوری‌که تابع f را برای مقادیر ورودی‌های مختلف که ممکن است به صورت تصادفی یا شبه تصادفی انتخاب شده باشند ارزیابی نموده تا زمانی که نتایج یکسانی برای بیش از یک ورودی بدست آید به دلیل مسئله روز تولد این روش می‌تواند کارا باشد. به‌طور خاص اگر تابع (f(x به ازای Hهای متفاوت خروجی با احتمال مساوی بدست بدهد و H به اندازه کافی بزرگ باشد سپس ما انتظار خواهیم داشت از یک زوج متفاوت x_{1},x_{2}نتیجه روبرو را حاصل کنیم f(x_{1})=f(x_{2}) بعد از ارزیابی تابع برای حدود  1.25{\sqrt {H}} آرگومان‌های متفاوت آزمایش زیر را ملاحظه می‌کنیم. از یک مجموعه مقادیر H، n مقدار را به صورت تصادفی انتخاب می‌کنیم  که در نتیجه اجازه تکرار به وجود خواهد آمد.
در(p(n; H  ملاحظه خواهید کرد که در طول این آزمایش احتمال اینکه حداقل یک مقدار انتخاب شده بیش از یکبار اتفاق خواهد افتاد این احتمال می‌تواند توسط رابطه زیر تخمین زده شود
p(n;H)\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^{2}/(2H)},\,
رابطه(n(p; H کوچکترین مقداری که انتخاب می‌کنیم را نشان می‌دهد چون احتمال پیدا کردن یک تصادم  حداقل  p است. با تبدیل کردن عبارت بالا، تخمین زیر بدست می‌آید:
n(p;H)\approx {\sqrt {2H\ln {\frac {1}{1-p}}}},
و با قرار دادن احتمال ۰٫۵ برای تصادم به رابطه زیر می‌رسیم:
n(0.5;H)\approx 1.1774{\sqrt {H}}.\,
با استفاده از(Q(H اعدادی را انتخاب می‌کنیم قبل از اینکه اولین تصادم اتفاق بیفتد این عدد با رابطه زیر تخمین زده می‌شود:
Q(H)\approx {\sqrt {{\frac {\pi }{2}}H}}.
به عنوان مثال اگر از یک هش ۶۴ بیتی استفاده شود به‌طور تخمینی ۱٫۸ × ۱۰۱۹خروجی متفاوت خواهیم داشت. اگر همه این موارد احتمال برابر داشته باشند به‌طور تخمینی خروجی متفاوت حدود  ۵٫۱ × ۱۰۹ خواهد بود که تلاش می‌کند با یکbrute force تصادم تولید کند به  این مقدار محدوده روز تولد  می‌گویند. و برای n  بیت کد، 2n/2  محاسبه صورت گرفته‌ است.
| Bits | Possible outputs (rounded)(H) | Desired probability of random collision (rounded) (p)> ۱۰−۱۸ | Desired probability of random collision (rounded) (p)> ۱۰−۱۵ | Desired probability of random collision (rounded) (p)> ۱۰−۱۲ | Desired probability of random collision (rounded) (p)> ۱۰−۹ | Desired probability of random collision (rounded) (p)> ۱۰−۶ | Desired probability of random collision (rounded) (p)> ۰٫۱% | Desired probability of random collision (rounded) (p)> ۱% | Desired probability of random collision (rounded) (p)> ۲۵% | Desired probability of random collision (rounded) (p)> ۵۰% | Desired probability of random collision (rounded) (p)> ۷۵% |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| ۱۶ | ۶٫۶ × ۱۰۴ | ۲ | ۲ | ۲ | ۲ | ۲ | ۱۱ | ۳۶ | ۱٫۹ × ۱۰۲ | ۳٫۰ × ۱۰۲ | ۴٫۳ × ۱۰۲ |
| ۳۲ | ۴٫۳ × ۱۰۹ | ۲ | ۲ | ۲ | ۲٫۹ | ۹۳ | ۲٫۹ × ۱۰۳ | ۹٫۳ × ۱۰۳ | ۵٫۰ × ۱۰۴ | ۷٫۷ × ۱۰۴ | ۱٫۱ × ۱۰۵ |
| ۶۴ | ۱٫۸ × ۱۰۱۹ | ۶٫۱ | ۱٫۹ × ۱۰۲ | ۶٫۱ × ۱۰۳ | ۱٫۹ × ۱۰۵ | ۶٫۱ × ۱۰۶ | ۱٫۹ × ۱۰۸ | ۶٫۱ × ۱۰۸ | ۳٫۳ × ۱۰۹ | ۵٫۱ × ۱۰۹ | ۷٫۲ × ۱۰۹ |
| ۱۲۸ | ۳٫۴ × ۱۰۳۸ | ۲٫۶ × ۱۰۱۰ | ۸٫۲ × ۱۰۱۱ | ۲٫۶ × ۱۰۱۳ | ۸٫۲ × ۱۰۱۴ | ۲٫۶ × ۱۰۱۶ | ۸٫۳ × ۱۰۱۷ | ۲٫۶ × ۱۰۱۸ | ۱٫۴ × ۱۰۱۹ | ۲٫۲ × ۱۰۱۹ | ۳٫۱ × ۱۰۱۹ |
| ۲۵۶ | ۱٫۲ × ۱۰۷۷ | ۴٫۸ × ۱۰۲۹ | ۱٫۵ × ۱۰۳۱ | ۴٫۸ × ۱۰۳۲ | ۱٫۵ × ۱۰۳۴ | ۴٫۸ × ۱۰۳۵ | ۱٫۵ × ۱۰۳۷ | ۴٫۸ × ۱۰۳۷ | ۲٫۶ × ۱۰۳۸ | ۴٫۰ × ۱۰۳۸ | ۵٫۷ × ۱۰۳۸ |
| ۳۸۴ | ۳٫۹ × ۱۰۱۱۵ | ۸٫۹ × ۱۰۴۸ | ۲٫۸ × ۱۰۵۰ | ۸٫۹ × ۱۰۵۱ | ۲٫۸ × ۱۰۵۳ | ۸٫۹ × ۱۰۵۴ | ۲٫۸ × ۱۰۵۶ | ۸٫۹ × ۱۰۵۶ | ۴٫۸ × ۱۰۵۷ | ۷٫۴ × ۱۰۵۷ | ۱٫۰ × ۱۰۵۸ |
| ۵۱۲ | ۱٫۳ × ۱۰۱۵۴ | ۱٫۶ × ۱۰۶۸ | ۵٫۲ × ۱۰۶۹ | ۱٫۶ × ۱۰۷۱ | ۵٫۲ × ۱۰۷۲ | ۱٫۶ × ۱۰۷۴ | ۵٫۲ × ۱۰۷۵ | ۱٫۶ × ۱۰۷۶ | ۸٫۸ × ۱۰۷۶ | ۱٫۴ × ۱۰۷۷ | ۱٫۹ × ۱۰۷۷ |
به راحتی خروجی‌های یک تابع توزیع یکنواخت دیده می‌شود بنابراین یک تصادم یافت می‌شود حتی سریعتر نیز این اتفاق می‌افتد.
مفهوم تعادل در یک تابع hash، مقدار مقاومت تابع در برابر حمله روز تولد را تعیین می‌کند و اجازه می‌دهد تا آسیب‌پذیری از رشته hashهای رایج مانند MD و SHA تخمین زده شود.