如何在后量子密码学库中避免侧信道攻击？-编程实验室

1. 引言

Trail of Bits 的加密团队近期发布了其开源纯 Go 实现的 ML-DSA (FIPS-204) 和 SLH-DSA (FIPS-205) 两个 NIST 标准化的后量子签名算法。这些实现已经经过了多个密码学家的工程设计和审查。

https://github.com/trailofbits/ml-dsa（FIPS-204）（Go）
https://github.com/trailofbits/go-slh-dsa（FIPS-205）（Go）

本文将详细介绍在 ML-DSA (FIPS-204) 和 SLH-DSA (FIPS-205) 代码实现中所做的一些工作，确保其是常量时间的。特别是，这些技巧适用于 ML-DSA (FIPS-204) 算法，防止诸如 KyberSlash 等攻击，但它们也适用于任何需要分支或除法的加密算法。

2. 实现常量时间 FIPS-204 的道路

SLH-DSA (FIPS-205) 相对容易实现，并且不会引入侧信道攻击，因为它是基于从哈希函数构建的伪随机函数，但 ML-DSA (FIPS-204) 规范包含了几个整数除法操作，这就需要更小心的处理。

除法是早期 Kyber 实现中发生 KyberSlash 时间攻击的根本原因，后来该算法变成了 ML-KEM (FIPS-203)。在此希望在实现中完全避免这种风险。

每个 ML-DSA 参数集（ML-DSA-44、ML-DSA-65 和 ML-DSA-87）都包括几个影响算法行为的其他参数。其中一个是叫做γ 2 γ_2γ2的低阶四舍五入范围。

γ 2 γ_2γ2总是一个整数，但它的值取决于参数集。

对于 ML-DSA-44，γ 2 γ_2γ2等于 95232；
对于 ML-DSA-65 和 ML-DSA-87，γ 2 γ_2γ2等于 261888。

ML-DSA 指定了一个名为Decompose的算法，将一个域元素转换为两个组件（r 1 r_1r1,r 0 r_0r0），使得( r 1 ⋅ 2 γ 2 ) + r 0 (r_1 \cdot 2γ_2) + r_0(r1⋅2γ2)+r0等于原始域元素。这需要在一步中除以2 γ 2 2γ_22γ2，并在另一步中计算2 γ 2 2γ_22γ2的余数。

若要求 AI 来实现 Decompose 算法，将得到如下代码：

// 此代码样本由 Claude AI 生成。// 不安全 - 请勿使用。// 这里 `alpha` 等于 `2 * γ2`，`r` 是域元素：funcDecomposeUnsafe(r,alphaint32)(r1,r0int32){// 确保 r 在范围 [0, q-1] 内r=r%qifr<0{r+=q}// 将 r 中心化到 0（映射到范围 [-(q-1)/2, (q-1)/2]）ifr>(q-1)/2{r=r-q}// 计算 r1 = round(r/alpha)，其中 round 是四舍五入，// 其中相等时向零取整ifr>=0{r1=(r+alpha/2)/alpha}else{r1=(r-alpha/2+1)/alpha}// 计算 r0 = r - r1*alphar0=r-r1*alpha// 如果 r0 太大，调整 r1ifr0>alpha/2{r1++r0-=alpha}elseifr0<-alpha/2{r1--r0+=alpha}returnr1,r0}

然而，这违反了密码学工程的最佳实践：

1）该代码明显使用了除法和取模运算符。
2）包含了多个基于域元素派生值的分支操作。

3. Zen与无分支密码学艺术

防止密码学算法中出现分支的直接方法是始终执行条件语句的两侧（真和假），然后基于条件使用常量时间的条件交换来获得正确的结果。这涉及到位掩码、二补码和异或（XOR）操作。

将该函数中的分支去除后，代码看起来像这样：

