0

问题

我有一个文本文件，其中每行包含一个字符串（换行符 \r\n）。该文件使用 CRC16 以两种不同的方式进行保护。

  1. 4096 字节块的 CRC16
  2. 32768字节块的CRC16

现在我必须修改这些 4096 字节块中的任何一个，所以它（块）

  • 包含特定字符串
  • 不改变文本文件的大小
  • 具有与原始块相同的 CRC 值（对于包含此 4k 块的 32k 块相同）

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

问题

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

它应该在几秒钟或最多时间内完成。一会儿。

4

2 回答 2

1

有数学方法可以解决这个问题，但我不知道。我提出了一个蛮力解决方案：

一个块看起来像这样：

SSSSSSSMMMMEEEEEEE

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

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

您也不需要重新计算以下字节。您只需要检查您所做的修改后的CRC状态是否相同或不同。如果相同，则整个块也将相同。如果不同，则整个区块可能不同（不能保证，但您应该中止试用）。因此，您只计算S+M'部分的 CRC（M'作为修改后的字节）。如果它等于CRC(S+M)你获胜的状态。

这样，您需要处理的数据要少得多，并且最近的桌面或服务器可以2^32在几分钟内完成所需的试验。使用并行性。

于 2013-09-02T10:03:02.023 回答
0

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

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

于 2013-09-02T15:43:34.290 回答