一种侧信道攻击Rainbow签名的算法

易海博

(深圳职业技术学院计算机工程学院 广东 深圳 518055)

随着量子计算机的不断发展，RSA和ECC等公钥密码面临着潜在威胁。文献[1]提出的一种在多项式时间内解决大整数因子分解和离散对数问题的量子算法表明量子计算机有能力破解RSA和ECC等公钥密码。但在公钥密码中存在少数几类密码算法不能被量子计算机攻破，它们是格密码(Lattice-based cryptography)、哈希密码(Hash-based cryptography)、基于编码的密码(code-based cryptography)以及多变量密码(MQ cryptography)[2]，被统称为后量子密码(post-quantum cryptography)。

在后量子密码中，多变量密码基于的数学困难问题是求解一组有限域上的多变量二次(multivariate quadratic, MQ)方程组，它被证明是NP(nondeterministic polynomial)困难问题，并且目前量子计算机并无较好的求解方法。多变量密码最早起源于20世纪80年代，第一种多变量密码算法是MI(Matsumoto Imai)加密算法。在数字签名算法方面，UOV(unbalanced oil-vinegar signature)、Rainbow、TTS(Tame transformation signature)等签名被认为是具有代表性的多变量签名算法[3-5]。

由于UOV、Rainbow、TTS等签名算法的抗量子计算攻击能力，它们的软件和硬件实现成为后量子密码领域研究的热点[6-12]。密码算法的硬件实现可以广泛运用于芯片领域，它除了要防御数学攻击，还同时需要防御侧信道攻击。侧信道攻击基于密码算法的硬件实现中泄露的信息进行破解，如能量消耗、电磁泄露、时间信息、声音等。相应的，常用的侧信道攻击方法包括时间攻击[13]、能量攻击[14]、电磁攻击[15]、故障攻击[16]等。

在侧信道攻击方法中，故障攻击的原理是尝试改变密码系统运行的环境，如电压、时钟、温度、光亮等，从而在密码运算过程中造成故障，观测相关变化，以达到破解密钥的目的。一种常用的故障攻击方法是对某一个寄存器使用激光束，导致寄存器的部分比特产生翻转，即从0变成1或从1变成0。故障攻击已经成功在攻击RSA签名中实施[17]。

能量攻击是常用的侧信道攻击方法，基于观测密码系统的能量变化而实现攻击。常用的能量攻击方法包括简单能量攻击SPA(simple power analysis)[18]和差分能量攻击DPA(differential power analysis)[19]。原始DPA(mono-bit DPA)针对寄存器单个比特进行观测，被扩展为multi-bit DPA，可以对某个中间运算结果的一组比特进行观测[20]。文献[20]对DPA进行再次扩展，即可以同时观测多个运算结果的功耗，这种方法被称为高阶DPA攻击。DPA攻击需要基于能量模型实现，如汉明重量模型和汉明距离模型[21]。一般来说，汉明距离模型更适合CMOS(complementary metal oxide semiconductor)密码系统攻击。

这些侧信道攻击方法被证明对不少对称密码系统有效，如DES(data encryption standard)、AES(advanced encryption standard)等[22]。但是，在侧信道攻击研究领域，针对多变量公钥密码进行侧信道攻击的成功例子很少，只有侧信道攻击方法[23-24]、多变量公钥密码的一种故障攻击方法[25]，且都只关注攻击理论的研究和讨论，并未涉及多变量密码的核心结构的攻击，还需要在真实环境下进一步论证。分析多变量签名算法的侧信道安全性对发现算法的漏洞，提高算法的安全性有重要价值。本文将多变量签名Rainbow作为目标，实施侧信道攻击。

1 Rainbow签名硬件实现

在多变量公钥密码中，Rainbow签名是油醋签名家族的一员，可以被看成多层的UOV签名。

1.1 Rainbow方案的选择

在Rainbow的所有安全方案中，本文选取了一种常用的方案Rainbow(10,10,4,3,10)作为硬件实现方案。它的安全级别达到802，在多项式时间内无法被数学分析攻击。Rainbow(10,10,4,3,10)由4层油醋结构组成。本文选定的Rainbow签名方案的参数如表1所示。签名生成包括第一次仿射变换、中心映射变换和第二次仿射变换，如图1所示。

表1 Rainbow签名方案

假定消息的散列值是 y (y0, y1, … ,y26)，它的长度是27字节，其中 y0, y1, … ,y26是 G F(28)的元素。而且，签名是 x (x0, x1, … ,x36)，它的长度是37字节，其中x0, x1, … ,x36是 G F(28)的元素。

图1 Rainbow签名生成过程

为了对消息的散列值 y (y0, y1, … ,y26)签名，需要进行如下计算：

