名称: 恒定时间测试 类型: 领域 描述: > 恒定时间测试检测密码代码中的定时侧信道。 在审计密码实现以查找定时漏洞时使用。
恒定时间测试
定时攻击利用执行时间的差异从密码实现中提取秘密信息。与针对理论弱点的密码分析不同，定时攻击利用实现缺陷——它们可以影响任何密码代码。
背景
定时攻击由Kocher于1996年引入。此后，研究人员已证明对RSA（Schindler）、OpenSSL（Brumley和Boneh）、AES实现甚至像Kyber这样的后量子算法的实际攻击。
关键概念
| 概念 | 描述 |
|---|---|
| 恒定时间 | 代码路径和内存访问与秘密数据无关 |
| 定时泄漏 | 与秘密相关的可观察执行时间差异 |
| 侧信道 | 从实现而非算法提取的信息 |
| 微架构 | CPU级定时差异（缓存、除法、移位） |
为何重要
定时漏洞可以：
- 暴露私钥 - 提取RSA/ECDH中的秘密指数
- 启用远程攻击 - 网络可观测的定时差异
- 绕过密码安全 - 破坏理论保证
- 持续无声 - 常未经专门分析而未被发现
两个前提条件启用利用：
- 访问预言机 - 对易受攻击实现的足够查询
- 定时依赖性 - 执行时间与秘密数据之间的相关性
常见恒定时间违规模式
四种模式占大多数定时漏洞：
// 1. 条件跳转 - 最严重的定时差异
if(secret == 1) { ... }
while(secret > 0) { ... }
// 2. 数组访问 - 缓存定时攻击
lookup_table[secret];
// 3. 整数除法（处理器依赖）
data = secret / m;
// 4. 移位操作（处理器依赖）
data = a << secret;
条件跳转导致不同的代码路径，导致巨大的定时差异。
数组访问依赖于秘密启用缓存定时攻击，如AES缓存定时研究所示。
整数除法和移位操作在某些CPU架构和编译器配置上泄漏秘密。
当模式无法避免时，采用掩码技术以去除定时与秘密之间的相关性。
示例：模幂定时攻击
模幂运算（用于RSA和Diffie-Hellman）易受定时攻击。RSA解密计算：
$$ct^{d} \mod{N}$$
其中$d$是秘密指数。平方求幂优化将乘法减少到$\log{d}$：
$$ \begin{align*} & \textbf{输入: } \text{底数 }y,\text{指数 } d={d_n,\cdots,d_0}_2,\text{模数 } N \ & r = 1 \ & \textbf{for } i=|n| \text{ downto } 0: \ & \quad\textbf{if } d_i == 1: \ & \quad\quad r = r * y \mod{N} \ & \quad y = y * y \mod{N} \ & \textbf{return }r \end{align*} $$
代码基于指数位$d_i$分支，违反恒定时间原则。当$d_i = 1$时，发生额外乘法，增加执行时间并泄漏位信息。
蒙哥马利乘法（常用于模算术）也泄漏定时：当中间值超过模数$N$时，需要额外的约简步骤。攻击者构造输入$y$和$y’$使得：
$$ \begin{align*} y^2 < y^3 < N \ y’^2 < N \leq y’^3 \end{align*} $$
对于$y$，两个乘法都花费时间$t_1+t_1$。对于$y’$，第二个乘法需要约简，花费时间$t_1+t_2$。这个定时差异揭示$d_i$是0还是1。
何时使用
在以下情况应用恒定时间分析：
- 审计密码实现（原语、协议）
- 代码处理秘密密钥、密码或敏感密码材料
- 从头实现密码算法
- 审查涉及密码代码的PR
- 调查潜在定时漏洞
在以下情况考虑替代方案：
- 代码不处理秘密数据
- 无秘密输入的公共算法
- 非密码定时要求（性能优化）
快速参考
| 场景 | 推荐方法 | 技能 |
|---|---|---|
| 证明无泄漏 | 形式验证 | SideTrail, ct-verif, FaCT |
| 检测统计定时差异 | 统计测试 | dudect |
| 运行时跟踪秘密数据流 | 动态分析 | timecop |
| 查找缓存定时漏洞 | 符号执行 | Binsec, pitchfork |
恒定时间工具类别
密码社区已开发四类定时分析工具：
| 类别 | 方法 | 优点 | 缺点 |
|---|---|---|---|
| 形式 | 模型上的数学证明 | 保证无泄漏 | 复杂性、建模假设 |
| 符号 | 符号执行路径 | 具体反例 | 时间密集的路径探索 |
| 动态 | 标记秘密的运行时追踪 | 精细、灵活 | 覆盖限于执行路径 |
| 统计 | 测量实际执行定时 | 实用、简单设置 | 无根因信息、噪声敏感 |
1. 形式工具
形式验证在代码的抽象（模型）上数学证明定时属性。工具从源代码/二进制创建模型并验证其满足指定属性（例如，变量标记为秘密）。
流行工具：
优点： 无泄漏证明、语言无关（LLVM字节码） 缺点： 需要专业知识、建模假设可能遗漏现实问题
2. 符号工具
符号执行分析路径和内存访问如何依赖于符号变量（秘密）。提供具体反例。专注于缓存定时攻击。
流行工具：
优点： 具体反例有助于调试 缺点： 路径爆炸导致长执行时间
3. 动态工具
动态分析标记敏感内存区域并追踪执行以检测定时依赖操作。
流行工具：
优点： 精细控制、目标分析 缺点： 覆盖限于执行路径
详细指南： 参见 timecop 技能以获取设置和用法。
4. 统计工具
用各种输入执行代码，测量经过时间，并检测不一致性。测试实际实现包括编译器优化和架构。
流行工具：
- dudect（见下文）
- tlsfuzzer
优点： 简单设置、实用现实结果 缺点： 无根因信息、噪声掩盖弱信号
详细指南： 参见 dudect 技能以获取设置和用法。
测试工作流
阶段1: 静态分析 阶段2: 统计测试
┌─────────────────┐ ┌─────────────────┐
│ 识别秘密数据流 │ → │ 检测定时差异 │
│ 工具: ct-verif │ │ 工具: dudect │
└─────────────────┘ └─────────────────┘
↓ ↓
阶段4: 根因分析 阶段3: 动态追踪
┌─────────────────┐ ┌─────────────────┐
│ 精确定位泄漏位置│ ← │ 追踪秘密传播 │
│ 工具: Timecop │ │ 工具: Timecop │
└─────────────────┘ └─────────────────┘
推荐方法：
- 从dudect开始 - 快速统计检查定时差异
- 如果发现泄漏 - 使用Timecop精确定位根因
- 对于高保证 - 应用形式验证（ct-verif, SideTrail）
- 持续监控 - 将dudect集成到CI管道
工具和方法
Dudect - 统计分析
Dudect测量两个输入类别（固定vs随机）的执行时间，并使用韦尔奇t检验检测统计显著差异。
详细指南： 参见 dudect 技能以获取完整设置、用法模式和CI集成。
恒定时间分析快速开始
#define DUDECT_IMPLEMENTATION
#include "dudect.h"
uint8_t do_one_computation(uint8_t *data) {
// 要测量的代码放在这里
}
void prepare_inputs(dudect_config_t *c, uint8_t *input_data, uint8_t *classes) {
for (size_t i = 0; i < c->number_measurements; i++) {
classes[i] = randombit();
uint8_t *input = input_data + (size_t)i * c->chunk_size;
if (classes[i] == 0) {
// 固定输入类别
} else {
// 随机输入类别
}
}
}
关键优点：
- 简单C头文件集成
- 通过韦尔奇t检验的统计严格性
- 适用于编译二进制（现实条件）
关键限制：
- 检测到泄漏时无根因信息
- 对测量噪声敏感
- 不能保证无泄漏（仅统计置信）
Timecop - 动态追踪
Timecop包装Valgrind以检测依赖于秘密内存区域的运行时操作。
详细指南： 参见 timecop 技能以获取安装、示例和调试。
恒定时间分析快速开始
#include "valgrind/memcheck.h"
#define poison(addr, len) VALGRIND_MAKE_MEM_UNDEFINED(addr, len)
#define unpoison(addr, len) VALGRIND_MAKE_MEM_DEFINED(addr, len)
int main() {
unsigned long long secret_key = 0x12345678;
// 标记秘密为中毒
poison(&secret_key, sizeof(secret_key));
// 任何依赖于secret_key的分支或内存访问
// 将由Valgrind报告
crypto_operation(secret_key);
unpoison(&secret_key, sizeof(secret_key));
}
使用Valgrind运行：
valgrind --leak-check=full --track-origins=yes ./binary
关键优点：
- 精确定位定时泄漏的准确行
- 无需代码插桩
- 追踪执行中的秘密传播
关键限制：
- 不能检测微架构定时差异
- 覆盖限于执行路径
- 性能开销（在合成CPU上运行）
实施指南
阶段1：初始评估
识别处理秘密的密码代码：
- 私钥、指数、随机数
- 密码哈希、认证令牌
- 加密/解密操作
快速统计检查：
- 为密码函数编写dudect测试套件
- 运行5-10分钟，命令
timeout 600 ./ct_test - 监控t值：高绝对值指示泄漏
工具： dudect 预期时间： 1-2小时（测试套件编写 + 初始运行）
阶段2：详细分析
如果dudect检测到泄漏：
根因调查：
- 用Timecop
poison()标记秘密变量 - 在Valgrind下运行以识别准确行
- 审查四种常见违规模式
- 检查汇编输出以查找条件分支
工具： Timecop, 编译器输出（objdump -d）
阶段3：修复
修复定时泄漏：
- 用恒定时间选择（位操作）替换条件分支
- 使用恒定时间比较函数
- 用恒定时间替代方案或掩码替换数组查找
- 验证编译器不会优化掉恒定时间代码
重新验证：
- 再次运行dudect更长时间（30+分钟）
- 测试不同编译器和优化级别
- 测试不同CPU架构
阶段4：持续监控
集成到CI：
- 将dudect测试添加到测试套件
- 在CI中运行固定时间（5-10分钟）
- 如果检测到泄漏则构建失败
参见 dudect 技能以获取CI集成示例。
常见漏洞
| 漏洞 | 描述 | 检测 | 严重性 |
|---|---|---|---|
| 秘密依赖分支 | if (secret_bit) { ... } |
dudect, Timecop | 关键 |
| 秘密依赖数组访问 | table[secret_index] |
Timecop, Binsec | 高 |
| 可变时间除法 | result = x / secret |
Timecop | 中 |
| 可变时间移位 | result = x << secret |
Timecop | 中 |
| 蒙哥马利约简泄漏 | 当中间值 > N时的额外约简 | dudect | 高 |
秘密依赖分支：深入分析
漏洞： 执行时间基于分支是否被采取而不同。常见于优化的模幂运算（平方求幂）。
如何用dudect检测：
uint8_t do_one_computation(uint8_t *data) {
uint64_t base = ((uint64_t*)data)[0];
uint64_t exponent = ((uint64_t*)data)[1]; // 秘密！
return mod_exp(base, exponent, MODULUS);
}
void prepare_inputs(dudect_config_t *c, uint8_t *input_data, uint8_t *classes) {
for (size_t i = 0; i < c->number_measurements; i++) {
classes[i] = randombit();
uint64_t *input = (uint64_t*)(input_data + i * c->chunk_size);
input[0] = rand(); // 随机底数
input[1] = (classes[i] == 0) ? FIXED_EXPONENT : rand(); // 固定vs随机
}
}
如何用Timecop检测：
poison(&exponent, sizeof(exponent));
result = mod_exp(base, exponent, modulus);
unpoison(&exponent, sizeof(exponent));
Valgrind将报告：
条件跳转或移动依赖于未初始化值
位于 0x40115D: mod_exp (示例.c:14)
相关技能： dudect, timecop
案例研究
案例研究：OpenSSL RSA定时攻击
Brumley和Boneh（2005年）从OpenSSL通过网络提取了RSA私钥。漏洞利用了蒙哥马利乘法的可变时间约简步骤。
攻击向量： 模幂运算中的定时差异 检测方法： 统计分析（dudect的前身） 影响： 远程密钥提取
使用工具： 自定义定时测量 应用技术： 统计分析、选择密文查询
案例研究：KyberSlash
后量子算法Kyber的参考实现包含多项式操作中的定时漏洞。除法操作泄漏秘密系数。
攻击向量： 秘密依赖除法定时 检测方法： 动态分析和统计测试 影响： 后量子密码中的秘密密钥恢复
使用工具： 定时测量工具 应用技术： 差分定时分析
高级用法
提示和技巧
| 提示 | 为何有帮助 |
|---|---|
将dudect固定到隔离的CPU核心（taskset -c 2） |
减少操作系统噪声，改进信号检测 |
| 测试多个编译器（gcc, clang, MSVC） | 优化可能引入或移除泄漏 |
| 运行dudect更长时间（小时） | 增加统计置信 |
| 最小化测试套件中的非密码代码 | 减少掩盖弱信号的噪声 |
检查汇编输出（objdump -d） |
验证编译器未引入分支 |
在测试中使用-O3 -march=native |
匹配生产优化级别 |
常见错误
| 错误 | 为何错误 | 正确方法 |
|---|---|---|
| 仅测试一种输入分布 | 可能遗漏其他模式可见的泄漏 | 测试固定vs随机、固定vs不同固定等 |
| 短时间dudect运行（< 1分钟） | 弱信号测量不足 | 运行5-10+分钟，高保证更长 |
| 忽略编译器优化级别 | -O0可能隐藏-O3中存在的泄漏 |
在生产优化级别测试 |
| 不在目标架构上测试 | x86 vs ARM有不同的定时特性 | 在部署平台上测试 |
| 在Timecop中标记太多为秘密 | 假阳性、结果不清 | 仅标记真实秘密（密钥，而非公开数据） |
相关技能
工具技能
| 技能 | 在恒定时间分析中的主要用途 |
|---|---|
| dudect | 通过韦尔奇t检验统计检测定时差异 |
| timecop | 动态追踪以精确定位定时泄漏位置 |
技术技能
| 技能 | 何时应用 |
|---|---|
| coverage-analysis | 确保测试输入覆盖密码函数的所有代码路径 |
| ci-integration | 在持续集成管道中自动化恒定时间测试 |
相关领域技能
| 技能 | 关系 |
|---|---|
| crypto-testing | 恒定时间分析是密码测试的重要组成部分 |
| fuzzing | 模糊密码代码可能触发定时依赖路径 |
技能依赖图
┌─────────────────────────┐
│ 恒定时间分析 │
│ （此技能） │
└───────────┬─────────────┘
│
┌───────────────┴───────────────┐
│ │
▼ ▼
┌───────────────────┐ ┌───────────────────┐
│ dudect │ │ timecop │
│ （统计） │ │ （动态） │
└────────┬──────────┘ └────────┬──────────┘
│ │
└───────────────┬───────────────┘
│
▼
┌──────────────────────────────┐
│ 支持技术 │
│ 覆盖分析、CI集成 │
└──────────────────────────────┘
资源
关键外部资源
这些结果必须是错误的：恒定时间分析工具的可用性评估 恒定时间分析工具的全面可用性研究。主要发现：开发人员挣扎于假阳性、需要更好的错误消息，并从工具集成中受益。评估FaCT、ct-verif、dudect和Memsan在多个密码实现中。推荐改进工具用户体验和更好文档。
恒定时间工具列表 - CROCS 恒定时间分析工具的精选目录和教程。覆盖形式工具（ct-verif, FaCT）、动态工具（Memsan, Timecop）、符号工具（Binsec）和统计工具（dudect）。包括设置和用法的实践教程。
Paul Kocher: Diffie-Hellman、RSA、DSS和其他系统实现的定时攻击 1996年介绍定时攻击的原始论文。展示对RSA和Diffie-Hellman中模幂运算的攻击。理解定时漏洞的基本历史背景。
远程定时攻击是实用的（Brumley & Boneh） 展示对OpenSSL的实际远程定时攻击。显示网络级定时差异足以提取RSA密钥。证明定时攻击在现实网络条件下有效。
AES上的缓存定时攻击 显示使用查找表的AES实现易受缓存定时攻击。展示通过缓存定时侧信道的实际攻击提取AES密钥。
KyberSlash: 除法定时泄漏秘密 Kyber（NIST后量子标准）中定时漏洞的最新发现。显示除法操作泄漏秘密系数。强调恒定时间问题即使在现代后量子密码中仍然存在。
视频资源
- Trail of Bits: 恒定时间编程 - 恒定时间编程原则和工具的概述