collision-detection - CRC32 碰撞

Question

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

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

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 位反馈。这可以在 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 中，然后再次进行。这应该会减少您随后需要搜索的解决方案空间。

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