式中，F是一个中心映射变换；L1和L2是两个可逆的仿射变换。

首先计算可逆仿射L1的逆变换：是可逆仿射变换的结果，的长度是27字节。L1的逆变换的形式为：

式中，A是规模为27×27的矩阵；b是维度为27的向量，A和b都被当作密钥来运算。

中心映射变换F由27个多变量多次多项式( f0, f1, … , f26)组成，它有如下形式：

中心映射F是4层的油醋结构，由27个多变量多次多项式组成，即 ( f0, f1, … , f26)被分成4层：

fi|i = 0 ,1,… ,9 ，共10个多项式；

fi|i = 1 0,11,12,13，共4个多项式；

fi|i = 1 4,15,16，共3个多项式；

fi|i = 1 7,18,… ,2 6，共10个多项式。

F的27个多变量多次多项式 ( f0,f1, … , f26)的定义为：

式中，Vi是醋变量；Oi是油变量；OiVj是油变量和醋变量的组合；ViVj是醋变量和醋变量的组合；ijα、ijβ、iγ、iδ和η是多变量多次多项式的系数，被当作私钥使用，η是常数。

多变量多次多项式包括5项，最高次数不超过二次，若将醋变量的数值代入多变量多次多项式，它将变换成关于油变量的一次多项式。通过4层的多项式系数求值和求解线性方程组，计算获得

1.2 Rainbow签名实现

为了攻击的普遍性，Rainbow签名实现基于原始方案，不采用优化手段。本文利用状态机的方式实现Rainbow签名设计，使用硬件描述语言Verilog作为编程语言，Xilinx公司开发的FPGA(fieldprogrammable gate array)工具ISE(integrated software environment)9.1作为编程工具，实现平台选取的是Xilinx FPGA。在FPGA测试通过后，将Verilog代码加载至Synopsis Design Compiler，签名所需时间为102.8 μs，等效门数约为15 490。

Rainbow签名的仿射变换由矩阵向量乘法和向量加法组成，中心映射变换由求解线性方程组和多项式系数求值组成。

下面是有限域加法、乘法、求逆和高斯消元运算的具体实现细节。

选择的有限域是8GF(2)，域的不可约多项式是有限域加法使用8GF(2)的加法运算；有限域乘法使用多项式基的一般乘法。假定a(x)和b(x)是8GF(2)的元素，那么c(x)=(a(x) × b(x) )mod f(x)是两者的乘积，其中 f(x)是GF(28)的不可约多项式。计算多项式相乘的结果，即 s0, s1, … ,s14：

模运算为：

c(x)(c7, c6, c5, … ,c0)是a(x)和b(x)的乘积，本文采用了基于费马小定理的求逆方法，假定β是GF(28)的元素，求逆过程如下：

计算 β2, β4, β8, β16, β32, β64和 β128可以并行进行， β-1是它们的乘积；需要求解4个线性方程组，这些方程组的系数矩阵的规模分别是10×10、4×4、3×3和10×10。本文采取有限域的高斯消元法作为求解线性方程组的方法：

在主元所在列选择一个非零元素作为主元；交换当前行与主元所在行的所有的元素，若当前行是主元所在行则不交换；对当前行所有的元素做归一操作；对当前行下面所有的元素做消元操作；结束本次迭代，重新选取下一列开始下一轮迭代；直到所有迭代完成，系数矩阵成为一个等效的上三角矩阵；接着使用回溯替代的方法对增广矩阵进行替代；完成回溯替代后，增广矩阵的最右一列(即常数项组成的向量)是线性方程组的解。

2 Rainbow签名侧信道攻击

2.1 总体方案

现有技术中，较少对Rainbow签名进行侧信道安全性分析，在一定程度上阻碍了Rainbow签名的广泛应用。针对Rainbow的侧信道分析可以分为对仿射变换L1、中心映射变换F、仿射变换L2的分析。

仿射变换L1：差分能量分析；中心映射变换F：故障分析结合差分能量分析；仿射变换L2：差分能量分析。图2对Rainbow的分析方法基于差分能量分析和故障分析。

图2 Rainbow分析过程

2.2 分析第一个仿射变换

对于第一个仿射变换，采用差分能量分析。假定y(y0, y1, … ,ym-1)是待签名的消息，是仿射变换=Ay+b的结果，A是m×m的矩阵，b是长度为m的向量，A和b是密钥。以计算 ai′j= aij× yi为例，aij是A第i行第 j列的元素(密钥)，yi是y第i个元素(消息)，ai′j是有限域乘法结果，均是有限域GF(2k)的元素。建立基于汉明距离的多比特差分能量分析模型(以下简称汉明距离模型)，那么攻击aij的思路如下：

