常数时间国密算法（二）：SM2的代码分支规避

见贤思齐

本期作者郭伟基哔哩哔哩技术专家负责B站高能链密码学、区块链相关技术研究与开发，特别是密码学技术的安全、高效实现，以及应用密码学技术实现链上隐私保护和业务赋能。背景区块链离普通人越来越近了。相应地，安全问题也会逐渐凸显出来。作为区块链基础设施建设者以及重要参与者，我们十分重视链的安全和用户资产的安全。其中一个至关重要的环节便是支持国家的商密算法，特别是其中的SM2椭圆曲线公钥密码算法、SM3杂凑算法、SM4分组密码算法。前面我们介绍SM2查表保护技术的时候，提到了代码分支问题。这篇文章具体讨论代码分支相关的安全隐患和规避代码分支的一些技术。代码分支的问题这里说的代码分支，特指根据敏感的数据作出代码分支，从而使得外界可以根据代码分支所造成的可观测效应，反推敏感数据的具体数值，进而导致秘密值的破解。我们回顾一下DaA技术的一个版本（如果您需要温习何为DaA技术，以及相关的椭圆曲线密码学技术，请参阅《常数时间国密算法（一）》）：func scalarMult(q *SM2Point, x scalar) (*SM2Point, error) { ?out := NewSM2Point() ?for _, bit := range x.bits { //从高位到低位遍历 ? ?out.Double(out) ? ?if bit == 1 { ? ? ?out.Add(out, q) ? ?} ?} ?return out, nil}在代码的第5行，根据敏感值取1还是0，作出了分支。那么这种分支，可能会造成哪些外界可观测的效应呢？一个不完全的列表是：1）造成电压波动或电磁辐射的变化；2）造成相关内存地址的访问速度变化。我们只能说这个列表是不完全的，因为只要这种分支存在，就有可能有各种可观测效应被攻击者发掘出来加以利用。接下来，我们先来具体分析以上两种攻击的依据；之后，再来讨论防御的要点。点加和倍点运算的区别要想理解为何一个代码分支会造成电压波动或者电磁辐射的变化，我们需要先了解椭圆曲线的点加运算和倍点运算有何不同。如下为SM2所使用的椭圆曲线方程：y2 = x3 - 3x + b ? ? ? ? ?（1）其中b为某个256位的大整数。在接下来的计算中，我们并不需要使用b的具体数值，因此这里就略去了。为了计算点加或者倍点运算的结果，我们需要确定一条既定直线与椭圆曲线的交点R，然后取其在X轴另一侧的对称点-R作为结果（X坐标不变，Y坐标取反）（如您不记得椭圆曲线上点的运算定义，请参阅《常数时间国密算法（一）》）。在点加的情况下，这条既定直线由已知的两个点P和Q所确定；在倍点的情况下，由点P和椭圆曲线方程共同确定。我们只需要计算出既定直线的斜率λ，再加以简单计算，便可得到R的坐标。其中，P，Q，R三点的横坐标满足如下关系：xp + xq + xr = λ2在倍点运算情况下，P和Q可以认为重合在一起，因此xp = xq。得到斜率λ和横坐标xr之后，再计算纵坐标就很简单了：?由于：λ = (yr - yp) / (xr - xp)?得到：? ?-yr = λ(xp - xr) - yp这里计算-yr，因为我们需要-R的坐标。现在回过头来计算斜率。为了求得经过P(xp, yp)和Q(xq, yq)的斜率λpq，在点加的情况下，只需要计算：λpq = (yq - yp) / (xq - xp) （2）上式有一个特例是P和Q正好沿X轴对称，因此分母为0。在这种情况下，P + Q的结果是无穷远点，也就是零点。而在倍点的情况下，P和Q相当于重合了，那么xq - xq就会得到零，因此无法使用上式进行计算。为了求得直线在P(xp, yp)与椭圆曲线相切处的斜率，其实也就是椭圆曲线在该点的斜率，我们需要对（1）进行求导：2y * y' = 3x2 - 3从而得到斜率λp为：λp = (3xp2 - 3) / 2yp ? （3）现在重点来了。仔细观察（2）和（3）式，可以发现它们的计算量是不一样的。注意，这里不是简单的四则运算，是定义在某个256位长的素域上的计算，计算量较大，其计算过程能够对处理器造成压力。其中计算量最大的为除法，在SM2中为素域的乘法求逆；但这是（2）和（3）都有的，并不能造成区别。主要的区别在于（3）的分子需要额外计算一次平方，这一般需要多次32位或64位乘法计算，辅以一定数量的加减法计算来达成。这种计算量的差别所造成的外部可观测效应，足以供外部观察者判断计算任务的不同。具体而言，在小型设备如单片机上（某些加密资产硬件钱包使用单片机处理器），前述计算压力足以造成电压的波动；而在大型的现代处理器上，能够造成电磁辐射模式的变化；这些都是外部可观测的效应。有了这些波动或者变化，就能够看出来何时在执行点加运算，何时在执行倍点运算；通过结合算法（算法细节一般无法保密，一个系统的安全性也不应该依赖算法细节的保密），便能反推分支处的具体数据，进而破解标量值。我们已经在《常数时间国密算法（一）》中提供了一个研究结果，为分析电磁辐射信号变化导致私钥被提取。可见对此种攻击实施防范措施，并非杞人忧天。这也是高能链的用心之处：我们始终把用户的资产安全和隐私保护放在十分重要的位置上，为此不惜投入巨大的研发成本。（注意：在实际实现中，由于需要避免计算量巨大的素域求逆运算，一般需要将点的X-Y坐标转换为雅可比坐标再加以计算，因此以上的算式只是一个基础，并非最终计算的版本，但点加和倍点运算的计算量差异，仍然显著存在，上述分析亦仍然有效）内存的变化如果计算量的不同，会造成分支的选择数值被侧信道泄露，那么有没有可能改进一下算法，使得点加和倍点运算的计算量没有区别呢？这种算法确实存在，称为Montgomery Ladder：func scalarMultLadder(q *SM2Point, x scalar) (*SM2Point, error) { out := NewSM2Point() t := NewSM2Point().Set(q) //拷贝 for _, bit := range x.bits { //从高位到低位遍历 if bit == 1 { out.Add(out, tmp) tmp.Double(tmp) } else { tmp.Add(out, tmp) out.Double(out) } } return out, nil}容易看出，不管用来分支的bit取值为何，外部可见的电压波动或电磁辐射变化的模式总是一致的：总是先计算一次点加，再计算一次倍点。这样确实能够防范基于运算量不同的那些攻击方式。然而，以上Montgomery Ladder算法仍然针对敏感值产生了分支。所产生的两个代码分支，虽然计算量和电压波动、电磁辐射变化的模式都一样，却在其它地方产生了外部可观测的影响：指令缓存。我们知道，在计算机执行计算任务的时候，处理器不停地读取下一条指令，并根据指令去操作相应的数据，以此完成计算任务。为了加速计算，现代的处理器都配备了高速缓存，避免高速运行的处理器等待慢速的主存储器。高速缓存又可以分为指令缓存和数据缓存，分别用来加速对指令的读取，以及对数据的读写。如果一条指令刚刚被执行过，处理器会判断其有可能很快还要被用到，于是会将其保留在高速缓存中。这本来并不是什么安全问题，但是部分处理器的架构设计缺陷，使得一个进程可以操纵其它进程的缓存，由此造成Flush+Reload方法可用于攻击Montgomery Ladder算法在这些处理器上的运行实例。具体而言，由于从主存储器加载指令相比从指令高速缓存加载要慢得多，攻击程序监控某几个指令地址的访问时间变化，便能推断其对应的代码分支是否被执行，从而结合以上算法，便能推断用来分支的敏感值为何，进而破解相关的秘密值。感兴趣的读者可以进一步参阅：Yuval Yarom, Naomi Benger.?Recovering OpenSSL ECDSA Nonces Using the FLUSH+RELOAD?Cache Side-channel Attack。这篇论文发表于2014年，所述处理器缺陷是否已经修复，目前未能查到相关信息。但更重要的仍然是尽量避免基于敏感值去作代码分支。防御技术要点在《常数时间国密算法（一）》中，我们通过选择方法，实现了对查表操作的保护，同时也实现了对代码分支的规避：无论选择出来的点是零点还是从预计算表里提取出来的，我们都执行一次点加运算。这个方法还需要进一步扩展：不仅是查表，在所有的计算中，为了避免基于敏感值作代码分支，我们都可以考虑应用选择方法。就DaA算法而言，我们可以使用选择方法对其进行简单改造。首先我们需要一个点级别的选择方法。基于已经在上一篇文章中讲解过的对64位整数的选择方法，这并不难构造，这里略过。以下为改造后的DaA算法：func selectPoint(out *SM2Point, mask int, a, b, *SM2Point) { //mask取0或者1 //如果mask为0，out的内容就是a，如果mask为1，out的内容就是b}func scalarMultSelect(q *SM2Point, x scalar) (*SM2Point, error) { ?out := NewSM2Point() ?zero := NewSM2Point() ?selected := NewSM2Point() ?for _, bit := range x.bits { //从高位到低位遍历 ? ?out.Double(out) ? ?selectPoint(&selected, bit, zero, q) ? ?out.Add(out, selected) ?} ?return out, nil}selectPoint函数在bit为1的时候，使得selected的内容为q，否则为zero（被初始化为零点）。后面无脑执行一次点加运算即可。在这里，跟零点进行点加运算，并不会实质改变该点（有可能改变其内容，例如在雅可比坐标系中，一个点由X-Y-Z三个坐标确定，同一个点可以对应多组坐标值）。再一次，这并非高能链在生产系统上使用的算法。选择方法使得点加运算的次数大为增加，性能下降，而实际生产应用则需要在优化算法（w-NAF等）的基础上再去叠加点加运算。总结代码分支规避并非一个技术点，它更多是一个安全要求，其重点并不在于针对每种攻击去消除或掩盖相应的效应，而是要从源头入手，避免根据敏感数据作出代码分支。因此，需要针对不同的上下文，采取不同的技术手段。除了基于Select的方法，也可以有其它方案，甚至可以将相关算法整体更换掉，我们在后面会看到这类例子。