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

重温恒定时间概念

恒定时间加密算法无论输入如何，总是在相同时间内执行完成。虽然并非所有操作都需要相同执行时间，但时间变化绝不能依赖于秘密数据。否则，攻击者可能推断出秘密信息。然而，在编译恒定时间加密代码时保持秘密数据的安全性颇具挑战性。

编译器需要保留程序的"可观察行为"，但由于它没有时间概念（除特殊编译器外），它可以自由改变代码的恒定时间特性。

实践中，为了防止编译器改变精心实现的恒定时间代码，我们必须对编译器"说谎"。我们需要告诉它我们知道代码的某些特性——就像多线程代码那样，我们会以编译器无法察觉的方式读写内存。我们将探索的选项是告诉编译器不要使用所有优化技巧来生成高效代码。

恒定时间实现

我们从第一部分中的示例开始：一个选择函数，根据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

生成的IR显示存在依赖于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。异或和与操作将确保返回值在choice为true时为a，为false时为b。

对抗编译器优化

现在我们有了调试版本中期望的IR代码，让我们探索如何使用LLVM属性optnone在函数级别禁用优化。LLVM文档说明：

“此函数属性指示大多数优化过程将跳过此函数，除了过程间优化过程。代码生成默认为’快速’指令选择器。此属性不能与alwaysinline属性一起使用；此属性也与minsize属性和optsize属性不兼容。”

“此属性要求函数也指定noinline属性，因此函数永远不会内联到任何调用者中。只有具有alwaysinline属性的函数才是内联到此函数体中的有效候选者。”

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

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

构建Rust编译器

要构建和运行Rust编译器，请参考相关指南。从现在开始，我们假设用于编译的命令是rustc +stage1。要验证是否使用了自定义编译器，请使用额外的-vV标志调用它。

实现optnone属性

在这方面已经有工作完成；Rust优化属性已经实现，可以优化程序的速度或大小。我们的目标是为optimize属性实现"never"选项。

目标是像这样编写conditional_select函数：

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属性。我们将使用此值作为信息载体，从解析到代码生成。

当在optimize属性中找到符号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

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需要noinline
}

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

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

结果

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

你会发现相应的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优化选项来提供帮助。