Half-Moon Cookie: Private, Similarity-Based Blocklisting with TOCTOU-Attack Resilience

1. 研究背景与问题定义 (Problem)

核心问题：
传统的黑名单（Blocklisting）机制在检测恶意内容（如恶意软件、垃圾邮件、CSAM 等）时面临两个主要矛盾：

1. 隐私泄露风险： 为了检查客户端的文件是否属于黑名单，通常需要客户端将文件哈希发送给服务器，或者服务器向客户端公开黑名单。这会导致客户端的私有数据（如未公开的软件代码）泄露给服务器，或者服务器的专有黑名单泄露给客户端。
2. TOCTOU（检查时与使用时）攻击漏洞： 为了性能，通常将昂贵的黑名单检查放在非关键路径（例如发送方在发送前检查），而接收方在接收时仅做快速确认。如果黑名单在“检查”和“使用”之间被更新（例如发现了新的恶意变种），接收方可能使用了一个在检查时是安全的、但在使用时已被标记为恶意的文件。现有的隐私保护方案通常缺乏一种既高效又能防止此类时间差攻击的确认机制。

具体挑战：

• 需要支持相似性匹配（Fuzzy Matching），而不仅仅是精确匹配，以检测经过混淆或微调的恶意软件。
• 需要隐私保护：服务器不知道客户端输入的具体内容，客户端不知道服务器的黑名单细节。
• 需要高性能：检查过程不能过于昂贵，且接收方的验证过程必须极快，以避免成为性能瓶颈。
• 需要防篡改：防止恶意发送方通过伪造哈希值绕过检查，或者在检查通过后篡改文件。

2. 方法论与系统设计 (Methodology)

作者提出了 Half-Moon Cookie (Half Moon) 框架，这是一个三方协议（发送方 $C_{snd}$、接收方 $C_{rcv}$、服务器 $S$），旨在解决上述问题。

核心架构：两阶段检查机制

系统分为两个阶段，通过“显式检查”和“隐式检查”来平衡隐私、安全性和性能：

1. 显式检查 (Explicit Check) - 由发送方发起：

   • 目的： 发送方将文件 $w$ 提交给服务器进行隐私保护的相似性黑名单检查。
   • 流程：
     • 嵌入与映射 (Embed-and-Map, FEM)： 使用可重用混淆电路 (Reusable Garbled Circuits, RGC) 技术。发送方在本地将文件 $w$ 嵌入到度量空间（如汉明空间），生成向量。服务器提供密钥，但不知道具体的嵌入结果。此步骤将文件哈希化并映射，同时防止发送方伪造哈希值。
     • 测试与提交 (Test-and-Commit, FTC)： 服务器使用模糊集合交集（Fuzzy PSI）技术（基于 Chakraborti et al. 的距离感知 PSI），在加密状态下比较嵌入向量与黑名单 $L$ 的距离。如果距离超过阈值（即未被列入黑名单），服务器生成一个隐藏且绑定的令牌 (Hiding and Binding Token) $\gamma$ 并将其存入“白名单 (Allowlist)"。
   • 输出： 发送方获得令牌 $\gamma$ 和一个随机数 (nonce)，用于后续验证。

2. 隐式检查 (Implicit Check) - 由接收方发起：

   • 目的： 接收方在接收文件后，快速验证该文件是否通过了之前的显式检查，且未被篡改。
   • 流程：
     • 接收方收到文件 $w$、掩码 $\vec{m}$ 和 nonce。
     • 接收方重新计算嵌入向量，并与服务器交互（使用不经意线性评估 OLE）。
     • 服务器验证计算出的令牌是否与白名单中存储的 $\gamma$ 匹配。
   • 优势： 此过程不依赖黑名单大小，仅涉及简单的令牌比对，因此速度极快，且能防止 TOCTOU 攻击（因为令牌绑定的是特定的文件内容，且白名单在黑名单更新时会重置）。

关键技术组件

• 可重用混淆电路 (CRGC)： 为了解决大文件（如可执行文件）在混淆电路中嵌入成本过高的问题，作者将电路分为“可重用部分”和“不可重用部分”。可重用部分处理与文件大小线性相关的操作（如扫描），不可重用部分处理逻辑判断。这显著降低了通信和计算开销。
• 度量空间嵌入： 将文件哈希（如 TLSH, ssdeep）映射到有限域向量空间，定义了一种名为 对称非公共根 (Symmetric Uncommon Roots, SUR) 的距离度量，使得可以在不泄露原始向量的情况下计算汉明距离。
• 一次性成对不可预测排列 (One-time Pairwise Unpredictable Permutation)： 用于保护嵌入后的向量，防止恶意客户端通过猜测或碰撞来伪造令牌。

