考虑一下：您创建一个包含 16 字节序列集的每个成员的文件。一个 MD5 校验和是一个 16 字节的序列，所以根据定义，这个文件包含它自己的 MD5 校验和。某处。

理论上？是的。

然而，实际上，由于 /any/ 对文件内容的更改，无论多么微小，都会导致校验和发生剧烈变化（毕竟这就是 md5 校验和的工作方式），您需要能够预测校验和的方式当您更改文件以包含校验和时会发生变化-出于所有意图和目的，这与能够破坏 md5 散列算法没有太大区别。

密码学中没有“不可能”之类的东西，但科学确实承认“实际上不可行”或“统计上不可能”的概念，而这正是您目前正在处理的内容。

更新：再想一想，我找到了一种方法，它可以比我最初解释的更快地构建包含自己的 MD5 的文件。新的成本应该是大约 2 ⁶⁵次MD5 基本调用，即比我说的 2 ^{119少得多；}它甚至在技术上是可行的（预算以数百万美元计算——但不是数十亿美元）。有关新方法的说明，请参见末尾。

原答案：

假设 MD5 是一个“完美”的哈希函数，可以建模为随机预言机。随机预言机是一个函数，在尝试一次之前，您对给定输入的输出一无所知。对于随机预言机，实现您正在寻找的最佳方法是希望：您尝试随机输入消息，直到找到包含自己哈希的消息。那么问题是：您应该使用多大的输入消息？

MD5通过添加一些填充位（至少65位，最多576位）来处理数据，使得长度是512的倍数；然后将数据拆分为 512 位块。散列消息的成本与此类块的数量成正比。即对于n位消息，成本是ceil((n+65)/512)。另一方面，一条n位消息提供n-127128 位的子序列。较长的消息使每条消息更有可能成功（以线性方式），但处理成本更高（也以线性方式）。所以消息长度大多是中性的，除了使用短消息时填充隐含的开销更大。总体而言，对于足够大的随机消息（例如 8 kB），您会发现一条消息包含其自己的 MD5，平均成本约为2 ¹¹⁹ MD5 基本评估。MD5 的基本评估在最近的 CPU 上使用了几百个时钟周期，而2 ¹¹⁹用今天的技术（以及明天的技术）是完全无法实现的。

（Graham Lee 所说的“具有所有 128 位序列的大文件”只是这种通用方法的一个特例，带有一条非常大的消息。）

现在众所周知，MD5不是随机预言机——如果只是因为可以有效地计算 MD5 上的冲突，这对于随机预言机来说是不可能的。因此可以想象，存在利用MD5结构弱点的捷径。但是，我不知道有任何攻击会导致包含自己的 MD5 的消息；这看起来像是一个接近原像电阻的问题，这被认为比碰撞要困难得多。

新方法：

MD5，像大多数（如果不是全部）哈希函数一样，是流式处理的：当它处理一个长输入时，它会一次性完成，保持一个小的固定大小的运行状态。具体来说，对于 MD5，运行状态的大小为 128 位（16 字节），数据以 512 位（64 字节）的块的形式进行处理。一个重要的结果如下：如果您有输入m和m||x（“||”表示连接），并且您想要计算 MD5( m ) 和 MD5( m||x )，那么需要额外的成本计算第二个与x的大小成正比，但与m的大小不成正比。换句话说，如果你有一个 1 GB 的输入m，计算 MD5( m)，然后想要计算m的 MD5后跟 20 字节的尾部x，那么第二个 MD5 可以重用为第一个完成的大部分工作，并且几乎是免费的。

这导致以下算法用于查找包含其自己的 MD5的消息m ：

1. 从某个值m开始。
2. 计算 MD5( m )。如果它是m的一部分，则退出（我们找到了我们的消息）。
3. 将m替换为m||x，其中x使得 m||x 的最后 128 位序列没有出现在m的任何位置。
4. 循环到 2。

可以使用De Bruijn 序列在每一步找到正确的“ x ”值。如果每个x是单个位，则使用B(2, 128)作为基本序列。如果您想要一个面向字节的解决方案（消息m必须由整数个字节组成，并且 MD5( m ) 必须出现在m的字节边界处），然后使用B(256, 16)。

要计算找到命中所需的平均迭代次数，请考虑在迭代n中，消息m包含n 个不同的 128 位（或 16 字节）子序列，因此总比较的累积次数将为n ( n +1) /2。假设 MD5 是一个随机预言机，那么每次比较都有 2 ^-128的概率被命中，所以n平均而言，将有n ( n +1)/2 = 2 ¹²⁸ - 转换为 n = 2 ^64.5次迭代。

但是，每次迭代都涉及计算一个 MD5( m || x )，其中x非常小（一位或一个字节），并且 MD5( m ) 已被计算；这通常只需要一个额外的基本 MD5 计算（处理单个 64 字节块）。（如果x是位，那么 512 中只有一次迭代需要处理两个块；如果x是字节，那么这将成为 64 中的一次迭代。）

无论哪种方式，困难的部分将是查找。将索引中的所有子序列进行适当排序以进行快速查找将需要大量快速 RAM，这可能比计算 2 ^64.5 MD5 更昂贵。然而，一些 De Bruijn 序列允许快速、无存储的解码。因此，使用该算法，我们可以找到包含自己的 MD5的消息m ，其成本接近 MD5 的 2 ⁶⁵次计算。结果消息的长度约为 3.3*10 ¹⁸字节，即大约一百万个现代硬盘（如果我们想要面向字节的解决方案，则为八倍）。

可以注意到，该算法可以从任意大小的任意消息m开始。该起点将出现在算法生成的 self-MD5 文件的开头。

（在我最初的回答中，错误出现在这句话中：“更长的消息使每条消息更有可能成功（以线性方式），但处理成本更高（线性）。”如上所述，更长的消息仍然可以只要我们通过重用公共前缀来生成它们，就可以非常有效地处理它们，就像在我的新算法中一样。）

从密码学上讲，您所描述的攻击实际上比找到第一个原像更难，甚至可能比找到第二个原像更难。

鉴于今天的计算能力和今天的加密攻击，这是不可能的。

当前对 MD5 的攻击甚至无法找到原像——我们谈论的是与已证明的各种碰撞攻击完全不同的东西（这也是 MD5 被认为有些不安全的原因）。创建包含 MD5 的文件所需的攻击与冲突无关。

我想说这种攻击，因为正如我所提到的，比原像攻击更难，在我们的有生之年是不太可能发生的。