我们如何在新的后量子Go密码库中避免侧信道攻击 - Trail of Bits博客

Scott Arciszewski 2025年11月14日 密码学，Go，开源，后量子

通往常数时间FIPS-204之路

Trail of Bits密码学团队正在发布我们开源的纯Go实现，包括ML-DSA（FIPS-204）和SLH-DSA（FIPS-205），这是两种NIST标准化的后量子签名算法。这些实现经过我们数位密码学家的工程开发和审查，因此如果您或您的组织正在寻求为数字签名过渡到后量子支持，请尝试使用它们！

本文将详细介绍我们为确保实现是常数时间所完成的一些工作。这些技巧特别适用于ML-DSA（FIPS-204）算法，以防御KyberSlash等攻击，但它们也适用于任何需要分支或除法的密码算法。

SLH-DSA（FIPS-205）相对容易实现而不引入侧信道，因为它基于由哈希函数构建的伪随机函数。但ML-DSA（FIPS-204）规范包含多个整数除法，需要更仔细的考量。

除法是被称为KyberSlash的计时攻击的根本原因，该攻击影响了Kyber的早期实现（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


// 此代码示例由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()的交换将如下所示：
        // 如果 remainder > d,  swap == 0
        // 如果 remainder == d, swap == 0
        // 如果 remainder < d,  swap == 1
        Rprime, swap := bits.Sub32(R, d, 0)

        // 反转sub32的逻辑以进行条件交换
        swap ^= 1
        /*
            期望：
                如果 R > D  那么 swap = 1
                如果 R == D 那么 swap = 1
                如果 R < D  那么 swap = 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语言中后量子签名算法的可用性，是迈向一个即使未来出现与密码学相关的量子计算机，互联网通信仍能保持安全的未来的重要一步。

如果您对高保障密码学感兴趣，即使面对新型对手（包括但不限于未来的量子计算机），请立即联系我们的密码学团队。

如果您喜欢这篇文章，请分享： X LinkedIn GitHub Mastodon Hacker News

揭秘Go后量子密码库：如何消除侧信道攻击漏洞

本文深入探讨了Trail of Bits团队在实现ML-DSA和SLH-DSA后量子签名算法时，如何通过分支消除、无除法算法和Barrett约减等高级技术，确保Go代码的常数时间执行，有效防御类似KyberSlash的计时攻击。