为LLVM引入恒定时间支持以保护加密代码

Trail of Bits为LLVM编译器开发了恒定时间编码支持，引入了__builtin_ct_select等内建函数，防止编译器优化破坏加密代码的时序安全，从而抵御基于分支的计时侧信道攻击。

引言

Trail of Bits 已为 LLVM 开发了恒定时间编码支持，为开发者提供编译器级别的保证，确保他们的加密实现免受与分支相关的计时攻击的影响。这些修改正在接受审查，并将添加到即将发布的 LLVM 22 中。这项工作引入了 __builtin_ct_select 系列内建函数及配套基础设施，防止 Clang 编译器（以及可能使用 LLVM 构建的其他编译器）无意中破坏精心编写的恒定时间代码。本文将引导您了解我们构建了什么、它是如何工作的以及它支持什么。我们还将讨论扩展此项工作的一些未来计划。

编译器优化问题

现代编译器擅长使代码运行得更快。它们消除冗余操作、矢量化循环并巧妙地重组算法以榨取每一分性能。但在处理加密代码时，这种优化热情就变成了一个缺点。

考虑以下来自 Sprenkels (2019) 的看似无害的恒定时间查找：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

uint64_t constant_time_lookup(const size_t secret_idx,
  const uint64_t table[16]) {
    uint64_t result = 0;
    for (size_t i = 0; i < 8; i++) {
        const bool cond = i == secret_idx;
        const uint64_t mask = (-(int64_t)cond);
        result |= table[i] & mask;
    }
    return result;
}

这段代码精心避免了基于秘密索引的分支。无论秘密值如何，每次迭代都执行相同的操作。然而，由于编译器旨在提高代码速度，它们会看到一个优化这段精心编写代码的机会，将其优化为包含分支的版本。

问题在于，编译后代码中的任何数据依赖行为都会产生计时侧信道。如果编译器引入类似 if (i == secret_idx) 的分支，CPU 将根据是否执行分支而花费不同的时间。现代 CPU 具有分支预测器，可以学习模式，使得正确预测的分支比错误预测的分支更快。攻击者如果能够在多次执行中测量这些计时差异，就可以统计地确定正在访问哪个索引，从而有效地恢复秘密。即使是几个 CPU 周期的小小计时变化，只要有足够的测量，也可以被利用。

我们构建了什么

我们的解决方案为密码学开发者提供了明确的内建函数，在整个编译管道中保持恒定时间属性。核心添加是 __builtin_ct_select 系列内建函数：

1
2

// 恒定时间条件选择
result = __builtin_ct_select(condition, value_if_true, value_if_false);

该内建函数保证无论优化级别如何，上述选择操作都将编译为恒定时间的机器码。当您在 C/C++ 代码中编写此函数时，编译器会将其转换为特殊的 LLVM 中间表示内建函数 (llvm.ct.select.*)，该函数具有语义含义：“此操作必须保持恒定时间。”

与优化器可以自由重新排列和转换的常规代码不同，该内建函数充当了一个屏障。优化器将其识别为安全关键操作，并在从源代码到汇编的每个编译阶段都保持其恒定时间属性。

实际影响

在最近的研究“Breaking Bad: How Compilers Break Constant-Time Implementations”中，Srdjan Čapkun 和他的研究生 Moritz Schneider 与 Nicolas Dutly 发现，编译器破坏了许多生产级密码库中的恒定时间保证。他们对五个编译器中的 19 个库进行的分析揭示了编译过程中引入的系统性漏洞。

使用我们的内建函数，有问题的查找函数变为以下恒定时间版本：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

uint64_t
constant_time_lookup(const size_t secret_idx,
                     const uint64_t table[16]) {
  uint64_t result = 0;

  for (size_t i = 0; i < 8; i++) {
    const bool cond = i == secret_idx;
    result |= __builtin_ct_select(cond, table[i], 0u);
  }
  return result;
}

内建函数的使用可以防止编译器对其进行任何修改，从而确保选择保持恒定时间。没有优化传递会将其转换为易受攻击的内存访问模式。

社区参与与采用

要将这些修改引入上游，需要大量的社区参与。我们于 2025 年 8 月在 LLVM Discourse 论坛上发布了我们的 RFC。