// 这是另一个 AI 生成的代码示例。// 不安全 - 请勿使用。funcDecomposeUnsafeBranchless(r,alphaint32)(r1,r0int32){// 确保 r 在范围 [0, q-1] 内r=r%q r+=q&(r>>31)// 如果 r < 0，则加上 q（使用算术右移）// 将 r 中心化到 0（映射到范围 [-(q-1)/2, (q-1)/2]）mask:=-((r-(q-1)/2-1)>>31)// 如果 r > (q-1)/2，则 mask = -1，否则为 0r-=q&mask// 计算 r1 = round(r/alpha)，其中四舍五入时向零取整// 对于 r >= 0：r1 = (r + alpha/2) / alpha// 对于 r < 0：r1 = (r - alpha/2 + 1) / alphasignMask:=r>>31// 如果 r < 0，则 signMask = -1，否则为 0offset:=(alpha/2)+(signMask&(-alpha/2+1))// r >= 0 时为 alpha/2，否则为 -alpha/2 + 1r1=(r+offset)/alpha// 计算 r0 = r - r1*alphar0=r-r1*alpha// 如果 r0 太大，调整 r1（无分支）// 如果 r0 > alpha/2：r1++，r0 -= alpha// 如果 r0 < -alpha/2：r1--，r0 += alpha// 检查 r0 > alpha/2adjustUp:=-((r0-alpha/2-1)>>31)// 如果 r0 > alpha/2，则为 -1，否则为 0r1+=adjustUp&1r0-=adjustUp&alpha// 检查 r0 < -alpha/2adjustDown:=-((-r0-alpha/2-1)>>31)// 如果 r0 < -alpha/2，则为 -1，否则为 0r1-=adjustDown&1r0+=adjustDown&alphareturnr1,r0}

这解决了条件分支问题；然而，还没有完成。仍然存在麻烦的除法运算符。

4. 无除法：无除法算法（Undivided by time: Division-free algorithms）

前面提到的常量时间条件交换技巧也可以用来在常量时间内实现整数除法。

funcDivConstTime32(nuint32,duint32)(uint32,uint32){quotient:=uint32(0)R:=uint32(0)// 处理的是32位整数，因此迭代32次b:=uint32(32)i:=bforrangeb{i--R<<=1// R(0) := N(i)R|=((n>>i)&1)// Sub32()中的交换操作看起来像这样：// 如果余数 > d，交换 == 0// 如果余数 == d，交换 == 0// 如果余数 < d，交换 == 1Rprime,swap:=bits.Sub32(R,d,0)// 对Sub32的逻辑取反来进行条件交换swap^=1/* 期望： 如果 R > D，则交换 = 1 如果 R == D，则交换 = 1 如果 R < D，则交换 = 0 */// Qprime := Q// Qprime(i) := 1Qprime:=quotient Qprime|=(1<<i)// 条件交换：mask:=uint32(-swap)R^=((Rprime^R)&mask)quotient^=((Qprime^quotient)&mask)}returnquotient,R}

这个代码按预期工作，但它比较慢，因为它需要完整的循环迭代来计算商和余数的每一位。可以做得更好。

5. 一个精妙的优化技巧：Barrett约简

由于对于给定的参数集，值γ 2 γ_2γ2是固定的，并且除法和取模操作是针对2 γ 2 2γ_22γ2进行的，可以使用Barrett约简，并通过预计算的值来代替除法。

Barrett约简涉及乘以倒数（在本情况下是2 64 / 2 γ 2 2^{64}/2γ_2264/2γ2），然后执行最多两次修正减法来得到余数。商是该计算的副产物。

// 计算 (n/d, n%d)，给定 (n, d)funcDivBarrett(numerator,denominatoruint32)(uint32,uint32){// 由于 d 总是 2 * γ2，可以预计算 (2^64 / d) 并使用它varreciprocaluint64switchdenominator{case190464:// 2 * 95232reciprocal=96851604889688case523776:// 2 * 261888reciprocal=35184372088832default:// 回退到慢速除法returnDivConstTime32(numerator,denominator)}// Barrett约简hi,_:=bits.Mul64(uint64(numerator),reciprocal)quo:=uint32(hi)r:=numerator-quo*denominator// 使用 bits.Sub32 进行两步修正（常数时间）fori:=0;i<2;i++{newR,borrow:=bits.Sub32(r,denominator,0)correction:=borrow^1// 如果 r >= d，则修正 = 1；如果 r < d，则修正 = 0mask:=uint32(-correction)quo+=mask&1r^=mask&(newR^r)// 使用 XOR 的条件交换}returnquo,r}

通过这个有用的函数，现在可以[无分支、无除法地实现Decompose](https://github.com/trailofbits/ml-dsa/blob/9fd8970f6bbad89baa5ddc0a45832bc8bcd5caf1/internal/field/field.go#L114-L160)。