حمله روز تولد

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

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

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

${\displaystyle 1-365!/((365-n)!\cdot 365^{n})}$

ریاضیات

یک تابع f مفروض است هدف از حمله پیدا کردن دو ورودی متفاوت X1 , x2 می‌باشد به‌طوری‌که ${\displaystyle f(x_{1})=f(x_{2})}$ به هر زوج ${\displaystyle x_{1},x_{2}}$ تصادم گویند. روش مورد استفاده جهت پیدا کردن تصادم ساده‌ است به‌طوری‌که تابع f را برای مقادیر ورودی‌های مختلف که ممکن است به صورت تصادفی یا شبه تصادفی انتخاب شده باشند ارزیابی نموده تا زمانی که نتایج یکسانی برای بیش از یک ورودی بدست آید به دلیل مسئله روز تولد این روش می‌تواند کارا باشد. به‌طور خاص اگر تابع (f(x به ازای Hهای متفاوت خروجی با احتمال مساوی بدست بدهد و H به اندازه کافی بزرگ باشد سپس ما انتظار خواهیم داشت از یک زوج متفاوت${\displaystyle x_{1},x_{2}}$نتیجه روبرو را حاصل کنیم${\displaystyle f(x_{1})=f(x_{2})}$ بعد از ارزیابی تابع برای حدود ${\displaystyle 1.25{\sqrt {H}}}$ آرگومان‌های متفاوت آزمایش زیر را ملاحظه می‌کنیم. از یک مجموعه مقادیر H، n مقدار را به صورت تصادفی انتخاب می‌کنیم که در نتیجه اجازه تکرار به وجود خواهد آمد. در(p(n; H ملاحظه خواهید کرد که در طول این آزمایش احتمال اینکه حداقل یک مقدار انتخاب شده بیش از یکبار اتفاق خواهد افتاد این احتمال می‌تواند توسط رابطه زیر تخمین زده شود

${\displaystyle p(n;H)\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^{2}/(2H)},\,}$ رابطه(n(p; H کوچکترین مقداری که انتخاب می‌کنیم را نشان می‌دهد چون احتمال پیدا کردن یک تصادم حداقل p است. با تبدیل کردن عبارت بالا، تخمین زیر بدست می‌آید:

${\displaystyle n(p;H)\approx {\sqrt {2H\ln {\frac {1}{1-p}}}},}$

و با قرار دادن احتمال ۰٫۵ برای تصادم به رابطه زیر می‌رسیم:

${\displaystyle n(0.5;H)\approx 1.1774{\sqrt {H}}.\,}$

با استفاده از(Q(H اعدادی را انتخاب می‌کنیم قبل از اینکه اولین تصادم اتفاق بیفتد این عدد با رابطه زیر تخمین زده می‌شود:

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

منابع

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