constant-time-testing

常量时间测试

时序攻击利用执行时间的变化，从密码实现中提取秘密信息。与针对理论弱点的密码分析不同，时序攻击利用的是实现缺陷，而且可能影响任何密码代码。

背景

时序攻击由 Kocher 于 1996 年提出。此后，研究人员展示了针对 RSA（Schindler）、OpenSSL（Brumley 和 Boneh）、AES 实现，乃至 Kyber 等后量子算法的实际攻击。

核心概念

概念	描述
常量时间	代码路径和内存访问不依赖秘密数据
时序泄漏	与秘密相关、可观察到的执行时间差异
侧信道	从实现而非算法中提取的信息
微架构	CPU 级别的时序差异（缓存、除法、移位）

为什么这很重要

时序漏洞可能：

• 泄露私钥 - 提取 RSA/ECDH 中的秘密指数
• 使远程攻击成为可能 - 可通过网络观察到的时序差异
• 绕过密码安全性 - 破坏理论保障
• 悄然持续存在 - 若不进行专门分析，往往难以发现

利用漏洞需要满足两个前提：

1. 能够访问预言机 - 可对有漏洞的实现进行足够多次查询
2. 存在时序依赖 - 执行时间与秘密数据相关

常见的违反常量时间原则的模式

以下四种模式导致了大多数时序漏洞：

// 1. Conditional jumps - most severe timing differences
if(secret == 1) { ... }
while(secret > 0) { ... }

// 2. Array access - cache-timing attacks
lookup_table[secret];

// 3. Integer division (processor dependent)
data = secret / m;

// 4. Shift operation (processor dependent)
data = a << secret;

条件跳转会导致执行不同的代码路径，从而产生巨大的时序差异。

依赖秘密数据的数组访问会引发缓存时序攻击，AES 缓存时序研究对此有相关展示。

整数除法和移位操作会在某些 CPU 架构和编译器配置下泄露秘密。

无法避免这些模式时，应使用掩码技术，消除时序与秘密之间的相关性。

示例：模幂运算时序攻击

模幂运算（用于 RSA 和 Diffie-Hellman）容易受到时序攻击。RSA 解密计算：

$$ct^{d} \mod{N}$$

其中 $d$ 是秘密指数。平方求幂优化可将乘法次数降至 $\log{d}$：

$$ \begin{align*} & \textbf{Input: } \text{base }y,\text{exponent } d={d_n,\cdots,d_0}_2,\text{modulus } 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$ 时，会额外进行一次乘法，延长执行时间并泄露位信息。

Montgomery 乘法（常用于模运算）也会泄露时序信息：当中间值超过模数 $N$ 时，需要额外执行一次约减。攻击者会构造输入 $y$ 和 $y'$，使得：

$$ \begin{align*} y^2 < y^3 < N \ y'^2 < N \leq y'^3 \end{align*} $$

对于 $y$，两次乘法耗时均为 $t_1$，总计 $t_1+t_1$。对于 $y'$，第二次乘法需要约减，耗时为 $t_1+t_2$。这种时序差异会揭示 $d_i$ 是 0 还是 1。

适用场景

以下情况适用常数时间分析：

• 审计加密实现（原语、协议）
• 代码处理密钥、密码或敏感加密材料
• 从头实现加密算法
• 审查涉及加密代码的 PR
• 调查潜在的计时漏洞

以下情况可考虑其他方法：

• 代码不处理秘密数据
• 使用不涉及秘密输入的公开算法
• 非加密相关的计时需求（性能优化）

快速参考

场景	推荐方法	技能
证明不存在泄漏	形式化验证	SideTrail、ct-verif、FaCT
检测统计上的计时差异	统计测试	dudect
在运行时跟踪秘密数据流	动态分析	timecop
查找缓存计时漏洞	符号执行	Binsec、pitchfork

常数时间工具类别

密码学社区已开发出四类计时分析工具：

类别	方法	优点	缺点
形式化	对模型进行数学证明	保证不存在泄漏	复杂度高，依赖建模假设
符号	符号执行路径	提供具体反例	路径探索耗时较长
动态	使用标记的秘密进行运行时跟踪	粒度细、灵活	覆盖范围仅限于已执行的路径
统计	测量实际执行时间	实用、设置简单	无法定位根因，对噪声敏感

1. 形式化工具

形式化验证会针对代码的抽象（模型），以数学方式证明其计时属性。工具会根据源代码或二进制文件创建模型，并验证其是否满足指定属性（例如，将变量标记为秘密）。

常用工具：

• SideTrail
• ct-verif
• FaCT

优点： 可证明不存在泄漏，语言无关（LLVM 字节码） 缺点： 需要专业知识，建模假设可能会遗漏现实问题

2. 符号工具

符号执行会分析路径和内存访问如何依赖符号变量（秘密），并提供具体反例。重点关注缓存计时攻击。