3. 主要贡献 (Key Contributions)

1. Half-Moon Cookie 原语定义： 形式化定义了一个支持显式检查和高效隐式检查的三方隐私黑名单协议，解决了 TOCTOU 攻击问题。
2. 高效的隐私保护实现：
   • 提出了基于可重用混淆电路的嵌入方案，将计算和通信成本与黑名单大小解耦，并大幅降低了大文件处理的开销。
   • 设计了基于SUR 距离度量的模糊 PSI 协议，支持在汉明空间进行隐私保护的相似性匹配。
3. 恶意软件防御应用实例： 将理论框架应用于基于相似性的恶意软件检测。
   • 发送方在分发前执行昂贵的隐私检查。
   • 接收方在运行前执行极快的隐式检查。
   • 实现了在不泄露发送方文件内容和不泄露服务器黑名单的前提下，有效识别恶意可执行文件。
4. 安全性证明： 在恶意发送方（试图绕过检查）和半诚实服务器（试图窃取文件信息）的威胁模型下，提供了形式化的安全性证明。

4. 实验结果 (Results)

作者在 C++ 中实现了该系统，并使用了 Enron 邮件数据集（附件）和 Ember 恶意软件数据集进行评估。

• 性能优化效果：
  • 使用可重用混淆电路 (RGC) 后，嵌入阶段（Embed-and-Map）的通信量减少了两个数量级以上（例如从 68MB 降至 60KB），响应时间减少了至少一个数量级（例如从 1000 秒降至 4.8 秒）。
  • 相比于传统的单体混淆电路，Half Moon 在平均 194KB 的邮件附件处理上，网络流量减少了 43,505 倍，延迟减少了 231 倍。
• 吞吐量与扩展性：
  • 在并发请求测试中，当黑名单大小 $|L|$ 增加时，系统吞吐量下降，但通过 RGC 优化，服务器负载与输入文件大小解耦。
  • 对于 10KB 的文件和 100 个黑名单条目，单客户端响应时间约为 19 秒；随着并发增加，系统能处理数百个并发请求。
• 隐式检查效率：
  • 隐式检查（$\Pi_{IC}$）的通信量仅为 7.2KB，响应时间为 0.19 秒。
  • 相比现有的模糊 PSI 方案（如 Chakraborti et al. 或 Blass & Noubir），隐式检查在响应时间上快了两个数量级，通信量快了三个数量级。
• 哈希函数选择： 实验比较了 TLSH、ssdeep 和 sdhash。由于 ssdeep 需要额外的编辑距离到汉明距离的转换，导致性能下降；TLSH 在整体性能上表现最佳，被选为默认哈希方案。

5. 意义与影响 (Significance)

1. 解决 TOCTOU 攻击的新范式： 提出了一个实用的框架，允许在隐私保护的前提下，将昂贵的安全检查前置，同时为接收方提供快速、安全的验证机制，有效填补了“检查”与“使用”之间的时间窗口漏洞。
2. 平衡隐私与性能： 通过巧妙结合可重用混淆电路和模糊 PSI，解决了传统隐私计算方案在处理大文件和大规模黑名单时性能不可用的问题，使其能够应用于实际的恶意软件检测场景。
3. 商业与合规价值： 该方案特别适用于需要保护专有软件（发送方）和专有威胁情报（服务器）的场景，如企业间的软件分发、云安全服务以及儿童色情内容（CSAM）检测等，能够在不泄露敏感数据的前提下满足合规要求。
4. 技术推动： 展示了如何通过电路分解和特定的密码学原语（如 SUR 距离）来优化安全多方计算（MPC）的实际部署，为未来的隐私保护安全系统提供了重要的设计参考。

总结：
Half-Moon Cookie 是一项将隐私保护、相似性匹配和 TOCTOU 防御相结合的创新工作。它通过“显式检查生成令牌，隐式检查验证令牌”的机制，成功地在保护双方隐私的同时，实现了高效、安全的恶意内容检测，为构建下一代隐私友好的安全基础设施奠定了坚实基础。