بازگشت به وبلاگ

PNGای که MD5ی خودش را نشان می‌دهد: The Arma Of Efe hashquine

چطور PNGی ساختیم که خلاصه‌ی MD5ی خودش را روی پیکسل‌هایش می‌نویسد، بدون استفاده از الگوی آماده؟ برخورد MD5، لایه‌های PNG و جست‌وجوی efe23…23efe با RTX 5070، در یک روایت تعاملی.

تصویر بالا یک لوگوی معمولی نیست. روی کمانِ سمت راست، از بالا به پایین، efe235ae1b88c53e73d1c11515623efe نوشته شده و این هش MD5ی خود فایل است. اگر تصویر را دانلود کنید و md5sum را اجرا کنید، همان ۳۲ رقم را خواهید دید.

به چنین فایل‌هایی hashquine می‌گویند. نمونهٔ مشهوری که در اینترنت می‌چرخد PNG اژدهادار retr0id است و بیشتر آدم‌ها از همان الگوی آماده استفاده می‌کنند. ما بدون هیچ الگویی، با لوگوی خودمان (The Arma Of Efe)، پیوند وبلاگ خودمان و یک هش سفارشی که با efe شروع و با efe تمام می‌شود، از صفر ساختیمش. در ادامه، گام‌به‌گام و با آزمون‌وخطا توضیح می‌دهم.

hashquine اژدهادار Retr0id به‌صورت PNG که چکیدهٔ MD5 خودش را نشان می‌دهد

hashquine از نوع PNG ساختهٔ David “Retr0id” Buchanan با MD5 برابر 1337e2ef42b9bee8de06a4d223a51337. تصویر: Retr0id، از طریق corkami/collisions.

هش چیست و چرا با هر حرف تغییر می‌کند؟

یک هش (خلاصه‌ی رمزنگاری) اثرانگشتی با طول ثابت است که از محتوای فایل ساخته می‌شود. MD5 تابع خلاصه‌سازی‌ای است که رونالد ریورست در ۱۹۹۱ طراحی کرد. ورودی ۱ بایت باشد یا ۵۰ گیگابایت، خروجی همیشه ۱۲۸ بیت است؛ یعنی 32 رقم از نویسه‌های 0-9 و a-f.

ویژگی اصلی توابع خلاصه‌سازی اثر بهمن است: کوچک‌ترین تغییر در ورودی، کل خروجی را از اول تا آخر عوض می‌کند. چند حرف تایپ کنید و ببینید:

معمای مرغ و تخم‌مرغ

به‌خاطر اثر بهمن، تصویری که MD5ی خودش را روی خودش دارد در نگاه اول غیرممکن به نظر می‌رسد:

  1. تصویر را می‌کشید و MD5ی آن را می‌گیرید، برای مثال 4a8c91e0….
  2. این کد را روی تصویر می‌نویسید و فایل را ذخیره می‌کنید.
  3. چون پیکسل‌ها تغییر کرده‌اند، MD5ی فایل حالا چیز دیگری است، برای مثال 9f02d71a….
  4. کد جدید را می‌نویسید و خلاصه دوباره عوض می‌شود.

برای شکستن این چرخه باید به درونِ MD5 نگاه کرد.

ایده‌ای که چرخه را می‌شکند: کلیدهایی که MD5 را عوض نمی‌کنند

MD5 فایل را یک‌جا پردازش نمی‌کند. فایل را به بلوک‌های ۶۴ بایتی تقسیم می‌کند و به ترتیب پردازش می‌کند: وضعیت اولیه (IV) با بلوک اول ترکیب می‌شود و یک وضعیت میانی (IHV) می‌سازد. این وضعیت میانی با بلوک بعدی ترکیب می‌شود و همین‌طور تا پایان فایل ادامه می‌یابد. آخرین وضعیت میانی همان MD5ی ۳۲ رقمی است.

نکتهٔ کلیدی این است که می‌توان دو بخش داده‌ی ۱۲۸ بایتیِ متفاوت (A و B) پیدا کرد که هر دو به یک وضعیت میانی می‌رسند. به این می‌گویند برخورد با پیشوند یکسان و ابزارهایی مثل FastColl آن را در مدت کوتاهی تولید می‌کنند. چون هر بلوکی که بعد از این بخش می‌آید همان وضعیت میانی را می‌بیند:

  • اگر بخش A قرار بگیرد، روی صفحه یک پاره‌خط دیده می‌شود؛ اگر B قرار بگیرد، دیده نمی‌شود،
  • ولی MD5ی انتهای فایل اصلاً تغییر نمی‌کند.

پس هر جفت برخورد یک کلید است که MD5 را خراب نمی‌کند اما باز و بسته می‌شود. ابتدا MD5ی فایل محاسبه می‌شود، سپس کلیدها طوری تنظیم می‌شوند که دقیقاً همان خلاصه را بکشند. چون خلاصه عوض نمی‌شود، چرخه شکسته می‌شود.

کمان حرف به حرف چطور کشیده شد؟

در فایل ما ۳۲ نویسه روی کمانی که از کمان لوگو پیروی می‌کند، از بالا به پایین چیده شده‌اند. هر نویسه یک رقم هفت‌بخشی است و هر بخش با کلید جداگانه‌ای کشیده می‌شود: در مجموع ۲۲۴ کلید. با نوار لغزان ببینید خلاصه چطور روی کمان قرار گرفته است:

چون از الگوی آماده استفاده نکردیم، PNG باید هر چهار لایهٔ اعتبارسنجی را هم‌زمان پاس می‌کرد:

  1. همترازی ۶۴ بایتی: هر کلید باید در فایل دقیقاً روی مرز ofset % 64 == 0 بنشیند. با افزودن بلوک‌های تهیِ طول‌صفر به جریان فشرده‌سازی DEFLATE، هر کلید را به این مرز هم‌تراز کردیم.
  2. فیلترهای Sub و Up در PNG: پالت را طوری تنظیم کردیم که اندیس‌های 0..254 سیاه و فقط اندیس 255 سفید باشد. دو بخشِ هر برخورد، در بیت پرارزشِ چند بایت با هم فرق دارند. در ردیفی با فیلتر Sub این تفاوت روی پیکسل‌های بعدی ۱۲۸ واحد جابه‌جایی می‌سازد و به خط افقی تبدیل می‌شود؛ ردیف‌های با فیلتر Up آن را پایین می‌برند. بایت‌های بعد از کلید را طوری انتخاب کردیم که خط در یک حالت کاملاً سفید (255) و در حالت دیگر سیاه باشد.
  3. تراز Adler-32 در zlib: داده‌ی فشرده هنگام باز شدن از جمع کنترلی Adler-32 عبور می‌کند و هر کلید این جمع را چند صد واحد جابه‌جا می‌کند. ردیف‌های سیاه را با ۱۶۰ کلید تعادل پر کردیم و زیرمجموعه‌ای را که دقیقاً این اختلاف را جبران می‌کند، با برنامه‌نویسی پویا و جست‌وجوی میان‌راهی (meet-in-the-middle) انتخاب کردیم.
  4. تأیید CRC-32 در IDAT: در انتهای هر تکهٔ IDAT یک CRC-32 ۳۲ بیتی قرار دارد. بلافاصله بعد از جریان فشرده ۴۰ بلوک اضافه گذاشتیم و با حل یک دستگاه معادلات خطی روی GF(2) به روش حذف گاوسی، مقدار CRC-32 را روی 0x1807EFE0 ثابت کردیم.

هشِ سفارشی: هر رقم کار را ۱۶ برابر سخت‌تر می‌کند

نشان دادن MD5ی خود فایل کافی نبود؛ می‌خواستیم خلاصه با efe شروع شود و با efe تمام شود. برای این کار، بلوک ۶۴ بایتیِ nonce در انتهای فایل را تغییر دادیم و میلیاردها خلاصه را امتحان کردیم.

هر رقم می‌تواند ۱۶ مقدار مختلف داشته باشد، پس هر رقم ثابتِ تازه، میانگین تعداد آزمایش‌ها را ۱۶ برابر می‌کند: برای N رقم ثابت، به‌طور میانگین 16^N آزمایش لازم است. پردازندهٔ ۲۴ هسته‌ای با یک حلقهٔ ساده در C، در ثانیه ۱۷۷ میلیون MD5 امتحان می‌کند. وقتی همان کار را با OpenCL روی کارت گرافیک لپ‌تاپیِ RTX 5070 انجام دادیم، سرعت به ۳٫۵۴ میلیارد در ثانیه رسید، یعنی حدود ۲۰ برابر. برای efe23…23efe به‌طور میانگین ۱٫۱ تریلیون آزمایش لازم است؛ نسخهٔ ما پس از ۹۰ میلیارد آزمایش، در حدود ۲۵ ثانیه پیدا شد.

تعداد ارقام ثابت را با نوار لغزان عوض کنید؛ نتایجی که واقعاً پیدا کردیم روی نقاط علامت‌گذاری‌شده دیده می‌شوند:

خودتان بررسی کنید

تصویر را دانلود کنید و در ترمینال اجرا کنید. در ویندوز از 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

32 رقمِ خروجی، همان کدی است که با حروف روی کمان، از بالا به پایین نوشته شده است.

کد تولیدکنندهٔ تصویر کامل در GitHub است: the-arma-of-owl/the-arma-of-efe-hashquine. چون اسکلت برخورد هم در مخزن است، می‌توانید با nonce دلخواه خودتان یک hashquine تازه بسازید.

منابع: Retr0id - MD5 collision with CRC32 preimage ↗ · Ange Albertini - Hashquines ↗