هجوم تصادمي

الموسوعة الحرة

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

يوجد نوعان رئيسيان من هجمات التصادم:

هجوم التصادم الكلاسيكي
ابحث عن رسالتين مختلفتين 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 خطوة زمنية (عدد مرات تقييم دالة التجزئة).

رياضياً، يجد هجوم التصادم رسالتين مختلفتين .م1{\displaystyle m_{1}}و​​م2{\displaystyle m_{2}}، بحيثحأsح(م1)=حأsح(م2){\displaystyle hash(m_{1})=hash(m_{2})}في هجوم التصادم الكلاسيكي، لا يملك المهاجم أي سيطرة على محتوى أي من الرسالتين، ولكن يتم اختيارهما بشكل عشوائي بواسطة الخوارزمية.

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

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

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

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

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

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

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

في ديسمبر 2008، نُشرت حادثة هجوم تصادم حقيقية، حيث نشر فريق من باحثي الأمن شهادة توقيع X.509 مزورة ، يمكن استخدامها لانتحال صفة جهة إصدار الشهادات ، مستغلين ثغرة هجوم تصادم البادئات ضد دالة التجزئة MD5. هذا يعني أن المهاجم يستطيع انتحال صفة أي موقع ويب مؤمّن بتقنية SSL ، وبالتالي تعطيل آلية التحقق من الشهادات المدمجة في جميع متصفحات الويب لحماية التجارة الإلكترونية . قد لا تتمكن الجهات الرسمية من إلغاء الشهادة المزورة، وقد يكون لها تاريخ انتهاء صلاحية مزور بشكل عشوائي. على الرغم من أن MD5 كان معروفًا بضعفه الشديد في عام 2004، [ 1 ] إلا أن جهات إصدار الشهادات كانت لا تزال على استعداد لتوقيع الشهادات التي تم التحقق منها باستخدام MD5 في ديسمبر 2008، [ 6 ] كما أن شهادة توقيع واحدة على الأقل من مايكروسوفت كانت لا تزال تستخدم MD5 في مايو 2012.

نجح برنامج Flame الخبيث في استخدام نسخة جديدة من هجوم تصادم البادئة المختارة لتزييف توقيع التعليمات البرمجية لمكوناته بواسطة شهادة جذر مايكروسوفت التي لا تزال تستخدم خوارزمية MD5 المخترقة. [ 7 ] [ 8 ]

في عام 2019، اكتشف الباحثون هجومًا يعتمد على اختيار بادئة معينة ضد خوارزمية SHA-1 ، بتعقيد حسابي يتراوح بين 2⁶⁶.⁹ و2⁶⁹.⁴ ، وبتكلفة تقل عن 100,000 دولار أمريكي. [ 9 ] [ 10 ] وفي عام 2020، خفّض الباحثون تعقيد هجوم مماثل إلى 2⁶⁳.⁴ . [ 11 ]

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

لا تعتمد العديد من تطبيقات دوال التشفير التجزئية على مقاومة التصادم ، وبالتالي لا تؤثر هجمات التصادم على أمانها. على سبيل المثال، لا تُعدّ رموز HMAC عرضةً لهذه الهجمات. [ 12 ] ولكي يكون الهجوم فعالاً، يجب أن يكون المهاجم متحكمًا في مُدخلات دالة التجزئة.

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

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

سيناريو الهجوم المعتاد يكون كالتالي:

  1. يقوم مالوري بإنشاء مستندين مختلفين، أ و ب، لهما نفس قيمة التجزئة، أي أنهما متطابقان. يسعى مالوري إلى خداع بوب لحمله على قبول المستند ب، ظاهريًا من أليس.
  2. ترسل مالوري المستند "أ" إلى أليس ، التي توافق على ما يقوله المستند، وتوقع على شفرته، وترسل التوقيع إلى مالوري.
  3. تقوم مالوري بإرفاق التوقيع من المستند أ إلى المستند ب.
  4. ثم ترسل مالوري التوقيع والمستند B إلى بوب ، مدعيةً أن أليس وقعت على B. ولأن التوقيع الرقمي يطابق تجزئة المستند B، فإن برنامج بوب غير قادر على اكتشاف الاستبدال.

