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

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

على الرغم من وجود بعض الثغرات الأمنية في التوقيع الرقمي المرتبطة بهجوم عيد الميلاد، إلا أنه لا يمكن استخدامه لكسر نظام التشفير بشكل أسرع من هجوم القوة الغاشمة . ^{[ 5 ] : 36}

كمثال، لنفترض سيناريو يقوم فيه معلم لديه فصل دراسي مكون من 30 طالبًا (ن = 30) بسؤال كل طالب عن تاريخ ميلاده (لتبسيط الأمر، نتجاهل السنوات الكبيسة ) لتحديد ما إذا كان أي طالبين لهما نفس تاريخ الميلاد (وهو ما يُعرف بتصادم التجزئة كما هو موضح لاحقًا). قد يبدو هذا الاحتمال ضئيلاً للوهلة الأولى. ولكن على عكس المتوقع، فإن احتمال أن يكون لطالب واحد على الأقل نفس تاريخ الميلاد مع أي طالب آخر في أي يوم يبلغ حوالي 70% (عندما ن = 30)، وذلك وفقًا للصيغة التالية:${\displaystyle 1-{\frac {365!}{(365-n)!\cdot 365^{n}}}}$[ ^{6 ]​}

إذا اختار المعلم يومًا محددًا (مثلاً، 16 سبتمبر)، فإن احتمال أن يكون طالب واحد على الأقل قد وُلد في ذلك اليوم المحدد هو${\displaystyle 1-(364/365)^{30}}$حوالي 7.9%.

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

بالنظر إلى دالة${\displaystyle f}$الهدف من الهجوم هو إيجاد مدخلين مختلفين${\displaystyle x_{1},x_{2}}$بحيث${\displaystyle f(x_{1})=f(x_{2})}$مثل هذا الزوج${\displaystyle x_{1},x_{2}}$يُطلق على هذا اسم التصادم. وتتمثل الطريقة المستخدمة لإيجاد التصادم ببساطة في تقييم الدالة.${\displaystyle f}$بالنسبة لقيم الإدخال المختلفة التي يمكن اختيارها عشوائيًا أو شبه عشوائيًا حتى يتم العثور على نفس النتيجة أكثر من مرة. نظرًا لمشكلة عيد الميلاد، يمكن أن تكون هذه الطريقة فعالة للغاية. على وجه التحديد، إذا كانت الدالة${\displaystyle f(x)}$ينتج أي من${\displaystyle H}$مخرجات مختلفة باحتمالية متساوية و${\displaystyle H}$إذا كانت القيمة كبيرة بما يكفي، فإننا نتوقع الحصول على زوج من الوسائط المختلفة${\displaystyle x_{1}}$و${\displaystyle 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)}}$^{[ 7 ]}

أين${\displaystyle n}$يمثل عدد القيم المختارة (المدخلات) و${\displaystyle H}$يمثل عدد النتائج المحتملة (مخرجات التجزئة المحتملة).

لنفترض أن n ( p ; H ) هو أصغر عدد من القيم التي يجب علينا اختيارها، بحيث يكون احتمال حدوث تصادم على الأقل p . وبقلب هذا التعبير أعلاه، نجد التقريب التالي:  

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

وبإسناد احتمال 0.5 للتصادم، نصل إلى

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

لنفترض أن Q ( H ) هو العدد المتوقع للقيم التي يتعين علينا اختيارها قبل العثور على أول تصادم. يمكن تقريب هذا العدد بواسطة

${\displaystyle Q(H)\approx {\sqrt {{\frac {\pi }{2}}H}}}$

على سبيل المثال، إذا تم استخدام تجزئة 64 بت، فسيكون هناك ما يقارب1.8 × 10 ^ ¹⁹ ناتجًا مختلفًا. إذا كانت جميع هذه النواتج متساوية الاحتمال (وهو أفضل سيناريو)، فسيتطلب الأمر حوالي 5 مليارات محاولة فقط.5.38 × 10⁹ ⁾ لتوليد تصادم باستخدام القوة الغاشمة. ^{[ 8 ]} تُسمى هذه القيمة حد عيد الميلاد ^{[ 9 ]} ويمكن تقريبها بـ 2l ^{/ 2} ، حيث l هو عدد البتات في H. ^{[ 10 ]} أمثلة أخرى هي كما يلي:

