CRC32碰撞 [英] CRC32 Collision

问题描述

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

I am trying to find a collision between two messages that will lead to the same CRC hash. Considering I am using CRC32, is there any way I can shorten the list of possible messages I have to try when doing a brute force attack?

任何链接带有提示的网站将很有帮助。我已经有一个蛮力算法可以做到这一点，但是它只是简单地增加整数，看看是否能匹配其他哈希值。

Any links to websites with hints on this will be helpful. I already have a brute force algorithm that will do this but it simply increment integers and sees if it will match other hashes.

推荐答案

这完全取决于您所说的消息。如果可以将四字节乱码添加到其中一条消息中。 （即，在消息上下文中没有意义的四个字节。）然后，从字面上最真实的意义来看，它变得微不足道了。

It depends entirely on what you mean by "message". If you can append four bytes of gibberish to one of the messages. (I.E. four bytes that have no meaning within the context of the message.) Then it becomes trivial in the truest sense of the word.

根据经过的位进行思考

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

CRC32 is based on a galois feedback shift register, each bit in its state will be replaced with the induction of 32 bits from the payload data. At the induction of each bit, the positions indicated by the polynomial will be exclusive ored with the sequence observed from the end of the Shift register. This sequence is not influenced by the input data until the shift register has been filled.

例如，假设我们有一个填充了初始状态10101110（多项式为10000011）的移位寄存器。 ，并用未知位X填充。

As an example, imagine we have a shift register filled with initial state 10101110, polynomial 10000011, and filling with unknown bits, 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达到充满了！
因此，为了生成带有预定校验和的邮件，您需要接收新邮件，生成新邮件的CRC，然后计算出下一个32位反馈。您可以在CRC功能的32个步骤中完成此操作。然后，您需要计算此反馈对移位寄存器的内容的影响。

The feedback isn't in terms of X until the SR has been filled! So in order to generate a message with a predetermined checksum, you take your new message, generate it's CRC and work out it's next 32 bits of feedback. This you can do in 32 steps of the CRC function. You then need to calculate the effect this feedback has on the contents of the shift register.

执行此操作的捷径是用四个零字节填充邮件，然后查看校验和。 （校验和是末尾SR的状态，如果用四个零字节填充，则是反馈和空字节的影响。）

A shortcut for doing this is to pad your message with four zero bytes and then look at the checksum. (Checksum is the state of the SR at the end, which if padded with four zero bytes is the influence of the feedback and the empty bytes.)

该影响的异或用所需的校验和值，用该计算值替换四字节尾部，然后重新生成校验和。您可以使用任何生成CRC32的程序，一个十六进制编辑器和一个可以处理十六进制的计算器来做到这一点。

Exclusive OR that influence with the checksum value you want, replace the four byte trailer with that computed value and regenerate the checksum. You could do this with any program that generates CRC32, a hex editor, and a calculator that can handle hex.

如果要生成两条完全有意义的消息并且不包含尾随的垃圾，事情会变得有点困难。确定一些可以写出合理选择的部分，长度完全相同。

If you want to generate two messages that both make complete sense and don't contain trailing garbage, things get a little harder. Identify a number of sections that you can write plausible alternatives, with exactly the same length.

以英语散文为例。
我认为这可以工作
和
我相信这种方法
具有大致相似的含义，并且长度完全相同。

Using english prose as an example. "I think that this can work" and "I believe in this approach" Have broadly similar meanings, and exactly the same length.

要确定消息中足够的示例，是很棘手的（除非您想用空格作弊！）CRC 32是线性的，只要数据在消息中具有正确的偏移量即可。因此CRC（[messagea] [padding]）^ CRC（[padding] [messageb]）= CRC（[messagea] [messageb]）
需要注意一些与单词对齐有关的注意事项，作为一般提示，您希望将段落扩展到邮件的固定部分。作为一般规则，您希望有n * 1.5段落的替代项，其中n是CRC的大小。

Identifying enough examples in your message is the tricky bit (Unless you want to cheat with whitespace!) CRC 32 is linear, provided the data has the correct offset within the message. So CRC([messagea][padding])^CRC([padding][messageb])=CRC([messagea][messageb]) There are some caveats with word alignment that you'll need to cope with, as a general hint, you want to extend the passages out into the "fixed" parts of the message. As a general rule you want to have alternatives for n*1.5 passages, where n is the size of the CRC.

现在，您可以计算出骨架消息具有的CRC。 ，每个替代段落都会对其产生的印象，然后绘制一张表格，比较每个替代段落对每个段落的影响。然后，您需要选择其他选项，这些选项将修改骨骼CRC以匹配所需的CRC。这个问题实际上很有趣，首先要找到可以唯一修改某位的任何替代方法，如果您的CRC需要更改该位，请选择该替代方法并将其影响范围扩大到CRC中，然后再进行一次尝试。这将减少您随后需要搜索的解决方案空间。

You can now calculate the CRC that the skeletal message has, the impression that each alternative passage would have on it, and then draw up a table comparing the influence that each alternative for each passage would have. You then need to select alternatives that will modify the skeletal CRC to match the CRC you want. That problem is actually quite fun to solve, First off find any alternatives that uniquely modify a bit, if that bit needs to change for your CRC, select that alternative and fold it's influence into the CRC, then go round again. That should reduce the solution space that you then need to search.

编写起来很困难，但是会在很短的时间内产生碰撞。

That's quite a tough thing to code up, but it would generate your collisions in a very short time span.

这篇关于CRC32碰撞的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！