هجوم تصادم

هجوم تصادم البادئة المختارة

علاوةً على ذلك، في سنة 2019، تمكن الباحثون من اكتشاف هجوم تصادم البادئة المختارة ضد دالة التجزئة SHA-1 بتعقيد حوسبي يُقدر ما بين 266.9 و 269.4، وبتكلفة مادية تقل عن 100,000 دولار أمريكي. وفي عام 2020، حقق باحثون آخرون تقدمًا إضافيًا في هذا المجال، حيث نجحوا في تقليل التعقيد الحسابي اللازم لتنفيذ هجوم تصادم البادئة المختارة ضد SHA-1 إلى 263.4 . هذه التطورات المستمرة تزيد من المخاوف الأمنية المتعلقة بخوارزمية SHA-1 وتؤكد على ضرورة التحول إلى استخدام خوارزميات تجزئة أكثر أمانًا. .

ومن ناحية أخرى، رياضيًا، وبالنظر إلى بادئتين مختلفتين يختارهما المهاجم، p1 و p2، يهدف هجوم تصادم البادئة المختارة إلى إيجاد لاحقتين مختلفتين، s1 و s2، بحيث تتحقق المعادلة التالية:

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

hash(p1∥s1)=hash(p2∥s2)

ومن ناحية أخرى، حيث يرمز الرمز ∥ إلى عملية دمج أو ربط السلاسل النصية (concatenation).

وفي هذا الصدد، يُعد هجوم تصادم البادئة المختارة تطورًا لهجوم التصادم، وهو ذو صلة خاصة بدوال التجزئة المبنية على هيكل Merkle–Damgård. في هذا النوع من الهجمات، يتمتع المهاجم بالقدرة على اختيار مستندين مختلفين بشكل حر، ثم يقوم بإضافة قيم محسوبة ومختلفة إلى نهاية كل مستند. ينتج عن هذه الإضافات أن يحصل المستندان بالكامل على نفس قيمة التجزئة النهائية. يُعتبر هذا الهجوم عمومًا أكثر تعقيدًا من هجوم التصادم الكلاسيكي، حيث يقدر التعقيد الزمني لكسر تجزئة بطول n بت بحوالي 2 (n/2)+1 خطوة زمنية. ومع ذلك، فإنه يمثل تهديدًا أقوى بكثير نظرًا لقدرة المهاجم على التحكم في جزء من المدخلات.

علاوةً على ذلك، في ديسمبر 2008، تم الكشف عن تطبيق عملي لهجوم التصادم عندما نشر فريق من الباحثين الأمنيين شهادة توقيع X.509 مزورة. وقد أظهروا كيف يمكن استغلال هذه الشهادة في انتحال شخصية هيئة إصدار الشهادات، وذلك من خلال الاستفادة من هجوم تصادم البادئة المختارة الذي تم تطويره ضد دالة التجزئة MD5.هذا الإنجاز العملي يعني أن المهاجم أصبح قادرًا على انتحال شخصية أي موقع ويب مؤمن بتقنية SSL والقيام بدور الوسيط الخفي (man-in-the-middle attack). ونتيجة لذلك، يتم تقويض آلية التحقق من صحة الشهادات المضمنة في جميع متصفح ويب، والتي تعتبر أساسية لحماية عمليات التجارة الإلكترونية وضمان أمان الاتصالات عبر الإنترنت. قد لا تكون الشهادة المارقة قابلة للإلغاء من قبل السلطات الحقيقية، وقد يكون لها كذلك تاريخ انتهاء صلاحية مزور تعسفي. على الرغم من أن MD5 كان معروفًا بضعفها الشديد في عام 2004، إلا أن سلطات الشهادات كانت لا تزال على استعداد لتوقيع شهادات تم التحقق منها باستخدام MD5 في ديسمبر 2008، وكانت شهادة توقيع كود واحدة على الأقل من Microsoft لا تزال تستعمل MD5 في مايو 2012.

كذلك، علاوةً على ذلك، يمكن تطوير هجمات أكثر كفاءة من خلال الاستفادة من تحليل الشفرات الخاص ببنية دوال التجزئة المستهدفة. ففي سنة 2007، تم اكتشاف هجوم تصادم البادئة المختارة ضد دالة التجزئة ام دي 5، وقد أظهرت النتائج أنه يتطلب قرابة 250 عملية تقييم لدالة MD5 لتنفيذه.

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

هجوم تصادم كلاسيكي

كذلك، أوجد رسالتين مختلفتين m 1 و m 2 بحيث يكون hash ( m 1 ) = hash ( m 2 ).

بشكل عام:

سيناريوهات الهجوم

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

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

التوقيعات الرقمية

