العودة إلى المدونة

صورة PNG تعرض بصمة MD5 الخاصة بها: The Arma Of Efe hashquine

كيف صنعنا صورة PNG تكتب بصمة MD5 الخاصة بها داخل بكسلاتها دون استخدام قالب جاهز؟ مفاتيح التصادم، وطبقات PNG، والبحث عن efe23…23efe على RTX 5070، مع شرح تفاعلي.

الصورة أعلاه ليست شعارًا عاديًا. على القوس الموجود في الجهة اليمنى يُكتب من الأعلى إلى الأسفل efe235ae1b88c53e73d1c11515623efe، وهذه هي بصمة MD5 للملف نفسه. إذا نزّلتم الصورة وشغّلتم md5sum ستجدون الخانات الاثنتين والثلاثين ذاتها.

تُسمّى مثل هذه الملفات hashquine. أشهر مثال متداول هو صورة PNG بالتنين من إنشاء retr0id، ومعظم الناس يستعملون قالبه الجاهز. أما نحن فلم نستعمل أي قالب، وصنعنا الملف من الصفر بشعارنا (The Arma Of Efe) ورابط مدونتنا، وببصمة مخصصة تبدأ بـ efe وتنتهي بـ efe. سأشرح ذلك خطوة بخطوة كما جرت التجربة.

صورة PNG من نوع hashquine لـ Retr0id فيها تنين وتعرض بصمة MD5 الخاصة بها

صورة PNG hashquine من إعداد David “Retr0id” Buchanan، وبصمتها MD5 هي 1337e2ef42b9bee8de06a4d223a51337. الصورة: Retr0id، عبر corkami/collisions.

ما البصمة، ولماذا تتغيّر مع كل حرف؟

البصمة (hash) قيمة ذات طول ثابت تُستخرج من محتوى الملف. أما MD5 فهي دالة بصمة صمّمها Ronald Rivest عام 1991: سواء كان الدخل بايتًا واحدًا أو 50 غيغابايت، فالناتج دائمًا 128 بت، أي 32 خانة من الأرقام 0-9 والحروف a-f.

الخاصية الأساسية لدوال البصمة هي تأثير الانهيار الثلجي: أصغر تغيير في الدخل يغيّر الناتج من أوله إلى آخره. جرّبوا كتابة أي شيء في الحقل أدناه:

معضلة الدجاجة والبيضة

بسبب تأثير الانهيار الثلجي، تبدو صورةٌ تحمل بصمة MD5 الخاصة بها مستحيلةً للوهلة الأولى:

  1. ترسمون الصورة وتحسبون بصمتها MD5، مثلًا 4a8c91e0….
  2. تكتبون هذه القيمة على الصورة وتحفظونها.
  3. لأن البكسلات تغيّرت، تصبح بصمة الملف شيئًا آخر، مثلًا 9f02d71a….
  4. تكتبون القيمة الجديدة، فتتغيّر البصمة من جديد.

لكسر هذه الحلقة يجب النظر داخل MD5 نفسها.

الفكرة التي تكسر الحلقة: مفاتيح لا تغيّر MD5

لا تعالج MD5 الملف دفعةً واحدة، بل تقسمه إلى كتل من 64 بايت وتعالجها بالتتابع: تُدمج الحالة الابتدائية (IV) مع الكتلة الأولى فتنتج حالة وسيطة (IHV)، ثم تُدمج هذه مع الكتلة التالية، وهكذا حتى نهاية الملف. والحالة الوسيطة الأخيرة هي البصمة المكوّنة من 32 خانة.

النقطة الحاسمة أنه يمكن العثور على جزأين مختلفين من البيانات (A وB) طول كل منهما 128 بايتًا، ومحاذيين تمامًا لحدود 64 بايت، ويؤديان كلاهما إلى الحالة الوسيطة نفسها. يُسمّى هذا تصادم البادئة المختارة، وتستطيع أدوات مثل FastColl توليده في وقت قصير. وبما أن كل كتلة تلي هذا الجزء ترى الحالة الوسيطة نفسها:

  • إذا وُضع الجزء A ظهر خطٌّ على الشاشة، وإذا وُضع B اختفى،
  • لكن بصمة MD5 في نهاية الملف لا تتغير أبدًا.

إذن كل زوج تصادم هو مفتاح يُفتح ويُغلق دون أن يكسر MD5. نحسب أولًا بصمة الملف، ثم نضبط المفاتيح بحيث ترسم تلك البصمة بالضبط. ولأن البصمة لا تتغير، تنكسر الحلقة.

كيف رُسم القوس حرفًا حرفًا؟