该 RFC 收到了来自编译器和密码学社区的大量反馈。来自 Rust Crypto、BearSSL 和 PuTTY 的开源维护者对采用这些内建函数来替换他们当前的内联汇编变通方案表现出浓厚兴趣，同时为实施方法和未来原语提供了宝贵的反馈。LLVM 开发人员帮助确保这些内建函数与自动矢量化和其他优化传递正常工作，同时还提供了特定于架构的实施指导。

基于现有工作

我们的方法综合了先前多项工作的经验教训：

  • Simon 和 Chisnall 的 __builtin_ct_choose (2018)：这项工作为保持恒定时间属性的编译器内建函数提供了概念基础，但从未被引入上游。
  • Jasmin (2017)：这项工作展示了编译器感知的恒定时间原语的价值，但需要一种新的语言。
  • Rust 的 #[optimize(never)] 实验：这些实验突显了对细粒度优化控制的需求。

跨架构工作原理

我们的实施确保 __builtin_ct_select 在每个平台上都能编译为恒定时间代码：

  • x86-64：该内建函数直接编译为 cmov（条件移动）指令，无论条件值如何，该指令始终以恒定时间执行。
  • i386：由于 i386 缺乏 cmov，我们使用带位运算的掩码算术模式来实现恒定时间选择。
  • ARM 和 AArch64：对于 AArch64，该内建函数被降级为 CSEL 指令，该指令提供恒定时间执行。对于 ARM，由于 ARMv7 没有像 AAarch64 那样的恒定时间指令，因此实施会使用位运算生成掩码算术模式。
  • 其他架构：通用后备实施使用位运算来确保恒定时间执行，即使在我们尚未原生支持的平台上也是如此。

每个架构都需要不同的指令来实现恒定时间行为。我们的实施透明地处理这些差异，因此开发者可以编写可移植的恒定时间代码，而无需担心特定于平台的细节。

基准测试结果

我们在苏黎世联邦理工学院 (ETH Zürich) 的合作伙伴正在使用他们来自“Breaking Bad”研究的测试套件进行全面基准测试。初步结果显示：

  • 大多数加密操作的开销最小。
  • 在所有测试的优化级别上，100% 保持恒定时间属性。
  • 成功集成到包括 HACL*、Fiat-Crypto 和 BoringSSL 在内的主要密码库中。

后续计划

虽然 __builtin_ct_select 解决了最迫切的需求，但我们的 RFC 概述了其他内建函数的路线图：

恒定时间操作

我们未来计划扩展恒定时间实现，特别是针对算术或字符串操作以及强制表达式无分支求值。

1
2

_builtin_ct<op> // 用于恒定时间算术或字符串操作
__builtin_ct_expr(expression)  // 强制整个表达式无分支求值

其他语言的采用路径

我们 LLVM 实施的模块化特性意味着任何以 LLVM 为目标的语言都可以利用这项工作：

  • Rust：Rust 编译器团队正在探索如何通过其 core::intrinsics 模块公开这些内建函数，并可能在标准库中提供安全的封装器。
  • Swift：Apple 的安全团队已表示有兴趣在其加密框架中采用这些原语。
  • WebAssembly：这些内建函数对于基于浏览器的加密尤其有用，尽管有沙盒保护，计时攻击仍然是一个隐患。

致谢

这项工作是与苏黎世联邦理工学院 (ETH Zürich) 的系统安全小组合作完成的。特别感谢 Laurent Simon 和 David Chisnall 在恒定时间编译器支持方面的开创性工作，以及 LLVM 社区在 RFC 过程中提供的建设性反馈。

我们特别感谢 Trail of Bits 密码学团队的技术审查。

资源

本博客文章中提及的工作由 Trail of Bits 根据 DARPA 合同号 N66001-21-C-4027（分发声明 A，批准公开发布：分发无限制）支持的工作进行。本材料中表达的任何意见、发现和结论或建议均为作者的意见，不一定代表美国政府或 DARPA 的观点。

comments powered by Disqus
© 2020 - 2026 qife
使用 Hugo 构建
主题 Stack 由 Jimmy 设计
本站总访问量次 本站访客数人次