常用工具：

• Binsec
• pitchfork

优点： 具体反例有助于调试 缺点： 路径爆炸会导致执行时间过长

3. 动态工具

动态分析会标记敏感内存区域并跟踪执行过程，以检测依赖计时的操作。

常用工具：

• Memsan：教程
• Timecop（见下文）

优点： 控制粒度细，可针对性分析 缺点： 覆盖范围仅限于已执行的路径

详细指南： 有关设置和用法，请参阅 timecop 技能。

4. 统计工具

使用各种输入执行代码，测量运行时间并检测差异。测试实际实现，包括编译器优化和架构的影响。

常用工具：

• dudect（见下文）
• tlsfuzzer

优点： 设置简单，结果贴近实际 缺点： 无法提供根因信息，噪声会掩盖微弱信号

详细指南： 有关设置和用法，请参阅 dudect 技能。

测试工作流

Phase 1: Static Analysis        Phase 2: Statistical Testing
┌─────────────────┐            ┌─────────────────┐
│ Identify secret │      →     │ Detect timing   │
│ data flow       │            │ differences     │
│ Tool: ct-verif  │            │ Tool: dudect    │
└─────────────────┘            └─────────────────┘
         ↓                              ↓
Phase 4: Root Cause             Phase 3: Dynamic Tracing
┌─────────────────┐            ┌─────────────────┐
│ Pinpoint leak   │      ←     │ Track secret    │
│ location        │            │ propagation     │
│ Tool: Timecop   │            │ Tool: Timecop   │
└─────────────────┘            └─────────────────┘

推荐方法：

1. 从 dudect 开始 - 快速进行统计检查，检测计时差异
2. 如果发现泄漏 - 使用 Timecop 定位根因
3. 对于高保证要求 - 应用形式化验证（ct-verif、SideTrail）
4. 持续监控 - 将 dudect 集成到 CI 流水线中

工具和方法

Dudect - 统计分析

Dudect 会测量两类输入（固定输入与随机输入）的执行时间，并使用 Welch t 检验检测具有统计显著性的差异。

详细指南： 有关完整的设置、使用模式和 CI 集成，请参阅 dudect 技能。

恒定时间分析快速入门

#define DUDECT_IMPLEMENTATION
#include "dudect.h"

uint8_t do_one_computation(uint8_t *data) {
    // Code to measure goes here
}

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) {
            // Fixed input class
        } else {
            // Random input class
        }
    }
}

主要优势：

• 简单的仅包含头文件的 C 集成方式
• 通过 Welch 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;

    // Mark secret as poisoned
    poison(&secret_key, sizeof(secret_key));

    // Any branching or memory access dependent on secret_key
    // will be reported by Valgrind
    crypto_operation(secret_key);

    unpoison(&secret_key, sizeof(secret_key));
}

使用 Valgrind 运行：

valgrind --leak-check=full --track-origins=yes ./binary

主要优势：

• 精确定位计时泄漏的代码行
• 无需插桩代码
• 跟踪秘密数据在执行过程中的传播

主要局限：

• 无法检测微架构计时差异
• 覆盖范围仅限于已执行的代码路径
• 性能开销较大（在合成 CPU 上运行）

实施指南

阶段 1：初步评估

识别处理秘密数据的加密代码：

• 私钥、指数、随机数
• 密码哈希、身份验证令牌
• 加密/解密操作

快速统计检查：

1. 为加密函数编写 dudect 测试框架
2. 使用 timeout 600 ./ct_test 运行 5-10 分钟
3. 监控 t 值：绝对值较高表示可能存在泄漏

工具： dudect 预计时间： 1-2 小时（编写测试框架 + 初次运行）

阶段 2：详细分析

如果 dudect 检测到泄漏：

调查根因：

1. 使用 Timecop poison() 标记秘密变量
2. 在 Valgrind 下运行，以定位具体代码行
3. 检查四种常见违规模式
4. 检查汇编输出中的条件分支

工具： Timecop、编译器输出（objdump -d）

阶段 3：修复

修复计时泄漏：

• 用恒定时间选择（按位运算）替换条件分支
• 使用恒定时间比较函数
• 用恒定时间替代方案或掩码操作替换数组查找
• 验证编译器不会优化掉恒定时间代码

重新验证：

1. 再次运行 dudect，并延长运行时间（30 分钟以上）
2. 使用不同的编译器和优化级别进行测试
3. 在不同的 CPU 架构上进行测试

阶段 4：持续监控

集成到 CI：

• 将 dudect 测试添加到测试套件
• 固定运行时长（CI 中为 5-10 分钟）
• 检测到泄漏时使构建失败

CI 集成示例请参阅 dudect 技能。

常见漏洞