في الملف 32 حرفًا مرتّبة من الأعلى إلى الأسفل على قوسٍ يتبع منحنى الشعار. كل حرف رقمٌ بسبعة قطاعات، ويرسم كل قطاع مفتاحه الخاص: المجموع 224 مفتاحًا. يمكنكم تتبّع كيف تستقر البصمة على القوس بالشريط المنزلق:

لأننا لم نستعمل قالبًا جاهزًا، كان علينا أن نجتاز في الوقت نفسه أربع طبقات تحقق في ملف PNG:

  1. محاذاة 64 بايتًا: يجب أن يقع كل مفتاح في الملف عند الحد ofset % 64 == 0 بدقة. أضفنا إلى تدفق ضغط DEFLATE كتلًا فارغة بطول صفر لمحاذاة كل مفتاح مع هذا الحد.
  2. مرشّحا Sub وUp في PNG: جعلنا الفهارس 0..254 في اللوحة سوداء، والفهرس 255 وحده أبيض. يتباعد جزءا تصادم الزوج في أعلى بت من بضعة بايتات؛ في صف يستعمل مرشّح Sub يحوّل هذا الفرق البكسلات التالية بمقدار 128 فتصير خطًا أفقيًا، ومرشّح Up ينقله إلى الأسفل. اخترنا البايتات التي تلي المفتاح بحيث يصير الخط أبيض تمامًا 255 في حالة وأسود في الأخرى.
  3. موازنة Adler-32 في zlib: تمرّ البيانات المضغوطة عند فكّها بمجموع التحقق Adler-32، وكل مفتاح يحرّك هذا المجموع بضع مئات الوحدات. وضعنا 160 مفتاح موازنة في الصفوف السوداء، واخترنا المجموعة الجزئية التي تعيد المجموع إلى مكانه بالضبط باستخدام البرمجة الديناميكية والبحث بالالتقاء في المنتصف.
  4. التحقق بـCRC-32 في IDAT: في نهاية كل كتلة IDAT قيمة CRC-32 من 32 بت. أضفنا 40 كتلة إضافية مباشرةً بعد تدفق zlib، وحللنا نظام معادلات خطية على GF(2) بحذف غاوس، فثبّتنا قيمة CRC-32 عند 0x1807EFE0.

البصمة المخصصة: كل خانة تضاعف العمل ستة عشر ضعفًا

لم يكفِ أن تعرض الصورة بصمتها، بل أردنا أن تبدأ البصمة بـefe وتنتهي بـefe. لذلك غيّرنا كتلة nonce بطول 64 بايتًا في نهاية الملف، وجرّبنا مليارات القيم.

لأن لكل خانة 16 قيمة ممكنة، فكل خانة ثابتة جديدة تضاعف متوسط عدد المحاولات 16 ضعفًا، إذ تحتاج N خانة ثابتة إلى متوسط 16^N محاولة. كان المعالج ذو 24 نواة ينفّذ حلقة C بسيطة تجرّب 177 مليون MD5 في الثانية. ولما كتبنا نواة OpenCL تعمل على بطاقة RTX 5070 المحمولة، ارتفعت السرعة إلى 3,54 مليار في الثانية، أي نحو 20 ضعفًا. يحتاج efe23…23efe إلى 1.1 تريليون محاولة في المتوسط؛ أما بصمتنا فظهرت في المحاولة 90 مليارًا، خلال نحو 25 ثانية.

حرّكوا الشريط المنزلق لتغيير عدد الخانات، والنتائج التي وجدناها فعلًا تظهر عند النقاط المعلّمة:

جرّبوا بأنفسكم

نزّلوا الصورة ونفّذوا الأمر في الطرفية. على Windows استخدموا certutil -hashfile dosya.png MD5، وعلى macOS استخدموا md5 dosya.png:

$ md5sum the-arma-of-efe-23-hashquine.png the-arma-of-efe-hashquine.png
efe235ae1b88c53e73d1c11515623efe  the-arma-of-efe-23-hashquine.png
efe8d2bee9dc7b5815f72581e5c17efe  the-arma-of-efe-hashquine.png

الخانات الاثنتان والثلاثون في المخرجات مطابقة تمامًا للرمز المكتوب على القوس من الأعلى إلى الأسفل.

صار الكود الذي يولّد الصورة كاملًا على GitHub: the-arma-of-owl/the-arma-of-efe-hashquine. ولأن هيكل التصادم موجود في المستودع أيضًا، يمكنكم توليد hashquine جديد بقيمة nonce خاصة بكم.

المصادر: Retr0id - MD5 collision with CRC32 preimage ↗ · Ange Albertini - Hashquines ↗