في عام 2008، استخدم باحثون هجوم تصادم البادئة المختارة ضد خوارزمية MD5، مستغلين هذا السيناريو، لإنتاج شهادة مزورة لهيئة إصدار شهادات مزيفة . أنشأوا نسختين من شهادة المفتاح العام لبروتوكول TLS ، إحداهما بدت شرعية وقُدّمت للتوقيع من قِبل هيئة إصدار شهادات RapidSSL. أما النسخة الثانية، التي تحمل نفس قيمة تجزئة MD5، فقد احتوت على علامات تُشير إلى متصفحات الويب لقبولها كهيئة شرعية لإصدار شهادات أخرى. [ 14 ]

فيضانات هاش

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

لمنع حدوث فيضان التجزئة دون تعقيد دالة التجزئة، تم استحداث دوال تجزئة جديدة تعتمد على المفاتيح ، بهدف أمني يتمثل في صعوبة اكتشاف التصادمات طالما أن المفتاح غير معروف. قد تكون هذه الدوال أبطأ من دوال التجزئة السابقة، لكنها لا تزال أسهل بكثير في الحساب من دوال التجزئة المشفرة. اعتبارًا من عام 2021، تُعد دالة SipHash (2012) التي طورها جان فيليب أوماسون ودانيال ج. بيرنشتاين ، دالة التجزئة الأكثر استخدامًا في هذه الفئة. [ 18 ] (تبقى دوال التجزئة "البسيطة" غير المعتمدة على المفاتيح آمنة للاستخدام طالما أن جدول التجزئة الخاص بالتطبيق غير قابل للتحكم من الخارج).

من الممكن تنفيذ هجوم مماثل لملء مرشحات بلوم باستخدام هجوم الصورة المسبقة (الجزئية). [ 19 ]

انظر أيضاً

