FourQ 是一种高性能的椭圆曲线加密算法，专为 128 位安全级别设计，由 Cloudflare 的 CIRCL 库实现。该库旨在支持后量子密码和椭圆曲线密码的实验性部署。然而，在 FourQ 的乘法（mul）和加法（add）操作中，存在定时和缓存侧信道泄漏风险，这些漏洞可能允许攻击者通过观察执行时间或缓存访问模式来推断私钥，从而破坏密钥封装机制（KEM）的安全性。本文将分析这些泄漏机制，并提出使用掩码算术的常时对策，以实现安全的 KEM 部署。
FourQ 曲线基于 Mersenne 素数 p = 2^127 - 1 定义，其坐标系统采用扩展扭曲 Edwards 形式，支持高效的群运算。CIRCL 库中的 FourQ 实现利用了该曲线的丰富算术特性，如四维 Gallant-Lambert-Vanstone 分解，以最小化椭圆曲线群操作数量。在标量乘法过程中，mul 和 add 操作是核心：mul 涉及点倍运算（point doubling），add 则处理点加（point addition）。这些操作在有限域 F_p 上执行，依赖于快速的模乘和模约简算法。
证据显示，FourQ 的 mul/add 操作易受侧信道攻击影响。首先，定时泄漏源于非常时实现：在传统实现中，条件分支（如基于输入的 if-else）会导致执行路径差异，产生可观测的时间偏差。例如，在 Hertzbleed 攻击中（CVE-2022-24436），研究人员将电源侧信道转化为远程定时攻击，影响了 CIRCL 库的解封装性能。该攻击利用动态电压频率缩放（DVFS），通过监控响应时间推断功耗变化，从而提取 SIKE 等算法的密钥。Cloudflare 已更新 CIRCL 以缓解此问题，但 FourQ 的 mul 操作中，模约简步骤的循环迭代次数可能依赖于中间值，导致类似定时泄漏。
其次，缓存侧信道泄漏源于内存访问模式。在 mul/add 中，访问查找表（如预计算的 Edwards 加法公式）会填充 CPU 缓存，攻击者通过 Prime+Probe 或 Flush+Reload 技术观察缓存命中率。例如，在嵌入式设备上，FourQ 的实现可能使用非掩码的坐标计算，暴露坐标点的比特表示。学术研究（如 CHES 2017 论文）证实，未保护的 FourQ 标量乘法在 ARM Cortex-M4 上易受差分功率分析（DPA）攻击，泄漏私钥比特。实验显示，仅需数百万条功率轨迹即可恢复密钥。
为应对这些泄漏，常时实现是基础对策。常时代码确保所有分支路径执行相同指令序列，避免定时差异。在 CIRCL 中，FourQ 的 DH 实现已采用常时 mul/add：例如，使用条件交换（cswap）代替分支，在 add 操作中统一计算两种可能的结果并选择一个。这类似于 Curve25519 的 Montgomery 梯子，但 FourQ 的 Edwards 坐标允许更快的加法公式（12M + 2S + 2D + 1I vs. 10M + 1S + 1D + 2I）。
进一步增强，使用掩码算术隐藏中间值。掩码算术将敏感变量拆分为多个共享（shares），如布尔掩码（每个比特随机化）或算术掩码（加法模 p 随机值）。在 FourQ mul 中，对坐标点 (X, Y) 应用 d-ary 掩码：X_s = X + r_s mod p，其中 r_s 是随机掩码，s 为共享数（推荐 2-3 阶）。add 操作需刷新掩码：新掩码 r' = sum r_s mod p，确保输出无泄漏。论文《FourQ on Embedded Devices with Strong Countermeasures》提出利用 FourQ 的富算术（如快速平方）优化掩码 mul，减少开销至 2-3 倍。
在 KEM 部署中，这些对策需参数化配置。推荐阈值：共享数 d=3（平衡安全与性能），噪声注入阈值 10-20%（模拟 DVFS 波动）。监控要点包括：执行时间方差 <5%（使用高精度时钟测量），缓存命中率稳定（通过 perf 工具监控 L1/L2 访问）。回滚策略：若检测异常泄漏，切换至备用曲线如 Curve25519。嵌入式部署参数：ARM Cortex-M4 上，掩码 FourQ ECDH 需 ~1.5M 周期（vs. 非掩码 500K），功耗增加 20%，但抵抗 10^6 轨迹 DPA。
实施清单：
- 审计 CIRCL FourQ 代码，确保 mul/add 无条件分支。
- 集成掩码库（如 CIRCL 的 poly 模块），在标量乘法前刷新掩码。
- 测试侧信道：使用 ChipWhisperer 采集 10^5 轨迹，验证无相关性（Pearson 系数 <0.1）。
- KEM 封装：使用 FourQ DH 派生共享密钥，结合 AES-GCM 加密，阈值重试 3 次。
- 部署监控：集成 Prometheus 记录时间/缓存指标，警报阈值 >10% 偏差。
这些对策使 FourQ 在 CIRCL 中适用于安全 KEM，如 HPKE 协议，确保后量子过渡中的鲁棒性。尽管性能开销存在（5-11% 如 Hertzbleed 缓解），收益远超风险。
资料来源：