CRC32碰撞

Question

我试图找到两个消息之间的碰撞，将导致相同的CRC哈希。 考虑到我正在使用CRC32，是否有任何方法可以缩短在暴力攻击时需要尝试的可能消息列表？

如果有任何提供线索的网站链接将非常有帮助。我已经有一个暴力攻击算法，它只是递增整数，并查看它是否与其他哈希匹配。

- Mike

Answer 1

这完全取决于您所说的“消息”的含义。如果您可以向其中一条消息附加四个无关上下文的字节（即没有任何含义的四个字节），那么它在最原始的意义上变得微不足道。

从位的角度考虑CRC32状态机。

CRC32基于一个伽罗瓦反馈移位寄存器，其状态中的每个位将被来自有效负载数据的32位归纳替换。在每个位的归纳中，由多项式指示的位置将与从移位寄存器末尾观察到的序列进行异或。该序列在填充移位寄存器之前不受输入数据的影响。

例如，假设我们有一个以初始状态10101110、多项式10000011填充未知位X的移位寄存器。

Polynomial *     **  |feedback (End of SR.)
State      10101110     0
State      X1010111     1
State      XX101000     0
State      XXX10100     0
State      XXXX1010     0
State      XXXXX101     1
State      XXXXXX01     1
State      XXXXXXX1     1
State      XXXXXXXX     0

在SR填充之前，反馈不以X为单位提供！因此，为了生成具有预定校验和的消息，您需要获取新消息并生成其CRC，然后计算其下一个32位的反馈。您可以在32步CRC函数中完成此操作。然后，您需要计算此反馈对移位寄存器内容的影响。

一种快捷方法是使用四个零字节填充消息，然后查看校验和。（校验和是SR在结尾处的状态，如果用四个零字节填充，则是反馈和空字节的影响）。将该影响与所需的校验和值进行异或，将四字节的尾部替换为计算出的值，并重新生成校验和。您可以使用任何生成CRC32的程序、十六进制编辑器和能够处理十六进制的计算器来完成此操作。

如果您希望生成两个完全合理且不包含尾随垃圾的消息，则变得有点困难。请确定多个部分，您可以编写 plausible alternatives，长度完全相同。

以英语散文为例。 "I think that this can work" 和 "I believe in this approach" 具有大致相似的意义，但长度完全相同。

识别消息中足够的示例是棘手的部分（除非您想欺骗空格！）如果数据在消息中具有正确的偏移量，则CRC 32是线性的。因此，CRC([messagea][padding]) ^ CRC([padding][messageb]) = CRC([messagea][messageb])。您需要处理一些有关单词对齐的注意事项，作为一般提示，您希望将段落延伸到消息的“固定”部分。通常规则是，您要为n * 1.5个段落提供替代方案，其中n是CRC的大小。

现在，您可以计算出骨架消息的CRC，以及每个替代段落对其的影响，并绘制一个表格，比较每个段落的每个替代方案的影响。然后，您需要选择可修改骨架CRC以匹配所需CRC的替代方案。这个问题实际上很有趣，首先找到任何唯一修改位的替代方案，如果该位需要更改以满足您的CRC，请选择该替代方案并将其影响折叠到CRC中，然后再次循环。那应该会减少您需要搜索的解决方案空间的数量。

这是一个相当难编码的事情，但它可以在非常短的时间内生成您的碰撞。

- scruffy_brit

Answer 2

假如我的计算没有错误，以下表格近似反映了在N次尝试后未找到一次冲突的概率：

  N        概率
-------  -----------
 50,000  74.7%
 77,000  50.1%
 78,000  49.2%
102,000  29.8%
110,000  24.5%
128,000  14.8%
150,000   7.3%
200,000   0.95%

换句话说，必须计算超过200,000个CRC32值才能找到一个重复项的概率小于1%，或者，在尝试102,000次之前找到一个重复项的概率为70.2%。
顺便说一句，这很remarkable，因为例如在第200,000次尝试中找到一个碰撞的概率仍然是1/1000分之1左右((4M - 200,0000) / 4M)，但在第200,000次尝试之前已经找到一个碰撞的概率几乎是确定的(无论如何也高于99%)。 这说明了保持迄今为止计算的CRC数据库的兴趣所在。

我们当然可以花时间研究CRC32算法及其基础数学，以寻找更可能产生CRC32碰撞的消息，但是所需的真正随机尝试次数相对较小(几乎可以肯定地找到至少一次碰撞)，这种密码分析方法几乎不值得花费努力。例如，假设我们能够发现一种选择更容易相互冲突的消息的方法，我们仍然需要尝试约63,000次才能达到99%的可能性至少有一次碰撞（比200,000好，但仍需要大致相同类型的应用）。

在这个领域，我们唯一需要考虑的是避免长度小于4个字节的消息（我在某处读到CRC32在该消息空间中是双射的），以及避免过于相似的消息（即仅相差一两个字符），因为CRC32的原始目的是检测（并可能自动纠正）这些消息中的小差异。

因此，看起来任务的难度不在于找到快速计算CRC32的方法（尽管我们也不应该太慢），而在于管理高达200,000条消息的可快速搜索的数据库（或消息“键”，下面会更详细说明）及其相关的CRC32值。

几个实现所有这些的想法：

• 需要一个简单的ISAM库，或者更好的正式DBMS接口，如MySql甚至SqlLite。
• 通过使用伪随机数生成器（PRNG）来生成消息，我们可以保存消息的键（即我们提供给PRNG以生成给定消息的任何内容），而不是存储整个消息。这将使数据库插入和搜索更加高效，但存在风险，即错误选择PRNG（或基于随机数字的消息生成器），即首先产生某种程度上不太可能发生CRC32冲突的消息...
• 最好批量处理，即生成大约1,000个新CRC，然后检查冲突并存储它们，而不是一次处理一个CRC。如果我们使用现成的DBMS，这一点尤为重要。

- mjv

Answer 3

就在昨天，这个问题在SO上被提出，其中有些指针可能会对您有所帮助。

- fvu

Answer 4

欺骗攻击 正是这样做的。它不需要暴力破解。

- Mark Adler

Answer 5

暴力破解需要大约sqrt(6N)个随机长度的消息来获得大小为N的哈希碰撞的95％概率。例如，CRC32，N = 2 ^ 32，您需要大约160,000条消息。

- user1087245

Answer 6

我会假设你的意思是“消息”而不是“密钥”。

如果你可以选择两个“密钥”，那么由于生日悖论，暴力破解将非常快。随机选择消息，计算它们的CRC，记住所有的消息和相关的CRC，每一个新的消息都有越来越多的机会与现有的消息发生碰撞，因为它们积累起来。坦率地说，我预计这种方法在现代计算机上比查找已知的使CRC32发生碰撞的方法更快。

- Pascal Cuoq

Answer 7

我相信CRC是线性的，所以如果您修改文件中的两个不同部分（原地修改，而不改变长度），CRC中的差异应该被异或在一起。

-- 更正：似乎并不是那么简单。然而，这仍然是我尝试构造碰撞的方法之一--您需要比我今晚倾向于做的更详细地跟踪数学...

- comingstorm

---

好的，但我觉得你说“原地”修改很有趣。我认为CRC是设计用于检测更大文件/字符串中的这些较小修改的，因为它用于检查完整性。 - Mike

这就是重点。CRC 计算速度非常快，能够很好地检测随机更改，但不适用于抵御密码分析。 - Anton Tykhyy