مراجع

  1. 1 2 شياويون وانغ، دينغقو فنغ، شويجيا لاي، هونغبو يو: تصادمات دوال التجزئة MD4، MD5، HAVAL-128 وRIPEMD ، تقرير أرشيف الطباعة الإلكترونية لعلم التشفير 2004/199، 16 أغسطس 2004، تمت مراجعته في 17 أغسطس 2004. تم استرجاعه في 27 يوليو 2008.
  2. ↑ ستيفنز، MMJ (يونيو 2007). حول التصادمات لـ MD5 (ملف PDF) (رسالة ماجستير). جامعة آيندهوفن للتكنولوجيا. [...] نستطيع إيجاد تصادمات لـ MD5 في حوالي 224.1 عملية ضغط للأجهزة الموصى بها، وهو ما يستغرق حوالي 6 ثوانٍ على معالج بنتيوم 4 بسرعة 2.6 جيجاهرتز.
  3. ↑ ماغنوس داوم؛ ستيفان لوكس . "تصادمات التجزئة (هجوم الرسالة المسمومة)" . جلسة يورو كريبت 2005. مؤرشف من الأصل بتاريخ 27-03-2010.
  4. 1 2 3 جيبهاردت، ماكس؛ إليس، جورج. شندلر ، فيرنر (31 أكتوبر 2005)، ملاحظة حول القيمة العملية لتصادمات التجزئة الفردية لتنسيقات الملفات الخاصة (PDF) ، Bundesamt für Sicherheit in der Informationstechnik، أرشفة من النسخة الأصلية (PDF) في 17-09-2008
  5. ↑ مارك ستيفنز؛ أرجين لينسترا؛ بيني دي ويجر (30 نوفمبر 2007). "تصادمات البادئات المختارة لـ MD5 وتصادم شهادات X.509 لهويات مختلفة" . التطورات في علم التشفير - EUROCRYPT 2007. سلسلة محاضرات في علوم الحاسوب. المجلد 4515. ص 1. Bibcode : 2007LNCS.4515....1S . doi : 10.1007/978-3-540-72540-4_1 . ISBN   978-3-540-72539-8.
  6. ↑ ألكسندر سوتيروف وآخرون (30 ديسمبر 2008). "إنشاء شهادة CA مزيفة" . مؤرشف من الأصل بتاريخ 18 أبريل 2012. تم الاطلاع عليه بتاريخ 7 أكتوبر 2009 . 
  7. ↑ "أصدرت مايكروسوفت إشعارًا أمنيًا رقم 2718704" . مايكروسوفت . 3 يونيو 2012. مؤرشف من الأصل في 7 يونيو 2012. تم الاطلاع عليه في 4 يونيو 2012 .
  8. ↑ مارك ستيفنز (7 يونيو 2012). "خبير تشفير من مركز المعلوماتية والتحليلية يكتشف نوعًا جديدًا من الهجمات التشفيرية في برمجية Flame Spy الخبيثة" . مركز الرياضيات والمعلوماتية . تاريخ الاسترجاع: 9 يونيو 2012 .
  9. ↑ كاتالين سيمبانو (13 مايو 2019). "هجمات تصادم SHA-1 أصبحت الآن عملية بالفعل وتشكل خطرًا محدقًا" . ZDNet .
  10. ↑ غايتان لورينت؛ توماس بيرين (2019-05-06). "من التصادمات إلى تطبيق تصادمات البادئة المختارة إلى SHA-1 الكامل" (PDF) .
  11. ↑ غايتان لورينت؛ توماس بيرين (2020-01-05). "SHA-1 عبارة عن فوضى - أول تصادم بادئة مختارة على SHA-1 وتطبيقه على شبكة الثقة PGP" (PDF) .
  12. ↑ "أسئلة وأجوبة حول تصادم التجزئة" . شركة أبحاث التشفير، 15 فبراير 2005. مؤرشف من الأصل في 17 يوليو 2008. نظرًا لطريقة استخدام دوال التجزئة في بناء رمز مصادقة الرسائل المجزأة (HMAC)، فإن التقنيات المستخدمة في هذه الهجمات الحديثة لا تنطبق.
  13. ↑ شاي هاليفي وهوجو كراوتشيك، التجزئة العشوائية والتوقيعات الرقمية، مؤرشفة بتاريخ 20 يونيو 2009 في أرشيف الإنترنت (Wayback Machine).
  14. ^ الكسندر سوتيروف. مارك ستيفنز؛ جاكوب أبلباوم؛ ارين لينسترا؛ ديفيد مولنار؛ داج آرني أوسفيك؛ بيني دي فيجر (30 ديسمبر 2008). يعتبر MD5 ضارًا اليوم . مؤتمر الفوضى الاتصالات 2008.
  15. ↑ فالكنبرغ، أندرياس؛ ماينكا، كريستيان؛ سوموروفسكي، يوراي؛ شوينك، يورغ (2013). "نهج جديد لاختبار اختراق هجمات حجب الخدمة على خدمات الويب". المؤتمر الدولي العشرون لخدمات الويب ، IEEE، 2013. الصفحات 491-498 . doi : 10.1109/ICWS.2013.72 . ISBN  978-0-7695-5025-1. S2CID 17805370 . 
  16. 1 2 "حول ثغرة استنزاف التجزئة في Node.js... · V8" . v8.dev .
  17. 1 2 سكوت أ. كروسبي ودان س. والاش. 2003. حجب الخدمة عبر هجمات التعقيد الخوارزمي. في وقائع المؤتمر الثاني عشر لندوة أمن USENIX - المجلد 12 (SSYM'03)، المجلد 12. جمعية USENIX، بيركلي، كاليفورنيا، الولايات المتحدة الأمريكية، 3-3.
  18. ↑ جان فيليب أوماسون ودانيال ج. بيرنشتاين (2012-09-18). "SipHash: دالة عشوائية زائفة سريعة ذات مدخلات قصيرة" (ملف PDF) .
  19. ↑ جيربيت، توماس؛ كومار، أمريت؛ لورادو، سيدريك (12 نوفمبر 2014). قوة الخيارات الشريرة في مرشحات بلوم (تقرير). INRIA غرونوبل.
  • "التصادمات ذات المغزى"، سيناريوهات هجومية لاستغلال تصادمات التشفير التجزئية
  • مولدات تصادم MD5 وMD4 سريعة - Bishop Fox (سابقًا Stach & Liu). أنشئ تصادمات تجزئة MD4 وMD5 باستخدام كود جديد رائد يُحسّن التقنيات التي طورها Xiaoyun Wang. باستخدام معالج  Pentium 4 بسرعة 1.6 جيجاهرتز، يُمكن توليد تصادمات MD5 في غضون 45 دقيقة في المتوسط، وتصادمات MD4 في غضون 5 ثوانٍ في المتوسط. صدرت في الأصل بتاريخ 22 يونيو 2006.