حمله روز تولد

حمله روز تولد یک نوع از حملات رمزنگاری است که از محاسبات ریاضی مسئله تاریخ تولد در تئوری احتمال استفاده می‌کند. این حمله می‌تواند جهت سواستفاده بین ارتباطاتی که دو یا چند قسمت با هم دارند مورد استفاده قرار بگیرد. انجام حمله و موفقیت آن به تصادم‌هایی که بین حملات تصادفی رخ می‌دهد بستگی دارد. این گونه حملات سعی دارند در جایگشتی قرار بگیرند همانطوری که در مسئله روز تولد توصیف شده‌است.

فهمیدن مسئله (مسئله روز تولد)

به عنوان یک مثال به سناریوی که یک معلم یک کلاس ۳۰ نفره از دانشجویانش در مورد روز تولد آنها سوال می‌کند توجه کنید. مشخص کنید آیا دو دانشجو که تاریخ تولد یکسان دارند وجود دارد. به طور حسی این شانش ممکن است کمتر اتفاق بیفتد. اگر معلم یک روز خاص را تعیین کند (مثلا ۱۳ اسفند) احتمال اینکه حداقل یکی از دانشجویان در آن روز متولد شده باشد برابر است با$1 - (364/365)^{30}$ در حدود ۷٫۹ %. با این وجود احتمال اینکه یک دانشجو با یک دانشجوی دیگر روز تولدش یکسان باشد تقریبا برابر ۷۰ ٪ است.

$1-365!/((365-n)!\cdot365^n)$

ریاضیات

یک تابع 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)
		۱۰−۱۸	۱۰−۱۵	۱۰−۱۲	۱۰−۹	۱۰−۶	۰٫۱%	۱%	۲۵%	۵۰%	۷۵%
۱۶	۶٫۶ × ۱۰۴	۲	۲	۲	۲	۲	۱۱	۳۶	۱٫۹ × ۱۰۲	۳٫۰ × ۱۰۲	۴٫۳ × ۱۰۲
۳۲	۴٫۳ × ۱۰۹	۲	۲	۲	۲٫۹	۹۳	۲٫۹ × ۱۰۳	۹٫۳ × ۱۰۳	۵٫۰ × ۱۰۴	۷٫۷ × ۱۰۴	۱٫۱ × ۱۰۵
۶۴	۱٫۸ × ۱۰۱۹	۶٫۱	۱٫۹ × ۱۰۲	۶٫۱ × ۱۰۳	۱٫۹ × ۱۰۵	۶٫۱ × ۱۰۶	۱٫۹ × ۱۰۸	۶٫۱ × ۱۰۸	۳٫۳ × ۱۰۹	۵٫۱ × ۱۰۹	۷٫۲ × ۱۰۹
۱۲۸	۳٫۴ × ۱۰۳۸	۲٫۶ × ۱۰۱۰	۸٫۲ × ۱۰۱۱	۲٫۶ × ۱۰۱۳	۸٫۲ × ۱۰۱۴	۲٫۶ × ۱۰۱۶	۸٫۳ × ۱۰۱۷	۲٫۶ × ۱۰۱۸	۱٫۴ × ۱۰۱۹	۲٫۲ × ۱۰۱۹	۳٫۱ × ۱۰۱۹
۲۵۶	۱٫۲ × ۱۰۷۷	۴٫۸ × ۱۰۲۹	۱٫۵ × ۱۰۳۱	۴٫۸ × ۱۰۳۲	۱٫۵ × ۱۰۳۴	۴٫۸ × ۱۰۳۵	۱٫۵ × ۱۰۳۷	۴٫۸ × ۱۰۳۷	۲٫۶ × ۱۰۳۸	۴٫۰ × ۱۰۳۸	۵٫۷ × ۱۰۳۸
۳۸۴	۳٫۹ × ۱۰۱۱۵	۸٫۹ × ۱۰۴۸	۲٫۸ × ۱۰۵۰	۸٫۹ × ۱۰۵۱	۲٫۸ × ۱۰۵۳	۸٫۹ × ۱۰۵۴	۲٫۸ × ۱۰۵۶	۸٫۹ × ۱۰۵۶	۴٫۸ × ۱۰۵۷	۷٫۴ × ۱۰۵۷	۱٫۰ × ۱۰۵۸
۵۱۲	۱٫۳ × ۱۰۱۵۴	۱٫۶ × ۱۰۶۸	۵٫۲ × ۱۰۶۹	۱٫۶ × ۱۰۷۱	۵٫۲ × ۱۰۷۲	۱٫۶ × ۱۰۷۴	۵٫۲ × ۱۰۷۵	۱٫۶ × ۱۰۷۶	۸٫۸ × ۱۰۷۶	۱٫۴ × ۱۰۷۷	۱٫۹ × ۱۰۷۷

