抗一阶侧信道攻击的QUAD高速并行实现

黄 娴，李伟键，毕远桥，张云琛，林 泳，林思瀚

(广东技术师范大学 计算机科学学院，广州 510665)

1 引 言

随着量子计算机的出现，传统的密码算法面临着巨大的威胁.1994年，Peter Shor证明量子计算机可以在多项式时间内有效地解决大数分解、椭圆曲线和离散对数等数论问题.随后，Monz等[1]在2016年提出了一种可扩展的Shor算法，这意味着一旦大规模量子计算机出现，传统的密码体制将变得不安全.为此，学者们提出了许多密码体制来抵抗量子攻击，如基于编码的密码[2]、基于格的密码[3]、基于多变量的密码[4]等.其中，多变量密码算法是最具有抗量子攻击潜力的重要候选算法之一.许多基于多变量二次多项式的密码体制不断地被提出，如UOV[5]、Rainbow[6]、ZHFE[7]、CHNN-MVC[8]和QUAD[9]等.多变量密码算法的安全性依赖于有限域GF(q)上求解多变量二次方程组的困难性，其求解难度已被证实为NP(Nondeterministic Polynomial)困难问题[10].其中在小域上实现多变量密码算法对时间和面积开销更低，适用于资源受限设备.多变量密码算法作为一种新的研究方向，受到了众多密码学者的关注.

2006年，Berbain等[9]在欧密上提出了一种实用的、可证明安全的流密码QUAD.QUAD的可证明安全性依赖于多变量二次方程组的求解难问题.2009年，Berbain等[11]又重新对QUAD的可证明安全性进行了讨论，给出了在各种参数下QUAD的安全强度.2013年，Bardet等[10]针对QUAD提出了一种复杂度为O(2134.56)的密码分析算法.近年为了应对量子计算机时代下，云计算和区块链的安全性需求，Tanaka等[12]提出了两种高效的并行QUAD实现和一种基于GPU的多变量二次多项式系统计算方法.2018年，Liao等[13]提出了一种用于计算高阶多变量密码系统的GPU加速框架.另一方面，多变量密码算法实现的面积开销低，适用于物联网设备(如RFID、传感器、ASICs和智能卡等普适设备).Billet等[14]指出QUAD可以有效地构造一个可证明安全的RFID隐私保护认证协议.Arditti等[15]提出了一个至今仍被认为是面积最小的可证明安全的QUAD实现方案，只需要2961 GE.这使得QUAD成为物联网安全的一个有竞争力的候选者.为了适用于更多的安全应用场景，2015年Hamlet等[16]提出了一种吞吐量优先的QUAD并行实现.

在实际应用中密码算法的实现需要考虑抵御广泛的物理攻击，特别是侧信道攻击.侧信道攻击利用密码系统在加密时所产生的物理信息 (如功耗、电磁、时间和温度等)与密钥之间的依赖关系，从而获取密钥.2017年，Yi等[17]针对在ASIC上实现的enTTS方案提出了故障攻击和差分能量分析攻击.2018年，Park等[18]提出了一种针对在8位AVR微控制器上实现的Rainbow和UOV方案的相关能量分析攻击，该攻击可获得完整的正确密钥.2019年，Krämer等[19]基于Hashimoto等的工作对多变量签名方案故障攻击的研究进行了补充.然而他们的攻击并没有恢复Rainbow和UOV的完整密钥.2019年，Li等[20]通过相关能量分析攻击证明了在FPGA上QUAD的串行实现存在信息泄露，但攻击成功率仍需要进一步提高.2020年，Li等[21]针对在FPGA上并行实现的QUAD提出了一种基于模糊匹配的模板攻击，成功恢复了完整的密钥.现已有多种针对多变量密码算法的侧信道攻击方法，大量研究表明，即使多变量密码算法能够抵抗量子攻击，但是无防护的多变量密码算法在面对侧信道攻击时是非常脆弱的[22].如何构造既安全、又节省时空开销的多变量密码算法是当前亟待解决的问题.

我们的工作：

