名称: 恒定时间测试类型: 领域描述: > 恒定时间测试检测密码学代码中的时序侧信道。用于审计密码实现中的时序漏洞。

恒定时间测试

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

背景

时序攻击由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$时，发生额外乘法，增加执行时间并泄漏位信息。

Montgomery乘法（常用于模算术）也泄漏时序：当中间值超过模数$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. 动态工具

动态分析标记敏感内存区域并跟踪执行以检测时序依赖操作。

流行工具：

Memsan: 教程
Timecop（见下文）

优势： 细粒度控制、针对性分析 弱点： 覆盖仅限于执行路径

详细指导： 参见timecop技能以获取设置和用法。

4. 统计工具

执行具有各种输入的代码，测量经过时间，并检测不一致性。测试实际实现包括编译器优化和架构。

流行工具：

dudect（见下文）
tlsfuzzer

优势： 简单设置、实用实际结果 弱点： 无根本原因信息、噪声掩盖弱信号

详细指导： 参见dudect技能以获取设置和用法。

测试工作流

阶段1: 静态分析        阶段2: 统计测试
┌─────────────────┐            ┌─────────────────┐
│ 识别秘密数据流 │      →     │ 检测时序差异   │
│ 工具: ct-verif  │            │ 工具: dudect    │
└─────────────────┘            └─────────────────┘
         ↓                              ↓
阶段4: 根本原因            阶段3: 动态跟踪
┌─────────────────┐            ┌─────────────────┐
│ 精确定位泄漏点 │      ←     │ 跟踪秘密传播   │
│ 工具: Timecop   │            │ 工具: Timecop   │
└─────────────────┘            └─────────────────┘

推荐方法：

从dudect开始 - 快速统计检查时序差异
如果发现泄漏 - 使用Timecop精确定位根本原因
对于高保证 - 应用形式验证（ct-verif, SideTrail）
持续监控 - 将dudect集成到CI管道

工具和方法

Dudect - 统计分析

Dudect测量两个输入类（固定vs随机）的执行时间，并使用Welch的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仅头文件集成
通过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;

    // 将秘密标记为毒化
    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	中
Montgomery约简泄漏	中间值>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 (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`	匹配生产优化级别

常见错误

错误	为什么错误	正确方法
仅测试一种输入分布	可能错过其他模式可见的泄漏	测试固定vs随机、固定vs不同固定等
dudect运行时间短（<1分钟）	弱信号测量不足	运行5-10+分钟，高保证需更长时间
忽略编译器优化级别	`-O0`可能隐藏`-O3`中存在的泄漏	在生产优化级别测试
未在目标架构上测试	x86 vs ARM具有不同时序特性	在部署平台上测试
在Timecop中标记过多为秘密	误报、结果不清晰	仅标记真正秘密（密钥，而非公共数据）

资源

关键外部资源

这些结果必须为假：恒定时间分析工具的可用性评估 恒定时间分析工具的全面可用性研究。关键发现：开发者面临误报、需要更好的错误消息，并从工具集成中受益。评估了FaCT、ct-verif、dudect和Memsan在多个密码学实现上。推荐改进工具UX和更好的文档。

恒定时间工具列表 - 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：恒定时间编程 - 恒定时间编程原则和工具的概述

技能	何时应用
coverage-analysis	确保测试输入覆盖密码函数的所有代码路径
ci-integration	自动化恒定时间测试在持续集成管道中

技能	关系
crypto-testing	恒定时间分析是密码学测试的重要组成部分
fuzzing	模糊测试密码代码可能触发时序依赖路径

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

名称: 恒定时间测试 类型: 领域 描述: > 恒定时间测试检测密码学代码中的时序侧信道。 用于审计密码实现中的时序漏洞。

恒定时间测试

背景

关键概念

为什么这很重要

常见的恒定时间违反模式

示例：模幂时序攻击

何时使用

快速参考

恒定时间工具类别

1. 形式化工具

2. 符号化工具

3. 动态工具

4. 统计工具

测试工作流

工具和方法

Dudect - 统计分析

恒定时间分析的快速入门

Timecop - 动态跟踪

恒定时间分析的快速入门

实施指南

阶段1：初始评估

阶段2：详细分析

阶段3：修复

阶段4：持续监控

常见漏洞

秘密依赖分支：深入探讨

案例研究

案例研究：OpenSSL RSA时序攻击

案例研究：KyberSlash

高级用法

技巧与窍门

常见错误

相关技能

工具技能

技术技能

相关领域技能

技能依赖图

资源

关键外部资源

视频资源

名称: 恒定时间测试类型: 领域描述: > 恒定时间测试检测密码学代码中的时序侧信道。用于审计密码实现中的时序漏洞。