CRC32碰撞

从比特在CRC32状态机中移动的角度进行思考。

例如,假设我们有一个移位寄存器,填充了初始状态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

因此,为了生成具有预定校验和的消息,您需要获取新消息,生成CRC,并计算出接下来的32位反馈。您可以在CRC函数的32个步骤中完成此操作。然后,您需要计算此反馈对移位寄存器内容的影响。

这样做的快捷方式是用四个零字节填充消息,然后查看校验和。(校验和是SR在末尾的状态,如果用四个零字节填充,则是反馈和空字节的影响。)

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

以英语散文为例。 和 “我相信这种方法” 含义大致相似,长度完全相同。

在消息中识别足够的示例是一个棘手的问题(除非你想用空格作弊!)只要数据在消息中具有正确的偏移量,CRC 32就是线性的。因此,CRC([messagea][padding])^CRC([padding][messageb])=CRC([message a][messageb]]) 单词对齐有一些需要注意的问题,作为一般提示,你想将段落扩展到消息的“固定”部分。作为一般规则,您希望有n*1.5通道的替代方案,其中n是CRC的大小。

如果我的微积分没有缺陷 不

  N      Probability
-------  -----------
 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%

换句话说,必须计算超过200000个CRC32值的概率 之前 找到重复项的概率小于1% 之前 102000次尝试占70.2%
顺便说一句,这是值得注意的,因为发现一次碰撞的概率,比如说, 正是 第20万次尝试仍然是1%的1/1000((4M-2000000)/4M),但可能已经发现了一次碰撞 之前 .

我们当然可以花一些时间研究CRC32算法及其底层数学,试图找到 更有可能产生CRC32冲突的消息 ,但是,以准确定性找到至少一个碰撞所需的真正随机的尝试次数相对较少,这使得这种密码分析方法几乎不值得付出努力。例如,假设我们可以找到一种方法来选择相互碰撞可能性高10倍的消息,我们仍然需要尝试63000次,才能达到至少发生一次碰撞的99%的几率(优于200000次,但仍然需要大致相同类型的应用程序)
避免过于相似的消息 (即仅相差一两个字符),因为CRC32的最初目的是检测(并可能自动纠正)消息中的这种微小差异。

管理一个最多可搜索200000条消息的快速数据库 (或消息“key”,详见下文)及其关联的CRC32值。

实现这一切的几个想法

• 通过使用伪随机数生成器(PRNG)来生成消息,我们可以保存消息 (即,无论我们向PRNG提供什么来生成给定的消息),而不是存储整个消息 消息

this question here on SO ,这里提到的几个建议可能会对你有所帮助。

spoof

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

我相信CRC是线性的,所以如果你修改(在不改变长度的情况下)文件的两个不同部分, CRC中的差异应该放在一起。

--更正:事情似乎没那么简单。然而,这仍然是我试图构建碰撞时会采取的策略——你需要比我今晚更详细地理解数学。..