优化屏障的生命周期 - 第1部分
许多工程师选择Rust作为实现密码学协议的首选语言，因为它提供强大的安全保证。尽管Rust使安全的密码学工程更容易，但仍需注意一些挑战。其中之一是需要保持恒定时间属性，确保无论输入如何，代码始终在相同时间内运行。这些属性对于防止定时攻击很重要，但可能被编译器优化破坏。
最近，一个客户询问我们：使用wasm-pack将库打包为npm模块，然后通过node运行，这会如何影响Rust实现的恒定时间加密代码？编写恒定时间代码始终是与优化器的斗争，但在此情况下，代码在执行前会被优化两次：首先由LLVM，然后由Turbofan JIT编译器。这会如何影响库使用的恒定时间加密代码？
我们运行了一些小型测试案例，探索双重优化代码库如何影响代码的恒定时间属性。本文将重点介绍实现恒定时间Rust代码的挑战，并展示LLVM在将恒定时间代码编译到WebAssembly（Wasm）时可能引入新的侧信道。在第2部分中，我们将探讨是否可以为需要恒定时间执行的安全关键代码选择性禁用优化。
什么是恒定时间？
密码学很难正确实现。无论您是在实现高级协议还是低级密码原语，这都是事实。除了担心整体正确性和可能以意外方式暴露秘密的边缘情况外，潜在的侧信道泄漏和定时攻击也是深层次关注点。
定时攻击试图利用应用程序的执行时间可能微妙地依赖于输入这一事实。如果应用程序基于秘密数据（如随机数生成器的种子或私钥）做出与控制流相关的决策，这可能会轻微影响应用程序的执行时间。同样，如果使用秘密数据确定从内存中的哪个位置读取，这可能导致缓存未命中，进而影响应用程序的执行时间。在这两种情况下，关于秘密数据的信息通过程序执行期间的时序差异泄漏。
为防止此类时序差异，密码学工程师通常避免基于秘密数据实现决策。然而，在代码需要基于秘密数据做出决策的情况下，有一些巧妙的方法以恒定时间实现它们，即无论输入如何，始终在相同时间内执行。例如，考虑以下在Rust中执行变量a和b之间条件选择的函数。
1
2
3
4
|
#[inline]
fn conditional_select(a: u32, b: u32, choice: bool) -> u32 {
if choice { a } else { b }
}
|
如果choice为true，函数返回a，否则返回b。根据编译器工具链和目标指令集，编译器可以选择使用分支指令（如x86上的jne或ARM上的bne）实现条件选择。这将在函数执行中引入时序差异，可能泄漏关于choice变量的信息。以下Rust实现使用一个巧妙技巧在恒定时间内执行相同的条件选择。
1
2
3
4
5
6
7
|
#[inline]
fn conditional_select(a: u32, b: u32, choice: u8) -> u32 {
// if choice = 0, mask = (-0) = 0000...0000
// if choice = 1, mask = (-1) = 1111...1111
let mask = -(choice as i32) as u32;
b ^ (mask & (a ^ b))
}
|
这里，我们不基于choice秘密值做出选择，这意味着函数只有一条路径。因此，执行时间将始终相同。
与编译器斗争
理想情况下，这应该是故事的结束，但在实践中，这种方法存在固有风险。由于编译器没有时间概念，它不将时序差异视为可观察行为。这意味着它可以自由重写和优化恒定时间代码，这可能向程序中引入新的时序泄漏。像上面这样精心编写的恒定时间实现仍可能被编译器优化为分支指令，从而泄漏choice的值！
这感觉像是一个不可能的情况。如果真是这样，编译器实际上在破坏我们精心制作的conditional_select恒定时间实现。那么，我们能做什么来阻止编译器优化函数并可能破坏代码的恒定时间属性？
最明显的解决方案是核选项——关闭所有优化，使用-C opt-level=0标志编译整个代码库。然而，这几乎总是一个不可行的解决方案。密码代码通常处理大量数据，这意味着它需要从编译器获得所有可能的优化。一个更有吸引力的解决方案是尝试使用所谓的优化屏障阻止编译器优化敏感代码路径。subtle crate使用以下构造尝试阻止LLVM优化恒定时间代码路径。
1
2
3
4
|
#[inline(never)]
fn black_box(input: u8) -> u8 {
unsafe { core::ptr::read_volatile(&input as *const u8) }
}
|
这里，对core::ptr::read_volatile的调用告诉编译器&input处的内存是易变的，它不能对其做任何假设。此调用作为优化屏障，阻止LLVM“看穿黑盒”并意识到输入实际上是一个布尔值。这反过来防止编译器将输出的布尔操作重写为条件语句，这可能泄漏关于输入的时序信息。Rust核心库文档对core::ptr::read_volatile有以下说明：
“Rust目前没有严格和正式定义的内存模型，因此这里‘volatile’的精确语义可能随时间变化。也就是说，语义几乎总是最终与C11的volatile定义非常相似。”
这似乎不太令人放心，但请记住，编译器不将时序差异视为可观察的，因此编译器总是可以自由重写恒定时间代码并引入新的侧信道泄漏。任何阻止编译器这样做的尝试都必然是基于最大努力的，直到有内置的语言和编译器支持秘密类型。（有一个Rust RFC引入秘密类型，但已被推迟，等待LLVM支持。）
让我们看看如果没有优化屏障编译conditional_select函数会发生什么。为了更好地说明这一点，我们将目标设定为没有像cmov（如x86_64和aarch64）这样的条件指令的指令集，这允许编译器优化函数而不破坏实现的恒定时间属性。以下函数简单地调用恒定时间版本的conditional_select返回a或b。
1
2
3
4
|
pub fn test_without_barrier(a: u32, b: u32, choice: bool) -> u32 {
let choice = choice as u8;
conditional_select(a, b, choice)
}
|
通过为ARM Cortex M0+（用于Raspberry Pi Pico）编译函数，我们得到以下反编译输出。
我们看到编译器用简单的基于choice值（在r2中）的分支替换了我们精心制作的条件选择，完全破坏了函数的恒定时间属性！现在，让我们看看如果插入优化屏障会发生什么。
1
2
3
4
|
pub fn test_with_barrier(a: u32, b: u32, choice: bool) -> u32 {
let choice = black_box(choice as u8);
conditional_select(a, b, choice)
}
|
查看相应的反汇编，我们看到它由单个基本块组成，导致通过函数的单一路径，独立于choice的值。这意味着我们可以合理确定函数将始终在恒定时间内运行。
那么Wasm呢？
现在，让我们回到原始问题。我们的客户运行从Rust编译到Wasm并使用node的代码。这意味着库首先使用LLVM编译到Wasm，然后由node使用Turbofan JIT编译器再次编译。我们期望LLVM尊重像subtle crate这样的库插入的优化防护，但Turbofan呢？
为了查看代码库将如何受到影响，我们使用wasm-bindgen和wasm-pack编译了上面定义的test_with_barrier函数。然后，我们转储了Turbofan JIT生成的代码，并检查输出以查看优化屏障是否保留以及实现的恒定时间属性是否保持。
以下代码是使用wasm-pack编译我们的示例并使用wasm2wat以文本格式转储结果Wasm的结果。（我们注释了一些函数并删除了与wasm-bindgen相关的一些部分以使代码更可读。）
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
(module
(type (;0;) (func (param i32) (result i32)))
(type (;1;) (func (param i32 i32 i32) (result i32)))
(func $black_box (type 0) (param $input i32) (result i32)
(local $__frame_pointer i32)
global.get $__stack_pointer
i32.const 16
i32.sub
local.tee $__frame_pointer ;; push __stack_pointer - 16
local.get $input
i32.store8 offset=15 ;; store input at __stack_pointer - 1
local.get 1
i32.load8_u offset=15) ;; load output from __stack_pointer - 1
(func $test_without_barrier (type 1)
(param $a i32) (param $b i32) (param $choice i32) (result i32)
local.get $a
local.get $b
local.get $choice
select)
(func $test_with_barrier (type 1)
(param $a i32) (param $b i32) (param $choice i32) (result i32)
local.get $b
local.get $a
i32.xor ;; push a ^ b
i32.const 0
local.get $choice
i32.const 0
i32.ne ;; push input = choice != 0
call $black_box ;; push output = black_box(input)
i32.const 255
i32.and ;; push output = output & 0xFF
i32.sub ;; push mask = 0 - output
i32.and ;; push mask & (a ^ b)
local.get $b
i32.xor) ;; push b ^ (mask & (a ^ b))
(table (;0;) 1 1 funcref)
(memory (;0;) 17)
(global $__stack_pointer (mut i32) (i32.const 1048576))
(export "memory" (memory 0))
(export "test_without_barrier" (func $test_without_barrier))
(export "test_with_barrier" (func $test_with_barrier)))
|
我们看到black_box已被编译为简单的i32.store8，后跟从相同偏移量的（无符号）i32.load8_u。这最初看起来可能被完全优化掉，因为内存从未在black_box之外读取。
我们还看到test_with_barrier没有在调用black_box时进行优化。函数仍然执行由优化屏障输出控制的无分支条件选择。这看起来很好，并给我们一些信心，当目标为Wasm时，subtle crate提供的恒定时间属性得以保留。然而，一旦Wasm模块被node加载，它就会被传递给Liftoff和Turbofan JIT编译器以进一步优化代码。
为了调查这如何影响我们的小示例，我们使用JavaScript加载编译的Wasm模块，并使用node转储Turbofan的跟踪输出。这可以通过向node运行时传递–trace-turbo标志来完成。然后，可以在Turbolizer web GUI（可以在V8存储库中找到）中查看node生成的跟踪。
Turbolizer可用于分析Turbofan编译管道的每个步骤。这里，我们感兴趣的是显示给定函数的发出汇编代码的样子。查看test_with_barrier的输出，我们看到在第2c行没有跨black_box函数调用执行优化。输出基本上与上面的反编译Wasm代码相同。
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
26
27
28
29
30
31
32
33
34
35
36
37
|
B0:
0 push rbp
1 REX.W movq rbp,rsp
4 push 0x8
6 push rsi
7 REX.W subq rsp,0x18
b REX.W movq rbx,[rsi+0x2f]
f REX.W movq [rbp-0x18],rdx
13 REX.W movq [rbp-0x20],rax
17 REX.W cmpq rsp,[rbx]
1a jna B2 <+0x4a>
B1:
20 cmpl rcx,0x0 ;; rax = choice? 1: 0
23 setnzl bl
26 movzxbl rbx,rbx
29 REX.W movq rax,rbx
2c call 0x7ffc2400fa31 ;; call to black_box(rax)
31 movzxbl rbx,rax ;; rbx = -black_box(rax)
34 negl rbx
36 REX.W movq rdx,[rbp-0x20] ;; rdx = a ^ b
3a xorl rdx,[rbp-0x18]
3d andl rbx,rdx ;; rbx = rbx & rdx
3f REX.W movq rax,[rbp-0x18] ;; rax = b ^ (rbx & (a ^ b))
43 xorl rax,rbx
45 REX.W movq rsp,rbp
48 pop rbp
49 retl ;; return rax
B2:
4a REX.W movq [rbp-0x28],rcx
4e call 0x7ffc2400fa7b
53 REX.W movq rsi,[rbp-0x10]
57 REX.W movq rcx,[rbp-0x28]
5b jmp B1 <+0x20>
5d nop
5e nop
|
查看black_box的Turbolizer输出也很有趣。查看black_box的发出汇编，我们看到除了设置本地堆栈帧外，函数简单地存储然后立即从内存加载输入（第14和18行）然后返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
B0:
0 push rbp
1 REX.W movq rbp,rsp
4 push 0x8
6 push rsi
7 REX.W movq rbx,[rsi+0x17]
b REX.W movq rdx,[rsi+0x67]
f movl rdx,[rdx]
11 subl rdx,0x10
14 movb [rdx+rbx*1+0xf],al ;; store input to memory
18 movzxbl rax,[rdx+rbx*1+0xf] ;; load output from memory
1d REX.W movq rsp,rbp
20 pop rbp
21 retl
|
您可能会惊讶此函数没有被Turbofan内联或优化掉。由于Wasm中没有与Rust中的volatile读取对应的内容，Turbofan真的没有理由再保留black_box。然而，由于black_box写入内存，它并非完全无副作用，因此不能被JIT编译器完全优化掉。
引入新的侧信道
编译版本的black_box在返回之前将输入写入内存这一事实实际上有些令人惊讶。由于black_box接受一个值作为输入，而read_volatile接受一个引用作为输入，LLVM需要以某种方式将输入值转换为引用。当为像x86或ARM这样的架构编译时，LLVM可以简单地使用堆栈上输入的地址，但Wasm堆栈不能以这种方式寻址，这意味着LLVM必须将输入写入内存才能引用它。所有这一切意味着我们想要使用优化屏障保护的秘密值被LLVM泄漏到Wasm内存。此外，查看上面编译的Wasm代码，我们看到此内存由Wasm模块导出，这意味着可以从JavaScript读取。如果我们调用导出的test_with_barrier函数并在调用前后检查内存，我们可以看到传递给black_box的秘密值现在可以从JavaScript访问。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
const path = require('path').join(__dirname, 'ct_wasm.wasm');
const bytes = require('fs').readFileSync(path);
// Load Wasm module from file.
const wasmModule = new WebAssembly.Module(bytes);
const wasmInstance = new WebAssembly.Instance(wasmModule);
const wasmMemory = new Uint8Array(wasmInstance.exports.memory.buffer);
const testWithBarrier = wasmInstance.exports.test_with_barrier;
// __stack_pointer defined by the Wasm module.
const stackPointer = 1048576;
// Print memory[__frame_pointer + 15] before call to black_box.
const before = wasmMemory[stackPointer - 1];
console.log("Before the call to black_box: " + before);
// Call test_with_barrier which calls black_box with secret value 1.
testWithBarrier(123, 456, 1);
// Print memory[__frame_pointer + 15] after call to black_box.
const after = wasmMemory[stackPointer - 1];
console.log("After the call to black_box: " + after);
|
运行此小测试产生以下输出，显示传递给black_box的秘密值确实被程序泄漏。
1
2
3
|
❯ node js/ct_wasm.js
Before the call to black_box: 0
After the call to black_box: 1
|
由于black_box函数的目的是保护代码免受基于秘密值的优化，根据定义，进入black_box的每个值都是敏感的。这不是一个好情况。
使用不同的优化屏障
Rust密码学兴趣组中有一些讨论关于基于此C++优化屏障定义新的Rust内在函数。相应的Rust实现将看起来像以下（这里使用现已弃用的llvm_asm宏）。
1
2
3
4
5
6
|
#[inline(never)]
fn black_box(input: u8) -> u8 {
unsafe { llvm_asm!("" : "+r"(input) : : : "volatile"); }
input
}
|
使用wasm-pack重新编译代码库并反编译结果Wasm模块后，我们看到black_box现在由单个local.get $input（返回函数的第一个参数）给出，这正是我们想要的。此函数不将秘密值泄漏到内存，但它被Turbofan保留了吗？
通过运行相应的test_with_barrier函数通过Turbofan，我们看到它产生与上面先前的恒定时间版本相同的机器代码。因此，使用基于llvm_asm的屏障，我们得到一个不将秘密值泄漏到周围JavaScript运行时的恒定时间实现。
然而，正如我们已经指出的，没有理由期望Turbofan在未来的编译器版本中不内联black_box函数。（事实上，如果我们查看V8存储库中负责Wasm编译管道的