代码之家 › 专栏 › 技术社区 › grubi

CRC16冲突(不同大小块的2个CRC值)

crc16 hash-collision crc security

0

grubi · 技术社区 · 11 年前

问题

我有一个文本文件,每行包含一个字符串(linebreak\r\n)。该文件通过两种不同的方式使用CRC16进行保护。

现在我必须修改这4096字节的块中的任何一个,所以它(块)

脱离这些限制,我可以对块进行任何修改,只要文件本身不破坏其格式,就可以完全填充它。我认为最好使用任何一个完全填充的4k块,而不是最后一个块,因为它可能很短。

问题

我应该如何开始解决这个问题?我会想到的第一件事是某种残忍,但不是需要很长时间才能找到导致两个CRC值保持不变的变化吗?可能有数学方法可以解决这个问题吗?

应该在几秒钟或几分钟内完成。

2 回复 | 直到 11 年前

1

usr 11 年前

那里是解决这个问题的数学方法,但我不知道。我提出了一个暴力解决方案:

一个块看起来是这样的:

SSSSSSSMMMMEEEEEEE

每个字符代表一个字节。S=起始字节,M=可以修改的字节,E=结束字节。

在将每个字节添加到CRC之后,它具有一个新的内部状态。您可以重复使用校验和状态,直到您修改的位置。您只需要重新计算修改后的字节和以下所有字节的校验和。因此,计算 S -只有一次。

您也不需要重新计算以下字节。您只需要在进行修改后检查CRC状态是相同还是不同。如果它是相同的,那么整个块也将是相同的。如果不同,整个区块可能会不同(不能保证,但你应该中止试验)。所以你只计算 S+M' 部分( M' 作为修改的字节)。如果它等于 CRC(S+M) 你赢了。

这样一来,您要处理的数据就少得多,而且最近的台式机或服务器可以完成 2^32 几分钟后需要进行试验。使用并行性。

2

0

Mark Adler 8 年前

看看 spoof.c 。这将直接解决您对4K块的CRC的问题。然而,您需要修改代码,以同时解决4K块的CRC和封闭32K块的CRC的问题。这只是一个添加更多方程来求解的问题。代码非常快,运行在O(log( n ))时间,其中 n 是消息的长度。

基本思想是,您需要在32个或更多的未知数中求解GF(2)上的32个线性方程,其中每个未知数都是您允许更改的位位置。提供超过32个未知数来解决问题是很重要的,因为如果你正好选择32个未知数,那么你最终得到一个奇异矩阵而没有解的可能性就不大了。欺骗码将自动地从>32。