利用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编译。要启用优化属性，我们向test.rs文件添加#![feature(optimize_attribute)]。

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