利用LLVM的optnone优化Rust加密代码实现

重温恒定时间

恒定时间加密算法无论输入如何，总是在相同时间内执行。并非所有操作都需要在相同时间内执行，但时间变化绝不能依赖于秘密数据。否则，攻击者可能推断出秘密数据。然而，在编译恒定时间加密代码时保持秘密数据的机密性可能很困难。编译器需要保留程序的“可观察行为”，但由于它没有时间概念（除了专用编译器），它也可以自由更改代码的恒定时间属性。

在实践中，为了防止编译器更改精心实现的恒定时间代码，我们必须对编译器撒谎。我们必须告诉它我们知道代码的一些事情，而它无法知道——我们将以它无法看到的方式读取或写入内存，类似于多线程代码。我们将探索的选项是告诉编译器不要使用所有技能来生成高效代码。

我们将从第1部分的示例开始：一个选择函数，根据choice参数选择参数a或b。以下是不考虑恒定时间执行的版本。

1
2
3
4

#[inline(never)]
fn conditional_select(a: u32, b: u32, choice: bool) -> u32 {
    if choice { a } else { b }
}

通过添加#[inline(never)]属性，更容易看到更改的效果。首先，让我们编译代码并从中生成LLVM-IR。

1

rustc --emit llvm-ir,link -C opt-level=0 test.rs

由此生成一个test.ll文件，我们将在其中找到conditional_select的IR。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

; Function Attrs: noinline uwtable
define internal i32 @_ZN4test18conditional_select17h01ca56cd2cc74a72E(i32 %a, i32 %b, i1 zeroext %choice) unnamed_addr #1 {
start:
  %0 = alloca i32, align 4
  br i1 %choice, label %bb1, label %bb2

bb2:                                              ; preds = %start
  store i32 %b, i32* %0, align 4
  br label %bb3

bb1:                                              ; preds = %start
  store i32 %a, i32* %0, align 4
  br label %bb3

bb3:                                              ; preds = %bb2, %bb1
  %1 = load i32, i32* %0, align 4
  ret i32 %1
}

我们可以看到有一个依赖于choice变量的分支。我们需要避免分支以保持choice值的秘密信息。现在让我们以移除分支的方式重新实现该函数。

恒定时间实现

1
2
3
4
5

#[inline(never)]
fn conditional_select(a: u32, b: u32, choice: bool) -> u32 {
    let mask = -(choice as i32) as u32;
    b ^ (mask & (a ^ b))
}

根据Rust的文档，“bool代表一个值，只能是true或false。如果将bool转换为整数，true将为1，false将为0。”这里，我们使用这个属性，将我们的bool转换为整数。

变量mask现在将是0xffffff或0，取决于choice是true还是false。

xor和and操作将确保返回值在choice为true时为a，在choice为false时为b。

完美！让我们看看我们是否能够生成没有分支的代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

define internal i32 @_ZN4test18conditional_select17h01ca56cd2cc74a72E(i32 %a, i32 %b, i1 zeroext %choice) unnamed_addr #1 {
start:
  %0 = icmp ule i1 %choice, true
  call void @llvm.assume(i1 %0)
  %_6 = zext i1 %choice to i32
  %_8 = icmp eq i32 %_6, -2147483648
  %1 = call i1 @llvm.expect.i1(i1 %_8, i1 false)
  br i1 %1, label %panic, label %bb1

bb1:                                              ; preds = %start
  %_5 = sub i32 0, %_6
  %_12 = xor i32 %a, %b
  %_10 = and i32 %_5, %_12
  %2 = xor i32 %b, %_10
  ret i32 %2

panic:                                            ; preds = %start
; call core::panicking::panic
  call void @_ZN4core9panicking5panic17h7dfe23182f4d1104E([0 x i8]* 
nonnull align 1 bitcast ([31 x i8]* @str.4 to [0 x i8]*), i64 31, %
"core::panic::location::Location"* align 8 dereferenceable(24) bitcast 
(<{ i8*, [16 x i8] }>* @alloc56 to %"core::panic::location::Location"*)) 
#9
  unreachable
}

哎呀！发生了什么？核心操作中的分支被移除了（见bb1）。这是一个成功，但这里还有更多事情发生。现在有一个条件分支到panic，取决于choice的值。这个条件分支是由rustc在调试构建中添加的，用于检测有符号整数溢出。在生产构建中，不会发出有符号整数溢出检查，分支也不会存在。

然而，一个令人担忧的细节是有一个对@llvm.assume的调用，它依赖于choice的值。根据LLVM的文档，“该内在函数允许优化器假设每当控制流到达内在函数调用时，提供的条件始终为真。不为该内在函数生成代码，并且仅对提供条件有贡献的指令不用于代码生成。如果在执行过程中违反条件，行为是未定义的。”

代码生成可能受到choice值的影响。在更仔细地检查条件时，条件断言choice的值范围被假定为[0,1]。真让人松了一口气！没有泄漏秘密信息，因为它只揭示了choice的范围（已经知道的信息），而不是其具体值。

