优化屏障的生命周期 - 第1部分

恒定时间是什么？

密码学的正确实现极具挑战性，无论是高级协议还是底层密码原语。除了关注整体正确性和可能意外泄露秘密的边缘情况外，潜在的侧信道泄漏和定时攻击也是重要关切。

定时攻击试图利用应用程序执行时间可能微妙地依赖于输入这一事实。如果应用程序基于秘密数据（如随机数生成器种子或私钥）做出控制流相关决策，这会轻微影响应用程序的执行时间。同样，如果使用秘密数据确定从内存中读取的位置，可能导致缓存未命中，进而影响应用程序的执行时间。在这两种情况下，关于秘密数据的信息都通过程序执行期间的时间差异泄露。

为防止此类时间差异，密码学工程师通常避免基于秘密数据实现决策。但在需要基于秘密数据做出决策的情况下，有巧妙的方法以恒定时间实现它们，即无论输入如何，始终以相同时间执行。

与编译器斗争

理想情况下，这应该是故事的结束，但实际上这种方法存在固有风险。由于编译器没有时间概念，它不将时间差异视为可观察行为。这意味着它可以自由重写和优化恒定时间代码，可能向程序中引入新的时间泄漏。

最明显的解决方案是核选项——关闭所有优化并使用-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"看穿黑盒"并意识到输入实际上是一个布尔值。这反过来防止编译器将输出上的布尔操作重写为条件语句，这可能泄露关于输入的时间信息。

WebAssembly的情况如何？

现在让我们回到最初的问题。我们的客户正在运行从Rust编译到WebAssembly并使用node运行的代码。这意味着库首先使用LLVM编译为Wasm，然后由node使用Turbofan JIT编译器再次编译。

我们期望LLVM会尊重像subtle crate这样的库插入的优化防护，但Turbofan呢？

为了查看代码库将如何受到影响，我们使用wasm-bindgen和wasm-pack编译了上面定义的test_with_barrier函数。然后我们转储了Turbofan JIT生成的代码，并检查输出以查看优化屏障是否保留，以及实现的恒定时间属性是否得到保留。

引入新的侧信道

编译版本的black_box将输入写入内存然后返回，这一事实实际上有些令人惊讶。由于black_box接受一个值作为输入，而read_volatile接受一个引用作为输入，LLVM需要以某种方式将输入值转换为引用。

当为x86或ARM等架构编译时，LLVM可以简单地使用堆栈上输入的地址，但Wasm堆栈不能以这种方式寻址，这意味着LLVM必须将输入写入内存才能引用它。所有这些意味着我们想要使用优化屏障保护的秘密值被LLVM泄漏到Wasm内存中。

使用不同的优化屏障

Rust密码学兴趣组中已经有一些讨论，关于基于这个C++优化屏障定义一个新的Rust内部函数。相应的Rust实现将类似于以下内容（这里使用现已弃用的llvm_asm宏）：

1
2
3
4
5

#[inline(never)]
fn black_box(input: u8) -> u8 {
    unsafe { llvm_asm!("" : "+r"(input) : : : "volatile"); }
    input
}

使用基于llvm_asm的屏障，我们得到一个不向周围JavaScript运行时泄露秘密值的恒定时间实现。

未来展望

很明显，通过插入优化屏障与LLVM斗争不是提供恒定时间保证的好方法。正在进行的努力旨在语言层面解决这个问题。秘密类型RFC和CT-Wasm项目（分别为Rust和Wasm引入秘密类型）是这类努力的两个很好的例子。

缺少的是将秘密类型和相应语义引入LLVM的前进道路。这很可能是Rust实现向前推进的先决条件。（Rust RFC目前被推迟，等待LLVM的相应RFC。）没有LLVM支持，很难看出依赖LLVM的高级语言如何提供任何绝对的恒定时间保证。在那之前，我们都只能与编译器后端玩捉迷藏游戏。

在这篇文章中，我们研究了使用优化屏障来防止优化器对Rust中的恒定时间密码实现造成破坏，以及优化屏障在针对Wasm时提供的安全保证。在即将到来的博客文章第二部分中，我们将探讨如何通过在函数级别选择性禁用优化来保持实现的恒定时间属性。