هجوم عيد الميلاد

هجوم عيد الميلاد هو هجوم تصادم عنيف يعتمد على الرياضيات الكامنة وراء مفارقة عيد الميلاد في نظرية الاحتمالات. يمكن استخدام هذا الهجوم لإساءة استغلال الاتصال بين طرفين أو أكثر. يعتمد الهجوم على ارتفاع احتمالية حدوث تصادمات بين محاولات الهجوم العشوائية ودرجة ثابتة من التباديل (مبدأ برج الحمام). لنفترض على سبيل المثال أن هناك عدد من الأشخاص الموجودين في غرفة واحدة=23 شخصًا، وفقا لنظرية الاحتمالات سيكون هناك احتمالًا لأن يوجد شخصين على الأقل في الغرفة لهما نفس تاريخ الميلاد، وبمعرفة أن السنة الميلادية تتكون احتمالية أن يتوافق تاريخ يوم ميلاد الشخص الأول مع تاريخ يوم ميلاد أحد الأشخاص الآخرين الموجودين بالغرفة هي 22/365، وإذا لم يتوافق تاريخ ميلاده مع تاريخ ميلاد أي شخص من الأشخاص الإثني والعشرين الموجوجين في الغرفة، ستكون احتمالية توافق تاريخ يوم ميلاد شخص آخر من الموجودين مع تاريخ يوم ميلاد أحد الأشخاص الإحدى والعشرين الباقين في الغرفة هي 21/365، وإذا لم يتوافق تاريخ ميلاد هذا الشخص الآخر مع تاريخ ميلاد أي شخص من الأشخاص الإحدى والعشرين ستكون احتمالية توافق تاريخ يوم ميلاد شخص ثالث مع تاريخ يوم ميلاد أحد الأشخاص العشرين المتبقين في الغرفة هي 20/365، وهكذا، وبجمع هذه الاحتمالات تتكون مفارقة يوم الميلاد، والتي بموجبها تكون احتمالية تطابق تاريخ الميلاد لشخصين من الأشخاص الثلاثة والعشرين الموجودين بالغرفة هي 50 بالمائة. وبالتالي إذا كان H هو عدد القيم الممكنة لدالة التجزئة، وكان ${\textstyle l}$ هو طول بت ناتج التجزئة، فإنّ ${\textstyle H=2^{l}}$، وباستخدام هجوم عيد الملاد فمن الممكن إيجاد تصادم لدالة تجزئة باحتمالية 50% حيث ${\textstyle {\sqrt {2^{l}}}=2^{l/2},}$.^[1][2]

على الرغم من وجود بعض نقاط الضعف في البصمة الرقمية المرتبطة بهجوم عيد الميلاد، فإنه لا يمكن استخدامها لكسر مخطط التشفير بشكل أسرع من هجوم القوة الغاشمة.

لفهم هذه المفارقة دعنا نفترض أن معلمًا في فصل دراسي مكون من 30 طالبًا (عدد الطلاب = 30) يسأل عن أعياد ميلاد جميع الطلاب (للتبسيط، تجاهل السنوات الكبيسة) لتحديد ما إذا كان أي طالبين لهما نفس تاريخ الميلاد (وهو ما يعني تصادم تجزئة كما سيتضح لنا لاحقًا). قد يبدو هذا الاحتمال ضئيلًا، لكن على عكس المتوقع، فإن احتمال أن يكون لطالب واحد على الأقل نفس تاريخ ميلاد أي طالب آخر في أي يوم هو حوالي 70% (لعدد الطلاب = 30)، وذلك وفقًا للمعادلة:^[3]

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

فإذا اختار المعلم يومًا محددًا (مثلًا ١٦ سبتمبر)، فإن احتمالية أن يكون هناك طالب واحد على الأقل مولود في ذلك اليوم المحدد هي:${\displaystyle 1-(364/365)^{30}}$ أي نحو ٧.٩٪ تقريبًا.

في هجوم أعياد الميلاد، يُعِدّ المهاجم العديد من أنواع العقود الحميدة والخبيثة، ولكل منها بصمة رقمية. بعد ذلك يتم البحث عن زوج من العقود الحميدة والخبيثة بنفس البصمة الرقمية. في هذا المثال الافتراضي، لنفترض أن البصمة الرقمية لسلسلة نصية كانت هي البايت الأول من تجزئة SHA-256، عندئذ يُشار إلى الزوج الذي عُثر عليه باللون الأخضر، وهنا يكون العثور على زوج من العقود الحميدة (الأزرق) أو زوج من العقود الخبيثة (الأحمر) لا طائل منه. بعد قبول الضحية للعقد الحميد، يستبدله المهاجم بالعقد الخبيث ويدّعي أن الضحية وقّع عليه، كما هو مُثبت بالبصمة الرقمية.