漏洞	描述	检测工具	严重性
依赖秘密数据的分支	if (secret_bit) { ... }	dudect、Timecop	CRITICAL
依赖秘密数据的数组访问	table[secret_index]	Timecop、Binsec	HIGH
可变时间除法	result = x / secret	Timecop	MEDIUM
可变时间移位	result = x << secret	Timecop	MEDIUM
Montgomery 约减泄漏	中间值 > N 时进行额外约减	dudect	HIGH

依赖秘密数据的分支：深入探讨

漏洞： 执行时间会因是否执行分支而异。这在经过优化的模幂运算（平方-乘法）中很常见。

如何使用 dudect 检测：

uint8_t do_one_computation(uint8_t *data) {
    uint64_t base = ((uint64_t*)data)[0];
    uint64_t exponent = ((uint64_t*)data)[1]; // Secret!
    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(); // Random base
        input[1] = (classes[i] == 0) ? FIXED_EXPONENT : rand(); // Fixed vs random
    }
}

如何使用 Timecop 检测：

poison(&exponent, sizeof(exponent));
result = mod_exp(base, exponent, modulus);
unpoison(&exponent, sizeof(exponent));

Valgrind 会报告：

Conditional jump or move depends on uninitialised value(s)
  at 0x40115D: mod_exp (example.c:14)

相关技能： dudect、timecop

案例研究

案例研究：OpenSSL RSA 定时攻击

Brumley 和 Boneh（2005）通过网络从 OpenSSL 中提取了 RSA 私钥。该漏洞利用了 Montgomery 乘法中耗时不定的约简步骤。

攻击向量： 模幂运算中的定时差异 检测方法： 统计分析（dudect 的前身） 影响： 远程提取密钥

使用的工具： 自定义定时测量 应用的技术： 统计分析、选择密文查询

案例研究：KyberSlash

后量子算法 Kyber 的参考实现，在多项式运算中存在定时漏洞。除法运算会泄露秘密系数。

攻击向量： 依赖于秘密数据的除法耗时 检测方法： 动态分析和统计测试 影响： 恢复后量子密码学中的密钥

使用的工具： 定时测量工具 应用的技术： 差分定时分析

高级用法

技巧和诀窍

技巧	帮助原因
将 dudect 固定到隔离的 CPU 核心（taskset -c 2）	减少操作系统噪声，提升信号检测能力
测试多个编译器（gcc、clang、MSVC）	优化可能引入或消除泄漏
让 dudect 长时间运行（数小时）	提高统计置信度
尽量减少测试框架中的非密码学代码	减少掩盖微弱信号的噪声
检查汇编输出（objdump -d）	确认编译器没有引入分支
在测试中使用 -O3 -march=native	与生产环境的优化级别相匹配

常见错误

错误	错误原因	正确做法
只测试一种输入分布	可能会漏掉其他模式下可见的泄漏	测试固定值与随机值、不同固定值之间等
dudect 运行时间过短（< 1 分钟）	测量次数不足，无法检测微弱信号	运行 5-10 分钟以上；若要求高保证，则运行更久
忽略编译器优化级别	-O0 可能掩盖 -O3 下存在的泄漏	按生产环境的优化级别进行测试
未在目标架构上测试	x86 与 ARM 的定时特性不同	在部署平台上测试
在 Timecop 中将过多数据标记为秘密	产生误报，结果不明确	只标记真正的秘密（密钥，而非公开数据）

相关技能

工具技能

技能	在常数时间分析中的主要用途
dudect	通过 Welch t 检验，以统计方法检测定时差异
timecop	动态追踪，精确定位定时泄漏的位置

技术技能

技能	适用时机
coverage-analysis	确保测试输入覆盖密码学函数中的所有代码路径
ci-integration	在持续集成流水线中自动执行常数时间测试

相关领域技能

技能	关联
crypto-testing	常数时间分析是密码学测试的重要组成部分
fuzzing	对密码学代码进行模糊测试，可能触发依赖于定时的路径

技能依赖关系图

                    ┌─────────────────────────┐
                    │  constant-time-analysis │
                    │     (this skill)        │
                    └───────────┬─────────────┘
                                │
                ┌───────────────┴───────────────┐
                │                               │
                ▼                               ▼
    ┌───────────────────┐           ┌───────────────────┐
    │      dudect       │           │     timecop       │
    │  (statistical)    │           │    (dynamic)      │
    └────────┬──────────┘           └────────┬──────────┘
             │                               │
             └───────────────┬───────────────┘
                             │
                             ▼
              ┌──────────────────────────────┐
              │   Supporting Techniques      │
              │ coverage, CI integration     │
              └──────────────────────────────┘

资源

关键外部资源

这些结果必须为假：恒定时间分析工具的可用性评估 对恒定时间分析工具进行的全面可用性研究。主要发现：开发者难以应对误报，需要更好的错误消息，并且能从工具集成中受益。研究评估了多个加密实现中的 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：恒定时间编程 - 恒定时间编程原则和工具概述