هجمات أعياد الميلاد والتصادم

في مجموعة تضم 23 شخصًا، يتجاوز احتمال أن يتشارك شخصان عيد الميلاد نفسه 50%. ومع 70 شخصًا، يتجاوز الاحتمال 99.9%. رياضيًا، في مجموعة حجمها N، يتجاوز احتمال التصادم 50% بعد نحو √N من العينات. ويُعرف ذلك بحد عيد الميلاد.

بالنسبة إلى دالة تجزئة من n بت، يمكن العثور على تصادم (H(m1) = H(m2)، m1 ≠ m2) باستخدام نحو 2^{n/2} من المحاولات العشوائية. وبالنسبة إلى SHA-256 (بطول 256 بت)، يتطلب التصادم نحو 2^{128} من العمل، وهو غير قابل للتنفيذ حسابيًا. أما MD5 (بطول 128 بت)، فيتطلب نحو 2^{64}، وهو قريب من أن يصبح قابلًا للتنفيذ.

العثور العام على التصادمات: أنشئ 2^{n/2} من الرسائل العشوائية، واحسب التجزئات، ورتّبها حسب قيمة التجزئة، ثم اعثر على القيم المكررة. يتطلب ذلك ذاكرة O(2^{n/2}). وتقلل خوارزمية Rho (العثور على الدورات باستخدام Floyd) الذاكرة إلى O(1) مع الحفاظ على تكلفة الوقت نفسها. ويقلل البحث المتوازي عن التصادمات وفق van Oorschot-Wiener الوقت باستخدام العتاد.

عثر Wang وزملاؤه (2004) على تصادمات عملية في MD5 باستخدام تحليل التشفير التفاضلي، وليس هجوم عيد الميلاد. ويمكن إنشاء رسالتين مختلفتين بطول 1024 بت لهما تجزئة MD5 متطابقة خلال ثوانٍ. وتتيح تصادمات Hertzbleed وتصادمات البادئة المختارة إنشاء تصادمات للشهادات. وقد أصبح MD5 مكسورًا تمامًا من ناحية مقاومة التصادم.

الأمر أكثر قوة: عند إعطاء بادئتين عشوائيتين P1 وP2، اعثر على لاحقتين S1 وS2 بحيث H(P1||S1) = H(P2||S2). عثر Stevens وزملاؤه (2017) على تصادمات MD5 ذات بادئات مختارة. واستُخدمت لإنشاء شهادة CA ضارة تحمل توقيع MD5 صالحًا. وأدى ذلك إلى إيقاف استخدام MD5 في الشهادات.

كان SHAttered من Google (2017) أول تصادم عملي لـ SHA-1. فقد أُنشئ ملفا PDF مختلفان لهما تجزئة SHA-1 نفسها. وتطلب ذلك 2^{63.1} من عمليات ضغط SHA-1، أي ما يعادل 6,500 سنة من وقت CPU و110 سنوات من وقت GPU. وبلغت التكلفة نحو 110,000 دولار. وقد أوقفت المتصفحات اعتماد شهادات SHA-1 في عام 2017.

بالنسبة إلى دوال التجزئة من نوع Merkle-Damgard ‏(MD5 وSHA-1 وSHA-2): إذا كنت تعرف H(m)، فيمكنك حساب H(m||padding||m') من دون معرفة m. وهذا يكسر بنيات MAC مثل H(secret||message). الحل هو استخدام HMAC (الذي يستخدم حشوًا داخليًا وخارجيًا) أو SHA-3 (بنية الإسفنجة، وهي محصّنة ضد تمديد الطول).

مقاومة التصادم: العثور على رسالتين مختلفتين كيفما كانتا ولهما قيمة التجزئة نفسها (يتطلب جهدًا قدره 2^{n/2}). مقاومة الصورة السابقة الثانية: عند إعطائك m، العثور على m' ≠ m ولهما قيمة التجزئة نفسها (يتطلب جهدًا قدره 2^n). مقاومة الصورة السابقة: العثور على أي رسالة لقيمة تجزئة معطاة (يتطلب جهدًا قدره 2^n). ويظل التصادم دائمًا أضعف هذه الخصائص.

إذا استخدم MAC دالة تجزئة معرّضة للتصادمات، فقد يتمكن مهاجم يستطيع العثور على تصادمات في H من تزوير قيم MAC. ويُعد HMAC-MD5 آمنًا رغم تصادمات MD5، لأن بنية HMAC تتطلب هجمات على الصورة السابقة، وليس مجرد تصادمات. ومع ذلك، ينبغي الانتقال من HMAC-MD5 في الأنظمة الجديدة.

أوضح Joux (عام 2004) أنه بالنسبة إلى تجزئات Merkle-Damgard، فإن العثور على تصادم متعدد الطرق من 2^k (أي 2^k رسالة لها قيمة التجزئة نفسها) يتطلب جهدًا يساوي k مرة جهد العثور على تصادم واحد فقط، وليس k مرات هذا الجهد. ويؤدي ذلك إلى تراكم الثغرات في دوال التجزئة المتسلسلة (فإن H1(m)||H2(m) ليست قوية بالقدر الذي قد تتوقعه).

استخدم SHA-256 أو SHA-3 للتجزئة المقاومة للتصادمات. وتجنب MD5 وSHA-1 لأي غرض أمني. بالنسبة إلى MAC، استخدم HMAC-SHA-256 أو HMAC-SHA-3. وبالنسبة إلى تجزئة كلمات المرور، استخدم Argon2 (وليس SHA-2 مباشرةً). استخدم SHA-3 دائمًا عند الحاجة إلى مقاومة تمديد الطول.

تقريبًا، كم عدد عمليات حساب التجزئة اللازمة للعثور على تصادم في دالة تجزئة n-bit؟

يعثر هجوم أعياد الميلاد على تصادمات التجزئة بجهد قدره 2^{n/2}. لدى MD5 تصادمات عملية ذات بادئة مختارة، وقد كُسر SHA-1 في عام 2017. تكسر هجمات تمديد الطول قيم MAC الساذجة من الشكل H(key||msg). استخدم SHA-256 أو SHA-3، واستخدم HMAC لمصادقة الرسائل. التالي: هجمات الالتقاء في المنتصف.