向量b的攻击方法也可以采用汉明距离模型，以计算 bi′ =yi′ +bi为例，向量 y ′ 是 y′=Ay的运算结果，′是 y ′的第i个元素(可以计算得出)，bi是向量b的第i个元素(密钥)，′是有限域加法结果。攻击bi的思路如下：

2.3 分析中心映射变换

对于中心映射变换，建立基于故障分析的模型。假定 x0, x1, … ,xn-1是Rainbow在中心映射变换时需要随机生成的变量，使用强光或涡流，基于BSR(bit set or reset)方法引入故障，使这些变量固定成预设值即这样，签名在每次运行时，产生的随机变量是预设值。

对于密钥 αij和运算Vj′=αijVj， 令D = Vj， R = Vj′， E = αij，通过故障攻击，将Vj固定为预设值，再基于 H (D ⊕R)采用汉明距离模型分析密钥；

对于密钥 δi和运算Vj′ = αijVj+ δi， 因 为=αijVj，令 D = Vj′， R = Vj′ ′ ，E= δi， 通 过故障 攻击，将Vj固定为预设值，再基于 H (D ⊕R)采用汉明距离模型分析密钥；

对于密钥 βij和运算Vi′=βijVi， 令 D=Vi，R = Vi，′ E = βij，通过故障攻击，将Vi固定为预设值，再基于 H (D ⊕R)采用汉明距离模型分析密钥；

对于密钥 γi和运算Vi′=γiVi， 令D = Vi，R= Vi′i′ ，E = γi，通过故障攻击，将Vi固定为预设值，再基于 H (D ⊕R)采用汉明距离模型分析密钥；

根据上述分析，中心映射变换通过建立故障分析模型，固定随机变量，结合差分能量分析，攻击获得全部密钥。

2.4 分析第二个仿射变换

向量d的攻击方法也可以采用汉明距离模型，以计算 di′ =xi′ +di为例，向量 x ′是x′=的运算结果，′是 x ′的第i个元素(可以计算得出)，di是向量d的第i个元素(密钥)，di′是有限域加法结果。攻击di的思路如下：

至此，完成了所有密钥的分析。

3 实 验

1) 依据第2节描述的Rainbow签名算法，使用Verilog编程语言实现了签名电路，通过Xilinx的FPGA EDA工具ISE软件，下载至Xilinx FPGA开发板上验证签名过程。

2) 在FPGA测试通过后，将Verilog代码加载至安装在Redhat操作系统上的Synopsis Design Compiler编译环境，编译运行。

3) 将Synopsis Design Compiler生成的电路文件加载至ModelSim(Mentor的VHDL和Verilog混合评估器)仿真，PrimeTime(Synopsys的电路功耗评估工具)评估功耗。

通过输入2 000条消息，进行Rainbow签名，使用ModelSim仿真，通过PrimeTime进行功耗采集，获得2 000条功耗曲线。然后，基于侧信道攻击模型，采用计算机集群，建立分布式功耗分析平台并分析功耗。首先，构建4个集合：功耗曲线集合、密钥运算集合、密钥时间集合、密钥猜测值集合。再基于密钥时间集合将功耗曲线集合中的曲线分成多个时间段，每个时间段应包含尽可能少的密钥运算，每个时间段的曲线各自组成一个集合；基于密钥运算集合，为每个时间段曲线集合限定参与运算的密钥；为每个密钥在密钥猜测值集合内猜测一个的值，基于汉明距离模型分析功耗，若猜测值在最后计算的曲线对应位置出现尖峰，则将该值记录为该密钥的分析结果。

图3 实验过程

通过以上方法，使用分布式功耗分析平台分析获得Rainbow的所有密钥的分析结果，经过验证全部正确，证明本文的实验能够完全攻破Rainbow签名。实验流程如图3所示。

4 结 束 语

本文提出了一种基于差分能量分析和故障分析的侧信道分析算法，将Rainbow作为目标，实施侧信道攻击。故障分析用于固定Rainbow的中心映射变换的随机变量，结合差分能量分析可攻击Rainbow所有的密钥。实现了Rainbow签名电路，然后使用Synopsis Prime Time进行功耗采集，对采集的2 000条功耗曲线进行分析和计算，获取了所有的密钥。实验结果表明了需要对Rainbow进行侧信道攻击保护。在未来的工作中，将设计基于掩码或隐藏的方法对Rainbow进行保护。

本文的研究工作得到了深圳市知识创新计划基础研究项目(JCYJ20170306144219159)，深圳市战略新兴和未来产业发展资金产业服务体系扶持计划项目(20170502142224600)，深圳职业技术学院校级科研项目(601722K20018)的资助，在此表示感谢！