似乎我们已经达到了目标。让我们确保在优化构建中一切仍然正常。

1

rustc --emit llvm-ir,link -C opt-level=3 test.rs

1
2
3
4
5
6
7

define internal fastcc i32 
@_ZN4test18conditional_select17h01ca56cd2cc74a72E(i32 %a, i32 %b, i1 
zeroext %choice) unnamed_addr #5 {
start:
  %0 = select i1 %choice, i32 %a, i32 %b
  ret i32 %0
}

根据目标架构，编译器可能将select语句降低为不同的指令。在x86上，它可能被降低为cmov指令，而在其他架构上，它成为条件分支。更糟糕的是，如果你编译我们开始的非恒定时间版本，你会得到完全相同的IR。所有的工作都白费了！

我们可以看到，只要代码没有启用优化，最终结果就是我们期望的。另一方面，启用优化可能会破坏代码的恒定时间属性。这引出了一个问题：我们能否影响编译器不优化conditional_select函数？Cargo和rustc接受全局禁用优化的参数，但通常不可能在整个系统上这样做。一个可能的解决方案是防止对特定函数进行优化。（这以前曾被建议作为改善情况的一种方式。）

对抗帮助编译器

既然我们在调试构建中有了所需的IR代码，让我们探索如何使用LLVM属性optnone在函数级别禁用优化。LLVM文档指出：“此函数属性指示大多数优化过程将跳过此函数，除了过程间优化过程。代码生成默认为’快速’指令选择器。此属性不能与alwaysinline属性一起使用；此属性也与minsize属性和optsize属性不兼容。此属性要求函数也指定noinline属性，因此函数永远不会内联到任何调用者中。只有具有alwaysinline属性的函数才是内联到此函数体内的有效候选者。”

我们的下一个目标是用optnone属性标记conditional_select函数。根据文档，该函数还需要noinline属性。碰巧的是，我们已经用#[inline(never)]标记了该函数。

我们将在Rust中实现一个属性，当编译时，它将为函数生成optnone和noinline属性。

构建Rust编译器

要构建和运行Rust编译器，请参考本指南。从现在开始，我们将假设用于编译的命令是rustc +stage1。要验证是否使用了自定义编译器，请使用额外的-vV标志调用它。你应该看到类似于以下的输出：

1
2
3
4
5
6
7

rustc 1.57.0-dev
binary: rustc
commit-hash: unknown
commit-date: unknown
host: x86_64-apple-darwin
release: 1.57.0-dev
LLVM version: 13.0.0

注意-dev版本字符串，表示自定义构建。

实现optnone属性

在这方面已经做了一些工作；Rust优化属性已经实现，以优化程序的速度或大小。我们的目标是为优化属性实现一个“never”选项。目标是像这样编写conditional_select。（关于命名“never”属性的讨论。命名很重要，但为了我们的目的，我们不需要关注它。）

1
2
3
4
5

#[optimize(never)]
fn conditional_select(a: u32, b: u32, choice: bool) -> u32 {
    let mask = -(choice as i32) as u32;
    b ^ (mask & (a ^ b))
}

在非优化构建中用属性注释函数将没有效果。在优化构建中，它将确保优化器不接触该函数。

要实现这样的选项，第一步是使用Never成员扩展OptimizeAttr属性。我们将使用此值作为信息载体，从解析到代码生成。

1
2
3
4
5
6
7

#[derive(Clone, Encodable, Decodable, Debug, HashStable_Generic)]
pub enum OptimizeAttr {
    None,
    Never,
    Speed,
    Size,
}

当在优化属性中找到符号never时，我们应该将以下行添加到codegen_fn_attr中，以发出先前添加的OptimizeAttr::Never成员：