在实际应用中，多变量密码算法在加密的过程中需要使用寄存器存储加密中间值，而数据回写寄存器的过程会产生侧信息泄露，从而削弱密码产品的安全性.本文以QUAD为例，利用多项式方程中各单项式的顺序可以被随机地打乱而不影响最终加密结果的特性，提出了一种通用于多变量密码算法的高效轻量级防护方案.通过增加一个乱序下标使得寄存器的内部初始状态随机化，并为了保证所有的单项式都只参与一次计算，在每一轮的加密中依次将寄存器中的值循环左移，从而打乱单项式的计算顺序.该方案只需增加11.7%的面积开销，即可获得良好的抗一阶侧信道攻击的能力.

2 背 景

2.1 QUAD的数学定义

多变量密码算法QUAD(q，n，r) 每一轮都要计算n+r条多变量二次方程，每条多项式方程包含n个密钥X=(x1，x2，…，xn)，X∈GF(q).QUAD主要由更新函数Sin={Q1，Q2，…，Qn}和输出函数Sout={Qn+1，Qn+2，…，Qn+r}组成，如公式(1)所示.在每一次的迭代中，更新函数输出的n比特的数据用于更新内部状态，而输出函数输出r比特密文.

S(X)={Q1(X)，Q2(X)，…，Qn+r(X)}，X={x1，x2，…，xn}

(1)

同所有其他基于MQ问题的密码算法一样，QUAD(q，n，r)在GF(2)上的多变量二次方程定义为：

(2)

其中，αij、βi和γ都是随机可公开的系数.

为了使得QUAD的密钥能够多次循环利用，通常需要设置一个初始向量IV，根据IV的值对内部状态X进行更新.QUAD的具体加密流程为：

1)根据初始向量IV初始化X0∈GF(q)n.

2)计算n个多变量二次方程Sin={Q1，Q2，…，Qn}，多项式方程Sin的输出是下一轮加密的密钥.

3)计算r个多变量二次方程Sout={Qn+1，Qn+2，…，Qn+r}，多项式方程Sout的输出是下一轮加密的密钥.

4)对秘密状态X0进行更新.

文献[11]和文献[23]中指出在GF(2)上的QUAD(2，160，160)有利于硬件高效实现，而且其安全强度高达280，在实际中难以攻击.根据GF(2)的运算特性可知xi·xi=xi，因此QUAD中的线性单项式的计算可以省略.此外，对于设备加密时所产生的能量消耗而言，常数项的加密等同于噪声.为了消除不必要的泄露，QUAD中常数项的计算也可以省略.因此公式(2)可以被简略为更简洁、更快、更清晰、更高效的公式(3)，其中αij、βi和γ仍是随机可公开的系数.

(3)

2.2 QUAD的并行实现

2015年，Hamlet等[16]在保证安全强度不变的前提下，提出了两种高吞吐量的QUAD(2，128，128) 并行实现.其中，QUAD(2，128，128)的安全强度为264，可以很容易地扩展到GF(2)中的其他版本.为了更好地保证密码产品的安全性，本文将该方案扩展至QUAD(2，160，160)，并基于FPGA实现了该扩展方案.在FPGA上QUAD(2，160，160)的并行实现需要事先生成加密过程所需的公开系数并存入ROM中.每一条多项式方程需要计算12880个单项式，即需要12880个系数，QUAD(2，160，160)一共需要实现生成12880×320=4121600个系数.依次计算多变量二次方程Q1(X)，Q2(X)，…，Qn+r(X)，为了获得更高的吞吐量，每一轮并行地计算多项式 的n个单项式.QUAD(2，160，160)的并行实现步骤如下：

1)循环执行步骤2～步骤6，顺序地计算多变量二次方程Q1(X)，Q2(X)，…，Qn+r(X).

2)根据初始化向量IV对内部状态X和rotatedx进行赋值.首次赋值时，X和rotatedx的数据是相同的.

3)同时计算160比特的数据乘积，即并行地计算ηi=xi&rotatedxi，1≤i≤160.

4)从ROM中加载160比特的系数α，将步骤2计算得到的结果η和系数α分别送入到40个8输入的AND-XORLUT模块中进行运算.AND-XORLUT模块的计算公式为Mc=∑3≥i≥0α4c-iη4c-i，1≤c≤40，并将相应的计算结果M存入Register(P1，P2，…，P40)中，即Mc=Pc，1≤c≤40.

