我们如何在新的后量子Go密码学库中避免侧信道攻击
Trail of Bits密码学团队发布了我们对ML-DSA和SLH-DSA的开源纯Go实现，这是两种NIST标准化的后量子签名算法。这些实现已由我们的多位密码学家进行工程设计和审查，因此，如果您或您的组织希望将数字签名过渡到后量子支持，请尝试它们！
这篇文章将详细介绍我们为确保实现是常数时间所做的一些工作。这些技巧特别适用于ML-DSA算法，以防止像KyberSlash这样的攻击，但它们也适用于任何需要分支或除法的密码算法。
通往常数时间FIPS-204之路
SLH-DSA相对容易实现而不引入侧信道，因为它基于从哈希函数构建的伪随机函数。但ML-DSA规范包含多个整数除法，需要更仔细的考虑。
除法是名为KyberSlash的时序攻击的根本原因，该攻击影响了Kyber（后来成为FIPS-203）的早期实现。我们希望在我们的实现中完全避免这种风险。
每个ML-DSA参数集都包含几个影响算法行为的参数。其中之一称为𝛾2，即低阶舍入范围。
𝛾2始终是整数，但其值取决于参数集。对于ML-DSA-44，𝛾2等于95232。对于ML-DSA-65和ML-DSA-87，𝛾2等于261888。
ML-DSA指定了一种称为“分解”的算法，它将一个域元素转换为两个分量，使得这两个分量的组合等于原始域元素。这需要在一个步骤中除以2𝛾2，并在另一个步骤中计算对2𝛾2的余数。
无分支密码学之道
在任何密码算法中防止分支的直截了当的方法是始终执行条件的双方（真和假），然后基于条件使用常数时间的条件交换来获得正确结果。这涉及位掩码、二进制补码和异或操作。
从该函数中移除分支看起来像这样：
// 这是另一个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)，平局时向零舍入signMask:=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（无分支）adjustUp:=-((r0-alpha/2-1)>>31)// 如果r0 > alpha/2则为-1，否则为0r1+=adjustUp&1r0-=adjustUp&alpha adjustDown:=-((-r0-alpha/2-1)>>31)// 如果r0 < -alpha/2则为-1，否则为0r1-=adjustDown&1r0+=adjustDown&alphareturnr1,r0}这解决了我们的条件分支问题；然而，我们还没有完成。仍然存在麻烦的除法运算符。
不分时间：无除法算法
常数时间条件交换的技巧也可以用来以常数时间实现整数除法。
funcDivConstTime32(nuint32,duint32)(uint32,uint32){quotient:=uint32(0)R:=uint32(0)b:=uint32(32)i:=bforrangeb{i--R<<=1R|=((n>>i)&1)Rprime,swap:=bits.Sub32(R,d,0)swap^=1Qprime:=quotient Qprime|=(1<<i)mask:=uint32(-swap)R^=((Rprime^R)&mask)quotient^=((Qprime^quotient)&mask)}returnquotient,R}这按预期工作，但速度很慢，因为它需要完整的循环迭代来计算商和余数的每一位。我们可以做得更好。
一个巧妙的优化技巧：Barrett约减
由于对于给定的参数集，值𝛾2是固定的，并且除法和取模运算是针对2𝛾2执行的，我们可以使用Barrett约减和预计算值来代替除法。
Barrett约减涉及乘以一个倒数，然后执行最多两次校正减法以获得余数。商是这个计算的副产品。
// 给定(n, d)计算(n/d, n%d)funcDivBarrett(numerator,denominatoruint32)(uint32,uint32){varreciprocaluint64switchdenominator{case190464:// 2 * 95232reciprocal=96851604889688case523776:// 2 * 261888reciprocal=35184372088832default:returnDivConstTime32(numerator,denominator)}hi,_:=bits.Mul64(uint64(numerator),reciprocal)quo:=uint32(hi)r:=numerator-quo*denominatorfori:=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)}returnquo,r}有了这个有用的函数，我们现在可以在没有分支或除法的情况下实现Decompose。
迈向后量子安全的未来
Go语言中后量子签名算法的可用性，是朝着即使未来开发出与密码学相关的量子计算机，互联网通信也能保持安全的未来迈出的一步。
B66Q6Ou1tAlwnlpPPdAu77+nNUwoBs1zkLmuVVwDZNmtEHD7CcWCLNSFI1wkVFRejhRsmVmhCO2uCc++7o/0FRpkMJmW41wZ/JUCPNCf4DRB3K9QUwyxWXbeH74lT0B9IPoMv/9n2cTW0wGrEb4yKGmy2mGFX4/8QYyO6dU8rVA=
更多精彩内容 请关注我的个人公众号 公众号（办公AI智能小助手）
对网络安全、黑客技术感兴趣的朋友可以关注我的安全公众号（网络安全技术点滴分享）