ومن ناحية أخرى، فيما بعد، ترسل مالوري التوقيع والمستند B إلى بوب ، مدعية أن أليس وقعت على B. ونظرًا لأن التوقيع الرقمي يتطابق مع تجزئة المستند B، فإن برنامج بوب غير قادر على اكتشاف الاستبدال.[ بحاجة لمصدر ]

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

السيناريو النموذجي لهجوم التصادم يتضمن الخطوات التالية:

من جانب آخر، في سنة 2008، قام باحثون بتطبيق سيناريو هجوم التصادم هذا عمليًا باستخدام هجوم تصادم البادئة المختارة ضد دالة التجزئة ام دي 5 لإنشاء شهادة سلطة إصدار شهادات مزيفة. وقد قاموا بتصميم نسختين مختلفتين من شهادة المفتاح العام TLS. بدت النسخة الأولى شرعية تمامًا وقُدمت إلى هيئة إصدار الشهادات RapidSSL لتوقيعها. أما النسخة الثانية، التي تم إنشاؤها بحيث يكون لها نفس قيمة تجزئة MD5 للنسخة الأولى، فقد احتوت على تعليمات خاصة ("علامات") توجه متصفحات الويب لقبولها كسلطة إصدار شهادات موثوقة وقادرة على إصدار شهادات أخرى لأي موقع ويب بشكل تعسفي.

يقوم مالوري بإرفاق التوقيع من المستند أ إلى المستند ب.

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

وعلى صعيد آخر، يقوم Mallory بإنشاء مستندين مختلفين A وB لهما قيمة تجزئة متطابقة، أي تصادم. تسعى مالوري إلى خداع بوب لقبول الوثيقة B، والتي يبدو أنها من أليس.

هجوم تصادم كلاسيكي

علاوةً على ذلك، يمكن أن تحتوي ملفات TIFF على صور مقطوعة، مع عرض جزء مختلف من الصورة دون التأثير على قيمة التجزئة.

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

كذلك، وقد كان الدافع الرئيسي وراء مسابقة NIST لاختيار دالة التجزئة هو سلسلة هجمات التصادم الناجحة التي نُشرت ضد اثنتين من دوال التجزئة واسعتي الانتشار آنذاك، وهما ام دي 5 و SHA-1. وتطورت هجمات التصادم ضد MD5 بشكل ملحوظ، لدرجة أنه بحلول عام 2007،لم يعد العثور على تصادم باستخدام جهاز كمبيوتر عادي يستغرق سوى بضع ثوانٍ معدودة . صحيح، فعلى الرغم من سرعة توليد تصادمات التجزئة باستخدام تقنيات تحليل الشفرات، فإن هذه التصادمات غالبًا ما تتسم بطول ثابت وهيكل عشوائي إلى حد كبير. هذا القيد يجعل استخدامها المباشر في مهاجمة تنسيقات المستندات المعقدة أو البروتوكولات واسعة النطاق أمرًا صعبًا.

كذلك، رياضيًا، يُعرف هجوم التصادم بأنه عملية إيجاد رسالتين متباينتين، نرمز إليهما بـ m1 و m2، تحققان الشرط التالي:

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

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

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

كذلك، تحتوي بعض تنسيقات المستندات مثل PostScript ، أو وحدات الماكرو في Microsoft Word ، على هياكل شرطية. (if-then-else) التي تسمح باختبار ما إذا كان الموقع في الملف يحتوي على قيمة واحدة أو أخرى للتحكم في ما يتم عرضه.

فيضان التجزئة

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

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

ومن جهة أخرى، لمعالجة مشكلة إغراق التجزئة دون الحاجة إلى تصميم دوال تجزئة بالغة التعقيد، تم تقديم جيل جديد من دوال التجزئة الرئيسية. يرتكز الهدف الأمني لهذه الدوال على جعل عملية العثور على التصادمات صعبة للغاية طالما أن المفتاح السري يظل غير معلوم للمهاجم. وعلى الرغم من أنها قد تكون أبطأ من دوال التجزئة السابقة، إلا أنها لا تزال أسرع بكثير من دوال التجزئة التعمية من حيث الحساب. وابتداءً من عام 2021،. تُعد دالة التجزئة SipHash (2012) الخاصة بـ Jean-Philippe Aumasson و دانييل يوليوس بيرنشتاين هي دالة التجزئة الأكثر استخدامًا في هذه الفئة. (تظل التجزئات "البسيطة" غير المفتاحية آمنة للاستخدام طالما أن جدول تجزئة التطبيق غير قابل للتحكم من الخارج.)

مراجع

هجوم تصادم البادئة المختارة

ومن جهة أخرى، بالنظر إلى البادئتين المختلفتين p 1 و p 2 ، أوجد اللاحقتين s 1 و s 2 بحيث يكون hash ( p 1 ∥ s 1 ) = hash ( p 2 ∥ s 2 )، حيث يشير ∥ إلى عملية التجميع .