أجزاء	المخرجات المحتملة (H)	الاحتمالية المطلوبة للتصادم العشوائي (برقمين معنويين) (p)
		10 −18	10-15​	10 −12	10 −9	10 −6	0.1%	1%	25%	50%	75%
16	2 16 (~6.5 × 10 4 )	<2	<2	<2	<2	<2	11	36	190	300	430
32	2 32 (~4.3 × 10 9 )	<2	<2	<2	3	93	2900	9300	50,000	77000	110,000
64	2 64 (~1.8 × 10^ 19 )	6	190	6100	190,000	6,100,000	1.9 × 10 8	6.1 × 10 8	3.3 × 10 9	5.1 × 10 9	7.2 × 10 9
96	2 96 (~7.9 × 10 28 )	4.0 × 10 5	1.3 × 10 7	4.0 × 10 8	1.3 × 10 10	4.0 × 10 11	1.3 × 10 13	4.0 × 10 13	2.1 × 10 14	3.3 × 10 14	4.7 × 10 14
128	2 128 (~3.4 × 10 38 )	2.6 × 10 10	8.2 × 10 11	2.6 × 10 13	8.2 × 10 14	2.6 × 10 16	8.3 × 10 17	2.6 × 10 18	1.4 × 10 19	2.2 × 10 19	3.1 × 10 19
192	2 192 (~6.3 × 10 57 )	1.1 × 10 20	3.7 × 10 21	1.1 × 10 23	3.5 × 10 24	1.1 × 10 26	3.5 × 10 27	1.1 × 10 28	6.0 × 10 28	9.3 × 10 28	1.3 × 10 29
256	2256 ( ~1.2 × 10 77 )	4.8 × 10 29	1.5 × 10 31	4.8 × 10 32	1.5 × 10 34	4.8 × 10 35	1.5 × 10 37	4.8 × 10 37	2.6 × 10 38	4.0 × 10 38	5.7 × 10 38
384	2384 ( ~3.9 × 10^ 115 )	8.9 × 10 48	2.8 × 10 50	8.9 × 10 51	2.8 × 10 53	8.9 × 10 54	2.8 × 10 56	8.9 × 10 56	4.8 × 10 57	7.4 × 10 57	1.0 × 10 58
512	2512 ( ~1.3 × 10 154 )	1.6 × 10 68	5.2 × 10 69	1.6 × 10 71	5.2 × 10 72	1.6 × 10 74	5.2 × 10 75	1.6 × 10 76	8.8 × 10 76	1.4 × 10 77	1.9 × 10 77

يوضح الجدول عدد التجزئات n ( p ) اللازمة لتحقيق احتمال النجاح المحدد، بافتراض أن جميع التجزئات متساوية الاحتمالية. للمقارنة،10 ⁻¹⁸ إلىيبلغ معدل الخطأ غير القابل للتصحيح في البتات لقرص صلب نموذجي 10⁻¹⁵ . ^{[ 11 ]} من الناحية النظرية، يجب أن تبقى تجزئات MD5 أو ^{معرّفات} UUID ، التي يبلغ طولها حوالي 128 بت، ضمن هذا النطاق حتى حوالي 820 مليار مستند، حتى لو كانت مخرجاتها المحتملة أكبر بكثير.

من السهل ملاحظة أنه إذا كانت مخرجات الدالة موزعة بشكل غير متساوٍ، فسيُمكن العثور على تصادم بشكل أسرع. يُحدد مفهوم "توازن" دالة التجزئة مدى مقاومة الدالة لهجمات عيد الميلاد (التي تستغل التوزيع غير المتساوي للمفاتيح). مع ذلك، يتطلب تحديد توازن دالة التجزئة عادةً حساب جميع المدخلات الممكنة، وبالتالي فهو غير عملي بالنسبة لدوال التجزئة الشائعة مثل عائلتي MD وSHA. ^{[ 12 ]} التعبير الفرعي${\displaystyle \ln {\frac {1}{1-p}}}$في معادلة لـ${\displaystyle n(p;H)}$لا يتم حسابها بدقة للقيم الصغيرة${\displaystyle p}$عند ترجمتها مباشرةً إلى لغات البرمجة الشائعة، قد log(1/(1-p))تفقد بعض الأرقام دلالتها . عند log1pتوفرها (كما هو الحال في C99-log1p(-p) على سبيل المثال)، يجب استخدام التعبير المكافئ بدلاً منها. ^{[ 13 ]} إذا لم يتم ذلك، فسيتم حساب العمود الأول من الجدول أعلاه على أنه صفر، وستفتقر العديد من العناصر في العمود الثاني إلى رقم معنوي واحد صحيح.