5)将Register中的数据分别送入到4输入XORLUT模块中进行异或运算.即计算Vd=∑3≥i≥0M4d-i，1≤d≤10，并将计算结果存入一个临时寄存器Temporary(T1，P2，…，T10).

6)将rotatedx旋转1比特，并回到步骤3继续执行下一组160个单项式的运算，直到Qk(X)计算完毕.每一条多变量二次方程的计算都需要循环「(n+1)/2⎤=81次.需要注意的是，在最后一次循环中只需要计算80条单项式，因此QUAD的并行实现中的每一组功能相同的模块，都只有一半的实例在进行运算.

7)重复上述步骤直到所有多变量二次方程都计算完毕.

(4)

(5)

3 针对并行QUAD的攻击

3.1 并行QUAD的侧信道泄露模型

将数据写入寄存器时的能量消耗取决于寄存器前后数据的位翻转次数，从而猜测引起寄存器数据变化的秘密数据的值.硬件实现中寄存器的功耗变化可以用汉明距离(HD)模型来描述.根据2.2节中描述的并行实现可知，QUAD的并行实现需要同时计算160个单项式，每4个单项式由AND-XORLUT模块将计算结果Mc，1≤c≤40存入Register(P1，P2，…，P40)中：

Mc=a4c-3，4c-3x4c-3x4c-3⊕a4c-2，4c-2x4c-2x4c-2
⊕a4c-1，4c-1x4c-1x4c-1⊕a4c，4cx4cx4c，1≤c≤40

(6)

(7)

(8)

3.2 基于模糊匹配的攻击

传统的模板攻击只能对单条功耗轨迹进行匹配，并在匹配阶段利用贝叶斯定理揭示密钥.然而在实际应用中，只使用单条功耗轨迹无法攻破算法.因此基于模板的DPA攻击方法被提出，它在模板匹配的过程中累积各功耗轨迹的匹配度，提高匹配成功率.然而在实际应用中，基于模板的DPA攻击的精确匹配方法并不适用.为了解决传统攻击存在的问题，Li等[21]提出了一种基于模糊匹配的模板攻击，该方法同样通过对多条功耗轨迹的累加分析，使用模糊匹配算法来揭示加密算法的密钥.本文针对在FPGA上并行实现的QUAD(2，160，160)实施基于模糊匹配的模板攻击.QUAD(2，160，160)一共执行了320次多项式计算操作，其密钥为X={x1，x2，…，x160}.

基于模糊匹配的模板攻击的主要实现步骤如下：

1)选择模板构建策略：根据公式(8)中的功耗泄露模型可知，需要构建两个模板，分别对应于泄露值0和1.

2)采集功耗轨迹构建模板：根据不同的泄露值采集两组功耗轨迹.

3)选取攻击兴趣点(特征)：为了提高攻击效率，需要采用特征选择方法选择最相关的兴趣点，主要方法包括基于t检验的特征点选择方法(SOST)[24]、皮尔森相关系数法[24]、主成分分析法(PCA)[24]、线性SVM封装器[25]和L1正则化[26]等.本文采用Barenghi等[27]强烈推荐的CPA峰值法选取兴趣点.

4)根据兴趣点构建模板：根据均值向量mi和协方差矩阵Ci构建两个模板hi=(mi，Ci)，0≤i≤1.其中mi和Ci的计算公式如公式(9)和公式(10)所示：

(9)

(10)

5)模板匹配阶段：向攻击设备中输入相同的密钥和不同的明文，采集功耗轨迹T={t1，t2，…，tD}.这组功耗用于匹配模板，公式(11)中计算得到的最高概率的p(tj;(mi，Ci))对应着正确的泄露值.

(11)

6)揭示正确密钥：记T={t1，t2，…，tD}对应的泄露值为H={h1，h2，…，hD}.根据公式(8)将假设的中间值映射为泄露值，并与H={h1，h2，…，hD}一起揭示正确密钥.对并行QUAD(2，160，160)实施攻击时，用S={s1，s2，…，s32}表示假设的泄露值，其中si={si1，si2，…，siD}.模糊匹配的计算方法如公式(12)所示：

