Brotli压缩算法与入侵攻击

Question

我花了很多时间在入侵攻击的实现上。理论上，Brotli压缩和使用lzz7家族算法的其他压缩一样，必须容易受到攻击。

我在测试环境中所做的经验和测试显示了gzip上的漏洞攻击有效性和性能。但是当我在Brotli上测试时，攻击失败了，因为压缩结果长度没有显示预期的结果。例如，它为真字符和假字符返回相等的值！

我不知道Brotli算法的具体细节，入侵攻击对压缩算法非常敏感，并且基于正确的字符压缩结果与伪字符之间的一个字节差来判断。使用静态字典或上下文建模可能是造成这种行为的原因之一。

为什么Brotli会这样？

Answer 1

我认为这是一个很有趣的问题，所以我尝试自己实施攻击，但反对的不是“真”或“假”。

为了简单起见，我使用了一个静态页面作为文件，并在最后将内容注入其中。目标的秘密如下所示：

<input type="hidden" name="secret" value="7253b8f45f322b411ce39b12c6e9a84c" />

我使用MSDN页面的源代码作为构建示例。我使用的完整目标页面源可以找到这里；秘密在第33行。这里的一个重要因素是页面内容包含许多其他十六进制字符串，这可能是一个更困难的攻击场景。

为了解决这个问题，我使用了一种相当天真的方法：

1. 将<input type="hidden" name="secret" value="追加到页面的末尾，然后追加我们以前的猜测(如果有的话)，然后按顺序将0000追加到ffff，并在压缩后查找最小的结果。
2. 对于产生最小结果的4个字符的十六进制字符串，将前三个字符添加到我们的猜测中。删除最后一个字符很重要，因为在最后一个字符中存在相当大的不确定性，如果它确实弄错了，那么它倾向于为所有剩余的猜测反复生成最后一个字符(例如，第一个7251将在所有后续猜测中生成1111 )。
3. 循环步骤1和步骤2，直到我们还有<4个字符可供猜测。运行其余可能的组合，在每种情况下都将" />添加到附加的字符串中以完成标记。

我在C#中编写了一个具有并行性的完整实现，您可以找到这里。

以下是GZip的结果：

................................
Guessed f45a
Secret: 7253b8f45
................................
Guessed f322
Secret: 7253b8f45f32
................................
Guessed 2b41
Secret: 7253b8f45f322b4
................................
Guessed 11ca
Secret: 7253b8f45f322b411c
................................
Guessed e39a
Secret: 7253b8f45f322b411ce39
................................
Guessed b12a
Secret: 7253b8f45f322b411ce39b12
................................
Guessed c6e9
Secret: 7253b8f45f322b411ce39b12c6e
................................
Guessed 9a84
Secret: 7253b8f45f322b411ce39b12c6e9a8
Reached last block.

Guessed 4c
Secret: 7253b8f45f322b411ce39b12c6e9a84c
Done!

它只花了几分钟就运行了，并正确地发现了这个秘密。

现在，让我们再次使用Brotli，使用“最快”的压缩模式，对攻击进行相同的配置：

................................
Guessed 7253
Secret: 725
................................
Guessed 3b77
Secret: 7253b7
................................
Guessed 4aa7
Secret: 7253b74aa
................................
Guessed 47aa
Secret: 7253b74aa47a
................................
Guessed 0aaa
Secret: 7253b74aa47a0aa
................................
Guessed 0aaa
Secret: 7253b74aa47a0aa0aa
................................
Guessed 3a0a
Secret: 7253b74aa47a0aa0aa3a0
................................
Guessed 0aaa
Secret: 7253b74aa47a0aa0aa3a00aa
................................
Guessed 4aaa
Secret: 7253b74aa47a0aa0aa3a00aa4aa
................................
Guessed 2aaa
Secret: 7253b74aa47a0aa0aa3a00aa4aa2aa
Reached last block.

Guessed 7a
Secret: 7253b74aa47a0aa0aa3a00aa4aa2aa7a
Done!

不怎么好。第二种猜测出错了，这就抛出了整个算法。因此，也许我们需要更加谨慎，每个块只接受2/4字符，而不是3/4。

................................
Guessed 411c
Secret: 7253b8f45f322b41
................................
Guessed 1c77
Secret: 7253b8f45f322b411c
................................
Guessed e377
Secret: 7253b8f45f322b411ce3
................................
Guessed 9b12
Secret: 7253b8f45f322b411ce39b
................................
Guessed 1277
Secret: 7253b8f45f322b411ce39b12
................................
Guessed c677
Secret: 7253b8f45f322b411ce39b12c6
................................
Guessed e977
Secret: 7253b8f45f322b411ce39b12c6e9
................................
Guessed a84c
Secret: 7253b8f45f322b411ce39b12c6e9a8
Reached last block.

Guessed 4c
Secret: 7253b8f45f322b411ce39b12c6e9a84c
Done!

在那里我们可以看到它又起作用了！因此，以这种方式攻击Brotli并不是不可能的。

解释攻击失败的关键部分是预定义字典：

与大多数通用压缩算法不同，Brotli除了使用动态填充的(“滑动窗口”)字典之外，还使用了一个预定义的120 to字典。预先定义的字典包含13000多个从大量文本和HTML文档中派生出来的常用单词、短语和其他子字符串。

(来自Brotli -维基百科)

那么“真”和“假”在这本字典里出现了吗？是!我找到了字典这里的文本副本，您可以在第6829和1204行分别找到true和false。

我的攻击有效而你的攻击无效的原因是我在寻找字典中没有的东西。对于"true“或"false”这样的单个令牌，使用字典索引比使用距离编码将字符与流中的另一个实例折叠在一起要有效得多。

但是，为什么使用Brotli执行成功的压缩甲骨文攻击要比使用GZip更难呢？字典中似乎没有多少十六进制字符串。我相信这只是因为Brotli压缩系统比GZip更复杂。GZip使用了LZ77和Huffman编码的组合，它非常注重重复消除，这对于压缩甲骨文攻击非常有用。另一方面，Brotli有更多的技巧，导致更高的可能性，其他压缩机制被使用，而不是重复消除在前几个街区，当复制不是很长。改进Brotli攻击的一种方法是在第一个块中强制设置更长的值(例如，6个甚至8个字符)，以试图导致重复的消除。这要慢得多，但可能会迫使可靠的压缩oracle退出Brotli压缩器。