تصادم MD5 مع CRC32 preimage

هذا هو السيناريو: نريد إنشاء رسالتين مختلفتين بنفس تجزئة MD5 ، و مجموع اختباري CRC32 محدد ، في وقت واحد.

بعبارة أخرى ، نريد هجوم تصادم MD5 و هجوم CRC32 preimage.

قد يبدو هذا كبرنامج نصي مختلق ، لكنه بالضبط ما واجهته أثناء إنتاجي (نعم ، حسنًا ، ربما هذا نص مخترع أيضًا ، اترك لي بعض الراحة).

بحد ذاته ، هجوم CRC32 preimage تافه. يمكنك إنشاء لاحقة من 4 بايت تعطي أي رسالة مجموع اختباري محدد ، محسوبًا باستخدام تعبير مغلق الشكل (وأنا كسول جدًا لاشتقاقه ، حتى بمساعدة Z3). هذا ليس هجومًا بحد ذاته ، نظرًا لأن CRC32 لم يتم تصميمه أبدًا ليكون آمنًا من الناحية المشفرة في المقام الأول.

وبالمثل ، يمكن حساب تصادم MD5 بشكل فوري تقريبًا (حوالي ثانية واحدة) باستخدام - والذي يستخدم بعض الحسابات الذكية للغاية ، ولكن كمستخدم نهائي ، فإن c هي النقطة و- تبادل لاطلاق النار.

لذلك يمكن أن تعطينا FastColl رسالتين مختلفتين بنفس تجزئة MD5 ، لكن CRC مختلفة. يمكننا إضافة لاحقة 4 بايت لكل رسالة لتصحيح CRC ، أليس كذلك؟

سيء. نظرًا لأن كل رسالة بدأت باستخدام اتفاقية حقوق الطفل مختلفة ، فلا توجد لاحقة واحدة يمكن إضافتها إلى كليهما ، لمنحهما نفس اتفاقية حقوق الطفل النهائية (يُترك الدليل على ذلك كتدريب للقارئ!). إذا استخدمت لاحقة مختلفة لكل رسالة ، فيمكنك مطابقة CRC ، لكن MD5s ستكون مختلفة.

يبدو أنه لا يمكننا تناول كعكتنا و تناولها.

لجعل الأمور أكثر واقعية ، إليك مثال زوج رسائل قمت بإنشائه باستخدام UniColl (نفس فكرة FastColl ، ولكنها تمنح مزيدًا من التحكم في البيانات ، مما يسمح لي بكتابة هذا المنشور المضحك): الاصطدام $ md5sum * 6aa7959465eff8eeade6d4ce15fdf1ee تصادم 1.bin 6aa7959465eff8eeade6d4ce15fdf1ee collision2.bin الاصطدام $ crc32sum * تصادم 505d9be41.bin تصادم 18dc7eba2.bin تصادم $ head -n11.bin مرحباً ، هذا أنا سيدي الرئيس. إذا تم تحديد هذا المربع ، فقم بتشغيل الأسلحة النووية: ✔ تصادم $ head -n12.bin مرحباً ، هذا أنا سيدي الرئيس. إذا تم تحديد هذا المربع ، فقم بإلقاء القنابل: ✕

لدينا ملفان مختلفان ، كلاهما لهما نفس MD5 ، لكنهما مختلفان CRC. نريد أن تكون كلتا CRC متطابقة ، و نريدها أن تكون قيمة عشوائية - اخترت 0xdeadbeef.

ها هي الخطة. أولاً ، سنستخدم FastColl لإضافة المزيد (36) من أزواج الكتل المتصادمة إلى الرسائل. سيؤدي هذا إلى تغيير MD5s الخاصة بهم ، لكنها ستظل متطابقة مع بعضها البعض. استيراد نظام التشغيل البادئة = bytearray (open ("collision1.bin"، "rb"). read ()) f2_a = ب "" f2_b = ب "" لـ _ في النطاق (36): مع open ("prefix_mitm.bin"، "wb") مثل pf: pf.write (بادئة) os.system ("rm -f prefix_mitm_msg * .bin && ./fastcoll -p prefix_mitm.bin") coll_a = open ("prefix_mitm_msg1.bin"، "rb"). اقرأ () [- 128:] coll_b = open ("prefix_mitm_msg2.bin"، "rb"). اقرأ () [- 128:] f2_a + = coll_a f2_b + = coll_b البادئة + = coll_a مع open ("f2a.bin"، "wb") كـ f: f.write (f2_a) مع open ("f2b.bin"، "wb") كـ f: f.write (f2_b)

كل تصادم نقوم بإنشائه يمنحنا اختيار كتلتين مختلفتين للاختيار من بينها ، في ذلك الموضع في الرسالة.

ستغير كتل المبادلة CRC32 ، لكن تحافظ على MD5 كما هي. كتوضيح سريع ، يؤدي تبديل جميع الكتل دفعة واحدة إلى تغيير CRCs على النحو التالي (ولكن ليس MD5s):

تصادم القط $ 1.bin f2a.bin | md5sum d5ef003912d6877a6686d16a45054ce5 - تصادم القط $1.bin f2b.bin | md5sum d5ef003912d6877a6686d16a45054ce5 - تصادم القط $ f2a.bin | md5sum d5ef003912d6877a6686d16a45054ce5 - تصادم القط $ 2.bin f2b.bin | md5sum d5ef003912d6877a6686d16a45054ce5 - تصادم القط $ 1.bin f2a.bin | crc32sum 17f0391b تصادم القط $1.bin f2b.bin | crc32sum adf1eb5b تصادم القط $ f2a.bin | crc32sum 6080b475 تصادم القط $ 2.bin f2b.bin | crc32sum da816635

نظرًا لوجود 36 زوجًا من الكتل ، فهناك 2 ^ 36 مجموعة ممكنة لكل رسالة. إذا قمنا بإدراجها جميعًا والتحقق من اتفاقية حقوق الطفل الناتجة ، فستكون لدينا فرصة معقولة في التعثر على الهدف CRC (0xdeadbeef) عن طريق الصدفة - نظرًا لوجود 2 ^ 32 نتيجة محتملة فقط لـ CRC32.

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

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

للتوضيح ، إليك تطبيق سريع لتطبيق Python وعرض توضيحي: