← Блог

Як створити PNG, що показує власний MD5-хеш: «The Arma Of Efe» з нуля

Що таке хеш і MD5? Як зображення може містити власний MD5 у своїх пікселях? Як ми з нуля створили hashquine з MD5 efe23…23efe на GPU RTX 5070, з інтерактивним поясненням.

Зображення вище не є звичайним логотипом. На дузі праворуч, зверху вниз, написано efe235ae1b88c53e73d1c11515623efe, і це MD5-хеш самого файлу. Завантажте зображення і виконайте md5sum, і ви побачите ті самі 32 символи.

Такі файли називають hashquine. Найвідоміший приклад у мережі - PNG із драконом від retr0id, і більшість людей використовує саме цей готовий шаблон. Ми ж не брали жодного шаблону: створили власний логотип (The Arma Of Efe), власне посилання на блог і хеш, який починається з efe і закінчується на efe, повністю з нуля. Нижче пояснюємо кроки так, як ми їх проходили, разом із невдалими спробами.

PNG-хешквайн Retr0id з драконом, що показує власний MD5

PNG-хешквайн Девіда «Retr0id» Б’юкенена, MD5 1337e2ef42b9bee8de06a4d223a51337. Зображення: Retr0id, через corkami/collisions.

Що таке хеш і чому кожна літера змінюється?

Хеш - це відбиток файлу фіксованої довжини, який обчислюється з його вмісту. MD5 - функція хешування, яку 1991 року розробив Рональд Рівест: вхідні дані можуть мати 1 байт або 50 ГБ, але результат завжди становить 128 біт, тобто 32 символи з 0-9 і a-f.

Головна властивість таких функцій - лавинний ефект: навіть найменша зміна вхідних даних змінює результат повністю. Спробуйте ввести щось нижче:

Проблема курки та яйця

Через лавинний ефект зображення, яке містить власний MD5, спершу здається неможливим:

  1. Малюємо зображення і обчислюємо його MD5, наприклад 4a8c91e0….
  2. Записуємо цей код на зображення і зберігаємо файл.
  3. Пікселі змінилися, тож MD5 файлу вже інший, наприклад 9f02d71a….
  4. Записуємо новий код, і хеш знову змінюється.

Щоб розірвати це коло, потрібно зазирнути всередину MD5.

Ідея, що розриває коло: ключі, які не змінюють MD5

MD5 не обробляє файл одразу. Він ділить його на блоки по 64 байти і обробляє їх по черзі: початковий стан (IV) змішується з першим блоком і дає проміжний стан (IHV). Цей стан змішується з наступним блоком, і так триває, доки файл не закінчиться. Останній проміжний стан і є 32-символьним MD5.

Ключовий момент: можна знайти два різні фрагменти даних по 128 байт (A і B), вирівняні по межі 64 байти, які обидва призводять до того самого проміжного стану. Це називається колізією з однаковим префіксом, і такі інструменти, як FastColl, знаходять її за короткий час. Оскільки кожен наступний блок бачить той самий стан, виходить так:

  • якщо на екрані має з’явитися відрізок лінії, вставляємо A, а якщо не має - B;
  • але MD5 наприкінці файлу взагалі не змінюється.

Отже, кожна пара колізій - це ключ, який можна відкривати і закривати, не зламавши MD5. Спершу обчислюємо MD5 файлу, а потім підбираємо ключі так, щоб вони малювали саме цей хеш. Оскільки хеш не змінюється, коло розривається.

Як ми намалювали дугу літера за літерою?

У файлі 32 символи, розміщені від верхнього до нижнього кінця дуги логотипа. Кожен символ - це семисегментна цифра, і кожен її сегмент малює окремий ключ: разом 224 ключі. Повзунком можна простежити, як хеш лягає на дугу:

Оскільки готового шаблону ми не використовували, PNG мав одночасно пройти чотири рівні перевірки:

  1. Вирівнювання по 64 байти: кожен ключ має в файлі точно потрапляти на межу зсув % 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 стоїть 32-бітний CRC-32. Одразу після стиснутого потоку ми додали 40 блоків, а систему лінійних рівнянь над GF(2) розв’язали методом Гауса. Так CRC-32 зафіксувався на значенні 0x1807EFE0.

Персоналізований хеш: кожна цифра збільшує роботу в 16 разів

Недостатньо було, щоб файл показував свій MD5; ми хотіли, щоб хеш починався з efe і закінчувався на efe. Для цього змінювали 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

32 символи у виводі точно збігаються з кодом, написаним на дузі зверху вниз.

Увесь код, який створює це зображення, є на GitHub: the-arma-of-owl/the-arma-of-efe-hashquine. Оскільки скелет колізій також є в репозиторії, ви можете створити новий hashquine зі своїм значенням nonce.

Джерела: Retr0id - MD5 collision with CRC32 preimage ↗ · Ange Albertini - Hashquines ↗