Constant-Time Cryptography Engineering: 时序攻击防护从理论到生产实践
引言
密码学实现的安全性不仅取决于算法本身的数学硬度，更取决于代码在硬件层面泄露的信息量。侧信道攻击（Side-Channel Attack）是一种利用密码系统物理实现特征（如执行时间、功耗、电磁辐射、缓存状态）而非数学结构来进行攻击的手段。在这些侧信道中，时序攻击（Timing Attack） 是最经典、最隐蔽、也最难以彻底消除的一种。
1996年，Paul Kocher 在其论文 *Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems* 中首次系统阐述了时序攻击的理论基础。此后二十余年间，从 OpenSSL 的 CVE-2014-0160（Heartbleed，虽非严格时序攻击但同属侧信道范畴）到 CVE-2018-0737（RSA 密钥恢复），从 CacheBleed 到 Spectre——时序侧信道始终是密码工程领域的核心威胁。
本文深入探讨常量时间编程（Constant-Time Programming）的理论与实践：为什么普通的分支和查表操作会泄露秘密信息？如何在不依赖特定编译器优化的前提下编写真正的常量时间代码？以及，如何在生产环境中验证和防御这些泄漏。
一、为什么代码不是"常量时间"
1.1 分支导致的泄漏
现代处理器采用分支预测器和推测执行来提升性能。但分支本身就会引入时间差异。考虑一个朴素的字符串比较函数：
// 标准实现 —— 存在严重时序泄漏
int insecure_compare(const char *a, const char *b, size_t len) {
for (size_t i = 0; i < len; i++) {
if (a[i] != b[i]) {
return 0; // 提前返回，比较次数泄露匹配前缀长度
}
}
return 1;
}攻击者通过测量响应时间，可以逐字节暴力破解未知字符串。对于长度为 N、字符集大小为 C 的密码/密钥，攻击复杂度从 O(C^N) 降至 O(C×N)。
1.2 CPU 缓存时序泄漏
现代 CPU 的多级缓存架构会导致内存访问时间差异巨大：L1 命中约 1ns，L3 命中约 10ns，主存访问约 100ns。AES 的 T-Table 实现利用预计算表来加速 S-Box 和列混合操作：
// AES T-Table 实现 —— 经典缓存时序攻击目标
static const uint32_t Te0[256] = { /* ... */ };
uint32_t aes_round_lookup(uint8_t plaintext_byte, uint8_t key_byte) {
// 访问 Te0[plaintext_byte ^ key_byte]
// 缓存是否命中取决于索引值，从而泄露 key_byte 信息
return Te0[plaintext_byte ^ key_byte];
}Osvik、Shamir 和 Tromer 在 2006 年提出的 *Cache Attacks and Countermeasures: the Case of AES* 论文中展示了如何利用这种缓存访问模式恢复完整 AES 密钥，攻击仅需数万次加密操作。
1.3 数据依赖的指令延迟
某些算术指令的执行时间依赖于操作数本身。例如，整数除法在多数架构上是可变时间的：ARM Cortex-A72 的 SDIV 指令执行时间在 4-12 个周期之间，取决于操作数。乘法在较老架构上也存在类似问题。
// 模约减的实现中如果存在条件交换，也会泄漏
uint32_t conditional_swap(uint32_t a, uint32_t b, uint32_t cond) {
// 当 cond=1 时执行交换，cond=0 时不交换
// 但无论 cond 为何值，都应该消耗相同时间
if (cond) { // 这会泄漏 cond 值
uint32_t tmp = a;
a = b;
b = tmp;
}
return a;
}1.4 推测执行的幽灵
Spectre（2017）揭示了更隐蔽的泄漏途径：推测执行会更新缓存状态，即使推测被回滚。这意味着即使代码在架构层面"正确"地不执行某个分支，微架构状态仍可能发生变化并被利用：
// 即使 bounds check 正确，推测执行仍会导致缓存泄漏
void spectre_gadget(uint8_t *array, size_t x) {
if (x < array_size) {
// CPU 可能在权限检查完成前推测执行此行
uint8_t probe = probe_array[array[x] * 4096];
}
}二、常量时间编程的核心原则
2.1 消除秘密相关的分支
常量时间代码的第一原则：任何条件分支的条件值都不能依赖于秘密数据。取而代之，应该使用位掩码操作来实现条件逻辑。
/// 常量时间条件选择：当 condition 为全1时返回 a，为全0时返回 b
///
/// # Safety
/// condition 必须是 0x00..00 或 0xFF..FF（由秘密数据经常量时间比较生成）
pub fn constant_time_select(a: u64, b: u64, mask: u64) -> u64 {
// 不使用 if，不使用条件分支
// mask = 0xFF..FF => 返回 a
// mask = 0x00..00 => 返回 b
(a & mask) | (b & !mask)
}
/// 常量时间比较（返回值语义与 select 中的 mask 一致：全1表示相等）
pub fn constant_time_eq(a: u64, b: u64) -> u64 {
let diff = a ^ b; // 全0表示相等
let diff_01 = diff.wrapping_sub(1); // 无借位传播
let diff_10 = !diff & diff.wrapping_neg();
// 若 diff==0，则 !diff=全1，diff.wrapping_neg()=0，故 diff_10=0，diff_01=全1
// 若 diff!=0，最高位会被置位
((diff_01 & !diff_10) >> 63).wrapping_neg()
}2.2 消除秘密相关的内存访问
第二个原则：内存访问的模式（地址、次数）不能依赖于秘密数据。这要求：
- 使用位运算替代查表
- 按需计算的算法实现中避免数据依赖的索引
- 所有数组的遍历必须采用全遍历+选择性合并的策略
/// 常量时间字节数组比较（通常用于 MAC 验证）
/// 返回 0 表示相等，非0表示不等
pub fn constant_time_compare(a: &[u8], b: &[u8]) -> u8 {
assert_eq!(a.len(), b.len());
let mut result: u8 = 0;
// 无论是否发现差异，都遍历全部字节
for i in 0..a.len() {
result |= a[i] ^ b[i]; // 使用或运算累积差异，避免短路
}
result // result == 0 表示相等
}
/// 常量时间从数组中选择一个元素（用于恒定时间查表替代）
pub fn constant_time_lookup<T: Copy>(table: &[T], index: usize) -> T {
let len = table.len();
let mut result = table[0];
for i in 0..len {
// 当 i == index 时 mask 为全1，否则为全0
let mask = constant_time_eq(i as u64, index as u64);
// 将 mask 扩展到 T 的宽度（此处简化为 u8 示例）
result = constant_time_select_u8(result, table[i], mask as u8);
}
result
}
fn constant_time_select_u8(a: u8, b: u8, mask: u8) -> u8 {
(a & mask) | (b & !mask)
}2.3 恒定延迟的算术操作
第三个原则：某些算术操作在硬件层面并非恒定延迟。在密码编码中需要避免使用这些操作，或用位运算替代：
/// 常量时间模 2^255 - 19（ Curve25519 的素数域）
///
/// 不使用除法（可变时间），改用乘法和条件约减
fn ct_mod_p25519(a: u64) -> u64 {
// a < 2*25519 只需要一次条件减法
// 但条件减法也必须是常量时间的！
let prime: u64 = (1 << 255) - 19;
let mask = ct_lt(a, prime); // 常量时间小于比较，返回全1或全0
// 当 a >= prime 时减去 prime
wrapping_sub_masked(a, prime, mask)
}
fn ct_lt(a: u64, b: u64) -> u64 {
// 计算 a < b 但避免分支
// 利用有符号数的溢出行为：a - b 的借位会反映在最高位
let diff = a.wrapping_sub(b);
// 当 a >= b 时无借位；a < b 时 diff 的最高位设置（假设 a-b溢出）
// 更精确的实现需要考虑相等的情况
((diff ^ a ^ b) >> 63).wrapping_neg()
}
fn wrapping_sub_masked(a: u64, b: u64, mask: u64) -> u64 {
// mask = 全1 时执行减法，mask = 全0 时返回原值
(a.wrapping_sub(b & mask))
}三、业界实践：密码编码中的常量时间实现
3.1 libsodium：简单与安全的平衡
libsodium 在设计上将安全性置于性能之上，其 API 强制使用常量时间比较：
// libsodium 核心比较函数（简化版）
int sodium_memcmp(const void *const b1_, const void *const b2_, size_t len) {
const unsigned char *b1 = (const unsigned char *)b1_;
const unsigned char *b2 = (const unsigned char *)b2_;
unsigned char diff = 0;
for (size_t i = 0; i < len; i++) {
diff |= b1[i] ^ b2[i];
}
// sodium_reduce 将 diff 归一化为 0 或 1
return (int)((diff | (unsigned char)(-(int)diff)) >> 7) ^ 1;
}
// 安全版本的常量时间交换（用于解密完成后的清理）
void sodium_memzero(void *const pnt, const size_t len) {
volatile unsigned char *volatile pnt_ = (volatile unsigned char *volatile)pnt;
size_t i = (size_t)0U;
while (i < len) {
pnt_[i++] = 0U;
__asm__ __volatile__("" : : "r"(pnt_[i - 1]) : "memory");
}
}注意到 __asm__ __volatile__("" : : "r"(pnt_[i - 1]) : "memory") 这一编译器屏障——这是为了防止"死存储消除"（Dead Store Elimination）优化。编译器可能认为置零操作在后续不读取时是无用的，从而将其优化掉。这与 volatile 一起确保了清零操作不会被跳过。
3.2 ring：Rust 生态中的常量时间实践
Briansmith 的 ring 库是 Rust 生态中常量时间实现的标杆。它通过结合 Rust 的 #[inline(never)]、内联汇编和 LTO 控制来保证常量时间属性不被编译器破坏：
// ring 风格的常量时间选择（实际代码更复杂）
#[inline(never)]
pub fn choice(a: u64, b: u64, choice: u64) -> u64 {
// 使用内联汇编阻止编译器优化掉常量时间掩码操作
let mut result: u64;
unsafe {
asm!(
"and {0}, {1}, {3}",
"and {2}, {2}, {4}",
"or {0}, {0}, {2}",
inlateout(reg) a => result,
inlateout(reg) b => _,
in(reg) !choice,
in(reg) choice,
);
}
result
}ring 库还维护了一个专门的 GCC/Clang 编译标志配置文件，确保即使在 -O3 下也能保留常量时间属性，包括禁用某些推测执行相关的优化。
3.3 OpenSSL 的演进
OpenSSL 作为使用最广泛的 C 密码库，其常量时间编程经历了漫长演化。早期的代码中处处是条件分支，后期逐步引入常量时间原语：
// OpenSSL 的 CRYPTO_memcmp（1.1.0+）
int CRYPTO_memcmp(const void * in_a, const void * in_b, size_t len) {
size_t i;
const volatile unsigned char *a = in_a;
const volatile unsigned char *b = in_b;
unsigned char x = 0;
for (i = 0; i < len; i++) {
x |= a[i] ^ b[i];
}
return x;
}从 1.1.0 版本开始，OpenSSL 正式取消了之前 API 中"返回值表示比较顺序"的行为——因为这种返回值本身就会泄漏信息。新的 CRYPTO_memcmp 仅返回 0（相等）或 1（不等），不允许返回比较结果的具体差异。
四、生产的挑战：编译器是你的最大敌人
4.1 优化器的"善意"破坏
即使你精心编写了常量时间代码，编译器的优化通道仍可能破坏它。常见场景包括：
- 模式识别：编译器识别出
mask ? a : b模式并转换为条件移动 - 循环展开：短循环被展开为序列化代码
- 死代码消除：对"逻辑上不必要"的操作直接删除
- 强度削减：用廉价操作替代昂贵操作，但可能引入数据依赖
- 使用
-ffunction-sections隔离常量时间函数 - 通过自定义编译器标志禁用特定优化
- 在构建脚本中检查关键函数的汇编输出
- ct-fuzz + ddverify：通过符号执行检测秘密相关的分支
- Clang's MemorySanitizer：检测未初始化和数据泄露
- SideTrail/ctgrind（Valgrind 插件）：标记秘密数据的时序泄漏
- dudect（Distinguishing attacks using undefined behavior and entropy）：通过统计大量调用的执行时间分布来判断是否存在泄漏
- Microwalk：基于执行轨迹的侧信道分析
- retpoline：将间接分支替换为永远不会被正确推测执行的代码序列
- lfence 屏障：在关键比较后插入加载屏障
- sitea/siteb 分离：将秘密数据和公开数据放置在不同内存页
- 输入验证前置：在涉及秘密数据前完成所有格式验证，验证失败时仍执行完整的密码流程（使用哑数据）。
- API 设计约束：公开 API 不应返回差异信息（<0/0/>0 模式），而是返回明确的枚举或布尔值。
- 内存访问统一化：查表操作前对整个表进行线性扫描再选择，或使用硬件 AES 指令替代软件查表。
- 避免可变时间算术：禁止使用可变时间的除法、取模；使用乘法替代条件选择。
- 编译器屏障：在关键路径使用
volatile或内联汇编防止优化。 - CI 集成验证：将 ct-fuzz、dudect 集成到 CI 流程，自动回归测试。
- 硬件特性利用：在支持的平台上使用 AES-NI、SHA-NI、AVX-512 VBMI2 等恒定延迟指令。
- 审计与形式验证：对关键代码进行手工汇编审计，对最高安全级别的代码进行形式化验证（如 HACL*、fiat-crypto）。
- *Kocher, P. (1996). Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems.*
- *Bernstein, D. J. (2005). Cache-timing attacks on AES.*
- *Osvik, Shamir, Tromer (2006). Cache Attacks and Countermeasures: the Case of AES.*
- *Kocher et al. (2019). Spectre Attacks: Exploiting Speculative Execution.*
- *Project Zero. Reading privileged memory with a side-channel.*
来看一个具体的例子：
// 看似常量时间的代码
uint8_t ct_select_uint8(uint8_t a, uint8_t b, uint8_t cond) {
return (a & -cond) | (b & ~(-cond)); // 当 cond=0 时全0，cond=1 时全1
}
// x86-64 GCC -O2 汇编输出：
// movzx edi, dil
// movzx edx, sil
// neg edi
// movzx eax, dil
// and eax, edx
// and esi, edi
// or eax, esi
// ret这段代码在 x86-64 上确实是常量时间的，因为 neg 和 and 指令都是固定延迟的。但并非所有平台都如此——某些 RISC 架构上条件移动 CMOV 的实现依赖于操作数，可能泄漏信息。
4.2 防御性策略
为对抗编译器的"优化"，生产代码采用以下策略：
策略一：使用 volatile 访问
// 阻止编译器优化掉关键操作
static inline void ct_zeroize(void *ptr, size_t len) {
volatile volatile_byte_t *p = ptr;
for (size_t i = 0; i < len; i++) {
p[i] = 0;
}
// 添加编译器屏障
__asm__ __volatile__("" ::: "memory");
}策略二：使用 inline assembly 隔离
// ring 的 MovableU32 类型：确保乘法不会被优化为数据依赖的移动
#[repr(C)]
pub struct MovableU32(u32);
impl MovableU32 {
pub fn ct_or(&mut self, other: MovableU32) {
unsafe {
asm!(
"or {0}, {1}",
inlateout(reg) self.0,
in(reg) other.0,
);
}
}
}策略三：链接时控制
4.3 验证工具
验证代码是否真正常量时间是另一个挑战。生产环境常用的验证方法：
静态分析工具：
动态检测方法：
// 使用 dudect 风格的统计测试来验证常量时间
fn dudect_test<F: Fn(&[u8]) -> u64>(f: F, iterations: usize) -> bool {
// 类别 0: 固定输入
// 类别 1: 随机输入
// 收集两类输入的执行时间
// 使用 Welch's t-test 判断是否可区分
// t 值 > 4.5 表示存在统计显著的差异（即有泄漏）
unimplemented!()
}五、高级话题：Spectre 与推测执行时代
5.1 retpoline 与软件缓解
Spectre 攻击表明，即使代码在架构层面是安全的，微架构层面的推测执行仍可能泄漏信息。软件缓解方案包括：
jmp .L2
.L1:
mov %rax, (%rsp)
ret
.L2:
call .L1
.L3:
pause
jmp .L3 ; 无限循环陷阱，阻止推测执行5.2 硬件层面的缓解
Intel (IBRS, IBPB, STIBP) 和 AMD (STIBP, SSBD) 的硬件缓解虽然有效，但带来显著的性能开销（某些场景下高达 30%）。因此，在密码学关键路径上仍需结合软件保障。
六、实战：编写安全的 HMAC 验证
将上述原则应用于 JWT token 验证场景：
/// 安全的 HMAC-SHA256 token 验证函数
/// 确保：
/// 1. 比较过程完全常量时间
/// 2. 即使 token 格式错误也执行完整的比较流程
/// 3. 清理所有敏感中间结果
pub fn verify_hmac_token(provided_token: &[u8], expected_hmac: &[u8]) -> bool {
// 步骤1: 提前计算提供给攻击者的信息
// （这一步的时间差异是安全的，因为 expected_hmac 是秘密但 provided_token 不是）
let provided_hmac = decode_padded_hmac(provided_token);
// 步骤2: 常量时间比较
let mut result = 0u8;
let mut accumulator_for_side_channel_resistance = 0u64;
// 确保两个 HMAC 都是正确的长度（防止长度泄漏攻击）
let expected_len = 32usize;
let actual_len = provided_hmac.len();
if actual_len != expected_len {
// 即使长度错误也要执行完整的比较，防止时间泄漏
// 使用哑数据执行比较，结果会被丢弃
let dummy_hmac = [0u8; 32];
result |= constant_time_compare_fixed(&dummy_hmac, expected_hmac);
result |= 1; // 确保最终结果是非零（即认证失败）
} else {
result |= constant_time_compare_fixed(&provided_hmac, expected_hmac);
}
// 步骤3: 清理
// 在现代 Rust 中，可以使用 zeroize crate
// zeroize::Zeroize::zeroize(&mut accumulator_for_side_channel_resistance);
result == 0
}
fn constant_time_compare_fixed(a: &[u8], b: &[u8]) -> u8 {
assert_eq!(a.len(), b.len());
let len = a.len();
let mut diff: u8 = 0;
for i in 0..len {
diff |= a[i] ^ b[i];
}
diff
}七、最佳实践清单
以下是密码编码中常量时间编程的最佳实践：
结语
常量时间编程是密码学工程中最关键的防御实践之一。攻击者不需要破解你的算法，只需要测量你的代码执行时间差异。在 Spectre 和 Meltdown 时代之后，侧信道防御从"最佳实践"升级为"强制要求"。
核心理念是：编译器优化与微架构预测是常量时间的敌人，而惟一的武器是消除一切与秘密数据相关的可观测差异。学会质疑你的编译器，验证你的代码，并对"安全的"实现保持健康的怀疑态度。
*References:*
发表评论 取消回复