如何在我们新的后量子Go密码学库中避免侧信道
Trail of Bits密码学团队正在发布我们开源的纯Go实现的ML-DSA（FIPS-204）和SLH-DSA（FIPS-205），这是两种NIST标准化的后量子签名算法。这些实现已经由我们的多位密码学家进行工程设计和审查，因此如果您或您的组织正在寻求为数字签名过渡到后量子支持，请尝试使用它们！
本文将详细介绍我们为确保实现是恒定时间所做的一些工作。这些技巧特别适用于ML-DSA（FIPS-204）算法，可防止像KyberSlash这样的攻击，但它们也适用于任何需要分支或除法的密码算法。
通往恒定时间FIPS-204之路
SLH-DSA（FIPS-205）相对容易实现而不引入侧信道，因为它基于从哈希函数构建的伪随机函数，但ML-DSA（FIPS-204）规范包括几个整数除法，这需要更仔细的考虑。
除法是称为KyberSlash的定时攻击的根本原因，该攻击影响了Kyber的早期实现，后来成为ML-KEM（FIPS-203）。我们希望在实现中完全避免这种风险。
每个ML-DSA参数集（ML-DSA-44、ML-DSA-65和ML-DSA-87）都包含几个影响算法行为的其他参数。其中一个称为𝛾2，即低阶舍入范围。
𝛾2始终是一个整数，但其值取决于参数集。对于ML-DSA-44，𝛾2等于95232。对于ML-DSA-65和ML-DSA-87，𝛾2等于261888。
ML-DSA指定了一种称为Decompose的算法，该算法将字段元素转换为两个分量（𝑟1, 𝑟0），使得（𝑟1⋅2𝛾2）+𝑟0等于原始字段元素。这需要在一个步骤中除以2𝛾2，在另一个步骤中计算2𝛾2的余数。
如果您要求AI为您实现Decompose算法，您将得到类似这样的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
// 此代码示例由Claude AI生成。
// 不安全 -- 请勿使用。
//
// 这里，`alpha`等于`2 * γ2`，`r`是字段元素：
func DecomposeUnsafe(r, alpha int32) (r1, r0 int32) {
// 确保r在范围[0, q-1]内
r = r % q
if r < 0 {
r += q
}
// 将r围绕0居中（映射到范围[-(q-1)/2, (q-1)/2]）
if r > (q-1)/2 {
r = r - q
}
// 计算r1 = round(r/alpha)，其中round是四舍五入到最接近的整数
// 平局时向零舍入
if r >= 0 {
r1 = (r + alpha/2) / alpha
} else {
r1 = (r - alpha/2 + 1) / alpha
}
// 计算r0 = r - r1*alpha
r0 = r - r1*alpha
// 如果r0太大，调整r1
if r0 > alpha/2 {
r1++
r0 -= alpha
} else if r0 < -alpha/2 {
r1--
r0 += alpha
}
return r1, r0
}
|
然而，这违反了密码工程最佳实践：
- 此代码公然使用除法和模运算符。
- 它包含几个基于字段元素派生值的分支。
禅与无分支密码学的艺术
在任何密码算法中防止分支的直接方法是始终执行条件的双方（真和假），然后基于条件使用恒定时间的条件交换来获得正确结果。这涉及位掩码、二进制补码和异或（XOR）。
从此函数中移除分支看起来像这样：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
// 这是另一个AI生成的代码示例。
// 不安全 -- 请勿使用。
func DecomposeUnsafeBranchless(r, alpha int32) (r1, r0 int32) {
// 确保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，否则为0
r -= q & mask
// 计算r1 = round(r/alpha)，平局时向零舍入
// 对于r >= 0: r1 = (r + alpha/2) / alpha
// 对于r < 0: r1 = (r - alpha/2 + 1) / alpha
signMask := r >> 31 // 如果r < 0，signMask = -1，否则为0
offset := (alpha/2) + (signMask & (-alpha/2 + 1)) // 如果r >= 0，则为alpha/2，否则为-alpha/2 + 1
r1 = (r + offset) / alpha
// 计算r0 = r - r1*alpha
r0 = r - r1*alpha
// 如果r0太大，调整r1（无分支）
// 如果r0 > alpha/2: r1++, r0 -= alpha
// 如果r0 < -alpha/2: r1--, r0 += alpha
// 检查r0 > alpha/2
adjustUp := -((r0 - alpha/2 - 1) >> 31) // 如果r0 > alpha/2，则为-1，否则为0
r1 += adjustUp & 1
r0 -= adjustUp & alpha
// 检查r0 < -alpha/2
adjustDown := -((-r0 - alpha/2 - 1) >> 31) // 如果r0 < -alpha/2，则为-1，否则为0
r1 -= adjustDown & 1
r0 += adjustDown & alpha
return r1, r0
}
|
这解决了我们的条件分支问题；然而，我们还没有完成。仍然存在麻烦的除法运算符。
时间不分：无除法算法
恒定时间条件交换的前一个技巧也可以用来实现恒定时间的整数除法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
func DivConstTime32(n uint32, d uint32) (uint32, uint32) {
quotient := uint32(0)
R := uint32(0)
// 我们处理的是32位整数，因此我们迭代32次
b := uint32(32)
i := b
for range b {
i--
R <<= 1
// R(0) := N(i)
R |= ((n >> i) & 1)
// 来自Sub32()的交换将如下所示：
// 如果余数 > d，交换 == 0
// 如果余数 == d，交换 == 0
// 如果余数 < d，交换 == 1
Rprime, swap := bits.Sub32(R, d, 0)
// 反转sub32的逻辑以进行条件交换
swap ^= 1
/*
期望：
如果R > D 那么交换 = 1
如果R == D 那么交换 = 1
如果R < D 那么交换 = 0
*/
// Qprime := Q
// Qprime(i) := 1
Qprime := quotient
Qprime |= (1 << i)
// 条件交换：
mask := uint32(-swap)
R ^= ((Rprime ^ R) & mask)
quotient ^= ((Qprime ^ quotient) & mask)
}
return quotient, R
}
|
这按预期工作，但速度很慢，因为它需要完整的循环迭代来计算商和余数的每一位。我们可以做得更好。
一个巧妙的优化技巧：Barrett约简
由于值𝛾2对于给定参数集是固定的，并且除法和模运算符是针对2𝛾2执行的，我们可以使用Barrett约简与预计算值来代替除法。
Barrett约简涉及乘以倒数（在我们的例子中，是264/2𝛾2），然后执行最多两次校正减法以获得余数。商作为此计算的副产品产生。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
// 给定(n, d)计算(n/d, n%d)
func DivBarrett(numerator, denominator uint32) (uint32, uint32) {
// 由于d始终是2 * gamma2，我们可以预计算(2^64 / d)并使用它
var reciprocal uint64
switch denominator {
case 190464: // 2 * 95232
reciprocal = 96851604889688
case 523776: // 2 * 261888
reciprocal = 35184372088832
default:
// 回退到慢速除法
return DivConstTime32(numerator, denominator)
}
// Barrett约简
hi, _ := bits.Mul64(uint64(numerator), reciprocal)
quo := uint32(hi)
r := numerator - quo * denominator
// 使用bits.Sub32进行两次校正步骤（恒定时间）
for i := 0; i < 2; i++ {
newR, borrow := bits.Sub32(r, denominator, 0)
correction := borrow ^ 1 // 如果r >= d，则为1；如果r < d，则为0
mask := uint32(-correction)
quo += mask & 1
r ^= mask & (newR ^ r) // 使用XOR进行条件交换
}
return quo, r
}
|
有了这个有用的函数，我们现在可以实现没有分支或除法的Decompose。
迈向后量子安全未来
Go中后量子签名算法的可用性是迈向未来的一个步骤，在这个未来中，即使开发出与密码学相关的量子计算机，互联网通信仍然安全。
如果您对高保证密码学感兴趣，即使面对新型对手（包括但不限于未来的量子计算机），请立即联系我们的密码学团队。