研究指出zlib deflate.c中38行注释有误,但三个隐藏Huffman不变量阻止了漏洞利用
来源标题:Right Code, Wrong Comment: The Pointer Chase Inside Zlib
一份对zlib 1.4的形式化安全证明研究指出,deflate.c中一段38行注释声称共享缓冲区不会覆盖未读符号是错误的。但研究者尝试构造漏洞利用时,发现三个隐藏的Huffman不变量挡住了去路,且发布版本中相关断言在编译时被移除。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
首页 博客 证明 正确的代码,错误的注释:zlib 内部的指针追逐 deflate.c 中一段 38 行的注释论证了 zlib 的共享缓冲区永远不会覆盖未读符号。那段注释是错的——然而当我们尝试构造漏洞利用时,三个隐藏的 Huffman 不变量挡住了去路。 在 zlib/trees.c:945,compress_block 内层循环里,有一行断言: /* Check for no overlay of pending_buf on needed symbols / #ifdef LIT_MEM Assert(s->pending < 2 * (s->lit_bufsize + sx), "pendingBuf overflow"); #else Assert(s->pending < s->lit_bufsize + sx, "pendingBuf overflow"); #endif 在 zlib 的每个 release 构建中(#ifndef ZLIB_DEBUG),Assert 都会被预处理为空白。compress_block、send_bits、put_byte 在写入 s->pending_buf 之前,都没有检查 s->pending 是否还有空间。 当我们着手为上游 zlib 1.4 构建机器可验证的 Lean 4 安全性证明时(zlib × Lean;仓库 cla7aye15I4nd/oss-proof),库的大部分内容都归结为熟悉的系统不变量:inflate_fast 中的环形缓冲区回绕、longest_match 中对未初始化槽位的哈希链边界,以及跨流式调用的状态机纪律。trees.c 第 945 行则不同。就在 deflate.c 中缓冲区分配的正上方,zlib 的作者写了一段 38 行的数学证明,论证这个被剥离的断言永远不会触发——而那个证明是错的。然而当我们放下定理证明器,尝试构造一个真正能让 compress_block 崩溃的利用输入时,每一次尝试都撞上了一堵无形的墙。 本文从头到尾梳理整个调查过程: deflate 实际做了什么:为什么 zlib 每个块需要两遍处理,以及为什么两个游标最终会在同一个 pending_buf 数组中赛跑。 为什么 deflate.c 的证明失败(以及为什么漏洞利用仍然放不进去):为什么平均比特长度上界无法阻止块中途的碰撞——以及为什么碰撞会触发越界的 .rodata 读取,而不仅仅是损坏输出。 C 代码如何连接到我们的 Lean 4 证明:逐步展示指针修改和 bi_buf 位移如何归约为纯 Huffman 树不等式——最终通过一个代数消去,在不进行暴力搜索的情况下封闭 memLevel 1..2。 证明几何 vs. 物理现实:我们在未修改的 deflate() 上合成出的精确字节和比特最近距离,为什么逐槽证明在接近 980 处撞上数学天花板而物理 C 停在 720,如何弥合这个差距,以及上游 zlib 确实出错的九个地方。 如果你从未读过 zlib 的源代码,pending_buf、sym_buf、bi_valid 和 dist_code 这样的变量名看起来晦涩难懂。然而,一旦你追踪一个像 "abcde_abcde!" 这样的具体字符串通过一个 DEFLATE 块,底层思想就变得直截了当。 假设 deflate 正在扫描 "abcde_abcde_!"。它的 LZ77 匹配器(deflate_fast 或 deflate_slow)发现第二个 "abcde" 重复了 6 个位置之前的字节,将 13 字节的字符串变成 9 个符号: 'a', 'b', 'c', 'd', 'e', '', Match(dist = 6, len = 5), '', '!' 为什么 deflate 不在看到 'a'、'b'、'c' 时立即将它们的 Huffman 位码写入输出流? 因为它还不知道 Huffman 树!最优 Huffman 编码将短比特串(最短 1 比特)分配给频繁符号,将长比特串(最长 15 比特)分配给稀有符号。在 deflate 扫描完整个块并统计每个字节和匹配长度的出现次数之前,它无法构建该块的自定义 Huffman 树。 所以 deflate 对每个块进行两遍处理: 在一切豁然开朗之前,我们还需要格式中的另一个细节:匹配是如何进行 Huffman 编码的。 匹配距离 dist 可以是 1 到 32,768 之间的任何值。如果 DEFLATE 构建一棵有 32,768 个叶子的 Huffman 树,在每个块的开头传输树描述将花费数千字节——远大于小文件!相反,RFC 1951 §3.2.5 将每个长度和距离拆分为一个粗粒度桶(进行 Huffman 编码)加上原始二进制"额外位"(精确定位该桶内的确切偏移): 因为 DEFLATE 将 Huffman 码长上限设为 15 比特,sym_buf 中的一个 3 字节符号可以变成: 当 Pass 1 完成记录最多 (n \le B - 1) 个符号时——其中 (B = \mathrm{lit}_\mathrm{bufsize} = 2^{\mathrm{memLevel}+6}) 的范围从 (128)(memLevel = 1)到 (32{,}768)(memLevel = 9,默认在 memLevel = 8 时为 (16{,}384))——tr_flush_block 评估该块的三种合法 DEFLATE 编码,并选择产生最少字节的那种: Stored(00):放弃压缩,直接从滑动窗口复制原始未压缩输入字节(stored_len + 4 字节)。 Fixed Huffman(01):使用 RFC 1951 硬编码的 Huffman 表(字面量占 8 或 9 比特,长度占 7 或 8 比特,距离占 5 比特)。不需要树头——只需一个 3 比特标签——每个符号最多花费 (8 + 5 + 5 + 13 = 31) 比特。 Dynamic Huffman(10):从 Freq[] 构建自定义树 dyn_ltree 和 dyn_dtree。因为解码器还不知道这些自定义树,send_all_trees 必须在块的最开头序列化树的码长(使用一棵称为 bl_tree 的微小 19 符号游程长度 Huffman 树进行压缩),然后 compress_block 才能编码符号 0。 现在看内存布局。Pass 2 仅在 pending_buf(输出队列)已完全刷新给调用者(pending = 0)时才开始,此时最多只有上一块遗留的 bi_valid <= 7 个比特留在 16 位移位寄存器 bi_buf 中。deflateInit2(deflate.c:463–520)没有为 pending_buf 分配 (4B) 字节再为 sym_buf 分配另外 (3B) 字节,而是分配一个 4B 字节的数组,将前 (B) 字节(8B 比特)留空作为起跑空间,并将 sym_buf 直接放在 pending_buf + B 处: s->lit_bufsize = 1 << (memLevel + 6); / B: 128 .. 32768 (16384 by default) */ ... s->pending_buf = (uchf ) ZALLOC(strm, s->lit_bufsize, LIT_BUFS); / 4 * B bytes / s->pending_buf_size = (ulg)s->lit_bufsize * 4; ... s->sym_buf = s->pending_buf + s->lit_bufsize; / starts 1/4 of the way in */
(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。