能否构造一个含有自己哈希或MD5等的文件？ 第1页

先说 MD5 吧，如果不要求 MD5 值一定要以 ASCII 字符串的形式出现的话，那 MD5 的自我指涉（Self-Reference）还是可以很轻松地做到的。

不仅可以，你甚至可以做得非常花哨，比如下面这个 GIF 图片，它能用动画效果来展示自身的 MD5 值。

因为不知道知乎会不会压缩图片，打乱原本的 MD5 散列，所以我在这里贴一下这个 GIF 的下载地址，大家感兴趣的话可以自己下载算一下它的 MD5 值。

https:// shells.aachen.ccc.de/~s pq/md5.gif

类似的还有这个 PDF 文件，打开后里面的文件内容就是文件自身的 MD5 值。

https://www. makomk.com/~aidan/selfm d5-lastfix.pdf

想要实现这种效果，你主要需要一个可行的碰撞攻击算法和一点巧思。

开始之前我们先来温习一条密码学知识—— MD5、SHA-1、SHA-2 等哈希算法，都属于著名的 Merkle–Damgård 构造。

这种构造会把数据分割成一个个固定长度的块（Block），然后把它们依次塞进一个压缩函数 里。压缩函数 每吃进去一个块，就会更新一下现在的“状态”。等到 吃不到更多的块了，它就会把最后的“状态”当作哈希结果输出来。

假设我们有 两段哈希值相等、长度是整数块的数据。既然 ，它们处理到最后的“状态”显然是一样的。那么如果我们把一段完全相同的数据 追加到两者的后面，最后的“状态”也应该是一样的，也就是说 。

换句话说，在整数块长度的碰撞数据后面追加相同的数据，哈希值不会发生变化。

进一步地，假设你手里还有另一对碰撞数据 ，且 。那么你把两对碰撞数据分别连接，就应该得到：

注意了，现在你已经可以自由地选择第一个位置是 还是 ，选择第二个位置是 还是 ，却不会对算出来的哈希值造成任何的影响，不同组合的哈希值都是完全相等的。

这个就是魔术的关键。

一个MD5值一共有32个位置，每个位置有16个字符可供选择。如果你能找出32组数据，每组数据有16个值，这16个值能够表达出16个不同的字符，且它们的 MD5 哈希相等，那么你就可以利用我们刚才发现的规律，自由地排列组合出任何一串字符，却又不改变文件的 MD5 值。

好，“找出16段 MD5 值一样的数据，还要分别表达16个不同的字符”，听起来很简单吧？

做起来其实也挺简单的，利用选择前缀碰撞攻击（Chosen-Prefix Collision Attack）就可以了。

给定任意两段数据 ，通过选择前缀碰撞攻击我们可以找出两段后缀 ，使得 。

而 GIF、PDF 这些文件格式，都是允许在一小块字符图片后面缀上没有用的垃圾数据的。这些垃圾数据都可以被跳过，不参与绘制。

掌握了这些基本知识后，我们就可以开始生成我们的碰撞数据了：

一、先给每个字符绘制一副图片，或者生成一段动画，得到16段画面数据 。

二、把16段数据两两一组分成8组，进行选择前缀碰撞攻击，得到

• （注： 指一段“添加后可以让 有相同哈希的垃圾数据”）
• ……

三、把8组数据两两一组分成4组，进行选择前缀碰撞攻击，得到

• ……

四、以此类推，一共进行8+4+2+1=15次选择前缀碰撞攻击后，我们就能得到一组16段哈希值彼此相等的碰撞数据了。（顺便一提，这个生成过程其实可以组成一种单独的攻击手段，叫 Nostradamus Attack / Herding Attack）。

这样的数据我们一共需要32组，也就是说一共进行32x15=480次选择前缀碰撞攻击，就可以做出想要的 GIF 动画了。

得益于王小云院士的突破性贡献，还有 HashClash 等开源框架，对 MD5 进行碰撞攻击现在轻松又愉快。理论上讲对 SHA-1 我们也可以玩出类似的把戏，但是因为 SHA-1 的碰撞攻击目前成本还挺高，所以暂时还没有人烧钱去玩。如果你熟练掌握了我们刚才讲授的思路，那等到 SHA-1 的碰撞成本降下来之后，你也可以在自己的笔记本电脑上玩玩看。

最后我们再来讨论一些更一般的情况吧。刚才的方案主要需要三点条件：

1. 针对该哈希函数，存在成熟的选择前缀碰撞攻击算法。
2. 针对该哈希函数，存在追加数据却不改变哈希值的手段。
3. GIF、PDF 等文件格式提供了足够的冗余，让我们能够给每个字符生成16段可替换的数据。

那么假设这些取巧的条件并不存在，我们的文件就是干巴巴一个文本文件，里面字符1就是1，2就是2，那么还有可能存在一个文件包含自身的哈希值吗？

理论上讲这样的文件是大概率存在的。我在 @诞于良夜之中 的答案里看到了一篇推导，大大节省了我开WolframAlpha的时间——令 为哈希函数的结果长度， 为一个内容随机的文件的长度，那么这个文件不包含自身哈希的概率就是 。随着 趋近于 ，这个概率也迅速趋近于 。

然而知道这个东西存在是一回事，把它找出来又是另一回事。

• 如果你能够指定一个哈希值，然后快速搜索所有能得到这个哈希值的文件的话，就意味着你破解了这个哈希算法的抗原像性。
• 如果你能够在编辑一个文件的同时控制它的哈希值向你想要的结果靠拢，那么你大概率可以借助这个能力破解这个哈希算法的抗原像性、抗二次原像性等一系列安全性质。

考虑到以上这些目标的达成难度，如果不采用类似前文的取巧方案的话，我认为这个任务除了暴力破解没别的好办法了，上量子计算都加不了多少速（https://arxiv.org/pdf/1603.09383.pdf）。

8月4日更新：

之前写答案的时候，想当然地认为MD5做CPC攻击的效率应该已经很高了，所以直接用Nostradamus attack构造16-way collision应该就够用了。

看了某某的答案我才意识到，原来这个问题在实现上还有这么多可以优化的细节，推荐有基础、有兴趣的读者阅读一下。