← Блог

PNG, в котором записан собственный MD5: hashquine The Arma Of Efe

Как мы создали PNG, который выводит собственный MD5 в своих пикселях, без готового шаблона? MD5, ключи коллизий, слои PNG и поиск efe23…23efe на 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. Фильтры PNG Sub и Up: индексы палитры 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-байтовый блок nonce в конце файла.

Каждый символ может принимать 16 значений, поэтому каждый новый зафиксированный символ увеличивает среднее число попыток в 16 раз: для N фиксированных символов в среднем нужно 16^N попыток. На 24-ядерном процессоре простой цикл на C перебирает 177 миллионов MD5 в секунду. Тот же перебор на видеокарте RTX 5070 в ноутбуке через OpenCL дал 3,54 миллиарда в секунду, примерно в 20 раз быстрее. Для efe23…23efe в среднем нужно 1,1 триллиона попыток; наш результат нашёлся на 90-миллиардной попытке примерно за 25 секунд.

Меняйте количество символов ползунком. Реально найденные результаты отмечены точками:

Проверьте сами

Скачайте изображение и запустите проверку в терминале. В Windows используйте certutil -hashfile файл.png MD5, в macOS — md5 файл.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 ↗