1
2

} else if list_contains_name(&items[..], sym::never) {
                    OptimizeAttr::Never

此时，我们可以在Rust编译器内部用OptimizeAttr::Never注释函数。剩下的工作是确保它也被应用到LLVM IR。

为此，我们将以下内容添加到from_fn_attrs中。当rustc发现带有#[optimize(never)]属性的函数时，此代码实际上用所需属性标记LLVM函数。

1
2
3
4
5
6
7

OptimizeAttr::Never => {
            llvm::Attribute::MinSize.unapply_llfn(Function, llfn);
            llvm::Attribute::OptimizeForSize.unapply_llfn(Function, llfn);
            llvm::Attribute::OptimizeNone.apply_llfn(Function, llfn);
            llvm::Attribute::NoInline.apply_llfn(Function, llfn); 
// noopt requires noinline
        }

现在，我们可以从#[optimize(never)] Rust属性向LLVM IR添加optnone和noinline属性。但是，还有一些簿记工作要做。

我们需要更新功能门以包含有关优化属性中never选项的信息。

1
2
3
4
5
6

// RFC 2412
    gated!(
        optimize, Normal, template!(List: "size|speed|never"), 
optimize_attribute,
        experimental!(optimize),
    ),

我们可以构建一个stage1编译器来测试我们的更改。

1
2

./x.py build -i library/std
rustup toolchain link stage1 build/x86_64-apple-darwin/stage1

结果

最后，我们准备好测试新属性。让我们用#[optimize(never)]属性标记conditional_select函数，并为opt-level=3编译。要启用优化属性，我们将#![feature(optimize_attribute)]添加到test.rs文件中。

1

rustc +stage1 --emit llvm-ir,link -C opt-level=3 test.rs

1
2
3
4
5

#[optimize(never)]
fn conditional_select(a: u32, b: u32, choice: bool) -> u32 {
    let mask = -(choice as i32) as u32;
    b ^ (mask & (a ^ b))
}

你会发现相应的IR现在是：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

; test::conditional_select
; Function Attrs: noinline optnone uwtable
define internal fastcc i32 @_ZN4test18conditional_select17h01ca56cd2cc74a72E(i32 %a, i32 %b, i1 zeroext %choice) unnamed_addr #5 {
start:
  %0 = icmp ule i1 %choice, true
  call void @llvm.assume(i1 %0)
  %_6 = zext i1 %choice to i32
  %_5 = sub i32 0, %_6
  %_11 = xor i32 %a, %b
  %_9 = and i32 %_5, %_11
  %1 = xor i32 %b, %_9
  ret i32 %1
}

成功！optnone和noinline属性正在使用中，IR指令符合预期。我们现在完成了吗？只需创建拉取请求并合并？等等！在这样做之前，我们当然应该实现测试（感兴趣的读者可以在这里找到它们）。

但我们现在将暂时搁置这一点。相反，让我们转向我们刚刚完成的另一个方面：代码生成的指令选择阶段。

总有一个“但是”

似乎我们取得了巨大进展，甚至解决了生成恒定时间代码的问题。这在一定程度上是正确的，但就像密码学（和编译器）中常见的情况一样，事情并不那么简单。尽管我们阻止了优化器重写函数，但在代码生成过程中仍然有一个指令选择阶段。在此阶段，编译器后端选择它认为合适的任何目标指令。这是我们简要讨论过的一个方面。我们隐含地假设LLVM IR中的指令，如xor，将成为目标指令集中的等效指令，如x86 xor指令。虽然IR xor指令很可能在目标架构中实现为xor，但不能保证它会。代码生成也可能随着时间的推移而发展，曾经成为特定指令的内容可能会随着编译器版本的不同而改变。

更糟糕的是，机器代码生成过程中存在优化。x86的一个例子是X86CmovConverterPass，它会在某些情况下将cmov转换为条件分支。这基本上将恒定时间操作（cmov）转换为非恒定时间条件分支，这可能重新启用基于时间的侧信道攻击。

这还不止于此。一旦我们达到实际的特定目标操作，仍然可能存在数据依赖的时间，例如在AMD上执行div：“硬件整数除法单元的典型延迟为8个周期，加上商每9位1个周期。除法器允许两个连续独立除法操作之间有限的重叠。‘典型’的64位除法允许每8个周期一个除法的吞吐量（实际吞吐量取决于数据）。”

总结

当用高级语言（如Rust）编写时，恒定时间执行代码的主张变得薄弱。对于像C和C++这样的语言也是如此。有太多我们无法控制的因素。

这是否意味着一切都失去了？是否每个不是用特定目标汇编语言编写的加密实现都被破坏了？可能不是，但这些实现必须依赖于技巧和对合理代码生成的希望。

几乎总是存在权衡，就像在许多领域中一样——大小与速度，上市时间与质量等。在用内存安全、现代语言和强大的分析工具可用的情况下实现加密有很大的好处。然而，手写的、特定目标的汇编语言可以做出更强的恒定时间属性主张，缺点是可能引入内存安全问题。

为了能够对用Rust编写的代码做出这样的主张，需要编译器的强大支持，从前端一直到后端的目标机器代码生成。我们可能需要恒定时间成为编译器意识到的属性，以便它保留它。这是一项重大任务，并且有几个正在进行的讨论和建议来实现这一目标。

目前，我们必须依赖我们所拥有的。一个小的进步可能是合并never优化选项来帮助。

如果你喜欢这篇文章，请分享： Twitter LinkedIn GitHub Mastodon Hacker News

页面内容 让我们实现加密！ 重温恒定时间 恒定时间实现 对抗帮助编译器 构建Rust编译器 实现optnone属性 结果 总有一个“但是” 总结 最近的帖子 构建安全消息传递很难：关于Bitchat安全辩论的细致看法 用Deptective调查你的依赖关系 系好安全带，Buttercup，AIxCC的评分回合正在进行中！ 使你的智能合约超越私钥风险 Go解析器中意外的安全陷阱 © 2025 Trail of Bits。 使用Hugo和Mainroad主题生成。