4. 秘密相关内存访问

在常数时间密码实现中，最隐蔽也最容易被忽视的泄漏来源，往往不是算术运算本身，而是内存访问地址依赖于秘密数据。当程序用秘密值作为数组下标去读取数据时，CPU 访问的缓存行、内存页乃至访问延迟都会随秘密变化，攻击者通过缓存计时、页错误、分支预测等侧信道即可反推出密钥。本节聚焦查表、S 盒、预计算表和数组索引这四类典型场景，剖析泄漏机制并给出可落地的消除策略。

一、泄漏的物理根源：地址即信息

现代处理器为提升性能引入了多级缓存、预取器和乱序执行。当访问 table[secret] 时，若 secret 落在不同的缓存行，命中与未命中的时间差可达数十到数百个时钟周期。攻击者通过 Prime+Probe、Flush+Reload 等手段测量这些差异，就能逐字节恢复索引值。更严重的是，即使数据本身不离开 CPU，地址总线上的活动、TLB 命中情况和分支预测器的状态都可能被观测。因此，只要访问地址与秘密相关，就存在泄漏风险，这与是否加密数据无关。

二、四类典型场景的泄漏机制

查表（Lookup Table）：常见于 AES 的 T 表实现、DES 的置换表、以及各类预计算乘法表。以 AES-128 的 T 表为例，每轮用状态字节索引 4 个 1KB 的表，索引值直接来自密钥异或后的中间状态。攻击者只需知道哪个缓存行被访问，就能缩小候选密钥范围。

S 盒（S-Box）：S 盒本质是一张 256 字节的替换表。软件实现中 sbox[state] 的访问模式完全暴露了状态字节。即使 S 盒只有 256 字节、恰好能放入一个缓存行，不同缓存行之间的访问差异仍可能被利用；若 S 盒跨多个缓存行，泄漏更明显。

预计算表：为加速模幂、椭圆曲线标量乘或密钥扩展，常预先计算 g^i、i·P 等表。标量或指数作为索引时，访问序列直接反映秘密比特。例如窗口法标量乘中，每个窗口值决定访问哪个预计算点。

数组索引：更一般地，任何 arr[f(secret)] 形式都危险。典型如根据密钥比特选择分支后访问不同数组、根据 S 盒输出更新状态数组等。这类模式在 C 代码中往往以 if (bit) a[i]=...; else b[i]=...; 出现，既泄漏地址又泄漏分支。

三、消除策略：从“避免”到“等价化”

策略一：全表扫描（Constant-Time Lookup）。最直接的方法是不用秘密做下标，而是遍历整张表，用掩码比较选出目标值。例如实现 256 字节 S 盒：

uint8_t ct_sbox_lookup(const uint8_t sbox[256], uint8_t idx) {
    uint8_t result = 0;
    for (int i = 0; i < 256; i++) {
        // 若 i == idx，mask 为 0xFF，否则为 0x00
        uint8_t mask = (uint8_t)(-(i == idx));
        result |= sbox[i] & mask;
    }
    return result;
}

该实现每次固定访问 256 个表项，地址序列与 idx 无关。代价是性能下降约 256 倍，因此实际中常配合位切片或查表分块优化。注意 i == idx 的比较本身必须是常数时间的，编译器可能将其优化为分支，需用 volatile 或内联汇编约束。

策略二：位切片（Bitslicing）。将 S 盒表示为布尔函数，用逻辑门直接计算输出，彻底消除内存访问。AES 的 S 盒可分解为有限域求逆加仿射变换，用 100 多个逻辑门实现。位切片适合批量处理，一次可并行计算 64 或 128 个字节，吞吐量反而可能超过查表。实现时需将数据按位转置，使每个比特位于独立寄存器位。

策略三：固定访问模式 + 掩码选择。当表较小且可放入寄存器或单个缓存行时，可先无条件读取所有候选，再用掩码选择。例如 16 项预计算表：

// 假设 table[16] 已加载到局部数组
uint32_t ct_select16(const uint32_t table[16], uint8_t idx) {
    uint32_t acc = 0;
    for (int i = 0; i < 16; i++) {
        uint32_t mask = (uint32_t)(-(i == idx));
        acc |= table[i] & mask;
    }
    return acc;
}

若表项为 32 位，16 项共 64 字节，恰好一个缓存行，访问模式完全固定。对于更大的表，可按缓存行分块，先固定访问所有块，再在块内选择。

策略四：预取与混淆。在访问真实地址前后，插入对无关地址的访问，打乱攻击者的测量。例如在查表前先访问一个随机但固定的填充数组，使缓存状态不可预测。但这种方法只能增加噪声，不能从根本上消除泄漏，适合作为辅助手段。

四、工程实践中的检查与验证

消除秘密相关内存访问后，必须验证效果。常用工具包括：dudect，通过统计测试判断执行时间是否与输入相关；ctgrind，基于 Valgrind 标记秘密数据，检测其是否影响分支或地址；缓存模拟器，如 Cachegrind，可统计不同输入下的缓存命中差异。实际项目中，建议对每个查表操作做一次“地址依赖审计”：列出所有数组访问，标记索引是否来自秘密，对可疑项逐一替换为常数时间实现。

总结而言，秘密相关内存访问的消除核心在于：让地址序列与秘密解耦。全表扫描、位切片、固定模式掩码选择是三种基本手段，分别适用于不同表大小和性能预算。工程中应结合审计、工具验证和汇编检查，确保实现真正达到常数时间。