key=arg minF(i)

(12)

4 并行QUAD的轻量级防护方案

4.1 并行QUAD的隐藏防护方案

能量分析攻击之所以有效是因为加密设备的能量消耗依赖于加密算法的中间值，若想抵抗这种攻击则需要尽可能减少甚至彻底消除这种依赖性.而隐藏防护方案的目的就是为了使得加密设备的功耗不受加密中间值的影响，令攻击者难以从功耗轨迹中得出有用信息.为了达到这个目的通常有两种方法：1)是为该密码产品设计一个专用的电路，通过改变物理结构设计的方法使得加密的功耗达到随机化效果；2)是使得加密设备的每一个操作和操作数所消耗的能量保持一致，即让加密设备的能量消耗在每一个时钟周期中都是相同的.

多变量密码算法加密的过程实际上就是对多个多项式方程组进行计算.其中，多项式的计算顺序和多项式里各个单项式的计算顺序都是相互独立的，执行顺序的先后不影响最后加密结果.因此，各个多项式方程的计算顺序和多项式里各个单项式的计算顺序都可以被随机地打乱.QUAD在每个周期中都有相似的操作，即每个操作所消耗的能量也是相似的，这意味着一旦对单项式进行打乱，攻击者很难确定某一时间刻度所做的操作在功耗轨迹中的位置.因此，通过对齐功耗轨迹来实现有效的能量分析攻击是不可能的.

本文利用各个多项式方程组之间的单项式互相独立的特性对并行QUAD提出简易可行的隐藏防护方案，该思想通用于具有多项式计算的密码算法.为了使防护后的QUAD仍适用于资源受限设备，本文设计了一个以较小代价来实现并行QUAD的乱序防护方案，即以较小的开销将各个多项式方程组的单项式进行随机打乱，从而达到抵抗一阶侧信道攻击的效果.

QUAD(q，n，r)具有(n+r)×n(n+1)/2个单项式，共有((n+r)×n(n+1)/2)!种不同的顺序随机计算单项式，从理论上来说，完全随机打乱的防护效果最佳，完全打乱之后攻击者无法对功耗轨迹进行对齐，从而达到防护的目标.然而，实现这样的算法所需的代价太大，如果要在加密过程中每次都随机地选择一个单项式进行计算，则需要增加寄存器对已完成计算的单项式进行记录，还需要对未被计算的单项式进行记录，以防重复计算.这样的防护方案需要耗费大量的额外开销，尤其是在FPGA这种硬件电路的实现中，其资源所需的存储开销和时间开销过于昂贵，不具备实用性.

为了提高并行QUAD的抗侧信道攻击能力，本文提出了一种低成本的轻量级隐藏防护方案，通过随机生成图中rotatedx寄存器中的初始值来打乱单项式的计算顺序.为了确保各单项式都能够参与运算且不会被重复地计算，在每一轮的计算中rotatedx寄存器中的数据是需要循环左移一位，即rotatedx=circshift(rotatedx≪1)，如图1所示.整体的防护方案实现如图 2所示，QUAD(2，160，160) 在加密过程中所需要的公开系数α会事先生成，并存入ROM中.在FPGA上并行实现的QUAD(2，160，160)的乱序防护方案的具体实施步骤如下：

图1 rotated x寄存器的内部状态变化Fig.1 Internal state change of rotated x

1)每一次加密都会打乱当前多项式中的单项式，循环地执行步骤2-步骤6，顺序地计算各个多变量二次方程Q1(X)，Q2(X)，…，Qn+r(X).

2)在计算每一条多变量二次方程Qk(X)之前，首先要生成一个初始值ls，用于打乱多项式的计算.为了保证QUAD(2，160，160)中各单项式不会被重复计算，ls的取值范围为1≤ls≤80.

3)根据初始化向量IV对内部状态X进行赋值，通过ls对rotatedx进行赋值.首次赋值时rotatedx=circshift(X≪ls)，即rotatedx寄存器的初始数据是由X循环左移ls位得到的.

