15

我试图找到两条消息之间的冲突，这将导致相同的 CRC 哈希。考虑到我正在使用 CRC32，有什么方法可以缩短我在进行蛮力攻击时必须尝试的可能消息列表？

任何带有此提示的网站链接都会有所帮助。我已经有一个蛮力算法可以做到这一点，但它只是增加整数并查看它是否会匹配其他哈希。

4

7 回答 7

25

这完全取决于您所说的“消息”是什么意思。如果您可以在其中一条消息中附加四个字节的乱码。（IE 四个字节在消息的上下文中没有任何意义。）然后它在真正意义上变得微不足道。

考虑通过 CRC32 状态机移动的位。

CRC32 基于 galois 反馈移位寄存器，其状态中的每一位将被替换为从有效载荷数据中感应的 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 位反馈。这可以在 CRC 函数的 32 个步骤中完成。然后，您需要计算此反馈对移位寄存器内容的影响。

这样做的捷径是用四个零字节填充您的消息，然后查看校验和。（校验和是最后SR的状态，如果填充四个零字节是反馈和空字节的影响。）

与您想要的校验和值影响的异或，用该计算值替换四字节尾部并重新生成校验和。您可以使用任何生成 CRC32 的程序、十六进制编辑器和可以处理十六进制的计算器来执行此操作。

如果您想生成两条完全有意义且不包含尾随垃圾的消息，事情会变得有些困难。找出一些你可以用完全相同的长度写出合理的替代方案的部分。

以英文散文为例。“我认为这行得通”和“我相信这种方法”具有大致相似的含义，并且长度完全相同。

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

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

编写代码是一件相当困难的事情，但它会在很短的时间内产生碰撞。

于 2009-10-05T12:11:17.417 回答
15

我的微积分没有缺陷，在 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% 顺便说一句，这是非常了不起的，因为找到一个冲突的概率例如，第200,000 次尝试仍然是 1% 的 1/1000（（4M - 200,0000）/4M），但在第 200,000 次尝试之前可能已经发现一次碰撞是准确定的（好吧，无论如何都在 99% 以上）。 这表明了保留迄今为止计算的 CRC 数据库的兴趣。

我们当然可以花一些时间研究 CRC32 算法及其基础数学，以尝试找到更有可能产生 CRC32 冲突的消息，但是要找到至少一个具有准确定性的冲突所需的真正随机尝试数量相对较少，这使得这种密码分析方法几乎不值得付出努力。例如，假设我们可以找到一种方法来选择相互碰撞可能性高 10 倍的消息，我们仍然需要尝试大约 63,000 次才能达到至少发生一次碰撞的 99% 的可能性（优于 200,000，但仍需要大致相同类型的应用程序。）
在这方面，我们可能要考虑的唯一事情是避免长度小于 4 字节的消息（我在某处读到 CRC32 在此消息空间中是双射的），并避免消息过于相似（即仅相差一个或两个字符），因为 CRC32 的最初目的是检测（并且可能自动更正）如此小的消息的差异。

因此，这项任务的难度似乎并不在于找到以极快的速度计算 CRC32 的方法（尽管我们也不应该太慢），而是管理一个可快速搜索的数据库200,000 条消息（或消息“密钥”，更多内容见下文）及其相关的 CRC32 值。

实现这一切的一些想法

  • 需要一个简单的 ISAM 库，或者更好的正式 DBMS 接口，例如 MySql 甚至 SqlLite。
  • 通过使用伪随机数生成器 (PRNG) 来生成消息，我们可以保存消息密钥（即我们提供给 PRNG 以生成给定消息的任何内容），而不是存储整个消息。这将使数据库插入和搜索更有效，但有错误选择 PRNG（或者更确切地说是基于消息生成器的 pm 随机数）的风险，即会产生（起初）不太可能发生 CRC32 的消息的风险-碰撞...
  • 分批工作可能更好，即生产 1,000 个新的 CRC，然后检查冲突并存储它们，而不是一次为一个 CRC 做​​所有这些事情。如果我们使用现成的 DBMS，则尤其如此
于 2009-10-05T00:28:18.547 回答
1

就在昨天在 SO 上出现了这个问题，那里提到的一些指针可能会对您有所帮助。

于 2009-10-04T09:27:52.670 回答
1

您需要关于大小为 N 的散列的 sqrt(6N) 随机长度消息的蛮力，以获得 95% 的碰撞概率。例如 CRC32 ， N = 2^32 ，您需要大约 160 000 条消息

于 2011-12-08T07:28:18.543 回答
0

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

如果允许您选择两个“键”，那么由于生日悖论，蛮力无论如何都会相当快。选择随机消息，计算它们的 CRC，记住所有消息和相关的 CRC，随着它们的积累，每个新消息都有越来越多的机会与现有消息发生冲突。坦率地说，我希望这种方法在现代计算机上比查找已知方法来使 CRC32 冲突更快。

于 2009-10-04T09:06:08.997 回答
0

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

——更正：似乎没有那么简单。然而，这仍然是我在尝试构建碰撞时会采取的策略——你需要比我今晚倾向于做的更详细地遵循数学......

于 2009-10-04T09:10:18.357 回答
0

欺骗正是这样做的。它不需要蛮力。

于 2018-05-17T16:50:53.780 回答