← 博客

能显示自身 MD5 摘要的 PNG:The Arma Of Efe hashquine

如何在不套用现成模板的情况下,制作一张在自己像素里写出自身 MD5 的 PNG?涉及 MD5、碰撞密钥、PNG 图层,以及用 RTX 5070 搜索 efe23…23efe 的过程,附互动讲解。

上面的图片不是普通的 logo。右侧弧线上自上而下写着 efe235ae1b88c53e73d1c11515623efe,它正是这个文件自身的 MD5 摘要。下载这张图片并运行 md5sum,就会看到同样的 32 位字符。

这类文件被称为 hashquine。网上流传最广的例子是 retr0id 那张带龙图案的 PNG,大多数人都直接套用那个现成模板。我们则没有使用任何模板,而是用自己的 logo(The Arma Of Efe)、自己的博客链接,以及一个以 efe 开头、以 efe 结尾的自定义摘要,从零开始制作。下面我会一步步边试边讲。

Retr0id 制作的带龙图案的 PNG hashquine,显示自身的 MD5

David “Retr0id” Buchanan 制作的 PNG hashquine,MD5 为 1337e2ef42b9bee8de06a4d223a51337。图片:Retr0id,来自 corkami/collisions。

什么是哈希,为什么每个字符都会变?

哈希(摘要)是从文件内容中提取的、长度固定的指纹。MD5 是 Ronald Rivest 于 1991 年设计的摘要函数:无论输入是 1 字节还是 50 GB,输出始终是 128 位,也就是由 0-9 和 a-f 组成的 32 位十六进制字符串。

摘要函数的基本特性是雪崩效应:输入中哪怕最微小的改动,都会让输出从头到尾彻底改变。不妨在下面输入点什么试试:

鸡生蛋还是蛋生鸡的难题

由于雪崩效应,一张把自己的 MD5 印在图上的图片乍看之下似乎不可能做到:

  1. 先画好图,算出它的 MD5,例如 4a8c91e0…。
  2. 把这串代码写到图片上并保存。
  3. 像素已经变了,所以文件的 MD5 也变成了别的值,例如 9f02d71a…。
  4. 把新的代码写进去,摘要又会再次改变。

要打破这个循环,就得深入 MD5 的内部去寻找办法。

打破循环的思路:不改变 MD5 的密钥

MD5 不会一次性处理整个文件。它把文件切成 64 字节的块,依次处理:初始状态(IV)与第一个块混合,得到一个中间状态(IHV)。这个中间状态再与下一个块混合,如此持续到文件结束。最后一个中间状态,就是那 32 位的 MD5 本身。

关键在于:可以找到两段按 64 字节边界对齐、各 128 字节的不同数据(A 和 B),它们会得出相同的中间状态。这被称为相同前缀碰撞,FastColl 之类的工具可以很快生成它。由于该段之后的每个块看到的都是相同的中间状态:

  • 放入 A 段时,屏幕上会出现一段线条;放入 B 段时则不会出现,
  • 但文件末尾的 MD5 完全不会改变。

也就是说,每一对碰撞数据都是一把钥匙:不改变 MD5 就能开关它显示的内容。先计算出文件的 MD5,再调整这些钥匙,让它们恰好拼出这个摘要。摘要本身没有变,循环因此被打破。

弧线上的字符是如何一个个画出来的?

在我们的文件中,32 个字符沿着 logo 中弧线的走向自上而下排列。每个字符都是一个七段数码管数字,每一段由独立的密钥绘制,共计 224 把密钥。拖动滑块,即可观察摘要是如何沿弧线排布的:

因为没有使用现成模板,我们必须同时通过 PNG 的四层校验:

  1. 64 字节对齐:每把密钥在文件中都必须恰好落在 偏移量 % 64 == 0 的边界上。我们在 DEFLATE 压缩流中插入零长度的空块,把每把密钥对齐到这一边界。
  2. PNG Sub 和 Up 过滤器:我们把调色板中索引 0..254 设为黑色,只有索引 255 设为白色。碰撞对的两部分会在若干字节的最高位上产生差异。在 Sub 过滤的行中,这一差异会使其后的像素偏移 128,变成一条水平线;Up 过滤的行则把它向下推移。我们选择密钥之后的字节,使线条在一种状态下恰好为 255(白色),在另一种状态下为黑色。
  3. Zlib Adler-32 平衡:压缩数据解压时要通过 Adler-32 校验和,而每把密钥都会使该校验和改变数百个单位。我们在黑色线条区域放入 160 把平衡密钥,并通过动态规划与中间相遇(meet-in-the-middle)搜索,选出能精确抵消总和的子集。
  4. IDAT CRC-32 校验:每个 IDAT 块末尾都有一个 32 位的 CRC-32。我们在压缩流之后紧接着放入 40 个额外块,并通过高斯消元法求解 GF(2) 上的线性方程组,把 CRC-32 的值固定为 0x1807EFE0。

自定义摘要:每多一位,工作量就翻 16 倍

只显示文件自身的 MD5 还不够,我们还要求摘要以 efe 开头、以 efe 结尾。为此,我们通过改变文件末尾一个 64 字节的 nonce 块,尝试了数十亿个摘要。

每一位可以取 16 种不同的值,因此每固定一位新的字符,平均尝试次数就会增加 16 倍:固定 N 位需要平均约 16^N 次尝试。在 24 核 CPU 上,一个简单的 C 循环每秒能尝试 1.77 亿次 MD5。改用 OpenCL 在 RTX 5070 笔记本显卡上运行,速度达到每秒 35.4 亿次,约为前者的 20 倍。efe23…23efe 平均需要 1.1 万亿次尝试;我们的结果在第 900 亿次尝试时找到,耗时约 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。碰撞骨架也在仓库中,因此你可以用自己的 nonce 值生成新的 hashquine。

参考资料: Retr0id - MD5 collision with CRC32 preimage ↗ · Ange Albertini - Hashquines ↗