4)同时并行地计算rotatedx和X之间每一位的乘积，即并行地计算160比特的数据乘积ηi=xi&rotatedxi，1≤i≤160.

5)顺序地从ROM中加载160比特的公开系数α用于计算单项式，将步骤4计算得到的结果η和公开系数α分别送入到40个8输入的AND-XORLUT模块中.AND-XORLUT模块的计算公式为Mc=∑3≥i≥0α4c-iη4c-i，1≤c≤40，并将相应的计算结果M存入Register(P1，P2，…，P40)中，即Mc=Pc，1≤c≤40.

6)将Register中的数据分别送入到4输入的XORLUT模块中进行异或运算.即计算Vd=∑3≥i≥0M4d-i，1≤d≤10，并将计算结果存入一个临时寄存器Temporary(T1，P2，…，T10)中.

7)将寄存器rotatedx循环左移1比特，即rotatedx=circshift(rotatedx≪1).回到步骤4继续执行下一组160个单项式的运算，直到Qk(X)计算完毕.在第81-ls+1轮的时候，图 2中的每一组功能相同的模块，都只有一半的实例在执行进行运算.

图2 QUAD(2,160,160)的并行防护方案Fig.2 Parallel protection scheme of QUAD(2,160,160)

在FPGA上并行实现的QUAD(2，160，160)轻量级乱序防护方案的加密顺序如图 3所示，为了使得各单项式的计算顺序更为直观，在图中省略公开系数α.本文针对并行实现的QUAD(2，160，160)所提的轻量级乱序防护实际上就是将每一个多项式中的各个单项式计算顺序打乱.

图3 并行QUAD(2，160，160)乱序防护方案的计算顺序Fig.3 Computation order of monomials for parallel shuffling QUAD(2，160，160)

本文所提的乱序防护方案通过打乱加密算法的操作顺序，从而随机化各功耗泄露操作的功耗值在功耗轨迹中的顺序.对于QUAD(2，160，160)而言，整个加密过程中一共需要计算320条多项式方程，而在每一条多项式的计算中，rotatedx寄存器中的取值有81种可能性.也就是说在整个加密过程中，攻击者若想使用穷举的方法对功耗轨迹进行对齐处理并成功实施攻击，则需要考虑81320种可能性，难度非常大.通过打乱各个单项式的执行顺序，使得泄露秘密信息的相同操作在不同的时刻中执行，攻击者无法通过观察功耗获得泄露信息，更无法对其进行预测.

本文针对并行QUAD(2，160，160)所提的乱序防护方案在硬件逻辑语言FPGA中实现.FPGA包含了大量的基本单元，而查找表LUTs(Look-Up-Tables)就是其中最为重要的基本单元之一，业界内通常采用查找表的数量定义面积开销.本文通过增加一个7位寄存器作为初始计算单项式的下标，此后为了确保各单项式均参与运算且只参与一次运算，每一轮的计算中都会将单项式寄存器rotatedx循环左移一位，从而打乱各单项式的执行顺序.防护前后的资源开销对比如表1所示.其中，时钟周期由Xilinx ISE Design Suite软件中的仿真结果获得，面积开销由Xilinx ISE Design Suite软件中的综合面积报告分析获得.本文所提的防护方案只需增加11.7%的面积开销，即可获得良好的抗一阶攻击能力.

表1 并行QUAD(2，160，160)的资源开销对比Table 1 Hardware requirements of parallel QUAD(2，160，160)

4.2 实验结果分析

实验所使用的设备如图4所示，本文的实验装置包括一块侧信道泄露标准评估板SAKURA-G、一台示波器和一台计算机.其中，SAKURA-G配备了两个独立的Spartan-6 FPGA芯片.一个芯片是控制芯片，另一个是密码芯片.密码芯片进行加密操作，而控制芯片主要负责芯片间的通信，以及芯片和计算机之间的通信.在加密过程中，示波器通过触发信号来测量加密芯片的功耗.最后，通过计算机进行功耗分析.

图4 实验设备Fig.4 Experimental setup

