هجوم تصادم

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

هناك نوعان تقريبًا من هجمات الاصطدام:

; هجوم تصادم كلاسيكي
: أوجد رسالتين مختلفتين *m* 1 و *m* 2 بحيث يكون *hash* ( *m* 1 ) = *hash* ( *m* 2 ).

بشكل عام:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

# يقوم Mallory بإنشاء مستندين مختلفين A وB لهما قيمة تجزئة متطابقة، أي تصادم. تسعى مالوري إلى خداع بوب لقبول الوثيقة B، والتي يبدو أنها من أليس.
# **ترسل مالوري المستند A إلى أليس** ، التي توافق على ما يقوله المستند، وتوقع التجزئة الخاصة به، وترسل التوقيع إلى مالوري.
# يقوم مالوري بإرفاق التوقيع من المستند أ إلى المستند ب.
# بعد ذلك، **ترسل مالوري التوقيع والمستند B إلى بوب** ، مدعية أن أليس وقعت على B. ونظرًا لأن التوقيع الرقمي يتطابق مع تجزئة المستند B، فإن برنامج بوب غير قادر على اكتشاف الاستبدال.&#x5B; *[[ويكيبيديا:بحاجة لمصدر|<span title="This claim needs references to reliable sources. (September 2023)">بحاجة لمصدر</span>]]* &#x5D;

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

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

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

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

## مراجع

## روابط خارجية

* "التصادمات ذات المغزى"، سيناريوهات هجومية لاستغلال تصادمات التجزئة التشفيرية
* مولدات الاصطدام السريعة MD5 وMD4 - Bishop Fox (سابقا Stach & Liu). إنشاء تصادمات التجزئة MD4 وMD5 باستخدام كود جديد رائد يعمل على تحسين التقنيات التي طورها في الأصل Xiaoyun Wang. باستخدام 1.6&nbsp;يمكن إنشاء تصادمات MD5 في معالج Pentium 4 بسرعة GHz في متوسط 45 دقيقة، ويمكن إنشاء تصادمات MD4 في متوسط 5 ثوانٍ. تم إصداره أصلا في 22 يونيو 2006.

تصنيف:هجمات باستعمال التعمية