موضوع مقاله: حمله روز تولد | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # حمله روز تولد | مقدمه: حمله روز تولد یک نوع از حملات رمزنگاری است که از محاسبات ریاضی مسئله تاریخ تولد در تئوری احتمال استفاده می‌کند. | ## بخش 1: حمله روز تولد | این حمله می‌تواند جهت سواستفاده بین ارتباطاتی که دو یا چند قسمت با هم دارند مورد استفاده قرار بگیرد. این گونه حملات سعی دارند در جایگشتی قرار بگیرند همانطوری‌ که در مسئله روز تولد توصیف شده‌است. فهمیدن مسئله (مسئله روز تولد) به عنوان یک مثال به سناریوی که یک معلم یک کلاس ۳۰ نفره از دانش آموزانش در مورد روز تولد آن‌ها سؤال می‌کند توجه کنید. اگر معلم یک روز خاص را تعیین کند (مثلاً ۱۳ اسفند) احتمال اینکه حداقل یکی از دانش‌آموزان در آن روز متولد شده باشد برابر است با در حدود ۷٫۹ %. با این وجود احتمال اینکه یک دانش آموز با یک دانش آموزی دیگر روز تولدش یکسان باشد تقریباً برابر ۷۰ ٪ است. ریاضیات یک تابع f مفروض است هدف از حمله پیدا کردن دو ورودی متفاوت X1 , x2 می‌باشد به‌طوری‌ که به هر زوج تصادم گویند. | ## بخش 2: حمله روز تولد | روش مورد استفاده جهت پیدا کردن تصادم ساده‌ است به‌طوری‌که تابع f را برای مقادیر ورودی‌های مختلف که ممکن است به صورت تصادفی یا شبه تصادفی انتخاب شده باشند ارزیابی نموده تا زمانی که نتایج یکسانی برای بیش از یک ورودی بدست آید به دلیل مسئله روز تولد این روش می‌تواند کارا باشد. به‌طور خاص اگر تابع (f(x به ازای Hهای متفاوت خروجی با احتمال مساوی بدست بدهد و H به اندازه کافی بزرگ باشد سپس ما انتظار خواهیم داشت از یک زوج متفاوتنتیجه روبرو را حاصل کنیم بعد از ارزیابی تابع برای حدود آرگومان‌های متفاوت آزمایش زیر را ملاحظه می‌کنیم. از یک مجموعه مقادیر H، n مقدار را به صورت تصادفی انتخاب می‌کنیم که در نتیجه اجازه تکرار به وجود خواهد آمد. در(p(n; H ملاحظه خواهید کرد که در طول این آزمایش احتمال اینکه حداقل یک مقدار انتخاب شده بیش از یکبار اتفاق خواهد افتاد این احتمال می‌تواند توسط رابطه زیر تخمین زده شود رابطه(n(p; H کوچکترین مقداری که انتخاب می‌کنیم را نشان می‌دهد چون احتمال پیدا کردن یک تصادم حداقل p است. با تبدیل کردن عبارت بالا، تخمین زیر بدست می‌آید: و با قرار دادن احتمال ۰٫۵ برای تصادم به رابطه زیر می‌رسیم: با استفاده از(Q(H اعدادی را انتخاب می‌کنیم قبل از اینکه اولین تصادم اتفاق بیفتد این عدد با رابطه زیر تخمین زده می‌شود: به عنوان مثال اگر از یک هش ۶۴ بیتی استفاده شود به‌طور تخمینی ۱٫۸ × ۱۰۱۹خروجی متفاوت خواهیم داشت. اگر همه این موارد احتمال برابر داشته باشند به‌طور تخمینی خروجی متفاوت حدود ۵٫۱ × ۱۰۹ خواهد بود که تلاش می‌کند با یکbrute force تصادم تولید کند به این مقدار محدوده روز تولد می‌گویند. | ## بخش 3: حمله روز تولد | مفهوم تعادل در یک تابع hash، مقدار مقاومت تابع در برابر حمله روز تولد را تعیین می‌کند و اجازه می‌دهد تا آسیب‌پذیری از رشته hashهای رایج مانند MD و SHA تخمین زده شود. حساسیت امضای دیجیتال امضای دیجیتال می‌تواند مستعد برای یک حمله روز تولد باشد پیام m به‌طور خاصی توسط اولین محاسبهعلامت‌گذاری شده‌است هرجا که f یک تابع رمز نگاری hash باشد و از بعضی کلیدهای رمزی برای نشان دادناستفاده می‌کنیم فرض کنید مسعود می‌خواهد با امضای قرارداد جعلی وحید را فریب دهد وحید برای قرارداد منصفانه m و جعلی آماده‌است. بنابراین او اعدادی را برای موقعیت‌های m که قابل تغییر می‌باشد می‌تواند پیدا کند بدون اینکه تغییری در امضا به وجود آید. با ترکیب کردن این تغییرات او می‌تواند تعداد زیادی از تغییرات بر روی m که قرار دادهای عادلانه آنان را می‌باشد را ایجاد کند. در حالتی مشابه، وحید همچنین تعداد زیادی از تغییرات بر روی که قراردادهای جعلی در آن می‌باشد را ایجاد می‌کند او سپس تابع HASH را به همه این تغییرات تا زمانی که یک نسخه از قرار داد منصفانه و یک نسخه از قرارداد جعلی پیدا کند اعمال می‌کند که در آن مقادیر HASH یکسانی هستند .او نسخه عادلانه و صحیح را برای امضا به مسعود ارائه می‌کند، پس از اینکه او امضا کرد وحید امضا نمودن آن را قرارداد جعلی الصاق می‌کند. | ## جمع‌بندی | احتمالات کمی متفاوت از مسئله اصلی روز تولد است، چرا که وحید دو قرارداد عادلانه یا دو قرارداد جعلی با یک HASH یکسان بدست نیاورده‌است.استراتژی وحید تولید کردن یک زوج قرارداد عادلانه و یک زوج قرارداد جعلی است.