حمله روز تولد
حمله روز تولد یک نوع از حملات رمزنگاری است که از محاسبات ریاضی مسئله تاریخ تولد در تئوری احتمال استفاده می‌کند. این حمله می‌تواند جهت سواستفاده بین ارتباطاتی که دو یا چند قسمت با هم دارند مورد استفاده قرار بگیرد. انجام حمله و موفقیت آن به تصادم‌هایی که بین حملات تصادفی رخ می‌دهد بستگی دارد. این گونه حملات سعی دارند در جایگشتی قرار بگیرند همانطوری‌ که در مسئله روز تولد توصیف شده‌است.
به عنوان یک مثال به سناریوی که یک معلم یک کلاس ۳۰ نفره از دانش آموزانش در مورد روز تولد آن‌ها سؤال می‌کند توجه کنید. مشخص کنید آیا دو دانشجو که تاریخ تولد یکسان دارند وجود دارد. به طور حسی این شانس ممکن است کمتر اتفاق بیفتد. اگر معلم یک روز خاص را تعیین کند (مثلاً ۱۳ اسفند) احتمال اینکه حداقل یکی از دانش‌آموزان در آن روز متولد شده باشد برابر است باformula_1 در حدود ۷٫۹ %. با این وجود احتمال اینکه یک دانش آموز با یک دانش آموزی دیگر روز تولدش یکسان باشد تقریباً برابر ۷۰ ٪ است.
formula_2
یک تابع f مفروض است هدف از حمله پیدا کردن دو ورودی متفاوت X1 , x2 می‌باشد به‌طوری‌ که formula_3 به هر زوج formula_4 تصادم گویند. روش مورد استفاده جهت پیدا کردن تصادم ساده‌ است به‌طوری‌که تابع f را برای مقادیر ورودی‌های مختلف که ممکن است به صورت تصادفی یا شبه تصادفی انتخاب شده باشند ارزیابی نموده تا زمانی که نتایج یکسانی برای بیش از یک ورودی بدست آید به دلیل مسئله روز تولد این روش می‌تواند کارا باشد. به‌طور خاص اگر تابع (f(x به ازای Hهای متفاوت خروجی با احتمال مساوی بدست بدهد و H به اندازه کافی بزرگ باشد سپس ما انتظار خواهیم داشت از یک زوج متفاوتformula_4نتیجه روبرو را حاصل کنیمformula_3 بعد از ارزیابی تابع برای حدود formula_7 آرگومان‌های متفاوت آزمایش زیر را ملاحظه می‌کنیم. از یک مجموعه مقادیر H، n مقدار را به صورت تصادفی انتخاب می‌کنیم که در نتیجه اجازه تکرار به وجود خواهد آمد. در(p(n; H ملاحظه خواهید کرد که در طول این آزمایش احتمال اینکه حداقل یک مقدار انتخاب شده بیش از یکبار اتفاق خواهد افتاد این احتمال می‌تواند توسط رابطه زیر تخمین زده شود
formula_8 رابطه(n(p; H کوچکترین مقداری که انتخاب می‌کنیم را نشان می‌دهد چون احتمال پیدا کردن یک تصادم حداقل p است. با تبدیل کردن عبارت بالا، تخمین زیر بدست می‌آید:
formula_9
و با قرار دادن احتمال ۰٫۵ برای تصادم به رابطه زیر می‌رسیم:
formula_10
با استفاده از(Q(H اعدادی را انتخاب می‌کنیم قبل از اینکه اولین تصادم اتفاق بیفتد این عدد با رابطه زیر تخمین زده می‌شود:
formula_11
به عنوان مثال اگر از یک هش ۶۴ بیتی استفاده شود به‌طور تخمینی ۱٫۸ × ۱۰۱۹خروجی متفاوت خواهیم داشت. اگر همه این موارد احتمال برابر داشته باشند به‌طور تخمینی خروجی متفاوت حدود ۵٫۱ × ۱۰۹ خواهد بود که تلاش می‌کند با یکbrute force تصادم تولید کند به این مقدار محدوده روز تولد می‌گویند. و برای n بیت کد، 2n/2 محاسبه صورت گرفته‌ است.
به راحتی خروجی‌های یک تابع توزیع یکنواخت دیده می‌شود بنابراین یک تصادم یافت می‌شود حتی سریعتر نیز این اتفاق می‌افتد. مفهوم تعادل در یک تابع hash، مقدار مقاومت تابع در برابر حمله روز تولد را تعیین می‌کند و اجازه می‌دهد تا آسیب‌پذیری از رشته hashهای رایج مانند MD و SHA تخمین زده شود.
امضای دیجیتال می‌تواند مستعد برای یک حمله روز تولد باشد پیام m به‌طور خاصی توسط اولین محاسبهformula_12علامت‌گذاری شده‌است هرجا که f یک تابع رمز نگاری hash باشد و از بعضی کلیدهای رمزی برای نشان دادنformula_12استفاده می‌کنیم فرض کنید مسعود می‌خواهد با امضای قرارداد جعلی وحید را فریب دهد وحید برای قرارداد منصفانه m و جعلی formula_14آماده‌است. بنابراین او اعدادی را برای موقعیت‌های m که قابل تغییر می‌باشد می‌تواند پیدا کند بدون اینکه تغییری در امضا به وجود آید. از قبیل قرار دادن کاما، خط خالی، یک جمله در دو جابجایی مترادف‌ها و غیره. با ترکیب کردن این تغییرات او می‌تواند تعداد زیادی از تغییرات بر روی m که قرار دادهای عادلانه آنان را می‌باشد را ایجاد کند. در حالتی مشابه، وحید همچنین تعداد زیادی از تغییرات بر روی formula_14که قراردادهای جعلی در آن می‌باشد را ایجاد می‌کند او سپس تابع HASH را به همه این تغییرات تا زمانی که یک نسخه از قرار داد منصفانه و یک نسخه از قرارداد جعلی پیدا کند اعمال می‌کند که در آن مقادیر HASH یکسانی هستند formula_16.او نسخه عادلانه و صحیح را برای امضا به مسعود ارائه می‌کند، پس از اینکه او امضا کرد وحید امضا نمودن آن را قرارداد جعلی الصاق می‌کند. این امضا پس از آن ثابت می‌کند که مسعود قرارداد جعلی را امضا کرده‌است. احتمالات کمی متفاوت از مسئله اصلی روز تولد است، چرا که وحید دو قرارداد عادلانه یا دو قرارداد جعلی با یک HASH یکسان بدست نیاورده‌است.استراتژی وحید تولید کردن یک زوج قرارداد عادلانه و یک زوج قرارداد جعلی است. مسئله روز تولد معادله‌ای که n یک عدد زوج می‌باشد را می‌پذیرد. تعداد hashهایی که وحید تولید کرده‌است برابر formula_17 می‌باشد. برای جلوگیری از این حمله، طول خروجی تابع hash استفاده شده برای طرح امضا می‌تواند به اندازه کافی بزرگ انتخاب شود تا اینکه حمله روز تولد با محاسباتی عملی نشود به این معنی که حدود دو برابر بیتهایی که مورد نیاز است برای جلوگیری از حمله brute force استفاده شود به عنوان مثال برای یک الگوریتم که از حمله روز تولد برای محاسبه الگوریتم گسسته استفاده می‌شود می‌توان به Pollard's rho algorithm for logarithms اشاره کرد. حمله روز تولد اغلب به عنوان یک ضعف موجود در سیستم‌های DNS اینترنت بحث می‌شود.