به راحتی خروجی‌های یک تابع توزیع یکنواخت دیده می‌شود بنابراین یک تصادم یافت می‌شود حتی سریعتر نیز این اتفاق می‌افتد. مفهوم تعادل در یک تابع hash، مقدار مقاومت تابع در برابر حمله روز تولد را تعیین می‌کند و اجازه می‌دهد تا آسیب پذیری از رشته hashهای رایج مانند MD و SHA تخمین زده شود.

حساسیت امضای دیجیتال

امضای دیجیتال می‌تواند مستعد برای یک حمله روز تولد باشد پیام m به طور خاصی توسط اولین محاسبه$f(m)$علامتگذاری شده‌است هرجا که f یک تابع رمز نگاری hash باشد و از بعضی کلیدهای رمزی برای نشان دادن$f(m)$استفاده می‌کنیم فرض کنید مسعود می‌خواهد با امضای قرارداد جعلی وحید را فریب دهد وحید برای قرارداد منصفانه m وجعلی $m'$آماده‌است. بنابراین او اعدادی را برای موقعیت‌های m که قابل تغییر می‌باشد می‌تواند پیدا کند بدون اینکه تغییری در امضا بوجود آید. از قبیل قرار دادن کاما، خط خالی، یک جمله در دو جابجایی مترادف‌ها و غیره. با ترکیب کردن این تغییرات او می‌تواند تعداد زیادی از تغییرات بر روی m که قرار دادهای عادلانه آنان را می‌باشد را ایجاد کند. در حالتی مشابه، وحید همچنین تعداد زیادی از تغییرات بر روی $m'$که قراردادهای جعلی در آن می‌باشد را ایجاد می‌کند او سپس تابع HASH را به همه این تغییرات تا زمانی که یک نسخه از قرار داد منصفانه و یک نسخه از قرارداد جعلی ییدا کند اعمال می‌کند که در آن مقادیر HASH یکسانی هستند $f(m) = f(m')$.
او نسخه عادلانه و صحیح را برای امضا به مسعود ارایه می‌کند، پس از اینکه او امضا کرد وحید امضا نمودن آن را قرارداد جعلی الصاق می‌کند. این امضا پس از آن ثابت می‌کند که مسعود قرارداد جعلی را امضا کرده‌است. احتمالات کمی متفاوت از مسئله اصلی روز تولد است، چرا که وحید دو قرارداد عادلانه یا دو قرارداد جعلی با یک HASH یکسان بدست نیاورده‌است.
استراتژی وحید تولید کردن یک زوج قرارداد عادلانه و یک زوج قرارداد جعلی است. مسئله روز تولد معادله‌ای که n یک عدد زوج می‌باشد را می‌پذیرد. تعداد hashهایی که وحید تولید کرده‌است برابر $2n$ می‌باشد.
برای جلوگیری از این حمله، طول خروجی تابع hash استفاده شده برای طرح امضا می‌تواند به اندازه کافی بزرگ انتخاب شود تا اینکه حمله روز تولد با محاسباتی عملی نشود به این معنی که حدود دو برابر بیتهایی که مورد نیاز است برای جلوگیری از حمله brute force استفاده شود به عنوان مثال برای یک الگوریتم که از حمله روز تولد برای محاسبه الگوریتم گسسته استفاده می‌شود می‌توان به Pollard's rho algorithm for logarithms اشاره کرد. حمله روز تولد اغلب به عنوان یک ضعف موجود در سیستمهای DNS اینترنت بحث می‌شود.

منابع

• مشارکت‌کنندگان ویکی‌پدیا، «Birthday attack»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۱۵ جولای ۲۰۱۲).