Як створити 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 1337e2ef42b9bee8de06a4d223a51337. Зображення: Retr0id, через corkami/collisions.
Що таке хеш і чому кожна літера змінюється?
Хеш - це відбиток файлу фіксованої довжини, який обчислюється з його вмісту. MD5 - функція хешування, яку 1991 року розробив Рональд Рівест: вхідні дані можуть мати 1 байт або 50 ГБ, але результат завжди становить 128 біт, тобто 32 символи з 0-9 і a-f.
Головна властивість таких функцій - лавинний ефект: навіть найменша зміна вхідних даних змінює результат повністю. Спробуйте ввести щось нижче:
Проблема курки та яйця
Через лавинний ефект зображення, яке містить власний MD5, спершу здається неможливим:
- Малюємо зображення і обчислюємо його MD5, наприклад
4a8c91e0…. - Записуємо цей код на зображення і зберігаємо файл.
- Пікселі змінилися, тож MD5 файлу вже інший, наприклад
9f02d71a…. - Записуємо новий код, і хеш знову змінюється.
Щоб розірвати це коло, потрібно зазирнути всередину MD5.
Ідея, що розриває коло: ключі, які не змінюють MD5
MD5 не обробляє файл одразу. Він ділить його на блоки по 64 байти і обробляє їх по черзі: початковий стан (IV) змішується з першим блоком і дає проміжний стан (IHV). Цей стан змішується з наступним блоком, і так триває, доки файл не закінчиться. Останній проміжний стан і є 32-символьним MD5.
Ключовий момент: можна знайти два різні фрагменти даних по 128 байт (A і B), вирівняні по межі 64 байти, які обидва призводять до того самого проміжного стану. Це називається колізією з однаковим префіксом, і такі інструменти, як FastColl, знаходять її за короткий час. Оскільки кожен наступний блок бачить той самий стан, виходить так:
- якщо на екрані має з’явитися відрізок лінії, вставляємо
A, а якщо не має -B; - але MD5 наприкінці файлу взагалі не змінюється.
Отже, кожна пара колізій - це ключ, який можна відкривати і закривати, не зламавши MD5. Спершу обчислюємо MD5 файлу, а потім підбираємо ключі так, щоб вони малювали саме цей хеш. Оскільки хеш не змінюється, коло розривається.
Як ми намалювали дугу літера за літерою?
У файлі 32 символи, розміщені від верхнього до нижнього кінця дуги логотипа. Кожен символ - це семисегментна цифра, і кожен її сегмент малює окремий ключ: разом 224 ключі. Повзунком можна простежити, як хеш лягає на дугу:
Оскільки готового шаблону ми не використовували, PNG мав одночасно пройти чотири рівні перевірки:
- Вирівнювання по 64 байти: кожен ключ має в файлі точно потрапляти на межу
зсув % 64 == 0. Ми вирівняли кожен ключ, додавши до потоку стиснення DEFLATE порожні блоки нульової довжини. - Фільтри
SubіUpу PNG: Палітру зробили так: індекси0..254- чорні, лише255- білий. Два фрагменти колізії відрізняються старшим бітом кількох байтів. У рядку з фільтромSubця різниця зсуває наступні пікселі на 128 і перетворюється на горизонтальну лінію; рядки з фільтромUpпереносять її вниз. Байти після ключа ми підібрали так, щоб лінія в одному стані була повністю білою (255), а в іншому - чорною. - Компенсація контрольної суми Adler-32 у zlib: під час розпакування стиснені дані проходять перевірку
Adler-32, і кожен ключ зсуває цю суму на кілька сотень одиниць. Для чорних рядків ми додали 160 ключів компенсації і підмножину, що повертає суму точно назад, знайшли динамічним програмуванням і пошуком «зустріч посередині». - Перевірка
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.

- Середня кількість спроб
- 24-ядерний CPU, 177 мільйонів за секунду
- RTX 5070 Laptop, 3,54 мільярда за секунду
Що ми знайшли
efe…efe: знайдено на GPU за третину секунди (1,06 мільярда спроб).
Що ми знайшли
efe23…23efe: приблизно 1,1 трильйона спроб у середньому; наш знайшовся після 90 мільярдів, приблизно за 25 секунд.
Що ми знайшли
efe1807…1807efe: лише розраховано, не шукали.
the-arma-of-owl/the-arma-of-efe-hashquine
Генератор зображень із цієї статті: каркас колізій, семисегментні цифри, виправлення контрольних сум і пошук nonce на GPU.
Джерела: Retr0id - MD5 collision with CRC32 preimage ↗ · Ange Albertini - Hashquines ↗