根据公式(8)中并行实现的泄露模型可知，在每一轮加密的过程中，每4比特密钥将会同时被累加到寄存器Register中，即每次需要猜测4比特的密钥.在模板构建阶段，从设备中采集了具有不同密钥和不同系数的10000条功耗轨迹.本文采用CPA峰值法选取35个攻击兴趣点.采集两组相对应于泄露值0和1的功耗轨迹，每组由35条功耗轨迹组成，构建两个模板.在模板匹配阶段，从设备中捕获320个具有相同密钥的功耗轨迹.针对在FPGA上并行实现的QUAD(2，160，160)实施基于模糊匹配的模板攻击，其成功率如图 5 (a)所示.当功耗轨迹数接近150时，成功率趋于100%.

图5 并行QUAD(2，160，160)的实验结果Fig.5 Experimental results of parallel QUAD(2，160，160)

为了进一步说明泄露的存在，本文采集了40万条功耗轨迹用于实施基于非特定型TVLA(Test Vector Leakage Assessment)的侧信道泄露评估，其评估结果如图 5 (b)所示.根据评估结果可知，在{170，233，263，265，297，328…}位置上的采样点，它们的t值均超出了4.5的阈值范围，即泄露确实存在.

根据实验结果可知，并行QUAD在加密过程中确实存在泄露，它的抗侧信道攻击的能力还有待加强.为了核实本文所提防护方案的有效性，同样对乱序防护后的QUAD(2，160，160)实施基于模糊匹配的模板攻击.乱序防护方案只是打乱了各单项式的计算顺序，并没有影响加密的结果.首先，根据公式(8)对乱序防护后的QUAD(2，160，160)进行泄露建模.在每一次的攻击中，仍需要猜测4比特的密钥.考虑到乱序后的功耗轨迹的信噪比会相对较低，因此在模板构建阶段，从设备中采集了具有不同密钥和不同系数的50000条功耗轨迹.采用CPA峰值法选取35个兴趣点，根据泄露模型采集了两组分别对应于泄露值为0和1的功耗轨迹，分别构建模板.在模板匹配阶段，从设备中捕获2000个具有相同密钥的功耗轨迹，并实施攻击，攻击结果如图 6 (a)所示.从图中可以看出即使用于匹配的功耗轨迹累加到2000条，攻击的成功率仍然只有50%左右，无法恢复其密钥.本文所使用的基于模糊匹配的模板攻击是对密钥的每一个比特逐一进行攻击的，因此乱序QUAD(2，160，160)的攻击成功率等同于二项随机分布，即本文所提出的防护方案具有良好的抗一阶攻击能力.

图6 乱序QUAD(2，160，160)的实验结果Fig.6 Experimental results of shuffling QUAD(2，160，160)

此外，同样采集40万条防护后的功耗轨迹用于实施基于非特定型TVLA的侧信道泄露评估，结果如图 6 (b)所示.根据实验结果可知，使用TVLA对功耗中的各样本点进行评估时，没有任何一个样本点的t值超出了4.5的阈值范围，即TVLA评估无法找出任何一个泄露点，经过防护后的QUAD具有良好的抗一阶侧信道攻击能力.

5 总 结

侧信道攻击技术的发展对物联网加密模块的安全性构成了严重的威胁.因此本文针对并行QUAD存在的泄露，提出了一种通用于多变量密码算法的轻量级防护方案.在多变量密码算法原有优点的基础上，增强了它的抗侧信道攻击能力.本文所提的隐藏防护方案权衡了多变量密码算法的执行效率、抗侧信道攻击的能力以及资源使用率，仅添加了一个7位的寄存器保存随机初始变量就提高了其抗侧信道攻击的能力.最后，对本文所提防护方案实施了基于模糊匹配的模板攻击，而攻击结果并不能恢复它的密钥.为更进一步说明防护方案的有效性，对轻量级防护方案实施了基于TVLA的侧信道泄露评估，根据评估结果可知，经过隐藏防护之后的QUAD不存在泄露.实验结果表明本文所提的防护方案切实有效，从而使多变量密码算法能够安全地应用于物联网设备中，为物联网设备的安全提供了保障.