قد تتعرض التوقيعات الرقمية لهجوم تاريخ الميلاد، أو بشكل أدق، لهجوم تصادم البادئة المختارة. رسالة${\displaystyle m}$يتم التوقيع عادةً بواسطة عملية حسابية أولى${\displaystyle f(m)}$، أين${\displaystyle f}$هي دالة تجزئة تشفيرية ، ثم يتم استخدام مفتاح سري للتوقيع${\displaystyle f(m)}$لنفترض أن مالوري تريد خداع بوب لحمله على توقيع عقد مزور . تقوم مالوري بإعداد عقد عادل.${\displaystyle m}$وواحدة احتيالية${\displaystyle m'}$ثم تجد عدداً من الوظائف حيث${\displaystyle m}$يمكن تغييرها دون تغيير المعنى، مثل إضافة الفواصل، أو الأسطر الفارغة، أو مسافة واحدة أو مسافتين بعد الجملة، أو استبدال المرادفات، وما إلى ذلك. ومن خلال الجمع بين هذه التغييرات، يمكنها إنشاء عدد هائل من الاختلافات في${\displaystyle m}$وهي جميعها عقود عادلة.

وبالمثل، ابتكر مالوري أيضاً عدداً هائلاً من الصيغ المختلفة للعقد الاحتيالي${\displaystyle m'}$ثم تقوم بتطبيق دالة التجزئة على جميع هذه الاختلافات حتى تجد نسخة من العقد العادل ونسخة من العقد الاحتيالي لهما نفس قيمة التجزئة.${\displaystyle f(m)=f(m')}$تُقدّم مالوري النسخة العادلة لبوب للتوقيع. بعد توقيع بوب، تأخذ مالوري التوقيع وتُلصقه بالعقد المُزوّر. يُثبت هذا التوقيع أن بوب قد وقّع على العقد المُزوّر.

تختلف الاحتمالات قليلاً عن مسألة عيد الميلاد الأصلية، إذ لا يحقق مالوري أي فائدة من إيجاد عقدين عادلين أو عقدين احتياليين بنفس قيمة التجزئة. تتمثل استراتيجية مالوري في توليد أزواج من عقد عادل وعقد احتيالي. بالنسبة لدالة تجزئة معينة${\displaystyle 2^{l}}$يمثل عدد التجزئات الممكنة، حيث${\displaystyle l}$يمثل طول البتات لمخرجات التجزئة. لا تنطبق معادلات مسألة عيد الميلاد هنا تمامًا. للحصول على احتمال 50% لحدوث تصادم، ستحتاج مالوري إلى توليد ما يقارب${\displaystyle 2^{(l/2)+1}}$التجزئة، وهو ضعف العدد المطلوب لحدوث تصادم بسيط في ظل مشكلة عيد الميلاد الكلاسيكية.

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

إلى جانب استخدام طول بت أكبر، يمكن للموقع (بوب) حماية نفسه عن طريق إجراء بعض التغييرات العشوائية وغير المسيئة على المستند قبل توقيعه، وعن طريق الاحتفاظ بنسخة من العقد الذي وقعه في حوزته الخاصة، حتى يتمكن على الأقل من إثبات في المحكمة أن توقيعه يطابق ذلك العقد، وليس فقط التوقيع الاحتيالي.

تُعد خوارزمية بولارد رو للوغاريتمات مثالاً على خوارزمية تستخدم هجوم عيد الميلاد لحساب اللوغاريتمات المنفصلة .

• هجوم تصادمي
• هجوم الالتقاء في المنتصف
• خوارزمية BHT

• ميهير بيلاري ، تادايوشي كوهنو: توازن دالة التجزئة وتأثيره على هجمات عيد الميلاد. مؤتمر يورو كريبت 2004: الصفحات 401-418
• التشفير التطبيقي، الطبعة الثانية، بقلم بروس شناير

• "ما هو التوقيع الرقمي وما هي المصادقة؟" من الأسئلة الشائعة حول العملات المشفرة لشركة RSA Security .
• أسئلة وأجوبة حول العملات المشفرة من شبكة X5 بعنوان "هجوم عيد الميلاد"